/// LSU EE 3755 -- Spring 2002 -- Computer Organization
//
/// Verilog Notes 3 -- Delay

/// Contents

 /// Delays
 /// Ripple Adder and Delays
 /// The Event Queue and Verilog Simulation

/// Lexicographic Conventions
//
// :Sample:  A short example of Verilog, much less than a whole module.
// :Example: A long example of Verilog code, usually a module.
// /foo/:    A defining reference, indicating that this is where foo is defined.
// [bar]:    Information that EE 3755 students are not yet responsible for
//            but is included here anyway.

/// References

// :P:   Palnitkar, "Verilog HDL"
// :Q:   Qualis, "Verilog HDL Quick Reference Card Revision 1.0"
// :H:   Hyde, "Handbook on Verilog HDL"
// :LRM: IEEE, Verilog Language Reference Manual  (Hawaii Section Numbering)
// :PH:  Patterson & Hennessy, "Computer Organization & Design"


////////////////////////////////////////////////////////////////////////////////
/// Delays

// :P: 6.2, 6.2.2, 6.2.3
// :H: Not covered for continuous assignments.
// :LRM: 6.1

// A /delay/ is a specification of elapsed time, the amount of
// time the simulator is supposed to wait.

// The simulator keeps track of simulated time, measured in cycles.
// This is unlike conventional languages.

// The default delay is zero.
//
// If delays are not specified things happen instantly.
//
// The default delay for a gate is zero.
//
// The default delay for an assign is zero.
//
// The default delay for an assign with a really complex expression is zero.
//
// The default delay for a module containing a zillion gates is zero.
//
// Zero is NOT the same as one.
//

// Delays can be specified in a variety of ways.
//
//   The following will be covered in class:
//
//      Delays in wires and assigns (this set).
//      Delays in behavioral statements (later this semester).
//
//   See "delays" module, below, for further description.


// :Example:
//
// A module that just passes the signal through, like wire.  Suppose
// at t=5 input a changes from 0 to 1, when does x change?

module no_delays(x,a);
   input a;
   output x;

   assign x = a;
   wire   w = x;

endmodule

// Ans: x changes at 5 + 0 = 5.


// :Example:
//
// A module that just passes the signal through unchanged, though it
// passes through two inverters.  Suppose at t=5 input a changes from
// 0 to 1, when does x change?

module no_delays2(x,a);
   input a;
   output x;

   wire   b;

   not n1(b,a);
   not n2(x,b);

endmodule

// Ans: x changes at 5.


// :Example:
//
// Illustration and explanation of delays in assigns and wires.

module delays(x,a);
   input a;
   output x;

   // Delay (For nets.)
   //
   wire #7   w = a;
   //
   // w gets value of a 7 cycles after each change in a (a must hold
   // steady for at least 7 cycles).

   // Delay (For continuous assignments.)
   //
   assign #3 x = w;
   //
   // x gets value of "w" 3 cycles after each change in "w" (w must
   // hold steady for at least 3 cycles).

endmodule



////////////////////////////////////////////////////////////////////////////////
/// Ripple Adder and Delays


// :Example:
//
// The binary full adder presented earlier.  There are no delays here.

module bfa_implicit(sum,cout,a,b,cin);
   input a,b,cin;
   output sum,cout;

   assign sum =
          ~a & ~b &  cin |
          ~a &  b & ~cin |
           a & ~b & ~cin |
           a &  b &  cin;

   assign cout = a & b | b & cin | a & cin;

endmodule


// :Example:
//
// The same BFA with delays.
// Suppose "a" changes at t=5 and "b" changes at t=20.
// When do sum and cout change?

module bfa_implicit_d(sum,cout,a,b,cin);
   input a,b,cin;
   output sum,cout;

   assign #3 sum =
          ~a & ~b &  cin |
          ~a &  b & ~cin |
           a & ~b & ~cin |
           a &  b &  cin;

   assign #2 cout = a & b | b & cin | a & cin;

endmodule

// Ans: sum: t=8 and t=23;  cout t=7 and t=22.


 /// More information
