Relay-Race Algorithm: A Novel Heuristic Approach to VLSI/PCB Placement

摘要

In this paper, we present a novel heuristic approach, called relay-race algorithm (RRA), with motivation to improve solution quality and reduce computational time for VLSI/PCB placement. RRA is to simulate the relay-race game, in which each runner participates in a part of race and then is relayed by another member of the team. RRA is designed to overcome the shortcomings of simulated annealing (SA) and genetic algorithm (GA). The basic idea is to use a guide to adjust running methods according to the experience of past runs and a relay to escape local optimum in only one step. Based on the experimental results, RRA improved the placement for both interconnect and area optimization, comparing with SA. For interconnect optimization using ami49_X benchmarks, RRA obtained stable improvement for the Pareto frontier of two conflicting objectives: power and performance. In several cases, we got more than 30% improvement of interconnect power consumption without any degradation of performance. For area minimization using MCNC benchmarks, RRA reduced at least 40% computational time with better solution quality. With respect to its impact, RRA has potential to improve the existing approaches for more NP-hard problems in different fields.