A Module Generator Based on the PQ-Tree Algorithm

Abstract

This paper describes GRAPES, a system for module generation that produces faster and denser layout than conventional CAD tools. The layout style produced by GRAPES resembles standard cell layout (vertical polysilicon wires crossing horizontal diffusion stripes) or sea-of-gates macro layout. Contrary to standard cells or macros, the complexity of the individual cells is not limited by any library, cells can be stretched, feedthroughs can run across them and the transistors can be permuted and sized individually. Cells and rows are produced at the same time in a top-down procedure. A novel algorithm based on the PQ-tree algorithm [1] orders the individual transistor gates in each row such that several rows abut, with no routing channels between the rows. The most critical nets can usually be connected by abutment, even when they connect several cells in different rows. In a comparison with a commercial standard-cell tool, GRAPES produced layout that is about two times smaller and has up to six times shorter total wire length. © 1992 IEEE