A General Approach for Regularity Extraction in Datapath Circuits

In majority of high-performance custom IC designs, designers take advantage of the high degree ofregularity present in circuits to generate e cient layouts in terms area and performance aswellastoreduce the design e ort. In this paper, 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-principaloutput (single-PO) templates, where all outputs of a template are in the transitive fanin of a particular output. The set of templates generated iscomplete 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.