Regularity extraction via clan-based structural circuit decomposition

Identifying repeating structural regularities in circuits allows the minimization of synthesis, optimization, and layout efforts. We introduce in this paper a novel method for identifying a set of repeating circuit structures, referred to as templates, and we report on using an efficient binate cover solver to select an appropriate subset of templates with which to cover the circuit. Our approach is comprised of three steps. First, the circuit graph is decomposed in a hierarchical inclusion parse tree using a clan-based decomposition algorithm. This algorithm discovers clans, grouping of nodes in the circuit graph that have a natural affinity towards each other. Second, the parse tree nodes are classified into equivalence classes. Such classes represent templates suitable for circuit covering. The final step consists of using a binate cover solver to find an appropriate cover. The cover will consist of instantiated templates and gates that cannot be covered by any templates. We describe the results of applying this algorithm to several circuits, and show that the algorithm is effective in extracting structural regularity.