/// LSU EE 3755 Computer Organization
//
/// Verilog Notes 5 Fall 2004
/// Contents
// Unsigned and Signged Adder
// Construction of ALUs
///
References
//
//
:P: Palnitkar, "Verilog HDL"
//
:Q: Qualis, "Verilog HDL Quick
Reference Card Revision 1.0"
//
:PH: Patterson & Hennessy,
"Computer Organization & Design"
////////////////////////////////////////////////////////////////////////////////
//
:Example:
//
//
An unsigned adder with an overflow output.
//
The overflow is the carry out. (Carry
//
out and overflow are not equivalent for signed adders.) In the
//
examples in this section the addition operator is used.
module
unsigned_adder(overflow,sum,a,b);
input [7:0] a, b;
output [7:0] sum;
output overflow;
assign {overflow,sum} = a + b;
endmodule
//
:Example:
//
//
A signed adder with an overflow output.
module
signed_adder(sum,overflow,a,b);
input [7:0] a, b;
output [7:0] sum;
output overflow;
assign sum = a + b;
wire
sa = a[7];
wire
sb = b[7];
wire
ssum = sum[7];
assign overflow = sa != sb ? 0 :
sb == ssum ? 0 : 1;
endmodule
//
:Example:
//
//
A signed adder in which the second input is half the size of
//
the first. The adder needs to
sign-extend the second input
//
before adding it.
module
signed_adder2(sum,overflow,a,b);
input [7:0] a;
input [3:0] b;
output [7:0] sum;
output overflow;
wire
sa = a[7];
wire
sb = b[3];
assign sum = a + { sb ? 4'b1 : 4'b0, b };
wire
ssum = sum[7];
assign overflow = sa != sb ? 0 :
sb == ssum ? 0 : 1;
endmodule
//
//
We covered this bfa_implicit at note 4.
//
We will use this at ALU below and 32bit ripple carry adder at the end.
module
bfa_implicit(sum,cout,a,b,cin);
input a,b,cin;
output sum,cout;
assign sum =
~a & ~b & cin |
~a & b & ~cin |
a & ~b & ~cin |
a & b & cin;
assign cout = a & b | b & cin | a
& cin;
endmodule
////////////////////////////////////////////////////////////////////////////////
///
Construction of ALUs
//
:PH: 4.5
//
/ALU/: The primary device in a computer for performing integer
//
arithmetic and logical operations.
[There may be other /functional
//
units/ that perform additional integer and also floating-point
//
operations.]
///
Goal: Design ALU that can share as much hardware as possible.
//
//
First ALU below does not share much hardware.
//
//
In the second ALU below adder is shared for addition, subtraction, and
// less than.
/// First ALU
//
//
Specifications
//
// Perform bitwise AND, bitwise OR, and addition.
//
// Two-bit input for operation, op.
//
// Operation encoding: and (0), or (1), add
(2)
//
Step 1:
//
Define a slice module that can perform any of the operations
//
(and, or, add) on two one-bit inputs and a carry input.
//
//
Step 2:
//
Connect the slices to construct the entire ALU.
//
:Example:
//
//
Slice for first alu. See :PH: Figure
4.14
module
alu_slice(result,cout,a,b,cin,op);
input a, b, cin;
input [1:0] op;
output
result, cout;
wire sum;
parameter
op_and = 0;
parameter
op_or = 1;
parameter
op_add = 2;
bfa_implicit bfa(sum,cout,a,b,cin);
assign result =
op == op_and ? a & b :
op == op_or ? a | b :
op == op_add ? sum :
0;
endmodule
//
:Example:
//
//
ALU using slice above. See :PH: Figure
4.15.
module
alu(result,a,b,cin,op);
input [31:0] a, b;
input cin;
input [1:0] op;
output [31:0] result;
wire [31:0] cout;
alu_slice
slice0(result[0],cout[0],a[0],b[0],cin,op);
alu_slice
slice1(result[1],cout[1],a[1],b[1],cout[0],op);
alu_slice
slice2(result[2],cout[2],a[2],b[2],cout[1],op);
alu_slice
slice3(result[3],cout[3],a[3],b[3],cout[2],op);
alu_slice slice4(result[4],cout[4],a[4],b[4],cout[3],op);
alu_slice
slice5(result[5],cout[5],a[5],b[5],cout[4],op);
alu_slice
slice6(result[6],cout[6],a[6],b[6],cout[5],op);
alu_slice
slice7(result[7],cout[7],a[7],b[7],cout[6],op);
alu_slice slice8(result[8],cout[8],a[8],b[8],cout[7],op);
alu_slice
slice9(result[9],cout[9],a[9],b[9],cout[8],op);
alu_slice
slice10(result[10],cout[10],a[10],b[10],cout[9],op);
alu_slice
slice11(result[11],cout[11],a[11],b[11],cout[10],op);
alu_slice slice12(result[12],cout[12],a[12],b[12],cout[11],op);
alu_slice
slice13(result[13],cout[13],a[13],b[13],cout[12],op);
alu_slice
slice14(result[14],cout[14],a[14],b[14],cout[13],op);
alu_slice
slice15(result[15],cout[15],a[15],b[15],cout[14],op);
alu_slice slice16(result[16],cout[16],a[16],b[16],cout[15],op);
alu_slice
slice17(result[17],cout[17],a[17],b[17],cout[16],op);
alu_slice
slice18(result[18],cout[18],a[18],b[18],cout[17],op);
alu_slice
slice19(result[19],cout[19],a[19],b[19],cout[18],op);
alu_slice
slice20(result[20],cout[20],a[20],b[20],cout[19],op);
alu_slice
slice21(result[21],cout[21],a[21],b[21],cout[20],op);
alu_slice
slice22(result[22],cout[22],a[22],b[22],cout[21],op);
alu_slice
slice23(result[23],cout[23],a[23],b[23],cout[22],op);
alu_slice
slice24(result[24],cout[24],a[24],b[24],cout[23],op);
alu_slice
slice25(result[25],cout[25],a[25],b[25],cout[24],op);
alu_slice
slice26(result[26],cout[26],a[26],b[26],cout[25],op);
alu_slice
slice27(result[27],cout[27],a[27],b[27],cout[26],op);
alu_slice
slice28(result[28],cout[28],a[28],b[28],cout[27],op);
alu_slice
slice29(result[29],cout[29],a[29],b[29],cout[28],op);
alu_slice slice30(result[30],cout[30],a[30],b[30],cout[29],op);
alu_slice
slice31(result[31],cout[31],a[31],b[31],cout[30],op);
endmodule
/// Second ALU
//
//
This ALU can perform additional operations: subtract and less than.
//
Both subtract and less than use the adder's hardware.
//
When it does subtraction operation, it uses add with inverted b and
// carry input of 1.
//
For set less than(slt)operation,if a < b Result = 0...001,
//
otherwise Result = 0...000.
//
:Example:
//
//
Slice for second ALU. See :PH: Figure
4.17. Input less is
//
generated by MSB slice which is alu_slice2MSB (set output of ALU31 of
//
PH: Figure 4.18 which is fed to less input of ALU0)
//
for ALU0 and 0 for all the others(ALU1 to ALU31).
module
alu_slice2(result,cout,a,b,cin,op,binvert,less);
input a, b, cin, binvert, less;
input [1:0] op;
output
result, cout;
parameter
sop_and = 0;
parameter
sop_or = 1;
parameter
sop_add = 2;
parameter
sop_slt = 3;
wire
b2 = binvert ? ~b : b;
wire
sum;
bfa_implicit bfa(sum,cout,a,b2,cin);
assign result =
op == sop_and ? a & b :
op == sop_or ? a | b :
op == sop_add ? sum :
less; // else, op == sop_slt
endmodule
//
:Example:
//
//
Bit slice for bit 31. This also
generates a set and overflow
//
output.
module
alu_slice2MSB(result,set,overflow,a,b,cin,op,binvert,less);
input a, b, cin, binvert, less;
output set, overflow;
input [1:0] op;
output
result;
parameter
sop_and = 0;
parameter
sop_or = 1;
parameter
sop_add = 2;
parameter
sop_slt = 3;
wire
b2 = binvert ? ~b : b;
wire
sum;
assign overflow =
op != sop_add ? 1'b0 :
a != b2 ? 1'b0 :
a == sum ? 1'b0 : 1'b1;
assign set = a == b ? sum : a;
//set is sign bit.
//we assume signed numbers.
//bit 31 is sign bit.
// A, B are 32 bit numbers and a, b are
sign bits of those numbers.
//
//
sign bits
// a
b set
// 0
0 sum //do subtraction, A -
B and check
//for the sign bit.
//if A < B then
sign bit of(A-B) is negative(1).
// 0
1 a //don't set.
//because A is
positive number,
// B is negative
number( A > B).
// 1
0 a //set.
// because A is
negative number ,
//B is positive
number(A < B).
// 1
1 sum //do subtraction, A -
B and
//check for the sign
bit.
//if A < B then
sign bit of(A-B) is negative(1).
// if A < B then the sign bit of(A-B)
//is
negative(1).
//
sum which is bit31 is the sign bit.
//
so check for the sum bit.
// case of same sign bits
// using ~b because we
are doing A-B.
// a b
~b carryln sum A < B ?
// 0 0
1 0 1 A
< B so set.
// 0 0
1 1 0
// 1 1
0 0 1 A
< B so set.
// 1 1
0 1 0
bfa_implicit bfa(sum,cout,a,b2,cin);
//
we are using b2, because sometimes we need subtraction operation
//
(set_less_than or subtraction).
assign result =
op == sop_and ? a & b :
op == sop_or ? a | b :
op == sop_add ? sum :
less; // else, op == sop_slt
endmodule
//
:Example:
//
//
Second ALU. The same module is used for
bits 0-30, bit 31
//
is computed by a special module(alu_slice2MSB)
//
that also determines overflow
//
and whether a < b.
module
alu2(result,overflow,a,b,alu_op);
input [31:0] a, b;
input [2:0] alu_op;
output [31:0] result;
output overflow;
wire [31:0] cout;
parameter op_and = 0;
parameter op_or = 1;
parameter op_slt = 2;
parameter op_add = 3;
parameter op_sub = 4;
parameter sop_and = 0;
parameter sop_or = 1;
parameter sop_add = 2;
parameter sop_slt = 3;
wire [1:0] op =
alu_op == op_and ? sop_and :
alu_op == op_or ? sop_or
:
alu_op == op_slt ? sop_slt :
alu_op == op_add ? sop_add :
alu_op == op_sub ? sop_add : 0;
wire
binvert = alu_op == op_sub || alu_op == op_slt;
wire
set; // MSB of sum.
// using binvert for cin of the LSB slice.
// when we do subtract or slt, the binvert
is set to 1.
alu_slice2
slice0(result[0],cout[0],a[0],b[0],binvert,op,binvert,set);
alu_slice2
slice1(result[1],cout[1],a[1],b[1],cout[0],op,binvert,1'b0);
alu_slice2 slice2(result[2],cout[2],a[2],b[2],cout[1],op,binvert,1'b0);
alu_slice2
slice3(result[3],cout[3],a[3],b[3],cout[2],op,binvert,1'b0);
alu_slice2
slice4(result[4],cout[4],a[4],b[4],cout[3],op,binvert,1'b0);
alu_slice2
slice5(result[5],cout[5],a[5],b[5],cout[4],op,binvert,1'b0);
alu_slice2 slice6(result[6],cout[6],a[6],b[6],cout[5],op,binvert,1'b0);
alu_slice2
slice7(result[7],cout[7],a[7],b[7],cout[6],op,binvert,1'b0);
alu_slice2
slice8(result[8],cout[8],a[8],b[8],cout[7],op,binvert,1'b0);
alu_slice2
slice9(result[9],cout[9],a[9],b[9],cout[8],op,binvert,1'b0);
alu_slice2
slice10(result[10],cout[10],a[10],b[10],cout[9],op,binvert,1'b0);
alu_slice2
slice11(result[11],cout[11],a[11],b[11],cout[10],op,binvert,1'b0);
alu_slice2
slice12(result[12],cout[12],a[12],b[12],cout[11],op,binvert,1'b0);
alu_slice2
slice13(result[13],cout[13],a[13],b[13],cout[12],op,binvert,1'b0);
alu_slice2
slice14(result[14],cout[14],a[14],b[14],cout[13],op,binvert,1'b0);
alu_slice2
slice15(result[15],cout[15],a[15],b[15],cout[14],op,binvert,1'b0);
alu_slice2
slice16(result[16],cout[16],a[16],b[16],cout[15],op,binvert,1'b0);
alu_slice2
slice17(result[17],cout[17],a[17],b[17],cout[16],op,binvert,1'b0);
alu_slice2 slice18(result[18],cout[18],a[18],b[18],cout[17],op,binvert,1'b0);
alu_slice2
slice19(result[19],cout[19],a[19],b[19],cout[18],op,binvert,1'b0);
alu_slice2
slice20(result[20],cout[20],a[20],b[20],cout[19],op,binvert,1'b0);
alu_slice2 slice21(result[21],cout[21],a[21],b[21],cout[20],op,binvert,1'b0);
alu_slice2
slice22(result[22],cout[22],a[22],b[22],cout[21],op,binvert,1'b0);
alu_slice2
slice23(result[23],cout[23],a[23],b[23],cout[22],op,binvert,1'b0);
alu_slice2
slice24(result[24],cout[24],a[24],b[24],cout[23],op,binvert,1'b0);
alu_slice2
slice25(result[25],cout[25],a[25],b[25],cout[24],op,binvert,1'b0);
alu_slice2
slice26(result[26],cout[26],a[26],b[26],cout[25],op,binvert,1'b0);
alu_slice2
slice27(result[27],cout[27],a[27],b[27],cout[26],op,binvert,1'b0);
alu_slice2
slice28(result[28],cout[28],a[28],b[28],cout[27],op,binvert,1'b0);
alu_slice2
slice29(result[29],cout[29],a[29],b[29],cout[28],op,binvert,1'b0);
alu_slice2
slice30(result[30],cout[30],a[30],b[30],cout[29],op,binvert,1'b0);
alu_slice2MSB
slice31(result[31],set,overflow,a[31],b[31],cout[30],op,binvert, 1'b0);
endmodule
//
//
Testbench for second ALU. Material for
this testbench not covered.
module
test_alu();
wire [31:0] result;
wire
overflow;
reg [31:0]
a, b;
reg [2:0]
alu_op;
alu2 alu(result,overflow,a,b,alu_op);
integer
i, shadow_result, shadow_overflow, as, bs;
initial begin
alu_op = alu.op_sub;
for(i=0; i<10000; i=i+1) begin
as = $random;
a = as;
bs = $random;
b = bs;
alu_op = ( $random & 32'h7fffffff
) % 5;
case( alu_op )
alu.op_and:
begin
shadow_result = as & bs;
shadow_overflow = 0;
end
alu.op_or:
begin
shadow_result = as | bs;
shadow_overflow = 0;
end
alu.op_add:
begin
shadow_result = as + bs;
shadow_overflow = as > 0
&& bs > 0 && shadow_result < 0
|| as < 0
&& bs < 0 && shadow_result > 0;
end
alu.op_sub:
begin
shadow_result = as - bs;
shadow_overflow = as > 0
&& bs < 0 && shadow_result < 0
|| as < 0
&& bs > 0 && shadow_result > 0;
end
alu.op_slt:
begin
shadow_result = as < bs;
shadow_overflow = 0;
end
endcase
#1;
if( shadow_result != result ) begin
$display("Wrong result op
%d, %d op %d = %d != %d",
alu_op, a, b,
shadow_result, result);
$stop;
end
if( shadow_overflow != overflow )
begin
$display("Wrong overflow op
%d, %x op %x; %d != %d",
alu_op, a, b,
shadow_overflow, overflow);
$stop;
end
end
$display("Done with test.");
end
endmodule