//////////////////////////////////////////////////////////////////////////////// /// /// Template for LSU EE 4702-1 Spring 2001 Homework 5 /// /// Name: /// Instructions: // // Copy this to a file named hw05sol.v to directory ~/hw in your // class account. (~ is your home directory.) Use this // file for your solution. Your entire solution should be in // this file. // // In addition to modifying the Verilog code, be sure to include // answers in the spaces provided. (See the assignment and the // comments next to each problem below.) // // Do not rename the modules in this file and be sure to use the // directory and filename given above. // // Do not move or rename the 'ifdef statements, they will be used // by the TA-bot to locate your solutions. However the 'defines // can be moved around. The TA-bot does not care how the 'defines // are set. // 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) //////////////////////////////////////////////////////////////////////////////// // // Non-synthesizable bsearch module. // // There is no need to modify this. It's here for comparison to // the synthesizable modules to be written. // `define NOT_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 "/home/classes/ee4702/files/v/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 // // Modify so that it is synthesizable and in Form 2. // // Answer questions below: (Do not change non-blank text.) // // Clock Frequency (MHz): // Area (number of gates): // Worst-case time to find a number: // `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 "/home/classes/ee4702/files/v/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 2: Form 3 bsearch Module // // Modify so that it is synthesizable and in Form 3. // Module should do at most one dtable lookup per cycle. // Identify and shorten a critical path, if necessary. // // Answer questions below: (Do not change non-blank text.) // // Clock Frequency (MHz): // Area (number of gates): // Worst-case time to find a number: // `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 "/home/classes/ee4702/files/v/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 3: Form 3 bsearch Module, Speed Enhanced // // Modify so that it is synthesizable and in Form 3. // Module must do less than `SIZE dtable lookups per cycle, // see problem for more information. // // Answer questions below: (Do not change non-blank text.) // // Clock Frequency (MHz): // Area (number of gates): // Worst-case time to find a number: // `define xFORM3_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 "/home/classes/ee4702/files/v/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 //////////////////////////////////////////////////////////////////////////////// // // 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"