A general approach for regularity extraction in datapath circuits

Inmajority ojhigh-performance custom ICdesigns, designers tuke advantage of the high degTee of Regularitypresent in circuits to generate eficient layouts in terms area and perfomance aswellas to Teducethe design effort.Inthis paper, we present a general and comprehensive approach to extTact functional regularity for datapath ciTcuits from their behavioralor structural HDL descn.ptions.The fundamental step is the generation ofa large set of templates, where a template as a subcircuit with multiple instances in the ciTcuit.Two novel template generation algorithms aTe presented -one fortemplates with a tree structure, andtheother foraspecial class of multi-output templates, called single-p n.ncipaloutput (single-PO) templates, wheTe all outputs of a template are in thetransitive faninof a particular output.The set of template$ generated is complete under a few simplifying, yet practical, assumptions.This is key to obtaining a desirable couerof theciTcuit using templates.Weshow that excellent cover$ are obtained for van"ous circuits, including ISCAS benchmarks.We also demonstrate that the regularitg extracted for these circuits can be used to understand their under[ging structure.We have successfully used our approach to identify bit slices of very large datapath circuits from general-purpose microprocessors.