OpenCores
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 
    /integer_square_root
    from Rev 6 to Rev 7
    ↔ Reverse comparison
  •

Rev 6 → Rev 7

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

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.