//////////////////////////////////////////////////////////////////////////////// // /// LSU EE 4755 Fall 2016 Homework 4 // /// Assignment http://www.ece.lsu.edu/koppel/v/2016/hw04.pdf /// Instructions: // // (1) Find the undergraduate workstation laboratory, room 126 EE // Building. // // (2) Locate your account. If you did not get an account please // E-mail: koppel@ece.lsu.edu // // (3) Log in to a Linux workstation. // // (4) If you haven't already, follow the account setup instructions here: // http://www.ece.lsu.edu/koppel/v/proc.html // // (5) Copy this assignment, local path name // /home/faculty/koppel/pub/ee4755/hw/2016/hw04 // to a directory ~/hw04 in your class account. (~ is your home // directory.) Use this file for your solution. // // (6) Find the problems in this file and solve them. // // Your entire solution should be in this file. // // Do not change module names. // // (7) Your solution will automatically be copied from your account by // the TA-bot. /// Additional Resources // // Verilog Documentation // The Verilog Standard // http://standards.ieee.org/getieee/1800/download/1800-2012.pdf // Introductory Treatment (Warning: Does not include SystemVerilog) // Brown & Vranesic, Fundamentals of Digital Logic with Verilog, 3rd Ed. // // Account Setup and Emacs (Text Editor) Instructions // http://www.ece.lsu.edu/koppel/v/proc.html // To learn Emacs look for Emacs tutorial. `default_nettype none ////////////////////////////////////////////////////////////////////////////// /// Problem 0 // // Look over but don't modify this module. module lookup_behav #( int charsz = 8, int nelts = 15, int idx_sz = $clog2(nelts) ) ( output logic found, output logic [idx_sz-1:0] index, input uwire [charsz-1:0] char, input uwire [charsz-1:0] chars[nelts] ); always_comb begin found = 0; index = 0; for ( int i=0; i<nelts; i++ ) if ( chars[i] == char ) begin index = i; found = 1; end end endmodule ////////////////////////////////////////////////////////////////////////////// /// Problem 1 // /// Complete lookup_linear so that it does the lookup using instantiated lookup_elt. // // [ ] The code must be synthesizable. // [ ] The code must synthesize to combinational logic. (No latches.) // [ ] Make sure that the testbench does not report errors. // [ ] Can use behavioral or implicit structural code. // [ ] Do not rename modules or change ports. module lookup_elt #( int charsz = 4 ) ( output logic match, input uwire [charsz-1:0] char_lookup, input uwire [charsz-1:0] char_elt); /// Don't modify this module. always_comb match = char_lookup == char_elt; endmodule module lookup_linear #( int charsz = 8, int nelts = 15, int idx_sz = $clog2(nelts) ) ( output logic found, output logic [idx_sz-1:0] index, input uwire [charsz-1:0] char, input uwire [charsz-1:0] chars[nelts-1:0] ); /// Solution goes here. endmodule ////////////////////////////////////////////////////////////////////////////// /// Problem 2 // /// Complete lookup_tree so that it does the lookup using recursive /// instantiations of itself. // // [ ] The code must be synthesizable. // [ ] The code must synthesize to combinational logic. (No latches.) // [ ] Make sure that the testbench does not report errors. // [ ] Can use behavioral or implicit structural code. // [ ] Do not rename modules or change ports. module lookup_tree #( int charsz = 8, int nelts = 15, int idx_sz = $clog2(nelts) ) ( output uwire found, output uwire [idx_sz-1:0] index, input uwire [charsz-1:0] char, input uwire [charsz-1:0] chars[nelts] ); /// Solution goes here. endmodule ////////////////////////////////////////////////////////////////////////////// /// Testbench Code // // The code below instantiates some of the modules above, // provides test inputs, and verifies the outputs. // // The testbench may be modified to facilitate your solution. Of // course, the removal of tests which your module fails is not a // method of fixing a broken module. (One might modify the testbench // so that the first tests it performs are thoe which make it easier // to determine what the problem is, for example, test inputs that // are all 0's or all 1's.) // cadence translate_off function automatic int min( int a, int b ); min = a <= b ? a : b; endfunction module testbench(); localparam int nelts[] = { 4, 5, 10, 15, 16, 30, 40, 64 }; localparam int nnelts = 8; logic start_done[-1:nnelts]; for ( genvar i = 0; i < nnelts; i++ ) testbench_sz #(nelts[i]) aa(start_done[i],start_done[i-1]); initial begin if ( nnelts != nelts.size() ) begin $write("Value of nnelts, %0d, different than number of elts in nelts, %0d. (See module testbench.\n", nnelts, nelts.size()); $fatal(1); end start_done[-1] = 1; end endmodule module testbench_sz #( int nelts = 100 ) ( output logic done, input uwire start ); localparam int telts = nelts * 2; localparam int idx_sz = $clog2(nelts); localparam int charsz = 8; localparam int charmk = ( 1 << charsz ) - 1; localparam int num_tests = min(nelts,500); localparam int stride = nelts/num_tests; localparam int nmuts = 3; logic [charsz-1:0] char, chars[telts-1:0]; uwire found[nmuts]; uwire [idx_sz-1:0] idx[nmuts]; logic shadow_found; logic [idx_sz-1:0] shadow_idx; lookup_behav #(charsz,nelts) l00(found[0],idx[0],char,chars[nelts-1:0]); lookup_linear #(charsz,nelts) l01(found[1],idx[1],char,chars[nelts-1:0]); lookup_tree #(charsz,nelts) l02(found[2],idx[2],char,chars[nelts-1:0]); string mutnames[] = { "lookup_behav", "lookup_linear", "lookup_tree" }; int err[nmuts]; initial begin automatic int tot_errors = 0; localparam int gap = charmk / telts; chars[0] = {$random} % gap; for ( int i=1; i<telts; i++ ) chars[i] = chars[i-1] + 1 + {$random} % gap; for ( int i=0; i<telts; i++ ) begin automatic int idx = {$random} % telts; {chars[i],chars[idx]} = {chars[idx],chars[i]}; end wait ( start == 1 ); for ( int i=0; i<num_tests; i++ ) begin automatic int idx_try = {$random} % telts; char = chars[idx_try]; shadow_found = idx_try < nelts; shadow_idx = idx_try; #1; for ( int mut=0; mut<3; mut++ ) begin automatic int cr_fnd = shadow_found === found[mut]; automatic int cr_idx = shadow_idx === idx[mut]; if ( cr_fnd && ( shadow_found == 0 || cr_idx ) ) continue; if ( err[mut] > 100 ) break; $write("Mod %s nelts %0d test %3d char %h: wrong %s. Found %h%s%h (correct) idx %4d %s %4d (correct)\n", mutnames[mut], nelts, i, char, cr_idx ? "found" : "index", found[mut], cr_fnd ? "==" : "!=", shadow_found, idx[mut], cr_fnd ? "!=" : "??", shadow_idx); err[mut]++; end end for ( int i=0; i<num_tests; i++ ) tot_errors += err[i]; $write("For nelts %0d performed %0d tests, %0d errors found.\n", nelts, num_tests, tot_errors); done = 1; end endmodule // cadence translate_on