URL
https://opencores.org/ocsvn/integer_square_root/integer_square_root/trunk
Subversion Repositories integer_square_root
Compare Revisions
- This comparison shows the changes necessary to convert path
/
- from Rev 6 to Rev 7
- ↔ Reverse comparison
Rev 6 → Rev 7
/integer_square_root/tags/v2.0/src/ISR.sv
0,0 → 1,156
`timescale 1ns / 1ps |
////////////////////////////////////////////////////////////////////////////////// |
// Company: |
// Engineer: Yihua Liu |
// |
// Create Date: 2022/06/08 16:50:36 |
// Design Name: |
// Module Name: ISR |
// Project Name: lab_3_b |
// Target Devices: xczu7eg-ffvf1517-2-i |
// Tool Versions: |
// Description: |
// |
// Dependencies: |
// |
// Revision: |
// Revision 0.01 - File Created |
// Additional Comments: |
// |
////////////////////////////////////////////////////////////////////////////////// |
|
|
typedef enum logic [3:0] { |
INIT, |
GUESS, |
MULT_LOAD, |
MULT_WAIT, |
COMPARE, |
CHANGE, |
CHECK, |
INCRE, |
ENDLOOP, |
DONE |
} state; |
|
module ISR_FSM( |
input reset, |
input [63:0] value, |
input clock, |
input mult_done, |
input [63:0] mult_result, |
output logic mult_start, |
output logic mult_reset, |
output logic [63:0] mult_input, |
output logic [31:0] result, |
output logic done |
); |
|
logic [63:0] value_reg; |
logic [31:0] result_next, guess, guess_next; |
integer i, i_next; |
|
state current_state, next_state; |
|
assign mult_input = {32'b0, guess}; |
assign mult_start = current_state == MULT_LOAD | current_state == MULT_WAIT; |
assign done = current_state == DONE; |
assign mult_reset = current_state == INIT | current_state == COMPARE; |
|
|
always_comb begin |
guess_next = guess; |
i_next = i; |
result_next = result; |
case (current_state) |
INIT: begin |
guess_next = 32'h0000_0000; |
i_next = 31; |
result_next = 0; |
next_state = GUESS; |
end |
GUESS: begin |
guess_next = guess + (32'h0000_0001 << i); |
next_state = MULT_LOAD; |
end |
MULT_LOAD: next_state = MULT_WAIT; |
MULT_WAIT: next_state = (mult_done) ? COMPARE : MULT_WAIT; |
COMPARE: next_state = (mult_result > value_reg) ? CHANGE : CHECK; |
CHANGE: begin |
guess_next = guess - (32'h0000_0001 << i); |
next_state = CHECK; |
end |
CHECK: next_state = i ? INCRE : ENDLOOP; |
INCRE: begin |
i_next = i - 1; |
next_state = GUESS; |
end |
ENDLOOP: begin |
result_next = guess; |
next_state = DONE; |
end |
DONE: next_state = DONE; |
default: next_state = INIT; |
endcase |
end |
|
always_ff @(posedge clock) begin |
if (reset) begin |
current_state <= INIT; |
value_reg <= value; |
result <= 32'b0; |
i <= 31; |
guess <= 32'h0000_0000; |
end |
else begin |
current_state <= next_state; |
value_reg <= value_reg; |
result <= result_next; |
i <= i_next; |
guess <= guess_next; |
end |
end |
|
endmodule |
|
|
|
module ISR( |
input reset, |
input [63:0] value, |
input clock, |
output logic [31:0] result, |
output logic done |
); |
logic mult_start; |
logic mult_done; |
logic [63:0] mult_result; |
logic [63:0] mult_input; |
logic mult_reset; |
|
|
mult multiplier( |
.clock(clock), |
.reset(mult_reset), |
.mcand(mult_input), |
.mplier(mult_input), |
.start(mult_start), |
.product(mult_result), |
.done(mult_done) |
); |
|
ISR_FSM FSM( |
.reset(reset), |
.value(value), |
.clock(clock), |
.mult_done(mult_done), |
.mult_result(mult_result), |
.mult_start(mult_start), |
.mult_reset(mult_reset), |
.mult_input(mult_input), |
.result(result), |
.done(done) |
); |
|
|
endmodule |
/integer_square_root/tags/v2.0/src/mult_stage.sv
0,0 → 1,68
`timescale 1ns / 100ps |
////////////////////////////////////////////////////////////////////////////////// |
// Company: |
// Engineer: Yihua Liu |
// |
// Create Date: 2022/06/06 12:58:15 |
// Design Name: |
// Module Name: mult_stage |
// Project Name: lab_3_a |
// Target Devices: xczu7eg-ffvf1517-2-i |
// Tool Versions: |
// Description: |
// |
// Dependencies: |
// |
// Revision: |
// Revision 0.01 - File Created |
// Additional Comments: |
// |
////////////////////////////////////////////////////////////////////////////////// |
|
|
// This is one stage of an 8 stage (9 depending on how you look at it) |
// pipelined multiplier that multiplies 2 64-bit integers and returns |
// the low 64 bits of the result. This is not an ideal multiplier but |
// is sufficient to allow a faster clock period than straight * |
module mult_stage( |
input clock, reset, start, |
input [63:0] product_in, mplier_in, mcand_in, |
|
output logic done, |
output logic [63:0] product_out, mplier_out, mcand_out |
); |
|
// This parameter is used to change the number of stages. |
// For example, if N_STAGE = 8, we are using an 8-stage pipelined multiplier. |
parameter N_STAGE = 8; |
|
logic [63:0] prod_in_reg, partial_prod_reg; |
logic [63:0] partial_product, next_mplier, next_mcand; |
|
assign product_out = prod_in_reg + partial_prod_reg; |
|
assign partial_product = mplier_in[64/N_STAGE-1:0] * mcand_in; |
|
// assign next_mplier = {{(64/N_STAGE){1'b0}},mplier_in[63:64/N_STAGE]}; |
// assign next_mcand = {mcand_in[64-64/N_STAGE-1:0],{(64/N_STAGE){1'b0}}}; |
assign next_mplier = mplier_in >> 64/N_STAGE; |
assign next_mcand = mcand_in << 64/N_STAGE; |
|
//synopsys sync_set_reset "reset" |
always_ff @(posedge clock) begin |
prod_in_reg <= #1 product_in; |
partial_prod_reg <= #1 partial_product; |
mplier_out <= #1 next_mplier; |
mcand_out <= #1 next_mcand; |
end |
|
// synopsys sync_set_reset "reset" |
always_ff @(posedge clock) begin |
if(reset) |
done <= #1 1'b0; |
else |
done <= #1 start; |
end |
|
endmodule |
|
/integer_square_root/tags/v2.0/src/pipe_mult.sv
0,0 → 1,57
`timescale 1ns / 100ps |
////////////////////////////////////////////////////////////////////////////////// |
// Company: |
// Engineer: Yihua Liu |
// |
// Create Date: 2022/06/06 13:54:21 |
// Design Name: |
// Module Name: mult |
// Project Name: lab_3_a |
// Target Devices: xczu7eg-ffvf1517-2-i |
// Tool Versions: |
// Description: |
// |
// Dependencies: |
// |
// Revision: |
// Revision 0.01 - File Created |
// Additional Comments: |
// |
////////////////////////////////////////////////////////////////////////////////// |
|
|
// This is an 8 stage (9 depending on how you look at it) pipelined |
// multiplier that multiplies 2 64-bit integers and returns the low 64 bits |
// of the result. This is not an ideal multiplier but is sufficient to |
// allow a faster clock period than straight * |
// This module instantiates 8 pipeline stages as an array of submodules. |
module mult( |
input clock, reset, |
input [63:0] mcand, mplier, |
input start, |
|
output [63:0] product, |
output done |
); |
|
// This parameter is used to change the number of stages. |
// For example, if N_STAGE = 8, we are using an 8-stage pipelined multiplier. |
parameter N_STAGE = 8; |
logic [63:0] mcand_out, mplier_out; |
logic [(N_STAGE-1)*64-1:0] internal_products, internal_mcands, internal_mpliers; |
logic [N_STAGE-2:0] internal_dones; |
|
mult_stage #(.N_STAGE(N_STAGE)) mstage [N_STAGE-1:0] ( |
.clock(clock), |
.reset(reset), |
.product_in({internal_products,64'h0}), |
.mplier_in({internal_mpliers,mplier}), |
.mcand_in({internal_mcands,mcand}), |
.start({internal_dones,start}), |
.product_out({product,internal_products}), |
.mplier_out({mplier_out,internal_mpliers}), |
.mcand_out({mcand_out,internal_mcands}), |
.done({done,internal_dones}) |
); |
|
endmodule |
/integer_square_root/tags/v2.0/src/test_ISR.sv
0,0 → 1,139
`timescale 1ns / 1ps |
////////////////////////////////////////////////////////////////////////////////// |
// Company: |
// Engineer: Yihua Liu |
// |
// Create Date: 2022/10/14 01:01:28 |
// Design Name: |
// Module Name: testbench |
// Project Name: lab_3_b |
// Target Devices: xczu7eg-ffvf1517-2-i |
// Tool Versions: |
// Description: |
// |
// Dependencies: |
// |
// Revision: |
// Revision 0.01 - File Created |
// Revision 0.02 - Update Testbench |
// Additional Comments: |
// |
////////////////////////////////////////////////////////////////////////////////// |
|
|
module testbench(); |
|
logic [63:0] test_input; |
logic clock, reset, quit; |
|
logic [31:0] result; |
logic done; |
|
integer i; |
|
ISR UUT( |
.reset(reset), |
.value(test_input), |
.clock(clock), |
.result(result), |
.done(done) |
); |
|
task compare_correct_result; |
input [63:0] value; |
input [31:0] result; |
|
logic [31:0] guess; |
logic [63:0] multi; |
begin |
// First, calculate the correct result |
guess = 32'h8000_0000; |
for (i = 0; i <= 31; i = i + 1) begin |
guess[31 - i] = 1'b1; |
multi = {32'b0, guess}; |
if ((multi * multi) > value) begin |
guess[31 - i] = 1'b0; |
end |
end |
// Then, compare the result with the correct one |
if (result == guess) begin |
end |
else begin |
$display("@@@Failed"); |
$display("Incorrect at time %4.0f",$time); |
$display("corrent_result = %h result = %h", guess, result); |
$finish; |
end |
end |
endtask |
|
|
always begin |
#250; |
clock = ~clock; |
end |
|
// Some users have had problems just using "@(posedge done)" because their |
// "done" signals glitch (even though they are the output of a register). This |
// prevents that by making sure "done" is high at the clock edge. |
task wait_until_done; |
forever begin : wait_loop |
@(posedge done); |
@(negedge clock); |
if (done) disable wait_until_done; |
end |
endtask |
|
|
initial begin |
$dumpvars; |
$monitor("Time:%4.0f done:%b input:%h result:%h ",$time, done, test_input, result); |
reset = 0; |
clock = 0; |
|
// First some special cases |
test_input = 64'h0000_0000_0000_03E9; |
@(negedge clock); |
reset = 1; |
@(negedge clock); |
reset = 0; |
wait_until_done(); |
$display("Calculate done!"); |
compare_correct_result(test_input, result); |
@(negedge clock); |
reset = 1; |
test_input = 64'hFFFF_FFFF_FFFF_FFFF; |
@(negedge clock); |
reset = 0; |
wait_until_done(); |
compare_correct_result(test_input, result); |
@(negedge clock); |
reset = 1; |
test_input = 64'h0000_0000_0000_0000; |
@(negedge clock); |
reset = 0; |
wait_until_done(); |
compare_correct_result(test_input, result); |
|
// Then some random tests |
@(negedge clock); |
reset = 1; |
@(negedge clock); |
quit = 0; |
quit <= #100000 1; |
while (~quit) begin |
reset = 1; |
test_input = {$random, $random}; |
@(negedge clock); |
reset = 0; |
wait_until_done(); |
compare_correct_result(test_input, result); |
end |
@(negedge clock); |
reset = 1; |
@(negedge clock); |
$display("@@@Passed"); |
$finish; |
end |
|
endmodule |
/integer_square_root/tags/v2.0/README.md
0,0 → 1,48
# Integer Square Root |
|
## Algorithm |
|
``` |
procedure ISR(value) |
for i<-31 to 0 do |
proposed_solution[i]<-1 |
if proposed_solution^2 > value then |
proposed_solution[i]<-0 |
end if |
end for |
end procedure |
``` |
|
## Specification |
|
- If reset is asserted during a rising clock edge (synchronous reset), the value signal is to be stored. |
- If reset is asserted part way through a computation, the result of that computation is discarded and a new value is latched into the module. |
- When the module has finished computing the answer, the output is placed on the result line and done line is raised on the same cycle. |
- It must not take more than 600 clock cycles to compute a result (from the last |
clock that reset is asserted to the first clock that done is asserted.) |
|
## ISR State Machine |
|
Computing: $\sqrt{\mathtt{value}}$ |
|
- On a reset |
- guess initialized to `32'h8000_0000` |
- `value` is clocked into a register |
|
- guess gets the next bit set each time we cycle through the FSM again |
|
- Square `guess` (multiply it with itself) |
|
- Wait until the multiplier raises its done |
|
- if `guess` <= `value` |
|
- Keep the current bit |
|
- else |
|
- Clear the current bit |
|
- Move to the next bit |
|
- After the last bit, raise `done` |