國立虎尾科技大學 |

On algorithms for technology mapping.

Record Type:	Language materials, manuscript : Monograph/item
Title/Author:	On algorithms for technology mapping./
Author:	Chatterjee, Satrajit.
Description:	1 online resource (179 pages)
Notes:	Source: Dissertations Abstracts International, Volume: 70-03, Section: B.
Contained By:	Dissertations Abstracts International70-03B.
Subject:	Electrical engineering. -
Online resource:	click for full text (PQDT)
ISBN:	9780549534860

On algorithms for technology mapping.
Chatterjee, Satrajit.

On algorithms for technology mapping. - 1 online resource (179 pages)

Source: Dissertations Abstracts International, Volume: 70-03, Section: B.

Thesis (Ph.D.)--University of California, Berkeley, 2007.

Includes bibliographical references

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.

Electronic reproduction.
Ann Arbor, Mich. :
ProQuest,
2024

Mode of access: World Wide Web

ISBN: 9780549534860Subjects--Topical Terms:

596380
Electrical engineering.
Subjects--Index Terms:

Electronic design automationIndex Terms--Genre/Form:

554714
Electronic books.

On algorithms for technology mapping.
LDR:03809ntm a22003737 4500 001 1147129
005 20240909062222.5
006 m o d
007 cr bn ---uuuuu
008 250605s2007 xx obm 000 0 eng d
020 $a 9780549534860
035 $a (MiAaPQ)AAI3306090
035 $a AAI3306090
040 $a MiAaPQ $b eng $c MiAaPQ $d NTU
100 1 $a Chatterjee, Satrajit. $3 1472782
245 1 0 $a On algorithms for technology mapping.
264 0 $c 2007
300 $a 1 online resource (179 pages)
336 $a text $b txt $2 rdacontent
337 $a computer $b c $2 rdamedia
338 $a online resource $b cr $2 rdacarrier
500 $a Source: Dissertations Abstracts International, Volume: 70-03, Section: B.
500 $a Publisher info.: Dissertation/Thesis.
500 $a Advisor: Brayton, Robert.
502 $a Thesis (Ph.D.)--University of California, Berkeley, 2007.
504 $a Includes bibliographical references
520 $a 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.
533 $a Electronic reproduction. $b Ann Arbor, Mich. : $c ProQuest, $d 2024
538 $a Mode of access: World Wide Web
650 4 $a Electrical engineering. $3 596380
650 4 $a Computer science. $3 573171
653 $a Electronic design automation
653 $a Lossless synthesis
653 $a Technology mapping
655 7 $a Electronic books. $2 local $3 554714
690 $a 0544
690 $a 0984
710 2 $a ProQuest Information and Learning Co. $3 1178819
710 2 $a University of California, Berkeley. $3 1183587
773 0 $t Dissertations Abstracts International $g 70-03B.
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3306090 $z click for full text (PQDT)