GEZEL Overview
From Gezel2
Overview
GEZEL is a language and open environment (LGPL) for exploration, simulation and implementation of domain-specific micro-architectures. GEZEL can help with the design of multiprocessor networks and embedded hardware. It has also been used as a teaching tool in class projects on VLSI architecture design. Highlights of the environment are as follows:
- A specialized language, called GEZEL, allows compact representation of the micro-architecture of domain-specific processors. GEZEL uses cycle-true semantics with dedicated modeling of control structures (FSMD).
- The simulation environment is scripted for fast edit-load-simulate cycles.
The simulation back-end is an open C++ library that enables easy integration of GEZEL into different host environments. * Cosimulation interfaces are available to several instruction-set simulators as well as to SystemC and Java.
- GEZEL can be customized with user-supplied custom library blocks in C++. Those blocks can be provided as dynamic libraries, those providing an excellent basis for exchange of intellectual-property simulation models.
- A design in the GEZEL language can be automatically translated to synthesizable code. In addition, extra support for stimuli capture is available so that GEZEL simulations can be ‘replayed’ on the hardware models.
- As a standalone environment, it works as a hardware exploration environment. When linked with an instruction-set simulator, it becomes a co-design environment.
A typical application of GEZEL would be the design of a coprocessor. In this application, one writes GEZEL code for the hardware coprocessor, and evaluates the performance of the design in the intended target architecture using cosimulation. The simulation is cycle-true but, because of the cosimulation technology, many times faster than a similar system model in (V)HDL.
GEZEL has also been used in multiprocessor simulations to connect several heterogeneous cores with a network-on-chip. VHDL code generated out of GEZEL has been mapped onto FPGA as well as onto ASIC.
In this manual, GEZEL features are discussed from a user-perspective. There is also a Language Reference Manual (LRM) where a more formal treatment of the GEZEL language and semantics is given.
The FSMD Model of Computation
The GEZEL language models hardware according to the semantics of a finite-state-machine with a datapath (FSMD). This section explains the FSMD model of computation. FSMD modeling will be covered later.
A model of computation helps to support a particular design style, by providing simulation semantics to a program. The model of computation of a C program is that of a procedural, sequentially executed language. The model of computation used for GEZEL is hardware-oriented, and is called FSMD (Finite State Machine with Datapath).
This figure illustrates that GEZEL designs contain of a set of modules connected by wires. A module can be an FSMD or else a library block. An FSMD is expressed in the GEZEL language using FSMD semantics. A library block on the other hand is a build-in simulation primitive provided by the GEZEL simulator. Memory cells and cosimulation interfaces are examples of library blocks. An FSMD is a cycle-true model of a datapath with a controller. The datapath contains registers and hardware operators, and the controller sequences operations in the datapath.
Consider first a cycle-true simulation of a hardware module with only registers and operators and no controller, i.e. a fully hardwired datapath. Each register in the module is simulated in terms of two values, one being the next-state value, at the register input, and the other being the state value, at the register output. A cycle-true hardware simulation algorithm takes two simulation phases per clock cycle. During the first phase, the next-state of the registers as well as the outputs of the datapath are evaluated based on the state of the registers as well as the inputs to the datapath.
next_state = f1(state, inputs) output = f2(state, inputs)
During the second phase, the newly obtained next-state values are copied into the state values so that the simulation of the next clock cycle can begin.
state = next_state
A digital cycle-true simulator executes these two phases in an alternating fashion. The behavior of the module therefore is completely defined by the functions f1 and f2. They specify a finite state machine (FSM). Depending on the exact form of f2, one distinguishes a Moore-type FSM and a Mealy-type FSM. In a Moore FSM, the output value is only dependent on the previous-state, not on the current input.
An FSMD is a refined form of the above model that makes a distinction between two kinds of state in the hardware module. The first is called control-state, and the other is called datapath-state. Control-state represents the storage to work with control steps. Many algorithms, when mapped into digital hardware, decompose in a sequence of control steps. Datapath-state on the other hand holds data values required to evaluate the actual expressions of the algorithm.
The next-state function f1 can be decomposed into a f1d to evaluate datapath state and a f1c to evaluate the control state. The datapath state machine uses the control step to implement instructions. The control state machine uses datapath state to implement conditional control steps. Thus, both state machines are cross-coupled. The first phase of the cycle simulation algorithm now becomes:
next_data_state = f1d(data_state, control_state, inputs) next_control_state = f1c(data_state, control_state) data_output = f2(data_state, control_state, inputs)
The second phase of the cycle simulation algorithm now becomes:
data_state = next_data_state control_state = next_control_state
A graphical representation of these equations shows that an FSMD consists of two cross-coupled finite state machines, one playing the role of controller, and the other playing the role of datapath. Information exchange between the two includes conditions (going from the datapath to the controller) and instructions (going from the controller to the datapath).
An FSMD offers important advantages over the basic FSM model when it comes to convenient modeling and mapping of algorithms.
- The explicit distinction of control and datapath state is something that a designer already does naturally. At the highest level, datapath state is naturally present in the state variables of an algorithm. Control state is introduced as a consequence of mapping the algorithm execution onto a time axis of clock cycles.
- A datapath and a controller have different modeling concepts. Datapaths are created by composition of expressions to make calculations. These expressions look like the ones from the C programming language. Controllers on the other hand are created by composition of state transition graphs.
A datapath and a controller have different logic implementation styles. Datapaths are regular, and can be created hierarchically as a composition of smaller elements. Controllers are irregular, and harder to create hierarchically.
An excellent reference on the underlying principles of FSMD modeling can be found in Chapters 10 to 14 of the digital system book by Davio. Unfortunately this reference is out of print. A more recent, also excellent reference are Chapters 1-5 from the digital design book by Frank Vahid. In addition, also SpecC supports FSMD modeling.
- Davio, Deschamps, Thayse, “Digital Systems with Algorithm Implementation,� Wiley and Sons, 1983.
- Vahid, "Digital Design," John Wiley and Sons Publishers, 2006.
- Doemer, Gerstlauer, Gajski, “SpecC Language Reference Manual v 2.0,� 2002.
The relation between controllers and datapaths in GEZEL will be elaborated further in GEZEL Controller Design. The next subsection presents a small example on the mapping of an algorithm into the FSMD model. The GEZEL syntax is introduced as well.
The Euclid Algorithm
In this section, a simple processor that evaluates the greatest common divisor (GCD) using Euclid's algorithm will be modeled into GEZEL modeling and simulation. The particular variant used here is the version defined by Silver and Tersion (1962). This processor determines the GCD of two numbers M and N as follows.
- If M and N are even, then GCD(M,N) = 2 * (GCD(M/2, N/2))
- If M is even and N is odd, then GCD(M,N) = (GCD(M/2, N))
- If M is odd and N is even, then GCD(M,N) = (GCD(M, N/2))
- If M and N are odd, then, assuming M > N, GCD(M,N) = (GCD(M-N, N))
GEZEL models are written at the register-transfer (RT) level of abstraction. An example of such a model that evaluates the GCD algorithm is shown in Figure 1.4. The datapath holds three registers. Two of them, M and N, hold the values of M and N in the GCD algorithm. Each clock cycle, M and N are subtracted, shifted right, or unchanged. This is determined by the control step of the Euclid algorithm. An FSM controller is used to express conditional sequencing.
GEZEL allows a description close to Figure 1.4. The program in Listing 1 shows a processor that evaluates the GCD with one iteration per cycle. The processor has a data processing part (dp) and a control part (fsm). It also has a test-bench that generates two test values. The test-bench is connected to the processor in the system interconnect description.
The datapath description is in lines 1—20. This datapath has two 16-bit input ports m_in and n_in, and one 16-bit output port gcd. In contrast to Figure 1.4a, this is not a structural description. The datapath consists of a number of signal flow graphs, indicated with sfg. An sfg expresses a single clock cycle of behavior on the datapath. You can think of an sfg as an instruction that can be executed by the datapath. The signal flow graphs collect expressions that operate on the datapath registers, created in lines 3—6.
The controller is shown in lines 22—32. This is a finite state machine description that has three states, one of which is the initial state. Line 25 shows an unconditional state transition, starting at state s0 and ending at state s1. During this state transition, the datapath will execute sfg init and outidle. A conditional state transition is expressed using if-then-else logic, such as shown in lines 26—30. A GEZEL Program to evaluate greatest common divisor (GCD)
dp euclid(in m_in, n_in : ns(16);
out gcd : ns(16)) {
reg m, n : ns(16);
reg done : ns(1);
reg factor : ns(16);
sfg init { m = m_in; n = n_in; factor = 0; done = 0;
$display("cycle=", $cycle," m=",m_in," n=", n_in);}
sfg flags { done = ((m == 0) | (n == 0)); }
sfg shiftm { m = m >> 1; }
sfg shiftn { n = n >> 1; }
sfg reduce { m = (m >= n) ? m - n : m;
n = (n > m) ? n - m : n; }
sfg shiftf { factor = factor + 1; }
sfg outidle { gcd = 0; }
sfg complete{ gcd = ((m > n) ? m : n) << factor;
$display("cycle=", $cycle, " gcd=", gcd); }
}
fsm euclid_ctl(euclid) {
initial s0;
state s1, s2;
@s0 (init, outidle) -> s1;
@s1 if (done) then (complete) -> s2;
else if ( m[0] & n[0]) then (reduce, outidle, flags) -> s1;
else if ( m[0] & ~n[0]) then (shiftn, outidle, flags) -> s1;
else if (~m[0] & n[0]) then (shiftm, outidle, flags) -> s1;
else (shiftn, shiftm,
shiftf, outidle, flags) -> s1;
@s2 (outidle) -> s2;
}
dp test_euclid(out m, n : ns(16)) {
sfg run {
m = 2322;
n = 654;
}
}
hardwired h_test_euclid(test_euclid) {run; }
dp euclid_sys {
sig m, n, gcd : ns(16);
use euclid(m, n, gcd);
use test_euclid(m, n);
}
system S {
euclid_sys;
}
The test-bench for the GCD processor is shown in lines 34—50. We will apply the constant values 2332 and 654 as test values. This GEZEL description can be simulated with the fdlsim simulation tool. To simulate 25 cycles from this description, execute the command line
>fdlsim euclid.fdl 25 cycle=0 m=912 n=28e cycle=22 gcd=6
The simulator reports that the GCD of the two test values is 6, and that this value is obtained at cycle 22 of the simulation. This line is printed using a simulation directive as shown on line 17 of Listing 1.
An interesting feature of GEZEL is that it does not require a compilation phase. When the simulator starts, it will parse in the GEZEL description and immediately start the simulation. This way the design and evaluation of hardware models becomes interactive. The GEZEL parser generates error messages immediately when it encounters an error. For example, when line 12 of Listing 1 contains ‘sff reduce’ then the following error message appears:
>fdlsim euclid.fdl 25
*** (line 13) Syntax Error
(9) sfg flags { done = ((m == 0) | (n == 0)); }
(10) sfg shiftm { m = m >> 1; }
(11) sfg shiftn { n = n >> 1; }
(12) >>> sff reduce { m = (m >= n) ? m - n : m;
Failed to parse euclid.fdl
