Change search
ReferencesLink to record
Permanent link

Direct link
Advanced algorithms for logic synthesis
KTH, Superseded Departments, Microelectronics and Information Technology, IMIT.
2004 (English)Licentiate thesis, comprehensive summary (Other scientific)
Abstract [en]

In this thesis, new algorithms for logic synthesis areexplored. Our work is motivated by two observations: (1)Traditional logic synthesis applies literal count as theprimary quality metric during the technology independentoptimization phase. Thissimplistic metric often leads to badcircuit structures as it cannot foresee the impact of earlychoices on the final area, delay, power consumption, etc. (2)Although powerful, global Boolean optimization is not robustand corresponding algorithms cannot be used in practice withoutartificially restricting the application window. Othertechniques, such as algebraic methods scale well but provideweaker optimization power.

In our most recent work, both problems are addressed byapplying a simulated annealing approach that is based on asimple circuit graph representation and a complete set of localtransformations, including algebraic and Boolean optimizationsteps. The objective of the annealing process can be tuned tocomplex cost functions, combining area, timing, routability,and power. Our experimental results on benchmark functionsdemonstrate the significant potential of the simulatedannealing approach.

Earlier work includes a fast rule-based system fortechnology independent optimization. A Boolean network isoptimized by applying local structural transformations thatpreserve its functionality. NPN classes of Boolean functionsare used to identify replacement rules for localtransformations. It provides fast and roboust optimization, butuses a simplistic objective.

Decomposition is one of the important steps of logicsynthesis. It can be applied during the technology independentoptimization phase as well as during the technology mapping. Wehave extended a conjunctive decomposition of Boolean functions[1]to multiple-valued input binary-valued output functions.Our extension provides a more efficient way for decomposingmutiple-output Boolean functions, since [1]only considerssingle-output functions.

Furthermore, we address the problems of technology mappingand logic optimization for Chemically Assembled ElectronicNanotechnoloy (CAEN).CAEN is a promising alternative toCMOS-based technology, allowing construction of extremeleydense low-power computational elements with inexpensivechemical self-assembly.

Place, publisher, year, edition, pages
Kista: Mikroelektronik och informationsteknik , 2004. , 43 p.
Trita-IMIT. LECS, ISSN 1651-4076 ; 04:01
URN: urn:nbn:se:kth:diva-1717OAI: diva2:7675
Available from: 2004-03-17 Created: 2004-03-17 Last updated: 2012-03-20

Open Access in DiVA

fulltext(259 kB)714 downloads
File information
File name FULLTEXT01.pdfFile size 259 kBChecksum MD5
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Färm, Petra
By organisation
Microelectronics and Information Technology, IMIT

Search outside of DiVA

GoogleGoogle Scholar
Total: 714 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 360 hits
ReferencesLink to record
Permanent link

Direct link