A behavioral synthesis system for asynchronous circuits

Matthew Sacker, Andrew D. Brown, Andrew Rushton, Peter R. Wilson

Research output: Contribution to journalArticle

10 Citations (Scopus)

Abstract

Behavioral synthesis of synchronous systems is a well established and researched area. The transformation of behavioral description into a datapath and control graph, and hence, to a structural realization usually requires three fundamental steps: 1) scheduling (the mapping of behavioral operations onto time slots); 2) allocation (the mapping of the behavioral operations onto abstract functional units); and 3) binding (the mapping of the functional units onto physical cells). Optimization is usually achieved by intelligent manipulation of these three steps in some way. Key to the operation of such a system is the (automatically generated) control graph, which is effectively a complex sequence generator controlling the passage of data through the system in time to some synchronizing clock. The maximum clock speed is dictated by the slowest time slot. (This is the timeslot containing the longest combinational logic delay.) Timeslots containing quicker (less) logic will effectively waste time: the output of the combinational logic in the state will have settled long before the registers reading the data are enabled. If we allow the state to change as soon as the data is ready, by introducing the concepts of "ready" and "acknowledge," the control graph becomes a disjoint set of single-state machines-it effectively disappears, with the consequence that the timeslot-timeslot transitions become self controlling. Having removed the necessity for the timeslots to be of equal duration the system becomes selftiming: asynchronous. This paper describes a behavioral asynchronous synthesis system based on this concept that takes as input an algorithmic description of a design and produces an asynchronous structural implementation. Several example systems are synthesized both synchronously and asynchronously (with no modification to the high level description). In keeping with the well-established observation that asynchronous systems operate at average case time complexity rather than worse case, the asynchronous structures usually operate some 30% faster than their synchronous counterparts, although interesting counterexamples are observed.
Original languageEnglish
Pages (from-to)978-994
Number of pages17
JournalIEEE Transactions on Very Large Scale Integration (VLSI) Systems
Volume12
Issue number9
DOIs
Publication statusPublished - 1 Sep 2004

Fingerprint

Networks (circuits)
Clocks
Scheduling

Cite this

A behavioral synthesis system for asynchronous circuits. / Sacker, Matthew; Brown, Andrew D.; Rushton, Andrew; Wilson, Peter R.

In: IEEE Transactions on Very Large Scale Integration (VLSI) Systems, Vol. 12, No. 9, 01.09.2004, p. 978-994.

Research output: Contribution to journalArticle

Sacker, Matthew ; Brown, Andrew D. ; Rushton, Andrew ; Wilson, Peter R. / A behavioral synthesis system for asynchronous circuits. In: IEEE Transactions on Very Large Scale Integration (VLSI) Systems. 2004 ; Vol. 12, No. 9. pp. 978-994.
@article{edfb8197dffa471a9bd2c3db1ef0f96a,
title = "A behavioral synthesis system for asynchronous circuits",
abstract = "Behavioral synthesis of synchronous systems is a well established and researched area. The transformation of behavioral description into a datapath and control graph, and hence, to a structural realization usually requires three fundamental steps: 1) scheduling (the mapping of behavioral operations onto time slots); 2) allocation (the mapping of the behavioral operations onto abstract functional units); and 3) binding (the mapping of the functional units onto physical cells). Optimization is usually achieved by intelligent manipulation of these three steps in some way. Key to the operation of such a system is the (automatically generated) control graph, which is effectively a complex sequence generator controlling the passage of data through the system in time to some synchronizing clock. The maximum clock speed is dictated by the slowest time slot. (This is the timeslot containing the longest combinational logic delay.) Timeslots containing quicker (less) logic will effectively waste time: the output of the combinational logic in the state will have settled long before the registers reading the data are enabled. If we allow the state to change as soon as the data is ready, by introducing the concepts of {"}ready{"} and {"}acknowledge,{"} the control graph becomes a disjoint set of single-state machines-it effectively disappears, with the consequence that the timeslot-timeslot transitions become self controlling. Having removed the necessity for the timeslots to be of equal duration the system becomes selftiming: asynchronous. This paper describes a behavioral asynchronous synthesis system based on this concept that takes as input an algorithmic description of a design and produces an asynchronous structural implementation. Several example systems are synthesized both synchronously and asynchronously (with no modification to the high level description). In keeping with the well-established observation that asynchronous systems operate at average case time complexity rather than worse case, the asynchronous structures usually operate some 30{\%} faster than their synchronous counterparts, although interesting counterexamples are observed.",
author = "Matthew Sacker and Brown, {Andrew D.} and Andrew Rushton and Wilson, {Peter R.}",
year = "2004",
month = "9",
day = "1",
doi = "10.1109/TVLSI.2004.832944",
language = "English",
volume = "12",
pages = "978--994",
journal = "IEEE Transactions on Very Large Scale Integration (VLSI) Systems",
issn = "1063-8210",
publisher = "IEEE",
number = "9",

}

