First-in first-out buffer in CHP

(It is a bit unfortunate that the computer science community uses the term buffer to refer to a fifo, while the circuits community uses the term buffer to refer to an electrical circuit that introduces gain to improve signal drive strength.)

ACT supports behavioral descriptions using the CHP language. The CHP language is a message-passing programming language. Its syntax is inspired by Dijkstra's guarded commands language and Hoare's CSP language. In this language, circuit components (processes) communicate over communication channels, where the communication channels have no buffer capacity (sometimes called rendezvous synchronization).

A one-place buffer is a component that repeatedly does the following: it receives a new input; once the input is received, it sends the new value on its output. Suppose we want to describe a CHP component that has an input channel L an output channel R, and has an internal variable x used to hold the received value. The statement

L?x

receives a value from channel L and stores it into variable x. This is a blocking receive: if there is a pending input, the communication action succeeds; otherwise the action waits until an input is available.

Once we have successfully received the input, we can follow this operation by sending the value x on the output channel R.

R!x

The send operation is also blocking; the send will block until the receiver is ready to communicate. Since these two actions occur in sequence, we write:

L?x; R!x

Finally, the one-place buffer corresponds to an infinite repetition of this sequence of operations. This is written as follows:

*[ L?x; R!x ]

To make this into a valid ACT program, we need to declare all the variables, and define the one-place buffer component.

defproc one_place_buffer (chan?(int) L; chan!(int) R)
{
   int x;
 
   chp {
       *[ L?x; R!x ]
  }
}

This defines a process called one_place_buffer. The name of the process is followed by its port list. Only signals/variables in the port list are accessible from outside the process.

We have specified two ports: L, and R. L is an input port of a channel, and the values communicated on the channel are of the integer datatype. The datatype used is int in this example, which corresponds to an unsigned integer. L has type chan?(int): an input (the ?) end of a channel (the chan) that carries integer data (int). Note that since the bit-width of the integer was not specified, it is implicitly 32 bits. R has a similar declaration, but uses ! to indicate that it is an output port of a channel.

Finally, the definition of the process includes the declaration of the variable x, and the behavior of the process specified in the CHP sub-language that is surrounded by chp { … }. x is a local variable, and is not accessible from outside the process definition.

The same process that manipulates 8-bit integers would be written as follows:

defproc one_place_buffer (chan?(int<8>) L; chan!(int<8>) R)
{
   int<8> x;
 
   chp {
       *[ L?x; R!x ]
  }
}

Note the use of angle brackets to specify the bit-width. In ACT, angle brackets are used to specify parameters to types (similar to C++).

A buffer that can hold ten values can be obtained by connecting ten one-place buffers to each other, where each buffer operates in parallel. When we defined a one_place_buffer earlier, we actually defined a new ACT type. This ACT type is a process with the specified port list. We can now use this type to create multiple instances of the process, just like we created x as an instance of an integer earlier.

 one_place_buffer b0;   // create buffer called b0
 one_place_buffer b1;   // create buffer called b1

ACT is a hardware description language; hence all processes operate in parallel. So far we have created two parallel one-place buffers. To convert this into a two-place buffer, we need to connect the output of b0 to the input of b1.

ACT provides a flexible syntax for connecting components/ports/instances to each other. The basic connection syntax is a = b, which connects a and b to each other. We can use this syntax to connect the output R of b0 to the input L of b1 as follows:

b0.R = b1.L;

We can repeat this process to create a ten-place buffer. Since linear arrays of processes are common in circuit design, ACT provides array syntax to simplify this process. We can create ten buffers as follows:

one_place_buffer b[10];

This creates ten concurrent buffers, named b[0], b[1], …, b[9]. We can connect them to each other to create a ten-place buffer like this:

b[0].R = b[1].L;
b[1].R = b[2].L;
...
b[8].R = b[9].L;

Since typing all of these connections gets tedious, ACT provides syntax for repetitive constructions. The same sequence of connections can be written:

(i : 9 : b[i].R = b[i+1].L;)

Here, i is a fresh variable that takes on values 0, 1, …, 8 (one less than 9 specified between the two colons). This is a special case of a general syntax that ACT uses for syntactic replication. The syntactic replication construct is written as follows:

(sym id : range : body(id) )

The sym (symbol) might be empty. id is a variable that can be used in body(id), and takes the range specified by range. range can be either an integer-valued expression or start .. end to indicate a start and end index. The result of the replication is

 body(lo) sym body(lo+1) sym ... sym body(hi)

where lo is the starting index of the range, and hi is the ending index.

The complete ten-place buffer with its primary input and output channels is given by:

defproc tenplace_buffer (chan?(int) L; chan!(int) R)
{
   one_place_buffer b[10];
   (i : 9 : b[i].R = b[i+1].L;)
   b[0].L = L;
   b[9].R = R;
}

Note that we connected the b[0] input to the primary input to the process, and the b[9] output to the primary output R.

Now that we have defined a ten-place buffer, how about a twenty-place one? Or some other capacity buffer? ACT provides parameters that can be used to guide circuit construction. An integer parameter in ACT has type pint to distinguish it from a normal int that is part of a physical circuit. Given a parameter N, we can define a parameterized buffer below by generalizing the ten-place buffer example above:

   one_place_buffer b[N];
   (i : N-1 : b[i].R = b[i+1].L;)
   b[0].L = L;
   b[N-1].R = R;

Finally, we need to define a process that is parameterized by N. The complete definition is:

template<pint N>
defproc buffer (chan?(int) L; chan!(int) R)
{
   one_place_buffer b[N];
   (i : N-1 : b[i].R = b[i+1].L;)
   b[0].L = L;
   b[N-1].R = R;
}

If we want to create a ten-place buffer, we would instantiate it as follows:

buffer<10> b;   // parameter is set to 10

Note once again the use of angle brackets to specify template parameters.

Assuming all the process definitions above are in a file buffer.act, we can create a test environment to run a simulation. Below, we create a test_source that sends ten data values on an output channel, and a test_sink that reads inputs and prints them to the screen using the built-in log() command. We then create a top-level test process (called test here) that connects a test_source and test_sink to the buffer.

test.act

import "buffer.act"; // import process definitions
 
defproc test_source (chan!(int) X)
{
    int i;
    chp {
        i := 0;
       *[ i < 10 -> X!i; i := i + 1 ]
   }
}
 
defproc test_sink (chan?(int) X)
{
   int x;
   chp {
      *[ X?x; log ("received ", x) ]
   }
}
 
defproc test()
{
    one_place_buffer b;
    test_source tsrc;
    test_sink tsink;
    b.L = tsrc.X;
    b.R = tsink.X;
}

This can be simulated using actsim as follows. The command-line specifies the ACT file to read, as well as the top-level process name.

% actsim test.act test

actsim> cycle
WARNING: test_sink<>: substituting chp model (requested prs, not found)
WARNING: test_source<>: substituting chp model (requested prs, not found)
WARNING: one_place_buffer<>: substituting chp model (requested prs, not found)
actsim> cycle
[                  30] <tsink>  received 0
[                  50] <tsink>  received 1
[                  70] <tsink>  received 2
[                  90] <tsink>  received 3
[                 110] <tsink>  received 4
[                 130] <tsink>  received 5
[                 150] <tsink>  received 6
[                 170] <tsink>  received 7
[                 190] <tsink>  received 8
[                 210] <tsink>  received 9
actsim>

The first set of numbers is the time (default delays are 10 time units for each step in the CHP program). Next, the instance name is specified in angle brackets. Finally the log message is displayed.

log() is used to print output for debugging purposes. When the circuit is going to be synthesized, the log() statements are simply skipped.