Processor and link assignment using simulated annealing

Abstract

Advances in VLSI technology have made possible a new generation of multicomputer systems that contain hundreds or thousands of processors and offer a combined processing power far beyond that possible in a single processor machine. Multicomputers can be used to solve a variety of computationally intensive applications, but they introduce the problem of handling communication between concurrent processes. In the design of multicomputer systems, the scheduling and mapping of a parallel algorithm onto a host architecture has a critical impact on overall system performance. The problem of how to best assign the resources of a host multicomputer system to the cooperating tasks of a parallel application program is known as the mapping problem. In this research we develop a graph-based solution to both aspects of the mapping problem using the simulated annealing optimization heuristic. A two phase mapping strategy is formulated: I) process annealing assigns parallel processes to processing nodes, and 2) connection annealing schedules traffic connections on network data links so that interprocess communication conflicts are minimized. To evaluate the quality of generated mappings, cost functions suitable for simulated annealing are derived that accurately quantify communication overhead. Communication efficiency is formulated to measure the quality of assignments when the optimal mapping is unknown. Application examples are presented using the hypercube as a host architecture, with host graphs containing up to 512 nodes. The influence of various parameters on the annealing algorithms is investigated, and results for several image graphs are presented.