Complexity and mission computability of adaptive computing systems

Abstract

There is a subset of computational problems that existing algorithms may not complete due to a lack of adequate computational resources on tactical edge computing platforms. Although this subset is computable in polynomial time, many polynomial problems are not computable in mission time. Here, we define a subclass of deterministic polynomial time complexity called mission class, wherein the computations must complete in mission time. By focusing on this subclass of languages in the context of successful military applications, we discuss their computational and network constraints. We investigate feasible (non)linear models that will minimize energy and maximize memory, efficiency, and computational power, and also provide an approximate solution obtained within a pre-determined length of computation time using limited resources so that an optimal solution to a language could be determined.

Keywords

Computability strategic solvability mission readiness optimization computational constraints heterogeneous computational platform

1. Introduction

The efficiency of computing platforms in mission-critical tactical environments is affected by computational resource constraints. Smart tactical edge computing platforms are aware of their computational and network constraints and dynamically adjust their computation strategies. These constraints can be anything from the availability of energy, communication scheduling conflicts, bandwidth, or even accessibility to hardware, such as a central processing unit (CPU), a graphics processing unit (GPU), or a field-programmable gate array (FPGA). Mission applications are time sensitive and computations in support of such applications must be completed within the delay tolerance. By focusing on mission requirements, we can analyze and then optimize the necessary computations in a tactical edge until they can be executed successfully within the mission parameters. The optimizations are done by first focusing on making the algorithms fit a new mission-ready M class of complexity, and then to propose a constraints-aware distributed computing algorithm that can distribute jobs to efficiently use resources at the tactical edge.

Given that each mission has a computational requirement that must be satisfied, much effort is expended to find computationally efficient algorithms. One gauge of efficiency is based on the computational complexity of an algorithm, which is generally expressed in terms of time complexity, that describes how long it takes for an algorithm to compute an answer using a limited number of resources. The time complexity will affect the efficiency of applications using those algorithms. Furthermore, the complexity of input tasks and the computational decision-making requirements will increase, having variable computational cost on each platform, and often these functions need to be optimized.^1–3 The type of optimization algorithms will also have an effect on the time to compute. For instance, optimizations can be linear or nonlinear, and nonlinear optimization can be further classified into concave and convex optimizations based on the complexity (see Figure 1). Linear optimization functions run faster than nonlinear optimization functions as linear programming isolates computation to just the vertices of the available parameter space, while nonlinear optimization must continuously explore the parameter space.

In mission-oriented tactical environments, computational efficiency in terms of flops/watt and computational speeds to match mission requirements are very important factors in determining the fitness of an application for mission deployment. The requirements include the computational efficiency of each platform in regards to the available resources and constraints. For example, network-specific constraints need to be taken into consideration when assessing the efficiency of distributed computation. In fact, mission-critical applications demand well-defined execution times. Mission-optimized computations combined with automated intelligence have been shown to be efficient and will achieve the desired results in mission time.^4–7 The mission requirements define the need for optimized algorithms, which are a subset of the deterministic polynomial time complexity class P of problems, where we define it as the M class for mission-ready algorithms.

Context-aware adaptive computational frameworks are remarkably flexible to support the class $M \subseteq P$ of languages using heterogeneous underlying hardware implementation details from multiple applications using non-intrusive methods under resource-constrained tactical environments. A mission-optimized adaptive computational framework will improve the execution efficiency of the mission applications. An adaptive computing framework will be highly useful in deploying intelligent tactical computing platforms in smart cities that present complex environments with constrained resources and heterogeneity with optimal efficiency. Such a framework will also enable the computing platforms to adapt to communication-related constraints, such as bandwidth and network reachability. In tactical environments, adaptive computing must make decisions regarding local or remote computing for solving a computational problem presented to it. Computational offloading is influenced by not only the computational complexity of the problem, but also the network resource constraints, such as the link quality and communication cost for the offloading. In this manuscript, we study a new class of polynomial time computational complexity called M, which is used to satisfy the mission requirements. We can use this new M class to better understand the computability of a given algorithm in mission time.

