align=right>

Towards behavioral synthesis of asynchronous circuits an Towards behavioral synthesis of asynchronous circuits an
implementation template targeting syntax directed compilation.
S. F. Nielsen
J. Sparsø
J. Madsen
Technical University of Denmark, Informatics and Mathematical Modelling
Richard Petersens Plads, Bldg. 322, DK-2800 Kgs. Lyngby, Denmark
e-mail: {sfn,jsp,jan}@imm.dtu.dk
Abstract
This paper presents a method for behavioral syn-
thesis of asynchronous circuits. Our approach aims
at providing a synthesis ow which is very similar to
what is found in existing synchronous design tools. We
adapt the synchronous behavioral synthesis abstraction
into the asynchronous handshake domain by introduc-
ing a computation model, which resembles the syn-
chronous datapath and control architecture, but which
is completely asynchronous. The datapath and control
architecture is then expressed in the Balsa-language,
and using syntax directed compilation a corresponding
handshake circuit implementation is produced.
The
paper also reports area, speed and power gures for
a couple of benchmark circuits, which have been syn-
thesized to layout.
1
Introduction
Asynchronous circuits have a number characteris-
tics that can be exploited to advantage in the design
of current and future submicron integrated circuits,
and the design and implementation of asynchronous
circuits is by now well understood [8, 10, 16, 19]; How-
ever, in order to enable a more widespread adaptation
of asynchronous design, access to ecient high level
synthesis tools is crucial and unfortunately such tools
are largely lacking. In this paper we outline a complete
behavioral synthesis ow, and present some important
steps of this ow which uses traditional front-end be-
havioral synthesis techniques and which uses an exist-
ing asynchronous synthesis tool as the backend.
Figure 1 illustrates the synchronous and asyn-
chronous design ows that are typical of today, and
it shows where the work presented in this paper ts
in. The details will be explained below and in the
following section.
Synthesis of synchronous circuits, which is illus-
trated in the left column of gure 1, has succeeded
program
Synchronous
Asynchronous
design
 ¡ ¡ 
 ¡ ¡ 
¢¡¢¡¢
¢¡¢¡¢
£¡£¡£
¤¡¤¡¤
Abstraction level
(Representations)
Behavioral
Synthesis
= This paper:
Computation model
Scheduling etc.
Implementation template
Design Flow:
Verilog
SystemC/
VHDL/
CDFG
description
RTL
Netlist of
components
Layout
Layout
Gate/ Cell
Gate/ Cell
Handshake
components
CSPtype
Behaviour > CDFG > CSPtype program > Circuit
design
Figure 1: Existing synchronous and asynchronous de-
sign ows and the design ow addressed in this paper.
in raising the level of abstraction to that of specify-
ing circuits at the behavioral level. From a behav-
ioral description in a language like VHDL, Verilog
or System-C some intermediate representation is ex-
tracted often a control data ow graph (CDFG).
From the CDFG the classic synthesis tasks [15] of
scheduling, allocation, and binding is performed re-
sulting in a RTL level circuit description which is then
synthesized into gate level circuits and eventually a
layout.
Synthesis of asynchronous circuits is illustrated in
the right column of gure 1. It is less mature and sev-
eral somewhat dierent approaches is being pursued.
The most inuential of the available synthesis tools
falls in two categories: (i) synthesis of large-scale RTL
level circuits based on syntax directed compilation
from CSP-like languages: Tangram [3, 20], OCCAM
[4], Balsa [2], ACK [14] and TAST [18], and (ii) syn- thesis of small-scale sequential control circuits [9, 11].
The tools that perform syntax directed compilation
target a library of so-called handshake components;
some examples will appear in section 5. The hand-
shake components can be designed using in principle
any of the sequential control circuit synthesis tools.
The syntax directed compilation approach is radi-
cally dierent from the behavioral synthesis ow used
by designers of synchronous circuits; the compiler
merely performs a one-to-one mapping of the program
text into a corresponding circuit structure. Although
syntax directed compilation does allow the designer
to work at a relatively high level it does not provide
any optimizations; what you program is what you
get. In some situations this can be considered an ad-
vantage but in general it puts more burden on the de-
signer: exploring alternative implementations requires
actually programming these, whereas in a traditional
synchronous synthesis ow, the designer can quickly
and easily experiment with dierent constraints and
goals and in this way create alternative implementa-
tions from the same program text. In our work we
use Balsa as a back-end and take advantage of the
one-to-one mapping which allow us to describe spe-
cic
implementations at a high level.
It is interesting to note that the internal representa-
tion of circuit behavior used in synchronous behavioral
synthesis is actually based on an asynchronous model
a CDFG, i.e., a dependency graph expressing the
control- and data-ow of the application. This natu-
rally raises the question, addressed in this paper: Is
it possible to apply the transformations and optimiza-
tions used in synchronous synthesis, for asynchronous
design as well?
The design ow that we target in our work is illus-
trated in gure 1, and as illustrated this paper focus on
behavioral synthesis, i.e. transforming a CDFG repre-
sentation into a structural netlist of handshake com-
ponents (represented as a Balsa program). In this way
we leverage existing and mature tools and techniques
for both high level design of synchronous circuits and
(back end) synthesis tools for asynchronous design.
The contribution of this paper is the addition of be-
havioral synthesis to asynchronous circuit design in
the form of automatic resource sharing and constraint
based design space exploration. In particular our con-
tributions are: (1) an abstract event based compu-
tation model, (2) synthesis algorithms for scheduling,
allocation and binding and (3) a suitable target im-
plementation template. We have previously studied
scheduling algorithms usable in this context [17] and
there is nothing preventing the use of scheduling algo-
rithms developed by other researchers [5, 12].
The paper is organized as follows: Section 3 in-
troduces the concept which allows us to adapth the
techniques from synchronous behavioral synthesis into
behavioral synthesis of asynchronous design. Section 4
describes details of the asynchronous datapaths. Sec-
tion 5 briey explains the Balsa templates, and nally
section 6 presents and discusses some results on the
eciency of the approach.
2
Related work
The introduction mentioned a number of asyn-
chronous high level synthesis tools. Tangram [3, 20] is
a proprietary tool of Phillips. It is quite mature and
has been used to design circuits which are currently in
production. Balsa [2] is a somewhat similar tool which
has been developed by the University of Manchester
and which is available in the public domain. These
tools are based on syntax directed compilation where
there is a one-to-one correspondence between the pro-
gram source and the resulting circuit and where the
control is highly distributed. TAST [18] and in par-
ticular ACK [14], involve the generation of a datapath
and one or more centralized controllers. ACK is no
longer supported and TAST is not available in the
public domain.
A number of papers have presented work on syn-
thesizing asynchronous circuits from DFG or CDFG
representations, but they are surprisingly few and they
have a dierent and/or more limited scope [1, 6, 7, 13].
The rst paper limits itself to DFGs and focus mostly
on a synthesis algorithm and its runtime. The remain-
ing papers address synthesis from a CDFG represen-
tation and they target solutions where a centralized
controller or a distributed structure of controllers are
specied at the level of individual signal transitions
(in the form of signal transition graphs or burst-mode
state graphs).
Our approach is dierent in that it targets hand-
shake components and syntax directed compilation.
This makes it both simpler and more powerful: Sim-
pler because the controller is synthesized implicitly in
a distrib