////////////////////////////////////////////////////////////////////////////////
///
/// 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"