GEZEL Datapath Design
From Gezel2
Datapaths are the basic building blocks in GEZEL, similar to a module in Verilog or an entity in VHDL. First, the essential datapath elements are considered: registers and signals, and expressions. Then datapath definitions are introduced that can embed these expressions. Finally, the different methods of datapath composition are discussed, either by creating interconnections between ports, or else by structural hierarchy: encapsulating one datapath into another one.
Contents |
Registers and Signals
GEZEL models synchronous, single-clock designs. Yet, a clock signal is not present in GEZEL language, it is implicit in the design description. By looking at a GEZEL program, you can say precisely how it will behave as a clock-cycle true description. You can do this by looking at the kind of variables it uses in calculations. GEZEL has two kinds of variables: signals and registers.
A signal can hold a value within a single clock cycle. It has the same meaning as a wire in an actual implementation. A signal also has a name and a type and is created with the sig keyword. For example, a signal with name v12 and type ns(12) is created as follows.
sig v12 : ns(12);
This type ns(12) stands for a 12-bit unsigned number. Signal v12 can hold values from 0 to 4095. When you force this signal to hold values outside of this range, precision loss will occur. This will be discussed in Section 2.2, “Expressions,�? on page 10. There is one other type available for values, called tc(n). This type represents arbitrary-length signed numbers with two’s complement representation. For example, to create the equivalent of a C integer on a 32-bit machine, use the following definition.
sig aCinteger : tc(32);
Registers are used to store values over multiple clock cycles. In contrast to signals, register variables have two values: a current-value and a next-value. The current-value is the value available at the output of a register, so it is the value obtained when reading from the register. The next-value is the value at the input of the register, so it is the value that is being written into the register. A register is created in the same way as a signal but uses the reg keyword. A 16-bit unsigned register for example is created as
reg r : ns(16);
The register lies at the basis of clock-cycle-true behavior. There are implicit simulation semantics tied to the register. At the start of each clock cycle, the next-value (of the previous clock cycle) is copied into the current-value (of the current clock cycle). In between clock edges, the next-value is updated based on the current-value, constants and inputs. This way, it is possible to create clock-cycle true descriptions without mentioning the clock explicitly. The initial value of a register is zero (0), while the initial value of a signal is undefined.
Expressions
Expressions enable calculations with signals and registers. Expressions are formed using operators that reference the names of signals and registers. For example, an addition of two signals b and c into signal a looks like
a = b + c;
When a has insufficient precision to hold all possible combinations of the sum b + c, precision loss can occur. For example, assume the following types for a, b and c:
sig a, b, c : ns (8);
Clearly, when b + c is bigger than 256, the result cannot be stored in a. GEZEL will throw out bits at the most-significant side of the result (overflow). If b + c is 260, then the resulting value in a will be 4 (260 = 256 + 4). In some expressions, intermediate values will occur. In the above expression, b + c is such an intermediate value. A more obvious example is
a = ((b+b) + (c+c));
Here, brackets are used to indicate the order in which this expression is to be evaluated. First, the sums b+b and c+c are obtained. These two intermediate values are combined and assigned to a. Intermediate values need a type, too. GEZEL uses a default type rule to choose the type of intermediate results. This is rule consists of two parts: (a) the result of an operation is the maximum wordlength of the operands and (b) if any of the operands is signed, then the result will be signed as well. There are exceptions to this rule which will be indicated later.
Expressions combine signals and registers with operators. Operators have a precedence, a preferred order of evaluation. For example, in an expression such as
a = b * b + c * c;
the multiplications (*) will be performed before the additions (+), because multiplication has a higher precedence than addition. Precedence rules can be modified by using round brackets. The following bullets introduce the different operators that can be used in expressions, starting at the ones with low precedence and going up to high-precedence operations.
- Assignment and Selection
The assignment operation updates the value of a signal or register. The selection operation conditionally extracts the value of a signal or register.
| a = expression; | The assignment operations assigns the value of epxression into a. At the moment of assignment, the value of expression is casted in a (cfr the casting operation). |
| b ? c : d | The selection operation implements choice. The value of b is evaluated. When it is nonzero, the expression evaluates to c. When it is zero, the result is d. |
- Bitwise Logical Operations
Bitwise logical operations combine two bitpatterns into a new bitpattern. The bits at corresponding indices are combined using a single-bit logical operations. The logical operations are Inclusive Or, Exclusive Or, and And.
| b | c | The bit pattern in b is IOR-ed with the bit pattern in c. |
| b ^ c | The bit pattern in b is XOR-ed with the bit pattern in c. |
| b & c | The bit pattern in b is AND-ed with the bit pattern in c. |
| ~ b | The bit pattern in b is inverted (This operation has higher precedence than all two-operand operations). |
- Comparison Operations
Comparison operations compare the value of two expressions and yield a true-or-false result. The value true or false is represented as a 1-bit unsigned number (ns(1)), with 1 indicating true, and 0 indicating false.
| a == b | True if the value of a is equal to the value of b. |
| a != b | True if the value of a is different from the value of b. |
| a < b | True if the value of a is smaller than the value of b. |
| a > b | True if the value of a is bigger than the value of b. |
| a <= b | True if the value of a is smaller than or equal to the value of b. |
| a >= b | True if the value of a is bigger than or equal to the value of b. |
- Arithmetic Operations
Arithmetic Operations do calculations on all of the bits of a signal or register, treated as an unsigned number or else a two’s complement signed number.
| a << b | a is shifted left over b positions. The wordlength of the result is equal to the wordlength of a plus 2-to-the-power (wordlength of b). |
| a >> b | a is shifted right over b positions. The wordlength and the sign of the result are equal to that of a (arithmetic shift). |
| a + b | a is added to b. |
| a - b | b is subtracted from a. |
| a * b | a and b are multiplied. |
| a % b | modulo: the remainer of the division of a by b. The sign of the divisor is ignored. The result is always positive. |
| a # b | b) |
| - a | Negate the value in a (this operation has higher precedence than all two-operand operations). |
- Cast Operation
A cast operation converts the value of a signal into one with another type. This way, it is possible to convert for example a 5-bit unsigned number into a 6-bit signed number. When the target type has enough bits, no precision will be lost. For two’s complement signed numbers, a concept called sign extension is applicable. Sign extension preserves the sign of a two’s complement number when the wordlength increases. When the target type has insufficient bits, some precision can be lost. Bits are chopped off at the most-significant side. The resulting bitpattern is interpreted as a signed/unsigned number of the targeted wordlength.
For example, if a is ns(8) and holds the value 7, and b is tc(4), then
b = (tc(3)) a;
will leave the binary pattern 0b1111 in b, which is interpreted as -1.
| (typespec) expr | Converts the type of expr to typespec. |
- Unary Operations
A unary operation has a single operand. There is a bitwise NOT operator and a negation operation, see ‘Bitwise Operations’ and ‘Arithmetic Operations’.
- Bit Selection Operation
A bit selection operation extracts part of a bitpattern in a word. There is a single-bit format as well as a bitvector format.
| a[n] | Returns bit n from a as a ns(1) number. n has to be a positive constant. If n is bigger than the wordlength of a, 0 is returned. |
| a[m:n] | Return bitvector from bit m to bit n (n >= m) from a as a ns(n-m+1) number. n and m have to be positive constants. If a bit index goes out of the wordlength range of a, 0 is returned for that bit. |
- Lookup Table Operation
A Lookup Table Operation offers access to a constant array, which is defined earlier in the code. The lookup table content needs to be defined first, after which it can be accessed using a lookup table operation. A Lookup Table definition is done by enumerating all the elements in the lookup table in a comma separated list as follows:
lookup a : ns(8) = {15, 22, 36, 0x4f};
This defines a lookup table a which holds elements of type ns(8). The table holds 4 elements. The element at index position 0 is 15 and the element at index position 3 is 0x4f (79).
The lookup table access operation simply access the array using the index in between round brackets. For example, to access the third element of a, one would use
a(2)
Signal flow graphs
The cycle-true execution model of GEZEL expresses concurrency by allowing multiple expressions to be evaluated in the same clock cycle. A set of expressions that execute together in the same clock cycle are grouped together in a signal flowgraph.
Consider the design of a Viterbi Butterfly operation (a well-known operation in convolutional decoding). This operation processes tuples of data according to an operation called add-compare-select
y1 = min( d1 + a, d2 - a ) y2 = min( d1 - a, d2 + a )
Assume the following set of signals and registers.
sig a1, s1, a2, s2 : ns(8); // intermediate signals reg d1, d2, y1, y2 : ns(8); // input and output tuple reg a : ns(8);
The signals flowgraph of expressions that implements this equation can be as follows
always {
a1 = d1 + a;
s1 = d1 - a;
a2 = d2 + a;
s2 = d2 + a;
y1 = (a1 > s2) ? s2 : a1;
y2 = (s1 > a2) ? a2 : s1;
}
The keyword always indicates that the group of expressions following it will execute each clock cycle. A signal flow graph can hold an arbitrary number of expressions. All expressions within a single signal flow graph are concurrent within one clock cycle. The order in which expressions are evaluated is independent of the order in which they appear in the GEZEL program (i.e., it is independent of their lexical order). Rather, the order is determined by the data precedences of signals and registers. A register can always be read, at any moment during a clock cycle. As discussed in Section 2.1 on page 9, a register has both a current value and a next value. For a signal, this is not the case. A signal has only an immediate value, valid within a single clock cycle. Thus, a signal has to be written first before it can be read. It has to be written the first time within a clock cycle based on values in registers and constants. As a consequence of this property of signals and registers, the order of expressions within a signal flow graph becomes irrelevant. For example, if you would write:
always {
y1 = (a1 > s2) ? s2 : a1;
y2 = (s1 > a2) ? a2 : s1;
a1 = d1 + a;
s1 = d1 - a;
a2 = d2 + a;
s2 = d2 + a;
}
then, when evaluating y1, the GEZEL simulator will notice that none of the signals a1, a2, s1 and s2 are available yet. Consequently, it would first find a current value for these signals. So, this signal flow graph behaves exactly the same as the one we described before that.
Named signal flow graphs
Besides the unnamed always signal flow graph, you can create signal flow graphs with a name using the sfg keyword. For example, the previous signal flow graph could be written as:
sfg mysfg {
y1 = (a1 > s2) ? s2 : a1;
y2 = (s1 > a2) ? a2 : s1;
a1 = d1 + a;
s1 = d1 - a;
a2 = d2 + a;
s2 = d2 + a;
}
The difference between a named signal flowgraph (sfg) and the unnamed always is that the former does not automatically execute each clock cycle. GEZEL will allow you to create a controller that schedules the named signal flowgraph. Controller design will be discussed in GEZEL Controller Design.
Datapath modules
A datapath corresponds to a module in Verilog or an entity in VHDL. It is a piece of hardware logic that is treated as a single entity by subsequent RT- and logic synthesis tools. A datapath combines a number of named signal flow graphs with a list of input and output signals. A signal flow graph can be thought of as an instruction for that datapath. A datapath can have only a single always signal flow graph, but it can have multiple named signal flow graphs.
A datapath is the smallest GEZEL unit that can be simulated. So, subsequent examples will be fully self-contained programs rather than snippets. Here is an example of a 2-bit counter as a hardwired datapath. A 2-bit counter as a hardwired datapath
dp counter(out value : ns(2)) {
reg c : ns(2);
always {
value = c;
c = c + 1;
$display(“Cycle “, $cycle, “: counter = “, value);
}
}
system S {
counter;
}
This datapath has a single output port called value. An output port also has a type, indicated after the colon following the port name. The ports define the outline of the datapath. The only way an ‘outsider’ can access the datapath is by reading/writing values on the datapath ports.
On line 2, we create a 2-bit register. This register is local to the datapath counter. It can be accessed only from within the datapath.
On line 3—7, we define a signal flowgraph called run. It contains, besides expressions, also a directive on line 6. A GEZEL directive does affect how the simulator behaves, but it does not affect the simulation outcome. In this case we are using the display directive, which is used to print out values on the datapath. One special variable that is accessed is called $cycle. This variable returns the current simulation cycle. Thus, the effect of the display directive will be to print out the current simulation cycle as well as the output value of the counter.
Finally, on lines 10—11, the toplevel of the system is expressed. A GEZEL file must always have a system statement.
The counter of Listing 2 can be simulated by means of the fdlsim standalone GEZEL simulator. To simulate 6 clock cycles, we execute
>fdlsim listing2.fdl 6 Cycle 1: counter = 0 Cycle 2: counter = 1 Cycle 3: counter = 2 Cycle 4: counter = 3 Cycle 5: counter = 0 Cycle 6: counter = 1
As expected, the counter counts up to three and then wraps around. A datapath definition thus consists of three elements: An IO definition, a definition of local signals and registers, and a set of signal flowgraphs. The IO definition can create input — as well as output ports. For example, a simple ALU that can add, subtract and accumulate would look as follows.
dp alu(in x, y : ns(8); out z : ns(8)) {
reg acc : ns(8);
sfg add {
z = x + y;
}
sfg sub {
z = x - y;
}
sfg accumulate {
acc = acc + x;
z = acc + x;
}
sfg rst {
acc = 0;
z = 0;
}
}
There are four named signal flowgraphs in this example. The datapath has two inputs, x and y, and one output, z. There is an internal accumulator register, acc. There is one signal flowgraph call rst. This will be used to reset the accumulator register. During this reset operation, we will also drive the output of the datapath to zero.
Not all datapath definitions that one can write down in GEZEL are valid. There are four rules to which a datapath definition must conform. When any of those rules are violated, then either the GEZEL parser will reject your code, or else a runtime error message will be triggered. The four rules are enumerated below.
- During any clock cycle, all datapath outputs are defined.
- During any clock cycle, no combinatorial loop between signals can exist. This happens when there is a circular dependence on signal values, i.e. signal a is used to define signal b, and signal b is used to define signal a. This implies that all signal values will eventually only be dependent, during any clock cycle, on datapath inputs, datapath registers and constant values.
- If an expression uses the value of a signal during a particular clock cycle, then that signal must also appear at the left-hand side of an assignment expression in the same clock cycle.
- Neither registers, nor signals or datapath outputs can be assigned more than once during a clock cycle. A special case of this is that a datapath input cannot be assigned inside of a datapath, because a datapath input must be driven by the output of another datapath.
Here are a few examples of erroneous signal flowgraphs.
// WRONG: output v is not always defined
dp bad1(out v : ns(1)) {
always {}
}
// WRONG: a combinatorial loop between signals
dp bad2 {
sig a, b : ns(1);
always {
a = b + 1; // a defines b, b defines a
b = a + 1; // and both are signals (not registers)
}
}
// WRONG: dangling signal
dp bad3 {
sig a, b : ns(1);
always {
a = b + 1; // b is unknown
}
}
// WRONG: a signal is assigned more than once
dp bad4 {
sig a : ns(1);
always {
a = 1;
a = 5;
}
}
Structural Hierarchy
Datapaths can be included inside of other datapaths, thus implementing structural hierarchy. For this purpose, GEZEL provides the keyword use. Consider the example of a 4-input AND gate.
dp andgate(in a, b : ns(1); out q : ns(1)) {
always {
q = a & b;
}
}
dp andgate2 : andgate
dp andgate3 : andgate
dp fourinputand(in a, b, c, d : ns(1); out q : ns(1)) {
sig s1, s2 : ns(1);
use andgate ( a, b, s1);
use andgate2( c, d, s2);
use andgate3(s1, s2, q);
always {
$display(a," ", b, " ", c, " ", d, " -> ", q);
}
}
dp tst(out a, b, c, d : ns(1)) {
reg n : ns(4);
always {
n = n + 1;
a = n[0]; b = n[1]; c = n[2]; d = n[3];
}
}
dp sysandgate {
sig a, b, c, d, q : ns(1);
use tst(a, b, c, d);
use fourinputand(a, b, c, d, q);
}
system S {
sysandgate;
}
Lines 10—18 define a four-input AND gate using three two-input AND gates. A use statement allows to include a two-input AND gate inside of the four-input AND gate. Connections can be made to datapath inputs, outputs or local signals. Of course, the semantic requirements enumerated earlier must be obeyed. Lines 20—26 define a testbench that enumerates all 4-bit input patterns by decomposing the bits of a counter. Finally, lines 28—32 interconnect the testbench to the four-input AND gate in a system block.
We can now simulate this design for 16 clock cycles, and observe all combinations of the AND gate to verify it works correctly:
>../../devel/build/bin/fdlsim listing4.fdl 16 0 0 0 0 -> 0 1 0 0 0 -> 0 0 1 0 0 -> 0 1 1 0 0 -> 0 0 0 1 0 -> 0 1 0 1 0 -> 0 0 1 1 0 -> 0 1 1 1 0 -> 0 0 0 0 1 -> 0 1 0 0 1 -> 0 0 1 0 1 -> 0 1 1 0 1 -> 0 0 0 1 1 -> 0 1 0 1 1 -> 0 0 1 1 1 -> 0 1 1 1 1 -> 1
Datapath cloning
Sometimes, multiple copies of one and the same datapath are needed. GEZEL provides a cloning operation to create such an identical copy of a single datapath. The next example shows how three identical AND gates can be created by defining one and then cloning the first AND gate two times.
dp andgate(in a, b : ns(1); out q : ns(1)) {
always {
q = a & b;
}
}
dp andgate2 : andgate
dp andgate3 : andgate
Cloning creates an identical but independent copy. If the parent datapath includes a register, then the cloned datapath will contain its’ own register. This completes basic modeling techniques for datapaths. The next section covers the modeling of controllers, that enable the use of datapath with multiple signal flowgraphs.
A note on the system statement
Before GEZEL 1.7, the system statement was used to express the toplevel interconnect. Starting with GEZEL 1.7, this practice is however deprecated, and it is suggested to use system blocks with only a single datapath. To express datapath interconnections, make use of structural hierarchy such as for example shown in listing above.
The main motivation to do so is to make the modeling style more consistent, and to enable future GEZEL tools to perform type checking on the interconnect. This modification was done as a result of discussions with Jorgen Steensgaard-Madsen, DTU.