Mission times can vary based on the mission objectives, but the deployability of a given algorithm is tied to its ability to complete its computation in that particular mission time. In Section 2, we provide a brief background on computational complexity. In Section 3, we define this new M class of algorithms and specifically look at how algorithms can be optimized to be placed from the P class into the M class by using an adaptive computing framework. Any adaptive computing framework must consider the constraints that we outline in Section 4. Next we apply those constraints to a constraints-aware distributed computing framework, and then give an example where computational jobs assigned to a cluster of local machines may fail and how the distributed computing platform reacts to these failures. In the final section, we summarize our construction of the mission class of problems and how focusing on this subset will enhance the performance of tactical mobile computing platforms.

2. Computational complexity

Computational complexity has a direct impact on mission-ready algorithms. For example, Rivest–Shamir–Adleman (RSA) encryption is simple if given the public key, but RSA decryption is difficult without knowledge of the private key. As such, asymmetric encryption can be performed easily in the field, but mounting a brute-force attack on an adversary using RSA encryption is not even considered in real-time applications. This variation in complexity is why we group problems into two types: class P and class NP.⁸ We denote P as the class of questions for which some algorithm can provide an answer, and thus solve the language, in polynomial time. So in the mathematics literature, we often refer to P as the deterministic polynomial time complexity class. The class P of problems is decidable in polynomial time on a deterministic single-tape Turing machine, $P = ⋃_{k \geq 0} Time (n^{k})$ , and such problems are simple for computers to solve, all within a reasonable amount of time. One example includes determining whether or not a word w is a member of the language $L = {0^{k} 1^{k} : k \geq 0}$ . Another example includes the problem determining whether a directed path exists from vertex s to vertex t in a directed graph, that is, given a directed graph G, define the following:

\begin{matrix} PATH (G, s, t) : = \\ {〈 G, s, t 〉 : G has a directed path from s to t} . \end{matrix}

(1)

This problem is known as directed $s$ -t connectivity, and it is a classical result that $PATH$ is indeed in the class P.⁹ In fact, reasonable deterministic computational models are polynomially equivalent, that is, one such model can simulate another model with only a polynomial increase in running time. We denote NP as the complexity class for which an algorithm can provide a solution in polynomial time with a non-deterministic Turing machine. We thus refer to NP as the non-deterministic polynomial time complexity class. Such questions are ones with solutions that can be verified in polynomial time using a deterministic Turing machine. By definition, NP is the class of languages that are decidable in polynomial time on a non-deterministic Turing machine, that is, $NP = ⋃_{k \geq 0} NTime (n^{k})$ , where:

\begin{matrix} NTime (t (n)) : = {L : L is a language decided by an \\ O (t (n)) - time nondeterministic Turing machine} . \end{matrix}

(2)

In fact, many questions in the class $P$ can be changed ever so slightly to then be placed in the class NP. For example, the previous directed path question that connects two vertices can be placed into the NP class by instead considering the question of whether or not a Hamiltonian path connects two vertices, where a Hamiltonian path in a directed graph G is a directed path that passes through each vertex exactly once. That is, given a directed graph G, we define a Hamiltonian path as follows:

\begin{matrix} HamPATH (G, s, t) = {〈 G, s, t 〉 : G is a directed \\ graph with a Hamiltonian path from s to t} . \end{matrix}

(3)

One can easily obtain an exponential time algorithm for the $HamPATH$ problem by a brute-force approach that checks all possible permutations of vertices (if there are n vertices, then there are $n!$ permutations to check, and we only need to verify that a potential path is Hamiltonian). Although it is well-known that $HamPATH$ is in NP,^10,11 it remains an open problem to determine whether or not $HamPATH$ is actually solvable in polynomial time. We thus have the containment $P \subseteq NP$ of classes of languages.

In the study of computability, $P \overset{?}{=} NP$ is one of the very important and interesting open problems in mathematics and in theoretical computer science with deep ramifications in cryptography,^12,13 algorithms,^14–16 artificial intelligence,^14,17 game theory,¹⁸ and economics,¹⁹ to name a few. Intuitively, the $P = NP$ conjecture is an investigation of whether every problem whose solution can be quickly verified in polynomial time can also be solved fairly quickly in polynomial time. So it remains an open problem to show whether or not the following containment $NP \subseteq^{?} P$ of languages holds.

