/// LSU EE 4755 -- Fall 2014 -- DD Using HDLs // /// Maxrun Sample Code // Time-stamp: <15 September 2014, 19:02:05 CDT, koppel@sky.ece.lsu.edu> // This file contains Verilog code describing hardware to find the // maximum number of consecutive 1's (the maximum run) in a binary // vector. The hardware is combinational. /// Versions // /// maxrun16_top / maxrun16 / maxrun4 / maxrun1 // // The simplest (arguably) synthesizable versions of the module. The // vector size is 16. // // The maximum run is found via a linear chain of 16 maxrun1 // modules. This approach, though simple to understand, results in // hardware that more costly and slower than necessary. // // /// maxrunn // // This describes the same hardware as maxrun16_top, however // any size vector can be used. // // This module shows how to use generate statements with a loop. // // Also slow and costly. // // /// maxrunrec_top / maxrunrec / maxrunrec_a // // Compute the maximum run use a tree-arrangement of modules. The // maxrunrec module is recursive: each module with in input vector // of 2 or more bits instantiates two smaller ones. // // This module (actually maxrunrec_a) demonstrates how to use // generate statements to control recursion. // // Performance is much better because of an O(lg N) critical path // and cost is O( N ), where N is the vector length. // // /// max_run_behav // // A non-synthesizable behavioral maximum run module. // // The purpose is to compute the maximum run in a simple way // and use that to check the other modules. // // Synthesizablity will be covered in future lectures. ////////////////////////////////////////////////////////////////////////////// /// Linear Maxrun Code, Fixed Sizes /// /// One-Bit // module maxrun1(maxrun,outrun,v,maxrunin,inrun); input wire v; input wire [4:0] inrun; // Abbreviation: IR input wire [4:0] maxrunin; // Abbreviation: MIR output wire [4:0] maxrun, outrun; // Abbreviation: MR, OR assign outrun = v ? inrun + 1 : 0; assign maxrun = outrun > maxrunin ? outrun : maxrunin; endmodule /// Four Bits // module maxrun4(maxrun,outrun,vector,maxrunin,inrun); input wire [3:0] vector; input wire [4:0] inrun; input wire [4:0] maxrunin; output wire [4:0] maxrun, outrun; wire logic [4:0] mr1, mr2, mr3, mr4, or1, or2, or3, or4; maxrun1 mrm1( mr1, or1, vector[3], maxrunin, inrun); maxrun1 mrm2( mr2, or2, vector[2], mr1, or1); maxrun1 mrm3( mr3, or3, vector[1], mr2, or2); maxrun1 mrm4( maxrun, outrun, vector[0], mr3, or3); endmodule /// Sixteen Bits /// module maxrun16(maxrun,outrun,vector,maxrunin,inrun); input [15:0] vector; input [4:0] inrun; input [4:0] maxrunin; output [4:0] maxrun, outrun; wire logic [4:0] mxrun[3:1], iorun[3:1]; maxrun4 m1( mxrun[1], iorun[1], vector[15:12], maxrunin, inrun ); maxrun4 m2( mxrun[2], iorun[2], vector[11:8], mxrun[1], iorun[1] ); maxrun4 m3( mxrun[3], iorun[3], vector[7:4], mxrun[2], iorun[2] ); maxrun4 m4( maxrun, outrun, vector[3:0], mxrun[3], iorun[3] ); endmodule /// Sixteen Bits, Without Extra Ports // module maxrun16_top(maxrun,vector); input [15:0] vector; output [4:0] maxrun; logic [4:0] outrun; maxrun16 m1(maxrun, outrun, vector, 5'b0, 5'b0); endmodule ////////////////////////////////////////////////////////////////////////////// /// Linear Maxrun, Parameter Determines Size module maxrunn #( int width = 16, bits = 5 ) ( output logic [bits-1:0] mr_len, input logic [width-1:0] vector ); logic [bits:1] iorun [width:-1]; logic [bits:1] mxrun [width:-1]; assign iorun[-1] = 0; assign mxrun[-1] = 0; generate for ( genvar i=0; i<width; i++ ) maxrun1 mrm1( mxrun[i], iorun[i], vector[i], mxrun[i-1], iorun[i-1] ); endgenerate assign mr_len = mxrun[width-1]; endmodule ////////////////////////////////////////////////////////////////////////////// /// Recursive Maxrun - Live `define max(a,b) ((a)>=(b)?a:b) `define max3(a,b,c) `max(`max(a,b),c) module maxrunrec_live #( int width = 16, bits = 5 ) ( output logic [bits-1:0] left, center, right, output logic full, input logic [width-1:0] vector ); localparam int nwidth = width/2; localparam int nbits = bits-1; generate if ( width == 1 ) begin assign left = vector[0]; assign center = vector[0]; assign right = vector[0]; end else begin maxrunrec_live #( nwidth, nbits ) mr_left (lleft, lcenter, lright, lfull, vector[width-1:nwidth] ); assign left = lleft; maxrunrec_live #( nwidth, nbits ) mr_right (rleft, rcenter, rright, rfull, vector[nwidth-1:0] ); assign right = rright; wire [bits-1:0] mid = lright + rleft; assign center = `max3( lcenter, mid, rcenter ); end endgenerate endmodule ////////////////////////////////////////////////////////////////////////////// /// Recursive Maxrun // `define max(a,b) ((a)>=(b)?a:b) // `define max3(a,b,c) `max(`max(a,b),c) module maxrunrec #( int width = 16, bits = 5 ) ( output logic [bits-1:0] left, center, right, output logic full, input logic [width-1:0] vector ); localparam int nwidth = width >> 1; localparam int nbits = bits - 1; wire logic [nbits-1:0] lleft, lcenter, lright; wire logic [nbits-1:0] rleft, rcenter, rright; wire logic lf, rf; maxrunrec_a #( nwidth, nbits ) mleft ( lleft, lcenter, lright, lf, vector[width-1:nwidth] ); maxrunrec_a #( nwidth, nbits ) mright ( rleft, rcenter, rright, rf, vector[nwidth-1:0] ); always @* begin logic [bits-1:0] mid; mid = lright + rleft; center = `max3( lcenter, mid, rcenter ); full = lf && rf; left = lf ? mid : lleft; right = rf ? mid : rright; end endmodule module maxrunrec_a #( int width = 16, bits = 5 ) ( output logic [bits-1:0] left, center, right, output logic full, input logic [width-1:0] vector ); generate if ( width == 1 ) always @* begin left = vector[0]; center = vector[0]; right = vector[0]; full = vector[0]; end else maxrunrec #( width, bits ) ml( left, center, right, full, vector ); endgenerate endmodule module maxrunrectop #( int vlen = 16, bits = 5 ) ( output logic [bits-1:0] mr_len, input logic [vlen-1:0] vector ); wire logic [bits-1:0] left, center, right; wire logic f; maxrunrec #(vlen,bits) mr(left,center,right,f,vector); assign mr_len = `max3( left, center, right ); endmodule ////////////////////////////////////////////////////////////////////////////// /// Behavioral Maxrun // cadence translate_off module max_run_behav #( int vlen = 16, bits = 5 ) ( output logic [bits-1:0] mr_len, input logic [vlen-1:0] vector ); always @* begin automatic int mr_len_so_far = 0; for ( int pos = 0; pos < vlen; ) begin automatic int pos_start = pos; int run_size; // Advance until a 0 is found. // while ( vector[pos] == 1 && pos < vlen ) pos++; // Note how many 1's were skipped (the run size). // run_size = pos - pos_start; if ( run_size > mr_len_so_far ) mr_len_so_far = run_size; // Advance until a 1 is found. // while ( vector[pos] == 0 && pos < vlen ) pos++; end mr_len = mr_len_so_far; end endmodule ////////////////////////////////////////////////////////////////////////////// /// Testbench module testmr(); localparam int bits = 5; localparam int vect_len = 1 << bits - 1; logic [vect_len-1:0] vector; wire logic [bits-1:0] maxrun[3]; max_run_behav #(vect_len,bits) mr_b(maxrun[0],vector); // maxrun16_top mr(maxrun[1],vector); maxrunn #(vect_len,bits) mrl(maxrun[2],vector); maxrunrectop #(vect_len,bits) mrt(maxrun[1],vector); initial begin automatic int numtests = 5000; automatic int errcount = 0; automatic int done_that[int]; vector = 0; for ( int i=0; i<numtests; i++ ) begin // Foolish use of an associative array. do vector = $random; while ( !done_that[vector]++ ); #1; if ( maxrun[0] !== maxrun[1] ) begin errcount++; if ( errcount < 10 ) $display ("Test %d, wrong value for input %b %d != %d (correct)\n", i, vector, maxrun[1],maxrun[0]); end end $display("Testbench finished %d tests, %d errors found.\n", numtests, errcount); end endmodule // cadence translate_on /// module maxrunn // // Instance Cells Cell Area Net Area Total Area Wireload // ------------------------------------------------------------------------- // maxrunn 499 50740 0 50740 <none> (D) // mr_len[0] out port +0 17314 F /// module maxrunrectop // // Instance Cells Cell Area Net Area Total Area Wireload // ------------------------------------------------------------------------- // maxrunrectop 370 42136 0 42136 <none> (D) // mr_len[0] out port +0 9106 F