//////////////////////////////////////////////////////////////////////////////// /// /// Solution to LSU EE 4702-1 Spring 2001 Homework 5 /// // Assignment: http://www.ee.lsu.edu/v/2001/hw05.pdf //////////////////////////////////////////////////////////////////////////////// // The log_2 of the number of numbers stored by the bsearch module. // Keep this small to limit synthesis time. `define SIZELG 4 `define SIZE (1<<`SIZELG) // The number of numbers stored by bsearch. `define SIZERANGE `SIZELG-1:0 `define ELEMBITS 8 // The number of bits in each number stored. `define ELEMRANGE `ELEMBITS-1:0 `define MAXELEM (1<<`ELEMBITS) //////////////////////////////////////////////////////////////////////////////// // // Original bsearch module. // // Not part of the solution, here for comparison to the other modules. // This module is synthesizable (despite misleading macro names). The // synthesized hardware does the entire lookup in one cycle, which // requires alot of hardware. // Number of gates : 5365 // clk : 50.7 MHz // Critical path: num_2_ -> result[1], 19.18 ns `define xNOT_SYN `ifdef NOT_SYN module bsearch(result,din,op,reset,clk); input din, op, reset, clk; output result; wire [7:0] din; wire [2:0] op; reg [2:0] result; `include "bsearch_names.v" reg [7:0] dtable [0:`SIZE-1]; reg [`SIZELG:0] num; reg [`SIZERANGE] current, try, delta; reg [`ELEMRANGE] trydata; reg match; // Bug workaround. Needed to avoid a synthesis bug. wire [`ELEMRANGE] bug_workaround = dtable[1]; always @( posedge clk ) if( reset ) begin num = 0; result = re_r_idle; end else begin case( op ) op_nop:; op_reset: begin num = 0; result = re_r_idle; end op_insert: if( num == `SIZE ) begin result = re_i_full; end else if( num > 0 && dtable[num-1] >= din ) begin result = re_i_misordered; end else begin dtable[num] = din; num = num + 1; result = re_i_inserted; end op_find: begin match = 0; current = 0; delta = 1 << ( `SIZELG - 1 ); begin:BLOOP forever begin try = current | delta; if( try < num ) begin trydata = dtable[try]; match = trydata == din; if( match ) disable BLOOP; if( trydata < din ) current = try; end if( !delta ) disable BLOOP; delta = delta >> 1; end end result = match ? re_f_present : re_f_absent; end endcase end endmodule `endif //////////////////////////////////////////////////////////////////////////////// // // Problem 1: Form 2 bsearch Module // // Synthesizable Form 2. // // // Clock Frequency (MHz): 113.5 MHz // Area (number of gates): 4275 // Worst-case time to find a number: 6 / 113.5 MHz = 52.9 ns // `define xFORM2 `ifdef FORM2 module bsearch(result,din,op,reset,clk); input din, op, reset, clk; output result; wire [7:0] din; wire [2:0] op; reg [2:0] result; `include "bsearch_names.v" reg looping; reg [7:0] dtable [0:`SIZE-1]; reg [`SIZELG:0] num; reg [`SIZERANGE] current, try, delta; reg [`ELEMRANGE] trydata; reg match; wire [`ELEMRANGE] bug_workaround = dtable[12]; always @( posedge clk ) if( reset ) begin looping = 0; num = 0; result = re_r_idle; end else if( looping ) begin try = current + delta; if( try < num ) begin trydata = dtable[try]; match = trydata == din; if( match ) looping = 0; if( trydata < din ) current = try; end if( !delta ) looping = 0; delta = delta >> 1; if( !looping ) result = match ? re_f_present : re_f_absent; end else begin case( op ) op_nop:; op_reset: begin num = 0; result = re_r_idle; end op_insert: if( num == `SIZE ) begin result = re_i_full; end else if( num > 0 && dtable[num-1] >= din ) begin result = re_i_misordered; end else begin dtable[num] = din; num = num + 1; result = re_i_inserted; end op_find: begin match = 0; current = 0; delta = 1 << ( `SIZELG - 1 ); result = re_busy; looping = 1; end endcase end endmodule `endif //////////////////////////////////////////////////////////////////////////////// // // Problem 2: Form 3 bsearch Module // // Synthesizable Form 3. // Module does one dtable lookup per cycle. // // Clock Frequency (MHz): 109.1 MHz // Area (number of gates): 4155 // Worst-case time to find a number: 5 / 109.1 MHz = 45.8 ns // // Critical path: reg_delta(1)/XQ to result[1], 8.47 ns `define xFORM3 `ifdef FORM3 module bsearch(result,din,op,reset,clk); input din, op, reset, clk; output result; wire [7:0] din; wire [2:0] op; reg [2:0] result; `include "bsearch_names.v" reg [7:0] dtable [0:`SIZE-1]; reg [`SIZELG:0] num; reg [`SIZERANGE] current, try, delta; reg [`ELEMRANGE] trydata; reg match; always @( posedge clk ) if( reset ) begin num = 0; result = re_r_idle; end else begin case( op ) op_nop:; op_reset: begin num = 0; result = re_r_idle; end op_insert: if( num == `SIZE ) begin result = re_i_full; end else if( num > 0 && dtable[num-1] >= din ) begin result = re_i_misordered; end else begin dtable[num] = din; num = num + 1; result = re_i_inserted; end op_find: begin match = 0; current = 0; delta = 1 << ( `SIZELG - 1 ); result = re_busy; begin:BLOOP forever begin @( posedge clk ); try = current + delta; if( try < num ) begin trydata = dtable[try]; // This would split the delta -> result path between two // cycles, but it would take nearly twice as long to find // a result. // @( posedge clk ); match = trydata == din; if( match ) disable BLOOP; if( trydata < din ) current = try; end if( !delta ) disable BLOOP; delta = delta >> 1; end end result = match ? re_f_present : re_f_absent; end endcase end endmodule `endif //////////////////////////////////////////////////////////////////////////////// // // Problem 3: Form 3 bsearch Module, Speed Enhanced // // Synthesizable, Form 3. // Module does two dtable lookups per cycle. // // Several solutions within module, area, time, and performance in comments // next to code. // Clock Frequency (MHz): // Area (number of gates): // Worst-case time to find a number: // `define FORM3_FAST `ifdef FORM3_FAST module bsearch(result,din,op,reset,clk); input din, op, reset, clk; output result; wire [7:0] din; wire [2:0] op; reg [2:0] result; `include "bsearch_names.v" reg [7:0] dtable [0:`SIZE-1]; reg [`SIZELG:0] num; reg [`SIZERANGE] current, try, delta; reg [`SIZERANGE] try0, try1, delta2; reg [`ELEMRANGE] trydata, trydata0, trydata1; reg match, match0, match1, m; always @( posedge clk ) if( reset ) begin num = 0; result = re_r_idle; end else begin case( op ) op_nop:; op_reset: begin num = 0; result = re_r_idle; end op_insert: if( num == `SIZE ) begin result = re_i_full; end else if( num > 0 && dtable[num-1] >= din ) begin result = re_i_misordered; end else begin dtable[num] = din; num = num + 1; result = re_i_inserted; end op_find: begin current = 0; delta = 1 << ( `SIZELG - 1 ); result = re_busy; `define ALWAYS `ifdef ALWAYS // Two iterations per clock cycle, dtable lookups done simultaneously. // Code below clk : 3 / 97.8 MHz = 30.7 ns // Number of gates : 7513 delta2 = delta >> 1; begin:BLOOP forever begin @( posedge clk ); try = current + delta; try0 = current + delta2; try1 = try + delta2; trydata = dtable[try]; trydata0 = dtable[try0]; trydata1 = dtable[try1]; match = trydata == din; match0 = trydata0 == din; match1 = trydata1 == din; if( try < num ) begin if( match ) begin m = 1; disable BLOOP; end if( trydata > din ) begin if( match0 ) begin m = 1; disable BLOOP; end if( trydata0 < din ) current = try0; end else if( try1 < num ) begin if( match1 ) begin m = 1; disable BLOOP; end if( trydata1 < din ) current = try1; else current = try; end else current = try; end else if( try0 < num ) begin begin if( match0 ) begin m = 1; disable BLOOP; end if( trydata0 < din ) current = try0; end end if( !delta ) begin m = 0; disable BLOOP; end delta = delta >> 2; delta2 = delta2 >> 2; end end `endif `ifdef NEVER // Completely unrolled, all five iterations in one cycle. // Code below clk : 1/ 55.5 MHz = 18.0 ns // Number of gates : 5482 match = 0; repeat ( `SIZELG + 1 ) begin try = current + delta; if( !match && try < num ) begin trydata = dtable[try]; match = trydata == din; if( trydata < din ) current = try; end delta = delta >> 1; end m = match; `endif `ifdef NEVER // Original Code // Code below: clk : 5/ 109.1 MHz = 46.2 ns // Number of gates : 4155 match = 0; begin:BLOOP forever begin @( posedge clk ); try = current + delta; if( try < num ) begin trydata = dtable[try]; match = trydata == din; if( match ) disable BLOOP; if( trydata < din ) current = try; end if( !delta ) disable BLOOP; delta = delta >> 1; end end m = match; `endif `ifdef NEVER // Two iterations per cycle. // Iterations are sequential. (Second dtable lookup after first.) // clk : 3 / 63.7 MHz = 47.1 ns // Number of gates : 6465 match = 0; begin:BLOOP forever begin @( posedge clk ); repeat( 2 ) begin try = current + delta; if( !match && try < num ) begin trydata = dtable[try]; match = trydata == din; if( trydata < din ) current = try; end delta2 = delta; delta = delta >> 1; end if( match ) disable BLOOP; if( !delta2 ) disable BLOOP; end end m = match; `endif result = m ? re_f_present : re_f_absent; end endcase end endmodule `endif //////////////////////////////////////////////////////////////////////////////// // // Testbench // // Testbench module is named testbsearch. // The testbench can be copied into this file or another one and // modified. The testbench might be updated before the homework // is due though. `include "/home/classes/ee4702/files/v/hw05tb.v"