====== 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.)//

===== A one-place buffer =====

ACT supports behavioral descriptions using the [[language:langs:chp|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
<code act>
L?x
</code>
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''.
<code act>
R!x
</code>
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:
<code act>
L?x; R!x
</code>
Finally, the one-place buffer corresponds to an infinite repetition of this sequence of operations. This is written as follows:
<code act>
*[ L?x; R!x ]
</code>

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

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

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:

<code act>
defproc one_place_buffer (chan?(int<8>) L; chan!(int<8>) R)
{
   int<8> x;
 
   chp {
       *[ L?x; R!x ]
  }
}
</code>
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 ten-place buffer =====

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.

<code act>
 one_place_buffer b0;   // create buffer called b0
 one_place_buffer b1;   // create buffer called b1
</code>
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 [[language:connections|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:
<code act>
b0.R = b1.L;
</code>

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:
<code act>
one_place_buffer b[10];
</code>
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:
<code act>
b[0].R = b[1].L;
b[1].R = b[2].L;
...
b[8].R = b[9].L;
</code>
Since typing all of these connections gets tedious, ACT provides syntax for [[language:controlflow|repetitive constructions]]. The same sequence of connections can be written:
<code act>
(i : 9 : b[i].R = b[i+1].L;)
</code>
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:
<code act>
(sym id : range : body(id) )
</code>
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
<code act>
 body(lo) sym body(lo+1) sym ... sym body(hi)
</code>
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:

<code act>
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;
}
</code>
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''.

===== An N-place buffer =====

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:
<code act>
   one_place_buffer b[N];
   (i : N-1 : b[i].R = b[i+1].L;)
   b[0].L = L;
   b[N-1].R = R;
</code>
Finally, we need to define a process that is parameterized by ''N''. The complete definition is:

<code act>
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;
}
</code>

If we want to create a ten-place buffer, we would instantiate it as follows:
<code act>
buffer<10> b;   // parameter is set to 10
</code>
Note once again the use of angle brackets to specify template parameters.

===== Simulating the buffer =====

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.

<file act 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;
}
</file>

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

<code>
% 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>
</code>
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.