An Efficient Algorithm for Multiple Folded Gate Matrix Layout

Shoichiro YAMADA  Shunichi NAKAYAMA  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E76-A   No.10   pp.1645-1651
Publication Date: 1993/10/25
Online ISSN: 
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)>>
Buy this Article

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.