There is, however, a class of (optimization) problems that lie in class NP, so a polynomial time reduction to their complexity may be difficult to construct with current tools. Now, suppose a high-performance computing (HPC) machine may not be available on the mission field, but a significant proportion of the language being computed within a confined time frame is sufficient to determine the validity of the language, and thus critical decisions may need to be immediately determined on site. Because of the importance and a critical significance of such problems, we define a subclass of problems in P in the following section.

3. Adaptive mission computation

With adaptive computing in mind,^20,21 the class M of functions can be described as having the ability to manage time constraints in such a way as to force computations to be computed in the class P. The unfortunate side effect is that some hard questions will be reduced to approximations of the original question. However, this will allow for minimal usage of limited computational resources, which includes such things as energy, time, and memory. Simultaneously, we attempt to maximize the computational efficiency by optimizing the computational constraints for heterogeneous edge computing platforms for the class M of languages. The timing of such computations may be optimized by using a convex or concave (non)linear platform. By investigating how computations perform in a mission, the limited computational capacity may be precisely measured so that the computational complexity can be varied to ensure mission success.

We are interested in a mission-focused problem $P$ , which is a relation from a set I of instances (input) to a set S of solutions, where deterministic and approximation algorithms exist, that is, $P \subseteq I \times S$ , $P \in P$ , and $P$ has an algorithm that consistently returns a feasible, approximated solution, which is characterized by its distance from its value to the optimal solution. Thus, the class M is defined as follows.

Definition 1. Given the polynomial time complexity class:

P = {P : \forall x \in I \exists y \in S ∍ (x, y) \in P},

(4)

we define mission-computable polynomial time complexity class as follows:

M = {P \in P : \forall x \in I \exists a p p r o x . s o l n . \tilde{y} ∍ (x, \tilde{y}) \in P} .

(5)

Note that the approximated solution $\tilde{y}$ does not need to be in the solution set S, but given any $ε > 0$ , $\tilde{y}$ must satisfy $d (y, \tilde{y}) < ε$ , where d is an intrinsic notion of a distance between the two solutions y and $\tilde{y}$ , which depends on the problem being considered. Our class M of computational complexity is aimed at solving computational problems in mission time and is restricted to the adaptive computing framework (see Figure 2).

Before we further discuss approximated solutions, we will give some basic conditions about $P$ . In order to solve the language $P$ , one needs to recognize if $(x, y) \in P$ . One then needs to construct (using a deterministic algorithm with polynomial time complexity) that for each x, there exists y such that $(x, y) \in P$ . Finally, we need to optimize the problem $P$ in such a way that for each instance x, we find the best (and most efficient) solution $\tilde{y}$ such that $(x, \tilde{y}) \in P$ . A feasible solution is an approximate solution, and such solutions are classified by the value of their distance from the ideal (optimal) solution. Thus, the ratio of the rough solution to the optimal solution is determined by the input size, the growth of the performance algorithm, and time limitations. Some current approximation algorithms include linear programming, dynamic programming, a local search, a randomized algorithm, and a heuristic algorithm. Linear programming formulates the language as a linear model. Dynamic programming constructs a solution from optimal solutions to sub-problems of the original language. A local search algorithm looks for a better neighboring solution when given a solution (this algorithm deforms an input until an improved and preferred optimal solution is found), a randomized algorithm embeds and executes a random decision generator, and a heuristic algorithm is encoded by exploratory learning strategies that offer no guarantee of a more suitable solution. The mission class M is the subclass of optimization problems that are reduced to polynomial time using an approximate algorithm that gives comparable results as the original algorithm. As an approximation algorithm, we force the number of operations (time complexity) and the storage space (space complexity) is in the order of polynomial time $Time (n^{k})$ for some k. By varying the complexity, we ensure that the approximation algorithm can fit within the computational resources while still completing in mission time.

4. Effect of resources on computational efficiency