TY - JOUR

T1 - A behavioral synthesis system for asynchronous circuits

AU - Sacker, Matthew

AU - Brown, Andrew D.

AU - Rushton, Andrew

AU - Wilson, Peter R.

PY - 2004/9/1

Y1 - 2004/9/1

N2 - Behavioral synthesis of synchronous systems is a well established and researched area. The transformation of behavioral description into a datapath and control graph, and hence, to a structural realization usually requires three fundamental steps: 1) scheduling (the mapping of behavioral operations onto time slots); 2) allocation (the mapping of the behavioral operations onto abstract functional units); and 3) binding (the mapping of the functional units onto physical cells). Optimization is usually achieved by intelligent manipulation of these three steps in some way. Key to the operation of such a system is the (automatically generated) control graph, which is effectively a complex sequence generator controlling the passage of data through the system in time to some synchronizing clock. The maximum clock speed is dictated by the slowest time slot. (This is the timeslot containing the longest combinational logic delay.) Timeslots containing quicker (less) logic will effectively waste time: the output of the combinational logic in the state will have settled long before the registers reading the data are enabled. If we allow the state to change as soon as the data is ready, by introducing the concepts of "ready" and "acknowledge," the control graph becomes a disjoint set of single-state machines-it effectively disappears, with the consequence that the timeslot-timeslot transitions become self controlling. Having removed the necessity for the timeslots to be of equal duration the system becomes selftiming: asynchronous. This paper describes a behavioral asynchronous synthesis system based on this concept that takes as input an algorithmic description of a design and produces an asynchronous structural implementation. Several example systems are synthesized both synchronously and asynchronously (with no modification to the high level description). In keeping with the well-established observation that asynchronous systems operate at average case time complexity rather than worse case, the asynchronous structures usually operate some 30% faster than their synchronous counterparts, although interesting counterexamples are observed.

AB - Behavioral synthesis of synchronous systems is a well established and researched area. The transformation of behavioral description into a datapath and control graph, and hence, to a structural realization usually requires three fundamental steps: 1) scheduling (the mapping of behavioral operations onto time slots); 2) allocation (the mapping of the behavioral operations onto abstract functional units); and 3) binding (the mapping of the functional units onto physical cells). Optimization is usually achieved by intelligent manipulation of these three steps in some way. Key to the operation of such a system is the (automatically generated) control graph, which is effectively a complex sequence generator controlling the passage of data through the system in time to some synchronizing clock. The maximum clock speed is dictated by the slowest time slot. (This is the timeslot containing the longest combinational logic delay.) Timeslots containing quicker (less) logic will effectively waste time: the output of the combinational logic in the state will have settled long before the registers reading the data are enabled. If we allow the state to change as soon as the data is ready, by introducing the concepts of "ready" and "acknowledge," the control graph becomes a disjoint set of single-state machines-it effectively disappears, with the consequence that the timeslot-timeslot transitions become self controlling. Having removed the necessity for the timeslots to be of equal duration the system becomes selftiming: asynchronous. This paper describes a behavioral asynchronous synthesis system based on this concept that takes as input an algorithmic description of a design and produces an asynchronous structural implementation. Several example systems are synthesized both synchronously and asynchronously (with no modification to the high level description). In keeping with the well-established observation that asynchronous systems operate at average case time complexity rather than worse case, the asynchronous structures usually operate some 30% faster than their synchronous counterparts, although interesting counterexamples are observed.

UR - http://dx.doi.org/10.1109/TVLSI.2004.832944

U2 - 10.1109/TVLSI.2004.832944

DO - 10.1109/TVLSI.2004.832944

M3 - Article

VL - 12

SP - 978

EP - 994

JO - IEEE Transactions on Very Large Scale Integration (VLSI) Systems

JF - IEEE Transactions on Very Large Scale Integration (VLSI) Systems

SN - 1063-8210

IS - 9

ER -