Change search
ReferencesLink to record
Permanent link

Direct link
All Around Logic Synthesis
KTH, School of Information and Communication Technology (ICT), Electronic, Computer and Software Systems, ECS.
2008 (English)Doctoral thesis, monograph (Other scientific)
Abstract [en]

This dissertation is in the area of Computer-Aided Design (CAD) of digital Integrated Circuits (ICs). Today's digital ICs, such as microprocessors, memories, digital signal processors (DSPs), etc., range from a few thousands to billions of logic gates, flip-flops, and other components, packed in a few millimeters of area. The creation of such highly complex systems would not be possible without the use of CAD tools. CAD tools play the key role in determining the area, speed and power consumption of the resulting circuits.

We address several problems related to the logic synthesis step of the CAD flow. First, we investigate properties of double-vertex dominators in directed acyclic graphs. We present an O(n) algorithm for identifying all O(n2) double-vertex dominators of a given vertex, where n is the size of the graph. The key to the algorithm's efficiency is a new data structure for representing double-vertex dominators which has O(n) size and can be efficiently manipulated. This work improves the state of the art in double-vertex dominators identification in terms of both space and time complexity. We also show how dominators can be used for structural decomposition of Boolean functions represented by circuit graphs.

Next, we present a depth-optimal technology mapping algorithm for look-up table (LUT) based Field Programmable Gate Arrays. This algorithm is two orders of magnitude faster than previous technology mapping algorithms while achieving solution with a smaller number of LUTs.

We also consider level-limited decomposition of Boolean functions which is of particular interest for applications which require circuit representations of a limited depth, such as control logic of microprocessors. We present an efficient algorithm for computing the decomposition of type f = g * h + r, where f, g, h and r are Boolean functions.

Another contribution of the dissertation is an algorithm for identifying and removing redundancy in combinational circuits. This algorithm provides a quick partial solution which might be more suitable than exact ATPG and SAT-based approaches for redundancy removal runs at the intermediate steps of the CAD flow. It is embedded into the internal logic synthesis tool of IBM.

Other contributions of the dissertation are a proof that, for some Reduced Ordered Binary Decision Diagrams, none of the bound-set preserving orderings is best, a proof of the existence of a perfect input assignment which guarantees that two non-equivalent Boolean functions hash to two different values, and a set of efficient algorithms for the analysis of random Boolean networks.

Place, publisher, year, edition, pages
Stockholm: KTH , 2008. , x, 149 p.
Trita-ICT-ECS AVH, ISSN 1653-6363 ; 08:02
Keyword [en]
graph dominators, FPGA mapping, redundancy removal, RBN
National Category
Computer Science
URN: urn:nbn:se:kth:diva-4700OAI: diva2:13508
Public defence
2008-04-28, Sal D, KTH-Forum, Isafjordsgatan 39, Kista, Stockholm, 10:00
QC 20100914Available from: 2008-04-21 Created: 2008-04-21 Last updated: 2010-09-14Bibliographically approved

Open Access in DiVA

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

Search in DiVA

By author/editor
Teslenko, Maxim
By organisation
Electronic, Computer and Software Systems, ECS
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 783 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: 484 hits
ReferencesLink to record
Permanent link

Direct link