Heuristic task partitioning and allocation algorithms for massively parallel systems
D. J. Jackson · 1990
Heuristic task graph partitioning and allocation algorithms are introduced to provide an environment for the automated analysis, decomposition, partitioning, and efficient allocation of large-scale real-time applications to a massively parallel system. The methodology employed here is the graph theoretical analysis of an application task graph to decompose the problem effectively into a set of minimally communicating parallel tasks. The decomposed task graph is then heuristically analyzed to provide an optimal mapping of the tasks to a given massively parallel architecture. The architecture chosen as a testbed for the algorithms is the binary hypercube. The goals of the heuristics are the generation of maximal-length, minimally-communicating, sequential chains of tasks, and the computational load balancing of processors in the parallel environment. To this end, a series of algorithms is developed to analyze the application task graphs. These methodologies include graph-precedence layering, graph-width partitioning-seed node generation, minimum-cut graph traversal for partitioning, partition-layer-spanning analysis, and strict-schedule-constraint regrouping for construction of a reduced execution task graph. Additionally, an allocation algorithm is developed based on hamming-distance-weighted mapping cardinality, and application/architecture graph matrix overlays. The effectiveness of these algorithms for mapping application task graphs to a hypercube is presented, with particular emphasis on the analysis of commonly occurring subgraphs, such as the binary tree, K$\sb{\rm n,m}$ graphs, and combinations/perturbations of these examples. Finally, several models for the Space Shuttle Main Engine are analyzed to determine the effectiveness of the developed partitioning and allocation algorithms for large-scale, real-world systems with a non-trivial task graph structure. The results of the partitioning and mapping analysis yield a nearly linear parallel execution speedup for the task graphs when allocated to a few processors. The analysis also determines the presence of bottleneck subgraphs which dominate the allocation process, and, which severely limit the maximum degree of parallelism feasibly attainable.