For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
A Hierarchical Global Router for Mscro-Block-Embedded Sea-of-Gates
Mototaka KURIBAYASHI Masaaki YAMADA Takashi MITSUHASHI Nobuyuki GOTO
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1993/10/25
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on VLSI Design and CAD Algorithms)
VLSI, CAD, router, hierarchical decomposition,
Full Text: PDF>>
A fast and efficient heuristic hierarchical global router for Sea-of-Gates(SOG) with embedded macro-blocks is described. The key point in the method is carry out a new optimal domain decomposition scheduling at every hierarchical level. This scheduling is intended to avoid macro-block-through wirings and to reduce wiring congestion near macro-blocks which may occur at lower levels. The new global router yielded superior results compared with previous hierarchical routers and a non-hierarchical maze router by evaluating with several actual SOG circuits including a 300K gate master chip and benchmark data supplied from MCNC. Overflows were reduced to one-half or one-quarter for macro-block embedded data compared with previous hierarchical routers. Concerning the running time, the router remarkably outperformed the non-hierarchical maze router, which took more than 390 times longer time for the tested large data.