One of the objectives of running a program on a multiprocessor network is to reduce the parallel execution time of the program. To do this, modules have to be clustered in a certain way. There are three main approaches for clustering: Graph, Integer Programming and Heuristic approaches. In this paper, a static heuristic algorithm for mapping precedence graphs to any multiprocessor architecture based on finding the critical path of a graph is presented. The look-ahead feature in the algorithm enables it to find first the cost of all paths of the graph prior to assignment then it maps the modules of the paths to the processors taking into consideration the topology of the processor network |
