| Publication Type |
technical report |
| School or College |
College of Engineering |
| Department |
School of Computing |
| Program |
Advanced Research Projects Agency |
| Creator |
Evans, John; Kessler, Robert R. |
| 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 e cient parallel systems?? Finding optimal solutions requires that maxi mum 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 di erences between several recent heuristic allocation approaches and identi es common problems inherent in these approaches?? This paper presents a new algorithm scheme and heuristics that resolves the identi ed problems and shows signi cant performance bene ts?? |
| Type |
Text |
| Publisher |
University of Utah |
| Subject |
Data flow computation model |
| Subject LCSH |
MIMD computers; Data flow computing |
| Language |
eng |
| Bibliographic Citation |
Evans, J., & Kessler, R. R. (1992). A communication-ordered task graph allocation algorithm. 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 |
339,022 bytes |
| Source |
University of Utah School of Computing |
| ARK |
ark:/87278/s6d79vjk |
| Setname |
ir_uspace |
| ID |
702808 |
| Reference URL |
https://collections.lib.utah.edu/ark:/87278/s6d79vjk |
