Satrajit Chatterjee

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2007-100

August 16, 2007

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-100.pdf

The task of technology mapping in logic synthesis is to express a given Boolean network as a network of gates chosen from a given library with the goal of optimizing some objective function such as total area or delay. In these general terms, technology mapping is intractable. The problem is usually simplified by first representing the Boolean network as a good initial multi-level network of simple gates called the subject graph. The subject graph is then transformed into a multilevel network of library gates by enumerating the different library gates that match at each node in the subject graph (the matching step) and selecting the best subset of matches (the selection step). However, this simplification means that the structure of the initial network dictates to a large extent the structure of the mapped network; this is known as structural bias. In this work we improve the quality and run-time of technology mapping by introducing new methods and improving existing methods for mitigating structural bias. To this end we propose some new algorithms addressing both matching and selection. Our methods are useful for mapping to standard cell libraries and to lookup table-based FPGAs.

We start with matching. We present a scalable and robust algorithm (based on recent advances in combinational equivalence checking) to combine multiple networks into a single subject graph with choices. This enables lossless synthesis where different snapshots taken during synthesis can be combined into one subject graph on which mapping is done. We improve on existing Boolean matching methods with a simpler and faster algorithm (based on improved cut computation and avoiding canonization) that finds matches across all networks encoded in the subject graph. We also introduce a new construct called a supergate that increases the number of matches found for standard cell mapping.

Having increased the set of matches found in the matching step, we turn to selection. For some cost functions such as delay under the constant-delay model, optimal selection is easy, but for an area cost function, optimal selection is NP-hard. We present a simple heuristic procedure that works well in practice even with the larger search space due to the increased set of matches with choices, and it outperforms the methods proposed in the literature. Although we focus on area for concreteness, the same procedure can be used to optimize for power since the two objectives are very similar.

Advisors: Robert K. Brayton

---

BibTeX citation:

@phdthesis{Chatterjee:EECS-2007-100,
    Author= {Chatterjee, Satrajit},
    Title= {On Algorithms for Technology Mapping},
    School= {EECS Department, University of California, Berkeley},
    Year= {2007},
    Month= {Aug},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-100.html},
    Number= {UCB/EECS-2007-100},
    Abstract= {The task of technology mapping in logic synthesis is to express a given Boolean network as a network of gates chosen from a given library with the goal of optimizing some objective function such as total area or delay. In these general terms, technology mapping is intractable. The problem is usually simplified by first representing the Boolean network as a good initial multi-level network of simple gates called the subject graph. The subject graph is then transformed into a multilevel network of library gates by enumerating the different library gates that match at each node in the subject graph (the matching step) and selecting the best subset of matches (the selection step). However, this simplification means that the structure of the initial network dictates to a large extent the structure of the mapped network; this is known as structural bias.  In this work we improve the quality and run-time of technology mapping by introducing new methods and improving existing methods for mitigating structural bias.  To this end we propose some new algorithms addressing both matching and selection. Our methods are useful for mapping to standard cell libraries and to lookup table-based FPGAs.

  We start with matching. We present a scalable and robust algorithm (based on recent advances in combinational equivalence checking) to combine multiple networks into a single subject graph with choices. This enables lossless synthesis where different snapshots taken during synthesis can be combined into one subject graph on which mapping is done. We improve on existing Boolean matching methods with a simpler and faster algorithm (based on improved cut computation and avoiding canonization) that finds matches across all networks encoded in the subject graph. We also introduce a new construct called a supergate that increases the number of matches found for standard cell mapping.

  Having increased the set of matches found in the matching step, we turn to selection.  For some cost functions such as delay under the constant-delay model, optimal selection is easy, but for an area cost function, optimal selection is NP-hard. We present a simple heuristic procedure that works well in practice even with the larger search space due to the increased set of matches with choices, and it outperforms the methods proposed in the literature. Although we focus on area for concreteness, the same procedure can be used to optimize for power since the two objectives are very similar.},
}

EndNote citation:

%0 Thesis
%A Chatterjee, Satrajit 
%T On Algorithms for Technology Mapping
%I EECS Department, University of California, Berkeley
%D 2007
%8 August 16
%@ UCB/EECS-2007-100
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-100.html
%F Chatterjee:EECS-2007-100