//
// If a changes at t=5 and b changes at t=6 the situation is
// different because there are two changes in "sum" within the
// 3-cycle delay.


// :Example:
//
// A 4-bit ripple adder constructed using the undelayed BFA.
// If a changes at t=5 when does sum change?

module ripple_4(sum,cout,a,b);
   input [3:0] a, b;
   output [3:0] sum;
   output       cout;

   wire         c0, c1, c2;

   bfa_implicit bfa0(sum[0],c0,a[0],b[0],1'b0);
   bfa_implicit bfa1(sum[1],c1,a[1],b[1],c0);
   bfa_implicit bfa2(sum[2],c2,a[2],b[2],c1);
   bfa_implicit bfa3(sum[3],cout,a[3],b[3],c2);

endmodule

// Ans: I'm sure everyone got it.


// :Example:
//
// A 4-bit ripple adder constructed using the BFA with delays.
// Suppose at t=0 a=0 and b=4'b1111
// If a changes to 1 at t=100 when does sum stop changing?

module ripple_4_d(sum,cout,a,b);
   input [3:0] a, b;
   output [3:0] sum;
   output       cout;

   wire         c0, c1, c2;

   bfa_implicit_d bfa0(sum[0],c0,a[0],b[0],1'b0);
   bfa_implicit_d bfa1(sum[1],c1,a[1],b[1],c0);
   bfa_implicit_d bfa2(sum[2],c2,a[2],b[2],c1);
   bfa_implicit_d bfa3(sum[3],cout,a[3],b[3],c2);

endmodule

// Ans t=109  (Not checked)


// :Example:
//
// A 4-bit adder using operators and no delays. This would be
// a better way of coding a 4-bit adder in Verilog, but it's
// not a good way to demonstrate the low speed of a ripple adder
// to a computer organization class.

module another_adder(sum,cout,a,b);
   input [3:0] a, b;
   output [3:0] sum;
   output       cout;

   wire [4:0]   sum_with_carry = a + b;
   assign       sum = sum_with_carry[3:0];
   assign       cout = sum_with_carry[4];

endmodule


// :Example:
//
// This is not really an example and students are not expected
// to understand it.  This is a testbench for the adder, it
// instantiates the adders, generates inputs for them, and checks
// for the correct output.

module demoadd();

   wire [4:0] sum1, sum2, sum3;
   reg [4:0] shadow_sum;
   reg [3:0]  a, b;
   integer    i;

   ripple_4 adder1(sum1[3:0],sum1[4],a,b);
   ripple_4_d adder2(sum2[3:0],sum2[4],a,b);
   another_adder adder3(sum3[3:0],sum3[4],a,b);

   task check_sum;
      input [4:0] s;
      input [79:0] name;

      if( s != shadow_sum ) begin
         $display("Wrong sum in %s: %d + %d = %d != %d\n",
                  name, a, b, shadow_sum, s);
         $stop;
         end

   endtask

   initial begin

      for(i=0; i<=255; i=i+1) begin
         a = i[3:0];
         b = i[7:4];
         shadow_sum = a + b;
         #10;
         check_sum(sum1,"Ripple");
         check_sum(sum2,"Ripple_d");
         check_sum(sum3,"Operator");
      end

      $display("Tests completed.");

   end

endmodule


////////////////////////////////////////////////////////////////////////////////
/// The Event Queue and Verilog Simulation

 /// The Verilog Simulator Event Queue
//
// Simulator maintains a "to-do list" called an /event queue/.
//
// An entry in the event queue specifies something that the simulator
//  needs to do.  These include:
//
//   (A) Changing the value of a wire [or reg].
//
//   (B) Evaluating an expression appearing in an assign statement.
//
//   (C) Determining the output of a gate.
//
// (The letters above are used in the example below.)
//
// Each entry has a /timestamp/ which indicates when the action
//  specified by the entry is supposed to be done.
//
// Entries are sorted by timestamp.  
//
// [Entries with the same timestamp are divided in to five layers.]

 /// How Verilog Simulators Run
//
// Wires [and registers] are initialized to x.
//
// Initial entries are put in the event queue. (Covered later in the
//  semester.)
//
// WHILE there the event queue is non-empty:
//
//   Remove any entry with the smallest time stamp.
//
//   Set the time to that time stamp.
//
//   If the entry changes the value of a wire [or reg]:
//
//      Put entries in the event queue for all gates and expressions
//      [and event controls] affected by the wire [or reg].
//
//   Else If the entry is for an expression in an assign statement:
//
//      Evaluate the expression.  Put an entry in the event queue
//      to modify the wire that's assigned.  The entry's time stamp
//      is the current time plus the delay (plus zero if no delay).
//      [Delete other entries in the event queue corresponding to the
//      same assign.]
//
//   Else If the entry is for a gate:
//
//      Determine the output of the gate. Put an entry in the event
//      queue to modify the wire connected to the gate's output.  The
//      entry's time stamp is the current time plus the delay (plus
//      zero if no delay).  [Delete other entries in the event queue
//      corresponding to the same gate instance.]
//
//   Else If ... (Covered with procedural code.)
//
// End simulation (when while loop is done).


// :Example:
//
// Module illustrating timing and event queue.  The testbench (shown
// further below) sets a and b equal to 0 at t=0.

module timing(x,y,a,b);
   input a, b;
   output x,y;

   wire d, e;
   
   not #2 n1(d,a);
   not #3 n2(e,d);

   assign x = b ^ d ^ e;

   xor a1(y,b,d,e);

endmodule

 /// Event Queue for Example
//
// The comments below show the contents of the event queue as the
// module above is simulated with the testbench way below.  Some
// events generated by the testbench have not been shown.

 // Event Queue After Testbench Starts, t = 0
//
// Entry 2  timestamp = 8;  Resume testbench procedural code.
// Entry 1  timestamp = 0;  A: Set a <- 0
// Entry 0  timestamp = 0;  A: Set b <- 0

// Entry 0 removed.
// Change b from x to 0.
// Add affected items:

 // Event Queue at t = 0
//
// Entry 2  timestamp = 8;  Resume testbench procedural code.
// Entry 4  timestamp = 0;  B: Evaluate:   xor a1(y,b,d,e);
// Entry 3  timestamp = 0;  B: Evaluate:   assign x = b ^ d ^ e;
// Entry 1  timestamp = 0;  A: Set a <- 0

// Entry 1 removed.
// Change a from x to 0.
// Add affected items.

 // Event Queue at t = 0
//
// Entry 2  timestamp = 8;  Resume testbench procedural code. 
// Entry 5  timestamp = 0;  C: Evaluate:   not #2 n1(d,a);
// Entry 4  timestamp = 0;  C: Evaluate:   xor a1(y,b,d,e);
// Entry 3  timestamp = 0;  B: Evaluate:   assign x = b ^ d ^ e;

// Entry 3 removed.
// Compute b ^ d ^ e, result wire x does not change (was undefined, still is)

 // Event Queue at t = 0
//
// Entry 2  timestamp = 8;  Resume testbench procedural code. 
// Entry 5  timestamp = 0;  C: Evaluate:   not #2 n1(d,a);
// Entry 4  timestamp = 0;  C: Evaluate:   xor a1(y,b,d,e);

// Entry 4 removed
// Compute xor a1(y,b,d,e).  Output y does not change (was x, still is).

 // Event Queue at t = 0
//
// Entry 2  timestamp = 8;  Resume testbench procedural code. 
// Entry 5  timestamp = 0;  C: Evaluate:   not #2 n1(d,a);

// Entry 5 removed.
// Compute n1(d,a).  d is to change from x to 1.
// Insert change to d in event queue for 2 cycles later.

 // Event Queue at t = 0
//
// Entry 2  timestamp = 8;  Resume testbench procedural code. 
// Entry 6  timestamp = 2;  Set d <- 1

// Remove entry 6.
// Change time to t = 2.
// Set d to 1.
// Add items affected by d.

 // Event Queue at t = 2
//
// Entry 2  timestamp = 8;  Resume testbench procedural code. 
// Entry 9  timestamp = 2;  assign x = b ^ d ^ e;
// Entry 8  timestamp = 2;  xor a1(y,b,d,e);
// Entry 7  timestamp = 2;  not #3 n2(e,d);

// Remove entry 7.
// Compute n2(e,d).  e is to change from x to 0
// Insert change to e in event queue for 3 cycles later.

 // Event Queue at t = 2
//
// Entry 2  timestamp = 8;  Resume testbench procedural code. 
// Entry 10 timestamp = 5;  Set e <- 0
// Entry 9  timestamp = 2;  assign x = b ^ d ^ e;
// Entry 8  timestamp = 2;  xor a1(y,b,d,e);

// Remove entry 8.
// Compute xor(y,b,d,e)
// No change in y. (Was x, still is.)

 // Event Queue at t = 2
//
// Entry 2  timestamp = 8;  Resume testbench procedural code. 
// Entry 10 timestamp = 5;  Set e <- 0
// Entry 9  timestamp = 2;  assign x = b ^ d ^ e;

// Remove entry 9
// Compute b ^ d ^ e
// No change in x.

 // Event Queue at t = 2
//
// Entry 2  timestamp = 8;  Resume testbench procedural code. 
// Entry 10 timestamp = 5;  Set e <- 0

// Remove entry 10.
// Change time to t = 5
// Set e to 0
// Add affected items.

 // Event Queue at t = 5
//
// Entry 2  timestamp = 8;  Resume testbench procedural code. 
// Entry 12  timestamp = 5;  assign x = b ^ d ^ e;
// Entry 11  timestamp = 5;  xor a1(y,b,d,e);

// Remove entry 11.
// Evaluate xor(y,b,d,e)  y to change from x to 1.
// Add change to queue.

 // Event Queue at t = 5
//
// Entry 2  timestamp = 8;  Resume testbench procedural code. 
// Entry 13  timestamp = 5;  Set x <- 1
// Entry 12  timestamp = 5;  assign x = b ^ d ^ e;

// Remove entry 12.
// Evaluate b ^ d ^ e.  wire x to change from x to 1.
// Add change to queue.

 // Event Queue at t = 5
//
// Entry 2   timestamp = 8;  Resume testbench procedural code. 
// Entry 14  timestamp = 5;  Set y <- 1
// Entry 13  timestamp = 5;  Set x <- 1

// Remove entry 13.
// Set x to 1.
// Add affected items. (The affected item is in the testbench which isn't shown.)

 // Event Queue at t = 5
//
// Entry 2   timestamp = 8;  Resume testbench procedural code. 
// Entry 15  timestamp = 5;  Some procedural stuff.[always @( a or b or x or y )]
// Entry 14  timestamp = 5;  Set y <- 1

// Remove entry 14
// Set y to 1.
// Add affected items. (The affected item is already there, the always thing.)

 // Event Queue at t = 5
//
// Entry 2   timestamp = 8;  Resume testbench procedural code. 
// Entry 15  timestamp = 5;  Some procedural stuff.[always @( a or b or x or y )]

// Remove entry 15
// The procedural code prints a message.

 // Event Queue at t = 5
//
// Entry 2   timestamp = 8;  Resume testbench procedural code. 

// Remove entry 2 (finally).
// Change time to t = 8
// Continue running the procedural code until... something else
//  is put in the event queue.  More details will be provided when procedural
//  code covered.

// :Example:
//
// The testbench for the code above.  This module uses procedural
// code which has not been covered yet.  It can be ignored for now.

module demo_timing();

   reg a, b;
   wire x, y;
   
   timing everyones_timing_module_instance(x,y,a,b);

   integer i;

   always @( a or b or x or y )
     $display(" a,b = %d, %d   x,y= %d, %d",a,b,x,y);

   initial begin

      for(i=0; i<4; i=i+1) begin

         {a,b} = i[1:0];

         #8;

      end

   end

endmodule