The Asynchronous Circuit Toolkit (ACT) is a suite of programs that can be used to design, verify, and test asynchronous circuits. The tools share a common input language (specified in a text .act file) which can be used to describe circuits at different levels of detail. In what follows, we assume that the reader is familiar with asynchronous design methodologies and terminology.
ACT is a hierarchical, lexically scoped circuit description language. A single ACT file can be used to describe the transistor implementation of a circuit as well as a high-level functional description of the same circuit.
There are three steps used to process an ACT file:
In the parsing phase, the input is converted into internal data structures. In the expansion phase, parameters are substituted, creating a concrete hierarchical netlist. In the instantiation phase, data structures are created for every circuit element specified in the ACT file. Errors may be reported in any of these stages. As a rule of thumb, errors are reported as soon as there is sufficient information to determine the error.
To get a feel for how a circuit is described in ACT, we begin with a simple example circuit. The purpose of this circuit is to create a dual rail channel (called a1of2 for a one-of-two encoded data channel and an acknowledge) and attach a bit-bucket to it.
/* my first act program */ defchan a1of2 <: chan(bool) (bool d0,d1,a) { spec { exclhi(d0,d1) // exclusive high directive } // channel description omitted } defproc bitbucket (a1of2 d) { prs { d.d0 | d.d1 -> d.a+ ~d.d0 & ~d.d1 -> d.a- } } bitbucket b; a1of2 c; b.d = c;
defchan a1of2 is used to create a new channel type named a1of2 with a port list that consists of three Boolean values named d0, d1, and a. A bool is a Boolean-valued electrical node in the circuit, and is a built-in type. Identifier names such as d0 and a1of2 conform to the C naming convention. The body of the type a1of2 is enclosed in braces.
The defchan construct specifies that a1of2 is a channel type, and the signature <: chan(bool) is used to specify that a1of2 is an implementation of a channel of type chan(bool). Boolean-valued variables can be sent or received on this channel since the type of the value communicated on the chan that it implements is bool. chan is also a built-in type that is used for communication channels.
The definition of type a1of2 consists of a spec body. The construct name { … } is used to specify a language-specific body within a type definition. A type can have any number of these language-specific bodies. A program using the ACT library typically will examine a subset of all possible language bodies. In our example, the word spec is recognized to be a specification body.
The specification body contains an assertion indicating that the nodes d0 and d1 are exclusive high, meaning that at most one of them can be true at any time (a form of an invariant). Whenever a circuit element of type a1of2 is created, this specification will be automatically attached to it. Tools that read ACT files can use this information for a variety of purposes, and can also check if this invariant is violated in case of an error in the design of a circuit that uses this channel.
The process bitbucket is defined to take a variable d of type a1of2 as its argument. bitbucket is a process rather than a channel because it was created using defproc instead of defchan. The body of bitbucket contains a different language-specific body, namely a prs body. prs bodies correspond to production rule set descriptions of the process. In the example, the production rules for bitbucket corresponds to what is commonly referred to as a ``bit-bucket or a ``token sink for a four phase dual rail channel.
The statement bitbucket b creates an instance of type bitbucket named b. The statement is said to be an
instantiation. Execution of this statement creates variable b of type bitbucket, production rules corresponding to the body of a bitbucket, and the specification body for the a1of2 variable b.d. Similarly, the statement a1of2 d creates an instance of type a1of2. ACT uses the standard dot-notation to access the names that are in port lists, since they are analogous to the fields of types/structures in conventional programming languages.
The final statement b.d=c connects the two a1of2 types b.d and c. The effect of connecting two types is to make the two instances aliases for each other. Therefore, the connect statement also specifies that the Booleans b.d.d0, b.d.d1, b.d.a are the same as the Booleans d.d0, d.d1, d.a respectively. Electrically, those Booleans correspond to the same circuit node.
ACT recognizes both C and C++ style comments, and they are treated as white space along with spaces, tabs, and new lines. A C-style comment begins with the characters /* and ends with */. Everything between the beginning and end of the comment is treated as whitespace. A C++ style comment begins with two forward slashes, and continues till the end of line.
Variables in ACT fall into two basic categories: parameters
and circuit elements. A parameter is a variable that is used to
parameterize a circuit element in some way and must be of type integer
(pint for unsigned integer or pints for signed integer),
real (preal), or Boolean (pbool). Circuit elements
consist of Booleans (bool), integers (int), or channels
(chan).
A variable identifier can be a sequence of digits, letters, and underscores. The following declarations are legal:
bitbucket b; a1of2 x1; a1of2 _2; bool x5;
On the other hand, the following declaration is incorrect.
pbool 5;
-[ERROR]-> Expecting bnf-item `instance_id', got `5'
Errors use names from the ACT BNF to describe the item that the parser was expecting. Error messages are accompanied by the file name, line number, and column number of the item that resulted in the error.
The variable names self and selfack are reserved. They are used to support
ACT language features like functions and user-defined types.
The names in the port list of a user-defined type are the only parts of
the type that are visible externally. Other parts of the defined type
cannot be accessed outside the body of the type itself. For example,
consider the following definition of bitbucket.
defproc bitbucket(a1of2 d) { bool p; prs { d.d0 | d.d1 -> d.a+ ~d.d0 & ~d.d1 -> d.a- } }
If we had used this definition, then although b.p is a bool
within the bit-bucket b, we cannot access it by statements
outside the body. Therefore, a statement such as b.p=c.d0 would
result in the following message:
bitbucket b; a1of2 c; b.p = c.d0;
-[ERROR]-> `p' is not a port for `bitbucket'
Expressions look very much like C expressions. Expressions can be of two
types: numeric or logical. Numeric expressions can be constructed from
identifiers, numeric constants, parentheses for grouping, and the
arithmetic operators +, -, *, and / for
addition, subtraction, multiplication, and division respectively. The
unary minus operator is also supported. The operator % is used
for computing the remainder. Logical expressions can be constructed from
logical variables, the logical constants true and false,
and the logical operators &, |, and ~ denoting
the and, or, and negation operations respectively. Numeric expressions
can be compared using <, < =, >, >=,
=, and != for the operators less than, less than or equal
to, greater than, greater than or equal to, equal to, and not equal to
respectively.
Most circuits contain a set of components that are replicated a number of times. This is especially common in datapath circuits. ACT has a very flexible array mechanism that can be used to construct complex circuits. The simplest way to create an array is shown below.
bool x[10]; a1of2 y[5][3];
The first statement creates an array of ten bools named x whose
elements are x[0], x[1], …, x[9]. The
second statement creates a two-dimensional array of a1of2
variables named y whose elements are y[0][0],
y[0][1], …, y[4][2]. The entire array range can also
be specified as shown below
bool w[4..7]; // create Booleans w[4], ..., w[7]
ACT also contains a mechanism for constructing sparse arrays. A sparse array is one that has 'holes' in it; in other words, valid indices of the array do not form a contiguous, rectangular block. Consider the following instantiation:
bool x[10]; bool x[12..14];
The first statement creates x[0], …, x[9]; the
second creates x[12], …, x[14]. This is a valid
sequence of statements, and it makes x a sparse array. The
following, on the other hand, is not valid.
bool x[10]; bool x[9..14]; -[ERROR]-> Sparse array: overlap in range in instantiation Original: [10]; adding: [9..14]
Each index of an array can only be created once.
Arrays can be connected to others using the = operation. If two
arrays have the same size, the same type, and the same number of
dimensions, the connection is valid. Conceptually, connections are
performed by converting each array into an ordered list of individual
elements, where the order is specified by the lexicographic ordering
on their indices (the leftmost index has precedence). Finally, an
element-by-element connection is performed. This is illustrated
below.
bool x[10]; bool x[12..14]; bool y[2]; x=y; -[ERROR]-> Types `bool[ [10]+[12..14] ]' and `bool[2]' are not compatible
Note the syntax used to report the sparse array type as a combination of two sub-arrays.
The dimensionality of the two arrays must match for a connection to succeed, and their shapes also have to be compatible.
bool x[12]; bool w[4][3]; x=w;
-[ERROR]-> Type-checking failed in connection
Types `bool[12]' and `bool[4][3]' are not compatible
The following are examples of valid connections:
bool x[10]; bool x[10..12]; bool y[13]; x=y; // success! bool u[4][3]; bool v[4][3]; u=v; // success!
Loops and conditionals can be used to describe complex circuit
structures in a compact manner. Loops are useful when creating array
structures, or connecting arrays in a regular manner. For example,
suppose fulladder is a process that contains channels ci
and co as its carry-in and carry-out. The following connects the
carry chain for a ten bit ripple-carry adder.
fulladder fa[10]; (i : 9 : fa[i].co=fa[i+1].ci; )
The parentheses are used to group the body of the loop. i is
the dummy variable, and it ranges from zero to eight in this
example. In general if only one integer is specified for
the range, the variable ranges from zero to one less than the integer.
This is a special case of a more general syntactic replication construct
that can be used in many contexts.
The conditional statement uses the guarded command notation. They are
used for describing the edge of repetitive structures, during
recursive constructions, or for creating special versions of processes
based on parameters. The following is an example where odd-numbered
indices of x are connected to y, and even-numbered
indices are connected to z.
bool x[10], y[10], z[10]; ( i : 10 : [ (i%2) = 0 -> x[i] = y[i]; [] (i%2) = 1 -> x[i] = z[i]; ] )
In the second definition of bitbucket, the variable p was
defined within the body of the type definition. Therefore, this variable
is local to the type, and cannot be accessed by any construct outside
the body of the type. Different instances of bitbucket get
different copies of p, since it is a local variable. If we had
created a dualrail channel p after the bitbucket, this p
has no relation to the p in the body of bitbucket.
The ACT language has two scopes: the global scope, and the scope within the entity being defined. Ports of types have the same scope as items defined within the body of the type. However, ports are special in that they can also be accessed from outside the type using dot-notation.
ACT does not have a special 'global' keyword. Global nodes can be created by simply defining them in the outer-most scope. For instance, ACT files will tend to begin with
bool Reset,Reset_;
This permits the names Reset and Reset_ to be used
throughout the ACT file.
Complex projects involve a large number of ACT files, including shared libraries and blocks designed by different people. One could easily envision a situation where a particular identifier name is used by multiple designers to describe different processes.
To keep names of processes, channels, and types separate for different
parts of a design, ACT provides the notion of a
namespace. Every instantiation and type definition resides in a
specific namespace. In all our examples so far, this was the
(implicit) global namespace (named Global).
The following example creates a namespace lib and defines types
within the namespace.
namespace lib { export defchan a1of2 <: chan(bool) (bool d0,d1,a) { ... } } lib::a1of2 d;
We have created a channel definition of type a1of2 within the
lib namespace. There are a few items that should be noted.
First, the directive export indicates that the a1of2
type is in fact visible outside the namespace scope. This is why we
can use the notation lib::a1of2 to access this type. The
rationale for this is that one might have created a library, but might
only want a few types exposed (e.g. top-level cells). By default, a
type is not visible outside a namespace unless it is explicitly
exported. Second, a user-defined namespace cannot contain any
global instances of processes. This means that the only legal items
within a namespace are namespace directives, type definitions, and
global data/channel types.
Namespaces can be nested. For instance, we could have:
namespace processor { namespace lib { export defchan a1of2 <: chan(bool) (bool d0,d1,a) { ... } } lib::a1of2 d; }
In this example, d is instantiated from namespace lib
within namespace processor. This brings up another subtlety of
the export directive. An exported definition is only exported
one level up in the namespace hierarchy. Hence, although the channel
processor::lib::a1of2 exists, it cannot be accessed outside the
processor namespace.
namespace processor { namespace lib { export defchan a1of2 <: chan(bool) (bool d0,d1,a) { ... } } } processor::lib::a1of2 d;
-[ERROR]-> Type is not exported up the namespace hierarchy:
processor::lib::a1of2
If this channel needs to be visible
outside the processor namespace, this can be accomplished by
exporting the namespace itself.
namespace processor { export namespace lib { export defchan a1of2 <: chan(bool) (bool d0,d1,a) { ... } } } processor::lib::a1of2 d;
In this approach, every element that is exported from namespace
lib is also exported out of namespace processor.
Something that is a little unusual is that a type cannot be accessed
within a sub-namespace unless it is exported. For instance, in the
example above, if a1of2 was defined within the
processor namespace, then it will not be visible within the
processor::lib namespace unless it is exported. An
export directive is needed to permit a type to be used in other
namespaces apart from the one in which the type was defined.
A namespace can have global variables. The global variables described
earlier were simply a special case corresponding to the namespace
Global. For instance, a collection of process definitions within
a namespace might have a reset signal that is global to the namespace
only, and which is generated using some logic defined within the
namespace.
The keyword import is used to include other design files. An
ACT file can begin with a sequence of import statements.
If the same file is imported twice within the same scope, chances are
that some types would be multiply defined. To avoid such problems,
imports of files which have already been imported within the same
scope or an outer scope are ignored. Therefore, always use
import to include type definitions defined elsewhere.
import "channel.act"; ...
import searches for the file in the current directory
first, then in the colon-separated path specified by $ACT_PATH,
and finally in $ACT_HOME/act.
A typical project would contain multiple files, each possibly having their own namespace. Namespaces can also have global variables, so importing a namespace automatically creates an instance of the global variables from that namespace, and from any sub-namespace that was also imported.
There are a few things that might create issues in such a situation.
First, duplicate namespaces might exist, especially when re-using old
files. For instance, suppose we have two files: lib1.act and
lib2.act both containing namespace lib, but having
definitions that are useful. Importing both would result in the union of
the namespaces, and could create naming conflicts (e.g. multiple
definition of types having the same name—an error). To solve this
problem, one can do the following:
import "lib1.act"; open lib -> lib1; import "lib2.act"; open lib -> lib2;
The open construct enables one to rename a namespace. Once this
has occured, there cannot be any naming conflicts. This version of
open is a renaming construct. The old name for the namespace is
eliminated.
A second issue is one that is more about convenience. Consider a
project that has many different people working on it, each in their
own namespace to avoid naming conflicts. This situation can result in
very long type names. Plus it would be more bookkeeping to have to
create a test environment for the types within, say,
processor::lib—not just because of the long type names, but
because not all types might be exported! In this case we can say:
import "lib.act"; open processor::lib; a1of2 d;
This version of the open directive has two
functions: (i) it adds processor::lib to the search path for
types, and (ii) it allows one to access all types within the
namespace, not just the ones that are exported (including types within
nested namespaces). Note that this open statement will fail if
all types cannot be uniquely resolved.
The sequence of open and import statements can only be
at the beginning of an ACT file.
A second version of import uses namespaces directly, but requires that ACT files be placed in locations that match the namespace hierarchy. The import statement
import processor::lib;
is equivalent to the following:
import "processor/lib/_all_.act";
It assumes that the file _all_.act in the directory
processor/lib contains all the definitions corresponding to the
processor::lib namespace.