---

Overview

               

This research effort is aimed at the core problem of the current parallel computing study to revolutionize the current fixed computation-to-machine matching. This paper describes an adaptive technique to optimize the matching between the computation data- flow task graph and the processor network topology. The matching process consists of multithread analysis for task partition, and processor/communication-channel assignment/scheduling. To tackle the NP-Hard complexity of the matching, a level-based heuristic is designed to prioritize the tasks. A critical path analysis and counting scheme is also added to help determine the task importance order. An A* algorithm is then applied sequentially to the prioritized task list to estimate the cost function to assign the best performing processing elements to the most important tasks. To aid the cost estimate, a shortest-path inter-processor routing matrix is maintained. The resulting algorithm-machine matching adapts based on power/speed/cost/communication/reliability constraints/tradeoffs. The research result will benefit all areas of computation from Instruction Level Parallelism (ILP), Very Long Instruction Word (VLIW) compiler, to cluster/grid resource allocation, fault- tolerance/recovery, algorithm/machine selection, algorithm-specific computer architecture design and adaptive/reconfigurable computing.