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.
An Efficient Algorithm for Multiple Folded Gate Matrix Layout
Shoichiro YAMADA Shunichi NAKAYAMA
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)
gate matrix layout, folding, module generator, multi-way mini-cut, polar graph,
Full Text: PDF(532KB)>>
We propose a new multiple folding algorithm for the gate matrix layout, and apply it to generation of rectangular blocks with flexible size. The algorithm consists of two phases, the net partitioning and the gate arangement, and both algorithms are based on the multi-way mini-cut technique. In the first and second phases, the width and height of the multiple folded gate matrix block are directly minimized, resperctively, such that the area is minimized and desired aspect ratio of the block is obtained. The features of the present algorithm are as hollows: (1) Dead space on the gate matrix block can be minimized, (2) the aspect ratio can be controlled finely, (3) since polar graphs are successfully used in the second phase, the efficiency of the algorithm can be much improved. The experimental results show the effectiveness of our algorithm.