Computer Laboratory

Course pages 2013–14

Advanced Computer Design

Exercise 1 - Divider in Bluespec

  • Begin with the Bluespec walk through.
  • Then create your own Bluespec version of an iterative divider + test bench with the following interface and module header:
    interface DividerIterativeIfc#(numeric type width);
       method Action operands(UInt#(width) numerator, UInt#(width) denominator);
       method ActionValue#(Maybe#(UInt#(width))) result();
    endinterface
    
    module mkDividerIterative(DividerIterativeIfc#(width))
          provisos(Add#(width,width,doublewidth));
    
  • Or use an alternative simpler (not generic) interface with "width" removed:
    interface DividerIterativeIfc;
       method Action operands(UInt#(32) numerator, UInt#(32) denominator);
       method ActionValue#(Maybe#(UInt#(32))) result();
    endinterface
    
    module mkDividerIterative(DividerIterativeIfc);
    
  • This should calculate result = (numerator/denominator) where result is assigned tagged Invalid if the denominator=0 but tagged with Valid otherwise.
  • Note that you may well want to use UInt#(doublewidth) types for intermediate results. The provisos statement allows type properties to be constrained.
  • In your test bench you'll want to instantiate the divider and specify the bit-width, e.g. for a 32-bit divider with 64-bit internal variables:
    DividerIterativeIfc#(32) my_div <- mkDividerIterative;
    
  • Create a Server version of the divider with the following types and module header:
    // structure containing input operands
    typedef struct {
             UInt#(width) numerator;
             UInt#(width) denominator;
             } DivOperandsT#(numeric type width) deriving(Bits);
    
    
    // define type for the DividerServer interface, specialising the Server interface
    typedef Server#(DivOperandsT#(width),Maybe#(UInt#(width)))
        DividerServerT#(numeric type width);
    
    module mkDividerServer(DividerServerT#(width))
          provisos(Add#(width,width,doublewidth));
    

    Tips

    A simple approach to division is repeated subtraction, but this is slow. A better approach is to do long division but in binary - see: binary division. Here is a version in C:

    unsigned short div(unsigned short numerator, unsigned short denominator)
    {
      long  n = (unsigned long) numerator;
      long  d = (unsigned long) denominator;
      long  t;
      unsigned short r = 0;
      int j;
      d = d<<15;
      for(j=16; j>0; j--) {
        t = n-d;
        if(t>=0) {
          n = t;
          r = (r<<1) | 1;
        } else
          r = r<<1;
        d = d>>1;
      }
      return r;
    }
    

    Assessment

    Your work will pass when you can demonstrate that both versions of your divider produce the correct result for every possible operand input for width=4.

    Optional Extra

    To find out more about the power of Bluespec, take a look at the ServerFarm example and try instantiating two copies of your divider server vis:

    DividerServerT#(`width) divServ <- mkServerFarm(2,mkDividerServer);
    

    What performance improvements do you see?

    Note: mkServerFarm uses higher-order types, i.e. you can pass a function as a variable. Try doing that in Verilog or VHDL!