Note: Descriptions are shown in the official language in which they were submitted.
CA 02346514 2001-05-04
METHOD AND DEVICE FOR HIGH LEVEL CIRCUIT DESIGN
FIELD OF THE INVENTION
This invention relates to a method of designing a digital circuit using a high
level programming
language.
BACKGROUND OF THE INVENTION
The usual alternative to building application-specific circuits is to use a
general-purpose processor,
and customize it for an application by writing a program. But for some
applications, particularly where
speed of execution or security is important, a custom-built circuit has some
advantages over the
usual processor-and-software combination. The speed is improved by the absence
of the "machine-
language" layer of circuitry with its "fetch-execute" cycle of interpretation,
and by the ease with which
parallelism may be introduced. Security is improved by the impossibility of
reprogramming. In
addition, unless the application requires a lengthy algorithm, there are space
savings compared to a
combination of software and processor.
The VHDL [S.Mazor, P.Langstraat: a Guide to VHDL, Kluwer, 1992] and Verilog
[D.E.Thomas,
P.Moorby: the Verilog Hardware Description Language, Kluwer, 1991] languages
are presently being
used by industry. There are interactive synthesis tools to aid in the
construction of circuits from
subsets of these languages. The circuits are then "verified" by simulation.
There are other high-level circuit design techniques being developed and
reported in the literature.
Early work includes (M.Rem: Partially Ordered Computations with Applications
to VLSI Design,
Technical Report MR8313, Eindhoven University of Technology, 1982], (J.L.A.van
de Snepscheut:
Trace Theory and VLSI Design, LNCS 200, Springer, 1985], and [C.DeIgadoKloos:
Semantics of
Digital Circuits, LNCS 285, Springer, 1987]. In [S.M.Burns, A.J.Martin:
"Performance analysis and
optimization of asynchronous circuits". In Proc. of the 1991 UC Sanfa Cruz
Conf. on VLSI, MIT Press,
1991] and [A.J.Martin: "Programming in VLSI: from communicating processes to
delay-insensitive
circuits". In Developments in Concurrency and Communication, C.A.R.Hoare
(ed.), Addison-Wesley,
University of Texas at Austin Year of Programming Series, 1990], a circuit is
specified in a subset of
CSP as a set of communicating processes, and is transformed into circuits via
an intermediate
mapping to production rules. A similar approach (and a similar circuit design
language) is used in
[C.H.vanBerkel, J.Kessels, M.Roncken, R.W.J.J.Saeijs, F.Schalij: "The VLSI
programming language
Tangram and its translation into handshake circuits". In Proceedings of the
European Design
Automation Conference, 1991] and [C.H.vanBerkel: Handshake circuits - an
asynchronous
architecture for VLSI programming. Cambridge University Press, 1993], except
that specifications are
mapped into connections of small components for which standard transistor
implementations exist. In
1
CA 02346514 2001-05-04
[S.Weber, B.Bloom, G.Brown: "Compiling Joy into Silicon". In Advanced Research
in VLSI and
Parallel Systems, T. Knight and J. Savage (eds.), MIT Press, 1992] circuits
are modeled as networks
of finite state machines, and their formalism is used to assist in proving the
correctness of their
compiled circuits. The works of [W.Luk, D.Ferguson, I.Page: "Structured
Hardware Compilation of
Parallel Programs". In More Field-Programmable Gate Arrays, W.Moore and W.Luk
(eds.), Abingdon
EE&CS Books, 1994] and [LPage, W.Luk: "Compiling occam into field-programmable
gate arrays". In
Field-Programmable Gafe Arrays, W.Moore and W.Luk (eds.), p.271-283, Abingdon
EE&CS Books,
1991 ] have a global clock.
SUMMARY OF THE INVENTION
This invention relates to two ways of implementing ordinary programs with
logic gates, a new method
of timing within circuits, and a new method of circuit verification.
Application-specific circuit may be
designed by using a standard programming language to describe the function
that a circuit is
intended to perform. The circuits are produced automatically; they behave
according to the programs,
and have the same structure as the programs. In both methods, local delays are
used for timing,
rather than a global clock or local handshaking. A formal semantics is given
for both programs and
circuits in order to prove the correctness of the associated circuits.
BRIEF DESCRIPTION OF THE DRAWINGS
Embodiments of the invention will be described by way of example and with
reference to the drawings
in which:
Fig. 1 is a schematic diagram of one embodiment of the merge circuit with
internal wires exposed and
hidden.
Fig. 2 is a schematic diagram of another embodiment of the merge circuit with
internal wires exposed
and hidden.
Fig. 3 is a schematic diagram of a general control relating to imperative
translation.
Fig. 4 is a schematic diagram showing two controls and memory relating to
imperative translation.
Fig. 5 is a schematic diagram of the control for one embodiment of the empty
program relating to
imperative translation.
Fig. 6 is a schematic diagram of the control for a delay relating to
imperative translation.
Fig. 7 is a schematic diagram of the control for an assignment relating to
imperative translation.
2
CA 02346514 2001-05-04
Fig. 8 is a schematic diagram of the control for an assignment to a scalar
variable relating to
imperative translation.
Fig. 9 is a schematic diagram of the control for an assignment to an array
variable relating to
imperative translation.
15
Fig. 10 is a schematic diagram of the control for sequential composition
relating to imperative
translation.
Fig. 11 is a schematic diagram of the control for parallel composition
relating to imperative translation.
Fig. 12 is a schematic diagram of the control for conditional composition
relating to imperative
translation.
Fig. 13 is a schematic diagram of the control for a loop relating to
imperative translation.
Fig. 14 is a schematic diagram of the control for a local variable declaration
relating to imperative
translation.
Fig. 15 is a schematic diagram of the control for a procedure declaration
relating to imperative
translation.
Fig. 16 is a schematic diagram of the control for a calling point to a
procedure relating to imperative
translation.
Fig. 17 is a schematic diagram of the control for a function declaration
relating to imperative
translation.
Fig. 18 is a schematic diagram of the control for a circuit to evaluate an
expression a relating to
imperative translation.
Fig. 19 is a schematic diagram of the control for a function relating to
imperative translation.
Fig. 20 is a schematic diagram of the control relating to functional
translation.
Fig. 21 is a schematic diagram of the control for an assignment to a scalar
variable relating to
functional translation.
Fig. 22 is a schematic diagram of the control for an assignment to an array
variable relating to
functional translation.
3
CA 02346514 2001-05-04
Fig. 23 is a schematic diagram of the control for sequential composition
relating to functional
translation.
Fig. 24 is a schematic diagram of the control for parallel composition
relating to functional translation.
Fig. 25 is a schematic diagram of the control for conditional relating to
functional translation.
Fig. 26 is a schematic diagram of the control for a loop relating to
functional translation.
Fig. 27 is a schematic diagram of the control for a while loop relating to
functional translation.
Fig. 28 is a schematic diagram of the control for a local variable declaration
relating to functional
translation.
Fig. 29 is a schematic diagram of the control for a procedure declaration
relating to functional
translation.
Fig. 30 is a schematic diagram of the control for a call to a procedure
relating to functional translation.
Fig. 31 is a schematic diagram of the control for a functional declaration
relating to functional
translation.
30
Fig. 32 is a schematic diagram of the control for a data expression result
statement in a function
relating to functional translation.
Fig. 33 is a schematic diagram of a functional circuit placed within an
imperative circuit.
Fig. 34 is a schematic diagram of an imperative circuit placed within a
functional circuit.
DETAILED DESCRIPTION OF THE INVENTION
Overview
A new language for circuit design is not presented; instead, it is advocated
to use a standard
programming language (for example, C), not to describe circuits, but to
describe algorithms. The
resulting circuits are produced automatically; they behave according to the
programs, and have the
same structure as the programs. For timing local delays are used, rather than
a global clock
(synchronous) or local handshaking (asynchronous). A formal semantics for both
programs and
circuits is presented in order to prove correctness of circuits, using a
theory presented in
[E.C.R.Hehner: "Abstractions of Time". In A Classical Mind: Essays in Honour
of C.A.R.Hoare, A.W.
Roscoe (ed.), Prentice-Hall, 1994].
4
CA 02346514 2001-05-04
The high-level instructions or statements describing the algorithm are then
compiled into a
specification of interconnections of digital circuit components using a
replacement compilation
process which maps the instructions on a one-to-one basis to circuit
components. As a result,
hardware implementation of the algorithm may then follow by following the
specification generated
from the compilation.
Time
Ideally, circuit components act instantly, with no gate delays, and are
represented accurately by
timeless Boolean expressions. In reality, there are gate delays, and sometimes
there are transient
signals (glitches) while a circuit settles into a stable state. A timing
discipline is introduced to ensure
that a result is not required, and has no effect, before it is ready. Time may
be considered to be
continuous or discrete; nothing in this invention will depend on that choice.
The operator a is introduced for convenience, pronounced "delay" or
"previous". It gives the value
that its operand had previously, a short time ago. Its circuit graphic is
similarly a triangle. Formally,
the constraints a delay time must satisfy is written to the left of the delay
operator, and inside its
circuit graphic.
Delay time is dependent on context and technology, it is usually determined by
experiment, and can
be known only approximately, say with an upper and lower bound. Sometimes it
is desired that the
delay be kept as short as possible; in this case, signal propagation time
through the wire and
surrounding gates is sufficient, and no extra circuitry is required. When more
delay is needed, it can
be implemented as an even number of negations, or by a suitable choice of
layout; these
implementations are not subject to glitches, and so do not raise again the
problem they are solving. In
addition to its logical use, the delay sometimes has the electrical job of
reshaping a pulse, both height
and width, to compensate for degradation. But that is a level of detail below
the concern here.
As a formal requirement, for proof of correctness, the output of a delay is
defined to be initially 1 for
the delay time, and thereafter it is the same as the input but delayed. This
initial 1 is the only
initialization in the circuits; initialization circuitry is not considered in
this invention. (1 is used to
signify low voltage, ground, or false; and T high voltage, power, or true.)
Merge
A merge preferably turns two sequences of pulses into a single sequence of
pulses. (A pulse is
defined as a momentary T). The 1-2-merge has inputs a and b and output q. One
embodiment has a
1-2-merge outputting a pulse when pulses arrive on a and b in that order, or
simultaneously, but not
CA 02346514 2001-05-04
in the other order. To design a 1-2-merge, an internal wire A is introduced
with the meaning " a is T
or has been T".
A=(avaaA)
q=(Anb)
a <_ (pulse time)
This is a one-time-only circuit; if ever there is a pulse on a, it will allow
all subsequent pulses on b to
pass. To obtain a circuit that resets itself on the falling edge of q ready to
be used repeatedly, one
more internal wire r is introduced that is T except at the falling edge of q.
The circuit (see Figure 1 for
the schematic diagram of the merge circuit) becomes preferably
r=(qv~y4q)
A = (r n (a v adA))
q=(Anb)
a <_ (pulse time) n a s y
Internal wires can be left exposed, as in the above specification of 1-2-merge
and the right-hand
diagram of Figure 1, or they can be hidden as in the left-hand diagram and the
following preferable
specification:
fir, A ~ r = (q v ~yaq)
nA=(rn(avaaA))
nq=(Anb)
If a pulse on a follows a pulse on b , there should preferably be a delay of
at least y after the end of b
before the start of a to avoid truncating the output pulse. No circuit can
constrain its inputs; its context
of use should preferably constrain its inputs, so a constraint is expressed
formally as an antecedent
rather than a conjunct. The circuit specification is therefore preferably
~(a n -,yda n b)
~ 3r, A ~ r = (q v ~yaq)
nA=(rn(avadA))
6
CA 02346514 2001-05-04
nq=(Anb)
A merge that outputs a pulse when the second of the two input pulses arrives,
regardless of their
order, and resets itself for reuse, is as follows. The inputs are a and b and
the output is q . Internal
wire A means " a is T or has been T "; internal wire 8 means " b is T or has
been T "; internal wire r
is T except at the falling edge of q. The circuit (see Figure 2 for the
circuit diagram) is preferably
r = (q ~ ~Ya4)
A = (r n (a v aaA))
B=(rn(bv[3a8))
q=(AnBn(avb))
a 5 (pulse time) n a <_ y
[i < (pulse time) n [i s y
1 ) Imperative Method
The circuits that result from the imperative translation in one preferred
embodiment of this invention
have two components: a control I, and a memory M, connected as in Figure 3. A
thin line indicates
one wire; a thick line indicates many wires. Logic is depicted, not layout;
the best place for a bit of
memory may be with a part of the control that uses it.
The memory consists preferably of a word for each global variable and a RAM
for each global array in
the program. (Local variables are discussed later. By making variables as
local as possible, the need
for the global memory is minimized.) Suppose the variables are x and y, and
the arrays are A and 8.
Then there are four clock wires, called Cx , Cy , CA , and CB , and
collectively called Ca . With one
clock wire for each variable and each array, the variables and arrays can be
independently and
asynchronously changed. The data inputs are Dx , Dy , DA , and DB ,
collectively called Da. For the
arrays, the writing address wires are WA and WB , collectively called Wa, and
the reading address
wires are RA and RB , collectively called Ra . The memory outputs are x, y,
A[RA] and 8[RB] ,
collectively called a , the state of memory. Altogether, memory is preferably
M - ( x = ( if ~Cx n yaCx then aDx else ax )
n y= ( if ~Cy n yaCy then aDy else 4y )
n(b'i~A[~]=if-,CAnya CAni=WA
7
CA 02346514 2001-05-04
then aDA else aA[i] )
n ( b'i~ 8[~] =if -~CB n yaCB n i=WB
then aD8 else a8[~] ) )
y >_ (edge time) + (negation delay)
The expression -,Cx n a Cx says that the clock for x is down but was just
previously up, so it is a
falling edge. The Cx-delay y should be just large enough to allow Cx to fall
and to allow that falling
edge to be negated. The Dx-delay determines what data is latched; for example,
what may be
desired is the data from before the falling edge, or at its start, or at its
end (this delay could be
omitted). The x-delay should be as small as possible. Similarly for the other
variables and arrays.
The state is input to the control, along with an initiator wire s. A pulse on
s starts the computation. As
the computation progresses, the control changes the state of memory, thus
providing itself with
further input. To change the value of variable x in memory, the control should
preferably send a pulse
on clock wire Cx and the desired new value on wire Dx. If the computation is
finite, then when it is
complete, the control indicates termination by a pulse on the completion wire
s'. It is the responsibility
of the context to ensure that the control is not restarted before it has
completed an execution.
A program is sometimes composed of smaller programs. (In other terminology, a
statement is
sometimes composed of smaller statements; "program" is not distinguished from
"statement".) When
a program is composed of parts, the control will be composed of the controls
for the parts. To make
the composition easy, the output of each part Dx be 1 at any instant when it
is not changing variable
x . Then the Dx wires may be disjoined on their way to memory. Other variables
and arrays are
similar. See Figure 4. Each disjunction is really many disjunctions, one for
each bit in its operands.
It is not intended to present a new programming language for circuit design;
the use of a standard
programming language is advocated. The control for a sampling of programming
constructs from
typical programming languages is now described.
Construct: empty
Begin with the simplest program: ok (sometimes called skip). It is the "empty'
program, whose
execution does nothing, taking no time. Program ok yields preferably the
control
s'=sn~Ran--,Can~Wan~Da
Its diagram is Figure 5. All its inputs and outputs are shown. But since the a
input is not connected to
anything, there is no point in bringing those wires from memory. And since the
Ra , Ca , Wa, and
8
CA 02346514 2001-05-04
10
Da outputs are 1, there is no point in taking them into a disjunction. So the
circuit reduces to nothing,
which is appropriate for a circuit that does nothing.
Construct: delay
The next simplest program is tick , which also does nothing, but takes time b
to do it. The preferable
control is
s'=Bas n ~Ra n -~Ca n -~Wa n ~Da
Constraints on 8 should preferably be stated with each use of tick. Leaving
out the nonexistent wires,
this is shown in Figure 6.
Construct: assignment
A variable assignment program x:= a yields preferably the control
s'=TaBas n Cx=Sas n Dx=(8qs n e)
-,Ran~Cpn-~Wan~Dp
b >_ (e time)
~ >_ (s pulse time) >_ (memory latch time)
where p is the state of memory except for x . See Figure 7. Box a evaluates
the data expression in
the assignment. It is assumed for now that adders and other circuits to
perform numerical operations
are available; when the high-level circuit design has been presented, there is
then the means to
design the circuits to perform integer and floating-point operations by
writing programs that use only
Boolean variables and arrays with a restricted form of indexing. Adders and
other arithmetic circuits
may be duplicated at each use for maximum speed, or shared among several uses
(by means of the
function call circuitry which is presented later), at the programmer's
discretion. The input to a is shown
as the entire state of memory, but in practice it is just the part of memory
that a depends on. When
the expression a is a constant, there is a further simplification. For
example, the assignment x:= 5
results in Figure 8 since the binary representation of 5 , which is
...0000101, has 1 s at bit positions 0
and 2.
Expression a may depend on an array element; if so, the reading address for
that array element
should preferably be output from the expression circuit, conjoined with s ,
and routed to memory
(instead of 1 as shown in the diagram). There may be references to elements of
several arrays, but
for now, assume there is at most one array element reference per array in a ;
later, the result
expression will provide a way to allow an arbitrary number of array element
references. It is also
9
CA 02346514 2001-05-04
assumed that evaluation of expression a takes a uniform, known amount of time,
and the 8 delay
should preferably exceed that time; later, with the result expression that
assumption is removed. The
1 outputs, as usual, are not really there.
An array element assignment program A[i]:=a yields preferably the control
s'=Tasas
CA=sas n DA=(84s n e) n WA=(bas n a)
Ran-~Cpn-,Wpn~Dp
8 >_ (e time) n 8 >_ (i time)
T >_ (s pulse time) >_ (memory latch time)
where p is the state of memory except for A . See Figure 9.
Construct: sequential composifion
To implement sequential composition P;Q assume that the controls IP and to for
programs P and Q
are available. To avoid name clashes systematically rename the inputs and
outputs of
IP by adding the subscript P, and similarly for IQ . Then the control for P;Q
is preferably
IP n IQ
S=Sp n S'p=Sp n S'p =S'
6p=6Q=Q
Ra=(R~PV Ro~Q) n Ca=(CAP V COQ)
Wa=(W~PV W~Q) n Da=(DQPV DQQ)
Diagrammatically, ignoring the connections between the controls and memory,
this is shown in Figure
10.
Construct: parallel composition
To implement parallel composition P~~Q, start both programs (operands of ~~
are often called
"processes"), and then merge the completion pulses. Assume that the controls
IP and to for programs
P and Q are available. To avoid name clashes systematically rename the inputs
and outputs of IP by
adding the subscript P , and similarly for IQ . Then the control for P~~Q is
preferably
!P n to n merge
s=sp-sQ n a=s'P n b=s'Q n s'=q
CA 02346514 2001-05-04
ap=QO=a
Ra=(Ra~pv Raq) n Ca=(Cape Ca-q)
Wa=(Wa~pv Wa~q) n Da=(DQpV Daq)
Ignoring the connections between the controls and memory, this is shown in
Figure 11. This
implementation of parallel composition allows P and Q to access memory
simultaneously. For the
memory already described, simultaneous access to different variables or arrays
poses no problem.
Even for the same variable, simultaneous reads are no problem. But
simultaneously reading and
writing the same variable, or two simultaneous writes to the same variable,
have unpredictable
results. Communication channels to allow programs to share information without
memory contention
will follow shortly.
Construct: conditional composition
To implement conditional composition if b then P else Q, assume that the
controls Ip and !q for
programs P and Q are available. To avoid name clashes systematically rename
the inputs and
outputs of Ip by adding the subscript p, and similarly for Iq. Then the
control for if b then P else Q is
preferably
Ip n !q
sp=(8<delta>snb) n sq=(8<delta>sn-,b) n s'=(s P vs'q)
Qp=Qq=a
Ra=(Ra~p v I?aq) n Ca=(CQp V Ca~q)
Wa=(WQpV WQq) n Da=(Da~pv Daq)
8 >_ (b time)
Diagrammatically, ignoring the connections between the controls and memory,
this is shown in Figure
12. The assumptions about b are the same as those about the expression in an
assignment. The if-
then-else box is a one-bit demultiplexer.
A one-tailed if b then P is the same as if b then P else ok. Making a circuit
for a case program
based on the if circuit would be clear to one knowledgeable in the art.
Construct: loop
To implement while b do P, assume that the control Ipfor program P is
available. To avoid name
clashes systematically rename the inputs and outputs of Ip by adding the
subscript p. Then the control
for while b do P is preferably
11
CA 02346514 2001-05-04
Ip
sp=(sa(svs'p) n b) n s' =(sa(svs'p) n -~b)
6p=cs n Ra=Rap n Ca=C6p
Wa=Wap n D6=Dap
8 >_ (b time)
Diagrammatically, ignoring the connections between Ip and memory, this is
shown in Figure 13.
Again, the assumptions about expression b are the same as those about the
expression in an
assignment.
Construct: local variable
Declaring local variable z of type T with scope P, write var z: T~ P. It
simply adds another word of
memory, which is used only within P. Formally, its control is preferably
~z, Cz, Dz~ Ip
where Ip is the control for P. Local declaration helps to locate the words of
memory near the control
circuitry that uses them. See Figure 14.
Declare local array A of size s and type T with scope P, write var A[s]: T~ P
. The size should
preferably be a compile-time constant. It simply adds another RAM, which is
used only within P.
There is another way to implement array declarations that is preferable in
some circumstances: treat
the declaration of array A[3] as syntactic sugar for the declaration of three
variables A0, A7, A2. Treat
the data expression A[i] as sugar for case i of AO ~ A 7 ~ A2, and the
assignment A[i]:= a as sugar for
case i of A0:= a ~ A7:= a ~ A2:= e. This implementation allows parallel access
and update of array
elements.
Construct: procedure
In many programming languages, a procedure is a unit of program that can be
named, so that it can
be called from several places, it is a scope for local declarations, and it
can have parameters. These
three aspects of procedures are separable. Local scope has already been dealt
with; parameters is
discussed later, and now calls and returns are first considered. Assume that
the control Ipfor
procedure P is available. This circuit is started from any of the calls, and
indicates its completion to all
calling points. See Figure 15. The calling points each become Figure 16. It is
a programmer's
responsibility (using communications to be described later) to make sure that
calls from parallel
programs are mutually exclusive, so that the procedure is not restarted before
it completes an
12
CA 02346514 2001-05-04
execution. This implementation works for tail-recursive calls, but not for
recursive calls in general,
which are significantly harder (actually, the calls are easy but the returns
are hard).
A parameter declaration can be treated exactly as though it were introducing a
local variable instead
of a parameter. Whenever a procedure P with parameter x is supplied an
argument a, the resulting
program P a can be treated as though it were (x:= a; P) , except that x has
been taken out of scope.
Construct: function
A function, in many languages, is even more of a mixture than a procedure. Its
separable features
are: the ability to name a data expression so that it can be used in different
places; the ability to nest
programs (statements) within a data expression; local scope; parameters. The
last two aspects have
been dealt with, and the first two is not discussed.
To associate a name with a data expression e, just put the circuit to evaluate
a somewhere. Its input
comes from memory, and its output goes to all uses of the name. See Figure 17.
Data expressions occur in various forms of program, such as assignment and if.
It has been assumed
that their evaluation time is predictable at compile-time, but to be general,
allow circuits for data
expressions to have a control line (s input and s' output). The data
expression P result a requires
execution of program P in order to create the correct state for evaluation of
e. Its circuit inserts the
appropriate delay in the control line. The delay may depend on the initial
state, varying from one
evaluation to another; it is not a worst-case delay. In Figure 18, IP is the
control for program P and
8 >_ (e time). If P changes only local variables, so that there are no side-
effects, then the outputs
Ca, Wa, D6 to memory are unnecessary. Expression a should be evaluated in the
local scope, so the
input to a should include local variables as necessary. A result expression is
often used as the body
of a function. Another use is to overcome an earlier difficulty: references to
different elements of the
same array within one basic data expression were not allowed. But a compiler
can transform an
expression like A[i]+,q~] into
(var t: int. t:= A[i] result t+A~])
and so the earlier restriction is lifted.
Construct: communication
To declare local channel c of type T with scope P write chan c: T~ P . For one
writing program and
one reading program it is defined preferably as follows.
(chan c: T~ P)
- (var c: T~ var ~c: boob ~c:= 1; P)
13
CA 02346514 2001-05-04
It preferably introduces two variables, called the buffer and the probe. The
buffer c (same name as
the channel) holds the value being communicated, and the probe ~c (pronounced
"check c ") tells
whether there is an unread message in the buffer. Define output of expression
a and input to variable
x on this channel as follows.
c! a - (while ~c do tick; c:= e; ~c:=T)
c? x - (while -,~c do tick; x:= c; ~c:=1)
Since all constructs on the right sides of these definitions have already been
implemented, there are
therefore implementations of channel declaration, input, and output. But there
are two points to note.
The tick delay should preferably be longer than the control pulse (the pulse
on s) so the control pulse
is not lost. And the while should preferably use an edge-triggered switch so
the control pulse will not
be truncated, split, or otherwise damaged by a change in ~c due to a parallel
program. Although the
buffer may also be shared by parallel programs that both read and write it,
the discipline of use
imposed by input and output ensures noninterference.
2) Functional Method
The second of the two translations from programs to circuits produces
"functional" circuits (as in
"functional programming") in a further preferred embodiment of this invention.
Functional circuits are
not composed of a control and a memory; instead, each functional circuit
computes its output a' from
its input a without the benefit of a separate memory (although some constructs
will require internal
memory). There is still a start signal s to initiate the computation and a
stop signal s'to indicate
completion. See Figure 19. The data input a includes all variables and array
elements. To use the
circuit there should preferably be provided the desired data input a and a
pulse (momentary T) on the
start wire s, and a should preferably be held constant ever after (until the
circuit is restarted). The
functional circuit F should preferably provide a correct data output a' and a
pulse on the stop wire a' ,
and it should hold 6' constant ever after (until the circuit is restarted).
Construct: empty
For program ok the functional circuit is straightforward, as it should be. See
Figure 20.
Construct: assignment
A variable assignment x:= a is preferably shown in Figure 21, where p' is all
variables and arrays
other than x'.
Array element assignment A[~]:= a is preferably shown in Figure 22, where p'
is all variables and
arrays other than A'.
14
CA 02346514 2001-05-04
Construct: sequential composition
Sequential execution is shown in Figure 23.
Construct: parallel composition
For parallel execution, the simplifying assumption is made that the parallel
programs do not
communicate via shared memory, but only via the communication constructs
provided. The variables
and array elements changed by one program are disjoint from those changed by a
parallel program,
and the changes made by one program are not seen by a parallel program. See
Figure 24. The entire
input can go to both programs, but each program produces only part of the
output. These outputs
together preferably form the entire output.
Construct: conditional composition
25
The functional circuit for if b then P else Q is shown in Figure 25. The data
output could,
alternatively, be selected using the b output without memory. The if circuit
is easily generalized to a
case circuit.
Construct: loop
The functional circuit for loop P with exits in it is shown in Figure 26. If
there is only a single exit, the
exit memory is unnecessary.
Since while b do P is the same as loop (if b then P else exit), its circuit is
Figure 27. Similarly
repeat P until b is identical to loop (P; if b then exit else ok).
Construct: local variable
The functional circuit for local variable declaration var z: T~ P is not
difficult; see Figure 28. Into the
functional circuit for P data lines for z should preferably be fed, with any
desired initial value. The
diagram shows the final value z' coming from Fp , but it is not wanted so its
wires are not needed. A
local array declaration is just like a local variable declaration; there is no
extra circuitry needed here
for access to elements.
Construct: procedure
Program declaration and calling work the same way in functional circuits as in
imperative circuits,
except that the data input should preferably also come from the calling point,
and the data output
should preferably be delivered back to the calling point. Like the imperative
version, the functional
implementation of procedures does not work for general recursion. Because the
functional parallelism
is disjoint, procedures cannot be called from parallel programs. For a
procedure declaration there is
the circuit shown in Figure 29, and for each call there is the circuit shown
in Figure 30.
CA 02346514 2001-05-04
Construct: function
Function declaration is similar to procedure declaration. See Figure 31.
Function call and return are
identical to procedure call and return. The programmer should preferably
ensure that calls from
parallel programs are mutually exclusive.
The data expression P result a is almost identical to the imperative circuit.
See Figure 32. The
communication constructs are not given functional implementations for lack of
truly shared memory in
the parallel composition. For these constructs, hybrid circuits are used,
described next.
Hybrid Circuits
In general, functional circuits are faster than imperative circuits, but
imperative circuits occupy less
space. Each approach has merit. One can obtain almost the speed of a
functional circuit with almost
the compactness of an imperative circuit by combining the two kinds within one
hybrid circuit. For
example, one might make most of a circuit imperative, but make inner loops
functional.
Hybrid circuits also allow the use of the imperative implementation of
communication within a larger
functional circuit.
To place a functional circuit within an imperative one, the functional circuit
should preferably be made
to look imperative. Ignoring arrays for simplicity of presentation, what one
does is shown in Figure 33.
The s' output also causes memory to change state. As usual, only some of the
wires to and from
memory are needed. The local memory is needed only if there are parallel
programs.
35
To place an imperative circuit within a functional one, one should preferably
make the imperative
circuit look functional. See Figure 34. In effect, one makes the memory (as
much of it as necessary)
local to the circuit.
3) Correctness
Proving that the circuits are correct requires a formal semantics for the
source programs and circuits.
The source semantics is presented below.
Let t and t'be the initial and final execution times, the times at which
execution starts and ends. If the
execution time is infinite, t'=~o. Let the state variables x, y, ... be
functions of time. The value of x at
time t is x t . An expression such as x+y is also a function of time; its
argument is distributed to its
variable operands as follows: (x+y) t = x t + y t . Let
wait = (t2t n tilt": t<_t"<_t' - xt"=xt n yt"=yt n ...)
so that wait takes an arbitrary time during which the variables are
unchanging.
16
CA 02346514 2001-05-04
The programming notations are defined as follows.
ok = (t'=t)
tick = (t'=t+8 n wait)
(x:=e) _ (Y=t+8+T n xY=et n waity,Z...)
where 8 >_ (e time) n T >_ (memory time).
(P; Q) _ fit" ~ (substitute t"for t'in P )
n (substitute t"for t in Q )
(Pa II Qp) _ (Pa ~ (Q; wait)a
v (P; waif)a n Qp)
(if b then P else Q) _ (if bt then P else Q)
=(btnPv-~btnQ)
where 8 >_ (b time).
(while b do P)
if b then (P; while b do P) else ok
(b'x, x', y, y', ..., f, Y~ W ~ if b then (P; W)
else ok)
(dx, x', y, y', ..., t, Y~ W ~ while b do P)
var z: T~ P = 3z: time--~T~ P
Where time-aT is the functions from time values (including ~o ) to T values.
Here is a simple example, in variables x and y. In this example discrete time
is used and one takes
8tobe0andTtobe1.
x:= x+3; x:= x+4
- (t'=t+1 n xt'=xt+3 n yt'=yt);
(t'=t+1 n xt'=xt+4 n yt'=yt)
- ~Y'~ (t"=t +1 n xt"=xt+3 n yt"=yt)
n (t'=Y'+1 n xt'=xt"+4 n yt'=yY')
17
CA 02346514 2001-05-04
- P=t+2 n x(t+1 )=xt+3 n x(t+2)=xt+7
n Yt=Y(t+1 )=Y(t+2)
In the parallel composition, a consists of those variables that appear on the
left of assignments within
P, and (i consists of those variables that appear on the left of assignments
within Q; a and (3 should
preferably be disjoint. The use of wait is just to make the faster side of the
parallel composition wait
until the slower side is finished. To illustrate the semantics, here is an
example in variables x and y,
and discrete time with 8=0 and i=1. In the left-hand program, only x is
assigned, so only x is treated
as a state variable. In the right-hand program, only y is assigned, so only y
is treated as a state
variable.
(x:= 2; x:= x+y, x:= x+Y) I~ (Y~= 3. Y~= x+Y)
- ( r = t +1 n xr=2; r = t+1 n xr = xf+yt;
Y = t+1 n xr = xt+yt)
n ( r = t +1 n yt'=3; r=f+1 n yr = xt+yt;
t2f n b'r': t<_r'<_r. yt"=Yt )
v ( r=t+1nxt'=2;r=t+1nxr=xt+yt;
t' = t+1 n xr = xt+yt;
t2t n b'r': f<r'<_r~ xt"=xt )
n ( r = t +1 n yt'=3; r=t+1 n yr = xt+yt )
- r = t+3 n x(t+1 )=2 n x(t+2) = x(t+1 )+y(t+1 )
n x(t+3) = x(t+2)+Y(t+2)
n r >_ t+2 n y(t+1 )=3 n y(t+2) = x(t+1 )+y(t+1 )
n dr': t+2<_r'<_r. yt"=y(t+2))
v t' >_ t+3 n (other conjuncts)
n r = t+2 n (other conjuncts)
- r=t+3 n x(t+1 )=2 n y(t+1 )=3 n x(f+2)=5
n y(t+2)=5 n x(t+3)=10 n y(t+3)=5
18
CA 02346514 2001-05-04
The example has the appearance of lock-step parallelism, as though there were
a global clock, only
because, for the sake of simplicity, discrete time is used with constants 8=0
and i=1 for all
assignments.
The first formula concerning the while loop says that it refines its first
unrolling. Stated differently,
while b do P is a pre-fixed-point of W ~ if b then (P; W) else ok . The second
formula says that it is
as weak as any pre-fixed-point, so it is the weakest pre-fixed-point.
The other programming constructs (channel declaration, input, output, signal
declaration, sending,
receiving, parameter declaration, argumentation) are defined in terms of the
ones already defined, so
there is no need to give them a separate semantics. And that completes the
source semantics.
The imperative circuit semantics was given with each circuit. For example, the
control for ok was
s'=sn-,Ran~Can-~Wan~Da
and the control for while b do P was
IP
s~(sa(svs'P) n b) n s'=(8a(svs'P) n -,b)
6P=o' n R6=RaP n Ca=C6P
Wa=Wa'P n Da=D6'P
8>_(btime)
where IP is the control for P .
To prove correctness, as adapted from [T.S.Norvell: a Predicative Theory of
Machine Languages and
its Application to Compiler Correctness. PhD thesis, University of Toronto,
1994]. roughly speaking, a
circuit is defined as "bush' if it has been started and has not yet stopped.
Formally, define 8 as
8 = ((s v 84B) n -~s')
8 <_ (pulse time)
The delay here should preferably be shorter than the pulse length used on the
control lines (s and s' )
If time is discrete and 8=1, then for any A
(aA)0=1
( 4A) (t+1 ) = At
and so for busy B
19
CA 02346514 2001-05-04
80=1
8(t+1 ) _ ((s(t+1 ) v Bt) n ~s'(t+1 ))
To prove that a circuit is correct, it should be proven that
!P n M n st n ('dt"~ Bf"n 48t" ~ ~st'~
n t'=(min t"~ t'2t~ n s'f')
P
Suppose one has the control IP (for program P), and the memory M, and a pulse
is put on the start
wire s at time t, and the circuit is not restarted while it's busy, and one
gives the name t' to the first
time at or after t when s' becomes T; then one would expect the circuit to
satisfy the semantics of
program P. It is not necessary to prove correct each circuit that is designed;
instead, only that the
circuit generation scheme is correct. The proof is long, and omitted; only two
lemmas are stated
which are useful steps on the way to the proof.
In~4Bn~s~-~s'
which says that a circuit does not spontaneously generate s'.
In-,8~-~Ran~C6n~W6n-~Da
which says that if a circuit is not busy, its Ra , C6 , Wa , and Da outputs
are all 1.
4) Synchronous and Asynchronous Circuits
There are two preferable ways to control the timing in circuits. One is by
using delays calculated, or
experimentally determined, to be long enough to ensure that all data values
have settled properly.
The other way, called "delay-insensitive", is to use handshaking signals that
allow a data transfer to
occur just when both sender and receiver are ready. These solutions can be
applied locally, or
globally, or at any level in between. The word "synchronous" is usually used
to describe a global
delay, or clock; the word "asynchronous" is sometimes used to describe local
handshaking.
The circuits resulting from the methods presented use local delays. But as a
special case, it is
possible to write a program in the form of a single loop, whose body is a
parallel composition of
assignments. This program structure forces a single, common delay for all
state changes; that delay
is in effect a global clock. It is possible to program a synchronous circuit
when one is desired. When
designing a circuit, there is little point in aiming for the synchronous
structure, and equally little point
CA 02346514 2001-05-04
in aiming to avoid it. One chooses a program structure that is appropriate for
the task, and one gets a
circuit that accomplishes that task. In principle, local delays should be
faster than a single global
delay. That is because a global delay should preferably be the maximum of all
the local delays. In a
synchronous circuit, each state change takes as long as the slowest state
change requires.
If one chooses to make each assignment into a little procedure, the 1-2-merges
at the calling points
are an implementation of local handshaking. It is possible to thus program
local handshaking when
desired. In principle, local delays should be faster than local handshaking.
That is because the
handshaking takes time. A local delay is just long enough for the data to be
ready, not long enough
for the data to be ready and to indicate its readiness.
It will be appreciated that the above description relates to the preferred
embodiments by way of
example only. Many variations on the apparatus for delivering the invention
will be obvious to those
knowledgeable in the field, and such obvious variations are within the scope
of the invention as
described and claimed, whether or not expressly described.
All patents, patent applications, and publications, if any, referred to are
incorporated by reference in
their entirety.
5) References
C.H.vanBerkel, J.Kessels, M.Roncken, R.W.J.J.Saeijs, F.Schalij: "The VLSI
programming language
Tangram and its translation into handshake circuits". In Proceedings of the
European Design
Automation Conference, 1991.
C.H.vanBerkel: Handshake circuits - an asynchronous architecture for VLSI
programming.
Cambridge University Press, 1993.
S.M.Burns, A.J.Martin: "Performance analysis and optimization of asynchronous
circuits". In Proc. of
the 1991 UC Santa Cruz Conf. on VLSI, MIT Press, 1991.
C.DeIgadoKloos: Semantics of Digifal Circuits, LNCS 285, Springer, 1987.
E.C.R.Hehner: "Abstractions of Time". In A Classical Mind: Essays in Honour of
C.A.R.Hoare, A.W.
Roscoe (ed.), Prentice-Hall, 1994.
W.Luk, D.Ferguson, I.Page: "Structured Hardware Compilation of Parallel
Programs". In More Field-
Programmable Gate Arrays, W.Moore and W.Luk (eds.), Abingdon EE&CS Books,
1994.
A.J.Martin: "Programming in VLSI: from communicating processes to delay-
insensitive circuits". In
21
CA 02346514 2001-05-04
Developments in Concurrency and Communication, C.A.R.Hoare (ed.), Addison-
Wesley, University of
Texas at Austin Year of Programming Series, 1990.
S.Mazor, P.Langstraat: a Guide to VHDL, Kluwer, 1992.
T.S.Norvell: a Predicative Theory of Machine Languages and its Application to
Compiler Correctness.
PhD thesis, University of Toronto, 1994.
LPage, W.Luk: "Compiling occam into field-programmable gate arrays". In Field-
Programmable Gate
Arrays, W.Moore and W.Luk (eds.), p.271-283, Abingdon EE&CS Books, 1991.
M.Rem: Partially Ordered Computations with Applications to VLSI Design,
Technical Report MR83i3,
Eindhoven University of Technology, 1982
J.L.A.van de Snepscheut: Trace Theory and VLSI Design, LNCS 200, Springer,
1985.
D.E.Thomas, P.Moorby: the Verilog Hardware Description Language, Kluwer, 1991.
S.Weber, B.Bloom, G.Brown: "Compiling Joy into Silicon". In Advanced Research
in VLSI and
Parallel Systems, T. Knight and J. Savage (eds.), MIT Press, 1992.
22
