A communication-ordered task graph allocation algorithm

Update Item Information
Publication Type technical report
School or College College of Engineering
Department School of Computing
Creator Kessler, Robert R.
Other Author Evans, John D.
Title A communication-ordered task graph allocation algorithm
Date 1992
Description The inherently asynchronous nature of the data flow computation model allows the exploitation of maximum parallelism in program execution. While this computational model holds great promise, several problems must be solved in order to achieve a high degree of program performance. The allocation and scheduling of programs on MIMD distributed memory parallel hardware, is necessary for the implementation of efficient parallel systems. Finding optimal solutions requires that maximum parallelism be achieved consistent with resource limits and minimizing communication costs, and has been proven to be in the class of NP-complete problems. This paper addresses the problem of static allocation of tasks to distributed memory MIMD systems where simultaneous computation and communication is a factor. This paper discusses similarities and differences between several recent heuristic allocation approaches and identifies common problems inherent in these approaches. This paper presents a new algorithm scheme and heuristics that resolves the identified problems and shows significant performance benefits.
Type Text
Publisher University of Utah
First Page 1
Last Page 25
Subject Task graph allocation algorithm
Subject LCSH Asynchronous circuits; Parallel processing (Electronic computers); Data flow computing; MIMD computers
Language eng
Bibliographic Citation Evans, J. D., & Kessler, R. R. (1992). A communication-ordered task graph allocation algorithm. 1-25. UUCS-92-026.
Series University of Utah Computer Science Technical Report
Relation is Part of ARPANET
Rights Management ©University of Utah
Format Medium application/pdf
Format Extent 4,318,655 bytes
Identifier ir-main,16251
ARK ark:/87278/s6bk1ww8
Setname ir_uspace
ID 706227
Reference URL https://collections.lib.utah.edu/ark:/87278/s6bk1ww8