AN EFFICIENT ALGORITHM FOR MAPPING VLSI CIRCUIT SIMULATION PROGRAMS ONTO MULTIPROCESSORS

Recent advances in VLSI and communications technology have made the use of multiprocessors in circuit simulation cost-effective. However, for achieving maximum speedup in concurrent circuit simulation, the problem of mapping the tasks of a concurrent program onto the processors of a multiprocessor must be satisfactorily solved. Unfortunately, the mapping problem, i.e. the problem of assigning the tasks of a concurrent program to the processors of a multiprocessor such that the difference of load among the processors is the smallest and the communication between the processors is minimum, is known to be NP-hard and hence there is not much hope of designing a polynomial time algorithm for solving it. Consequently, researchers have focused on designing heuristic algorithms which obtain near-optimal solutions in a reasonable amount of computation time. In this paper we propose a new heuristic algorithm for solving the mapping problem and compare its performance with that of simulated annealing. Experimental results show that our algorithm is typically an order of magnitude faster and produces solutions which are substantially better than those obtained with annealing using M = 10.