Verilog RTL Synthesis Algorithm: 3-Step Recipe

1. First we remove all of the blocking assignment statements to obtain a `pure' RTL form. For each register we need exactly one assigment (that becomes one hardware circuit for its input) regardless of however many times it is assigned, so we need to build a multiplexor expression that ranges over all its sources and is controlled by the conditions that make the assignment occur. For example:

   if (a) b = c; d = b + e; if (q) d = 22;

   is converted to

   b <= (a) ? c : b; d <= q ? 22 : ((a) ? c : b) + e;

   »Conversion to `pure RTL' list form, ML fragment
2. For each register that is more than one bit wide we generate separate assignments for each bit. This is colloquially known as `bit blasting'. This stage removes arithmetic operators and leaves only boolean operators. For example, if v is three bits wide and a is two bits wide:

   v <= (a) ? 0: (v>>1)

   is converted to

   v[0] <= (a[0]|a[1]) ? 0: v[1]; v[1] <= (a[0]|a[1]) ? 0: v[2]; v[2] <= 0;

   »Conversion to Bit Blasted Form, ML fragment
3. Build a gate-level netlist using components from the selected library of gates. (Similar to a software compiler when it matches operations needed against instruction set.) Sub-expressions are generally reused, rather than rebuilding complete trees. Clearly, logic minimization (Karnaugh maps and Espresso) and multi-level logic techniques (e.g. ripple carry versus fast carry) as well as testability requirements affect the chosen circuit structure.

The following ML fragment will make a ripple carry adder from lsb-first lists of nets:

fun add c (nil, nil) = [c]
|   add c (a::at, b::bt) =
    let val s = gen_xor(a, b)
        val c1 = gen_and(a, b)
        val c2 = gen_and(s, c)
        in (gen_xor(s, c))::(add (gen_or(c2, c1)) (at, bt))
        end

Can division be bit-blasted ? Yes, and for some constants it is quite simple.

For instance, division by a constant value of 8 needs no gates - you just need wiring!

For dynamic shifts make a barrel shifter using a succession of broadside multiplexors, each operated by a different bit of the shifting expression.

See link »Barrel Shifter, ML fragment.

To divide by a constant 10 you can use that 8/10 is 0.11001100 recurring, so if n and q are 32 bit unsigned registers, the following computes n/10:

   q = (n >> 1) + (n >> 2);
   q += (q >> 4);
   q += (q >> 8);
   q += (q >> 16);
   return q>>3;

There are three ML fragments on the course web site that demonstrate each step of this recipe: ~ 1: »pure conversion~ 2: »bit-blasting~ 3: »gate building (The details of the algorithms and being able to reproduce them is not examinable but being able to draw the gate-level circuit for a few lines of RTL is examinable).

20: (C) 2008-13, DJ Greaves, University of Cambridge, Computer Laboratory.

Flash Player Upgrade Needed    READY