A Novel High-Performance Heuristic Algorithm with Application to Physical Design Optimization

Yiqiang SHENG
Atsushi TAKAHASHI

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E97-A    No.12    pp.2418-2426
Publication Date: 2014/12/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E97.A.2418
Type of Manuscript: Special Section PAPER (Special Section on VLSI Design and CAD Algorithms)
Category: Physical Level Design
Keyword: 
NP-hard problem,  optimization,  conflicting objectives,  physical design,  placement,  

Full Text: PDF>>
Buy this Article


Summary: 
In this paper, a novel high-performance heuristic algorithm, named relay-race algorithm (RRA), which was proposed to approach a global optimal solution by exploring similar local optimal solutions more efficiently within shorter runtime for NP-hard problem is investigated. RRA includes three basic parts: rough search, focusing search and relay. The rough search is designed to get over small hills on the solution space and to approach a local optimal solution as fast as possible. The focusing search is designed to reach the local optimal solution as close as possible. The relay is to escape from the local optimal solution in only one step and to maintain search continuity simultaneously. As one of typical applications, multi-objective placement problem in physical design optimization is solved by the proposed RRA. In experiments, it is confirmed that the computational performance is considerably improved. RRA achieves overall Pareto improvement of two conflicting objectives: power consumption and maximal delay. RRA has its potential applications to improve the existing search methods for more hard problems.