For smooth operations, adaptive computations require allocation algorithms and technology congestion protocols using behavior models along with network efficiency fairness characterization. These algorithms need to make an optimal decision that can be characterized as either a linear or nonlinear optimization problem. As such, objective functions together with a set of constraint inequalities are often used to broaden the scope of a successful military operation. Computational constraints, such as power, memory, size, storage, and CPU, influence the performance of a computational platform in contested and congested environments, and are driving the need for a constraints-aware adaptive computation framework. Such a framework will change the computational behaviors of the platforms in response to available resources and the complexity of the input computational tasks. For example, a computational problem can be solved in a distributed manner in order to optimize the available computational resources among different computational platforms. However, when a local computing platform is incapable of performing a required computation due to a lack of resources or a lack of required software, the computations are offloaded to a remote computer capable of computing the problem and providing the solution. The network-related constraints, such as signal strength, bandwidth, and energy required for offloading, are important factors in determining if a remote computation makes sense. Any adaptive computing framework will need to take these factors into consideration when making decisions.

5. Constraints-aware distributed computing

The M class computational complexity model can be used to profile any algorithm in the NP complexity class to train algorithms that exist in the new mission-ready M class. The process starts by finding a 100% accurate algorithm that may take minutes to hours to compute for each input. Despite the long computation times, we can use solutions from the accurate algorithm to train approximation strategies that can be varied in accuracy to reduce computation time to fit the mission requirements.

The goal of the constraints-aware distributed computing algorithm is to maximize the number of successful computations at the edge. For this algorithm, we take as a given that there are too many jobs assigned to an array of cores, so the algorithm must decide which computational jobs must be abandoned. The logic for multiple cores on multiple machines can be extended easily from a base of just a single machine with a single core from which many jobs will possibly be scheduled. The optimization for a single machine with a single core can be programmed using integer programming. Given we want to maximize the total computations done on a single machine, our decision variables can be an ordered list that is represented as a binary matrix $b_{i, j}$ (see Equation (6)), where i represents the ith job that will be computed in order on the host machine, while j represents whether or not the jth image is assigned to the ith job. Given the decision variables, the objective function can be used to maximize the computations done on the local machine by doing a weighted sum (see the first term of Equation (8)). Constraints are added to prevent multiple images being assigned to the same job, as in Equation (9), or to prevent the same image being applied to multiple jobs, as in Equation (10), while the time constraints in Equation (11) are put in place to prevent images from being scheduled too far into the future on the local machine. Integer programming must work within the constraints. However, we expect some jobs to fail to be assigned, so a null image with zero computation time and zero constraints is assigned to the $0$ th image. Furthermore, a compact list with all null jobs appearing at the end is preferable to limit degeneracy, so the objective function has an additional term for the zeroth null image appearing later in the list (see the second term of Equation (8)). Feeding the variables, objective function, and constraints into an integer optimizer will show which jobs should be abandoned on the local machine. These abandoned jobs can then be scheduled on a distributed computing platform:

