Extraction of functional regularity in datapath circuits

Datapath circuits exhibit a very high degree of regularity, which is exploi ted by designers to generate layouts with a high density and performance as well as to reduce the overall design effort. Regularity in a datapath circ uit manifests itself at functional, structural, and topological levels, Fun ctional regularity of a circuit implies the existence of logically equivale nt subcircuits-a common feature of datapath circuits. We present a new and comprehensive approach to extract functional regularity for datapath circui ts from their high-level or gate-level descriptions. The key step is the ge neration of a large set of templates, where a template is a subcircuit with multiple instances in the circuit. Two novel template generation algorithm s are presented-one for templates with a tree structure, and the other for a special class of multioutput templates, called single-principal-output-gr aph (SPOG) templates, where all outputs of a template are in the transitive fanin of a particular output. The set of templates generated is shown to b e complete under a few simplifying, Set practical, assumptions, which is ke y in obtaining a desirable cover of the circuit using templates. We present a few extensions to our regularity extraction approach to demonstrate its generality; these extensions include hierarchical representation of regular ity and generation of instances of user-specified templates. We show that the generation of the above two classes of templates results i n good covers for datapath circuits with a regular bus structure, including several International Conference on Computer-Aided Design benchmark circui ts. The regularity extracted from these circuits can be used to easily unde rstand their structure. We have successfully used our approach to identify bit slices of very large datapath circuits from general purpose microproces sors.