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