\begin{matrix} i = job index, j = image index, \\ b_{i, j} = {\begin{matrix} 0 & if j - th image not assigned to job i, \\ 1 & if j - th image assigned to job i, \end{matrix} \end{matrix}

(6)

\begin{matrix} T_{j} = analysis time for the j - th image, \\ R_{j} = time the j - th image must be processed, \end{matrix}

(7)

objective function:

\sum_{i, j \neq 0} b_{i, j} \cdot T_{j} + 10^{- 5} \cdot \sum_{i} i \cdot b_{i, 0},

(8)

constraint: one image per job:

\forall i \sum_{j} b_{i, j} = 1,

(9)

constraint: each image is processed at most once:

\forall j \neq 0 \sum_{i} b_{i, j} \leq 1,

(10)

constraint: image processed on time:

\forall i \sum_{k \leq i, j} b_{k, j} \cdot T_{j} \leq \sum_{j} b_{i, j} \cdot R_{j} .

(11)

Once the abandoned jobs are handed to a distributed computing platform, a global optimizer can determine which jobs should be scheduled or rescheduled. The distributed computing platform consists of multiple local machines connected together, with each machine competing for the same resources, so again each application must be willing to accept that some jobs will be dropped. This means each machine must throttle its own computational usage through tagging its own jobs with the appropriate priority level. In the scenario of image analysis, every 10th frame can be tagged as a high-priority job relative to the calling machine. Although the local optimizer outlined previously is fairly trivial, the same framework can be expanded to include a number of cores (c) and a number of machines (m). The decision variables are again just an expansion of the binary matrix, from $b_{i, j}$ to $b_{m, c, i, j}$ . Extra constraints can be added to satisfy transfer times, power used, or even the amount of random-access memory (RAM) used. The objective function can be tweaked to emphasize particular features, such as computation time or energy consumed/operation.

The common theme between the local optimizer and the global optimizer is that the computational size must be varied to fit the computational resources. This is just a foundation for adaptive computing, as the next step is to vary the allocation of resources to competing applications. Two hypothetical applications could be image analysis across multiple security cameras, and using machine learning to detect hostile agents from the data provided by the security cameras. The overall goal is to maximize mission effectiveness by varying the resources to each application as the needs change. For example, image analysis in hostile zones should be given priority access to local resources, while the machine learning project should be given loose timing constraints to allow the jobs to be scheduled on HPC machines located far away from the hostile zone.

6. Discussion

Tactical computing platforms are mostly mobile, with limited computing and communication resources. Data processing and problem-solving tasks are time sensitive and their speed depends upon the available computational resources. In order to accomplish mission computation goals, the platforms and the algorithms must be optimized to the mission requirements. To achieve this optimization, we have described a new class of computational complexity class M that is a subset of the polynomial time class P in order to address a class of problems that needs to be computed in mission time. Mission times are determined by the context in which the computation is used and the completion time of that task to determine the usefulness of the computation. All the polynomial class of computational tasks that can be completed in mission time will fall into computational complexity class M, and they are mission ready. Polynomial problems that cannot be computed in mission time will require additional optimization until they satisfy mission requirements.

Defining a new computational complexity class will allow us to define the computational requirements for any applications and algorithms to be mission ready. For example, the scheduling problem outlined in Section 5 works as an integer program, but the time requirements have forced the scheduling problem to be recast as a genetic program to achieve relatively consistent results in a reasonable time. Although the scheduling problem was formulated as a foundation for an adaptive computing framework, the actual framework should be programmed to accept computational work that has multiple pathways to completion. For example, an image analysis computation can be coded to work on a CPU, GPU, FPGA, or even coded as a local distributed computation. The framework would choose the appropriate pathway to satisfy the constraints of the image analysis computation while also maximizing the desired global properties of the mission resources. This adaptive computing framework brings flexibility to tactical computations, but the framework must still enforce the constraints of the mission. As such, any application or algorithm must also fit within this new mission complexity class to fit within the mission constraints.

Modeling and simulation are essential parts of studying the performance complexity of mission-critical applications, such as seeing through walls using radio signals.²² Our proposed new class of computational complexity will help the deployability of such applications during the modeling simulations in addition to providing performance metrics, thereby suggesting possible modifications to the original applications until they satisfy the mission completeness. For example, benchmarking the application that can see through walls sets a cost for the computational work. If the cost is determined to be too high, a suggested alternative is to first apply a pre-pass to determine whether or not a human is even within the frame at all. If the costs are still determined to be too high, the time complexity can be reduced further by tuning the parameters of the algorithms associated with the application. By mapping the performance metrics of an application collected during simulation with the computational complexity classifications, one could determine the deployability of those applications in a resource-constrained tactical environment. In our future work, we will test a variety of mission-deployable applications to determine their mission readiness without additional optimization and adjustments to their code.

Footnotes

Funding

The authors disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work is supported by a research collaboration between the US Army Research Laboratory and US Military Academy. MSI is partially supported by the National Research Council Research Associateship Programs.

ORCID iD

Venkat R. Dasari

Author biographies

Venkat R Dasari is a research scientist with the Combat Capability Development Command (CCDC) Army Research Laboratory in the Computational and Information Sciences Directorate, Network Science Division. His research is in the broad areas of tactical edge computing, programmable networks, machine learning, and artificial intelligence, with current focus on optimizing adaptive computing for AI/ML implementation at the resource constrained tactical edge. For one element of this, he is developing adaptive coded private computation algorithms in order to secure information during computation offloading and distributed computation for AI processing. Dr. Dasari received a Ph.D. degree in biology from Osmania University, India, in 1993, and a Master’s Degree in Computer Science from Temple University, Philadelphia in 2000.

Mee Seong Im is a National Academy of Sciences Research Associate teaching at the United States Military Academy in West Point, NY and researching with Supercomputing Research Center at Army Research Laboratory in Aberdeen Proving Ground, MD. Her research interests include quantum programmable computers and studying the complexity and mission computability of adaptive computing systems.

Billy E Geerhart III is a computer scientist and works at Army Research Laboratory as a contractor. His research interests include adaptive computing, quantum computing, dark matter and energy in relation to fundamental physics.

References

Fazel

Chiang

Network utility maximization with nonconcave utilities using sum-of-squares method. In: 44th IEEE conference on decision and control, 2005 and 2005 European control conference (CDC-ECC’05), Seville, 15 December 2005, pp.1867–1874. Piscataway, NJ: IEEE.

Lee

Mazumdar

Shroff

NB.

Non-convex optimization and rate control for multi-class services in the Internet. IEEE/ACM Trans Network 2005; 13: 827–840.

Nygren

Sitaraman

Sun

The Akamai network: a platform for high-performance internet applications. ACM SIGOPS Operating Syst Rev 2010; 44: 2–19.

Spang

Sabnis

Sitaraman

, et al. MON: mission-optimized overlay networks. In: INFOCOM 2017-IEEE conference on computer communications, 2017, pp.1–9. Piscataway, NJ: IEEE.

Bejan

Gibbens

Hancock

, et al. Capacity bounds and robustness in multipath networks. In: proceedings of the 9th EAI international conference on performance evaluation methodologies and tools, Berlin, 4 January 2016, pp.9–16. Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering.

Afergan

Wein

LaMeyer

. Experience with some principles for building an internet-scale reliable system. In: proceedings of the 2nd conference on real, large distributed systems - volume 2, San Francisco, CA, 13 December 2005, pp.1–6. Berkeley, CA: USENIX Association.

Jalaian

Dasari

Hou

. Modeling and optimization for programmable unified control plane in heterogeneous wireless networks. In: 2016 IEEE 37th Sarnoff symposium, Newark, NJ, 19–21 September 2016, pp.37–42. Piscataway, NJ: IEEE.

Bossaerts

Murawski

Computational complexity and human decision-making. Trend Cognit Sci 2017; 21: 917–929.

Barnes

Buss

Ruzzo

, et al. A sublinear space, polynomial time algorithm for directed s-t connectivity. SIAM J Comput 1998; 27: 1273–1282.

10.

Gurevich

Shelah

Expected computation time for Hamiltonian path problem. SIAM J Comput 1987; 16: 486–502.

11.

Itai

Papadimitriou

Szwarcfiter

JL.

Hamilton paths in grid graphs. SIAM J Comput 1982; 11: 676–686.

12.

Baker

Gill

Solovay

Relativizations of the P=?NP question. SIAM J Comput 1975; 4: 431–442.

13.

Marks

The universality of polynomial time Turing equivalence. Math Struct Comput Sci 2016; 28(3): 1–9.

14.

Cook

The P versus NP problem. Millenn Prize Prob . In: Carlson

Jaffe

Wiles

(Eds) The Millennium Prize Problems. Providence, RI: American Mathematical Society. 2006; 87–104.

15.

Yan

. Number theory for computing. Berlin: Springer Science & Business Media, 2002.

16.

Shor

PW.

Progress in quantum algorithms. Quantum Inf Process 2004; 3: 5–13.

17.

Buss

SR.

Towards NP–P via proof complexity and search. Ann Pure App Logic 2012; 163: 906–917.

18.

Sahni

Computationally related problems. SIAM J Comput 1974; 3: 262–279.

19.

Vives

Duopoly information equilibrium: Cournot and Bertrand. J Econ Theory 1984; 34: 71–94.

20.

Pozueco

Pañeda

Garca

, et al. Adaptable system based on Scalable Video Coding for high-quality video service. Comput Electr Eng 2013; 39: 775–789.

21.

Urbieta

González-Beltrán

Mokhtar

, et al. Adaptive and context-aware service composition for IoT-based smart cities. Future Gener Comput Syst 2017; 76: 262–274.

22.

Zhao

Alsheikh

, et al. Through-wall human pose estimation using radio signals. In: 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, Salt Lake City, UT, 18–23 June 2018, pp. 7356–7356. Piscataway, NJ: IEEE.