A general approach for regularity extraction in datapath circuits

In the majority of high performance custom IC designs, designers take advantage of the high degree of regularity present in circuits to generate efficient layouts in terms of area and performance as well as to reduce the design effort. We present a general and comprehensive approach to extract functional regularity for datapath circuits from their behavioral or structural HDL descriptions. The fundamental step is the generation of a large set of templates, where a template is a subcircuit with multiple instances in the circuit. Two novel template generation algorithms are presented-one for templates with a tree structure, and the other for a special class of multi output templates, called single principal output (single-PO) templates, where all outputs of a template are in the transitive fanin of a particular output. The set of templates generated is complete under a few simplifying, yet practical, assumptions. This is key to obtaining a desirable cover of the circuit using templates. We show that excellent covers are obtained for various circuits, including ISCAS benchmarks. We also demonstrate that the regularity extracted for these circuits can be used to understand their underlying structure. We have successfully used our approach to identify bit slices of very large datapath circuits from general purpose microprocessors.