Extending Pitchmatching Algorithms to Layouts with Multiple Grid Constraints

Hiroshi MIYASHITA  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E79-A   No.6   pp.900-909
Publication Date: 1996/06/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: VLSI Design Technology and CAD
Keyword: 
compaction,  pitchmatching,  multiple grid constraints,  leaf cells,  macro cells,  mixed-integer linear programming,  

Full Text: PDF(846.4KB)>>
Buy this Article




Summary: 
Pitchmatching algorithms are widely used in layout environments where no grid constraints are imposed. However, realistic layouts include multiple grid constraints which facilitate the applications of automatic routing. Hence, pitchmatching algorithms should be extended to those realistic layouts. This paper formulates a pitchmatching problem with multiple grid constraints. An algorithm for solving this problem is constructed as an extension of conventional pitchmatching algorithms. The computational complexity is also discussed in comparison with a conventional naive algorithm. Finally, examples and application results to realistic layouts are presented.