STG-level decomposition and resynthesis of speed-independent circuits

Ren Der Chen, Jer-Min Jou

Research output: Contribution to journalArticle

Abstract

This paper presents a time-efficient method for the decomposition and resynthesis of speed-independent (SI) circuits. Given the specification of an SI circuit, our method first generates its standard C implementation. Then, the combinational decomposition is performed to decompose each high-fanin gate that does not exist in the gate library into some available low-fanin gates. The time efficiency of our method is achieved in two ways. First, the signal transition graph (STG), whose complexity is polynomial in the worst case, is adopted as our input specification. Second, to reduce the resynthesis cycles, which constitute a major part of the run time, our method first investigates the hazard-free decomposition of each high-fanin gate without adding any signals. Then, for those gates that cannot be decomposed hazard free, two signal-adding methods constructed at the STG level are developed for resynthesis. This decomposition and resynthesis process is iterated until all high-fanin gates are successfully decomposed or no solution can be found. Several experiments have been done on the asynchronous benchmarks and it can be seen from the results that our method largely reduces the run time only at a little more area expense when compared with previous work.

Original languageEnglish
Pages (from-to)1751-1763
Number of pages13
JournalIEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications
Volume49
Issue number12
DOIs
Publication statusPublished - 2002 Dec 1

Fingerprint

Decomposition
Networks (circuits)
Hazards
Specifications
Polynomials
Experiments

All Science Journal Classification (ASJC) codes

  • Electrical and Electronic Engineering

Cite this

@article{6dd7485f4778416cbf4f842312ac95dd,
title = "STG-level decomposition and resynthesis of speed-independent circuits",
abstract = "This paper presents a time-efficient method for the decomposition and resynthesis of speed-independent (SI) circuits. Given the specification of an SI circuit, our method first generates its standard C implementation. Then, the combinational decomposition is performed to decompose each high-fanin gate that does not exist in the gate library into some available low-fanin gates. The time efficiency of our method is achieved in two ways. First, the signal transition graph (STG), whose complexity is polynomial in the worst case, is adopted as our input specification. Second, to reduce the resynthesis cycles, which constitute a major part of the run time, our method first investigates the hazard-free decomposition of each high-fanin gate without adding any signals. Then, for those gates that cannot be decomposed hazard free, two signal-adding methods constructed at the STG level are developed for resynthesis. This decomposition and resynthesis process is iterated until all high-fanin gates are successfully decomposed or no solution can be found. Several experiments have been done on the asynchronous benchmarks and it can be seen from the results that our method largely reduces the run time only at a little more area expense when compared with previous work.",
author = "Chen, {Ren Der} and Jer-Min Jou",
year = "2002",
month = "12",
day = "1",
doi = "10.1109/TCSI.2002.805704",
language = "English",
volume = "49",
pages = "1751--1763",
journal = "IEEE Transactions on Circuits and Systems II: Express Briefs",
issn = "1549-8328",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "12",

}

STG-level decomposition and resynthesis of speed-independent circuits. / Chen, Ren Der; Jou, Jer-Min.

In: IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications, Vol. 49, No. 12, 01.12.2002, p. 1751-1763.

Research output: Contribution to journalArticle

TY - JOUR

T1 - STG-level decomposition and resynthesis of speed-independent circuits

AU - Chen, Ren Der

AU - Jou, Jer-Min

PY - 2002/12/1

Y1 - 2002/12/1

N2 - This paper presents a time-efficient method for the decomposition and resynthesis of speed-independent (SI) circuits. Given the specification of an SI circuit, our method first generates its standard C implementation. Then, the combinational decomposition is performed to decompose each high-fanin gate that does not exist in the gate library into some available low-fanin gates. The time efficiency of our method is achieved in two ways. First, the signal transition graph (STG), whose complexity is polynomial in the worst case, is adopted as our input specification. Second, to reduce the resynthesis cycles, which constitute a major part of the run time, our method first investigates the hazard-free decomposition of each high-fanin gate without adding any signals. Then, for those gates that cannot be decomposed hazard free, two signal-adding methods constructed at the STG level are developed for resynthesis. This decomposition and resynthesis process is iterated until all high-fanin gates are successfully decomposed or no solution can be found. Several experiments have been done on the asynchronous benchmarks and it can be seen from the results that our method largely reduces the run time only at a little more area expense when compared with previous work.

AB - This paper presents a time-efficient method for the decomposition and resynthesis of speed-independent (SI) circuits. Given the specification of an SI circuit, our method first generates its standard C implementation. Then, the combinational decomposition is performed to decompose each high-fanin gate that does not exist in the gate library into some available low-fanin gates. The time efficiency of our method is achieved in two ways. First, the signal transition graph (STG), whose complexity is polynomial in the worst case, is adopted as our input specification. Second, to reduce the resynthesis cycles, which constitute a major part of the run time, our method first investigates the hazard-free decomposition of each high-fanin gate without adding any signals. Then, for those gates that cannot be decomposed hazard free, two signal-adding methods constructed at the STG level are developed for resynthesis. This decomposition and resynthesis process is iterated until all high-fanin gates are successfully decomposed or no solution can be found. Several experiments have been done on the asynchronous benchmarks and it can be seen from the results that our method largely reduces the run time only at a little more area expense when compared with previous work.

UR - http://www.scopus.com/inward/record.url?scp=0036959270&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0036959270&partnerID=8YFLogxK

U2 - 10.1109/TCSI.2002.805704

DO - 10.1109/TCSI.2002.805704

M3 - Article

VL - 49

SP - 1751

EP - 1763

JO - IEEE Transactions on Circuits and Systems II: Express Briefs

JF - IEEE Transactions on Circuits and Systems II: Express Briefs

SN - 1549-8328

IS - 12

ER -