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