Transcript Chapter 4: Computer Arithmetic

Chapter 4: Arithmetic for
Computers
(Part 1)
CS 447
Jason Bakos
1
Notes on Project 1
• There are two different ways the following two words can
be stored in a computer memory…
– word1
– word2
•
00
01
0000
02
03
0001
Another way is little-endian, where the word is stored in
memory in reverse order…
– word1:
– word2:
•
0,1,2,3
0,1
One way is big-endian, where the word is stored in
memory in its original order…
– word1:
– word2:
•
.byte
.half
03
0001
02
01
00
0000
Of course, this affects the way in which the lw
instruction works…
2
Notes on Project 1
• MIPS uses the endian-style that the
architecture underneath it uses
– Intel uses little-endian, so we need to deal with
that
– This affects assignment 1 because the input
data is stored as a series of bytes
– If you use lw’s on your data set, the values will
be loaded into your dest. register in reverse
order
– Hint: Try the lb/sb instruction
• This instruction will load/store a byte from an
unaligned address and perform the translation for
you
3
Notes on Project 1
• Hint: Use SPIM’s breakpoint and singlestep features to help debug your program
– Also, make sure you use the registers and
memory/stack displays
• Hint: You may want to temporarily store
your input set into a word array for sorting
• Make sure you check Appendix A for
additional useful instructions that I didn’t
cover in class
• Make sure you comment your code!
4
Goals of Chapter 4
• Data representation
• Hardware mechanisms for
performing arithmetic on data
• Hardware implications on the
instruction set design
5
Review of Binary
Representation
•
•
•
•
Binary/Hex -> Decimal conversion
Decimal -> Binary/Hex conversion
Least/Most significant bits
Highest representable number/maximum
number of unique representable symbols
• Two’s compliment representation
– One’s compliment
– Finding signed number ranges (-2n-1 to 2n-1-1)
– Doing arithmetic with two’s compliment
• Sign extending with load half/byte
– Unsigned loads
• Signed/unsigned comparison
6
Binary Addition/Subtraction
• Binary subtraction works exactly
like addition, except the second
operand is converted to two’s
compliment
• Overflow in signed arithmetic occurs
under the following conditions:
Operation
Operand A
Operand B
Result
A+B
Positive
Positive
Negative
A+B
Negative
Negative
Positive
A-B
Positive
Negative
Negative
A-B
Negative
Positive
Positive
7
What Happens When
Overflow Occurs?
• MIPS detects overflow with an
exception/interrupt
• When an interrupt occurs, a branch occurs
to code in the kernel at address 80000080
where special registers (BadVAddr, Status,
Cause, and EPC) are used to handle the
interrupt
• SPIM has a simple interrupt handler built-in
that deals with interrupts
• We may come back to interrupts later
8
Review of Shift and Logical
Operations
• MIPS has operations for SLL, SRL, and SRA
– We covered this in the last chapter
• MIPS implements bit-wise AND, OR, and
XOR logical operations
– These operations perform a bit-by-bit parallel
logical operation on two registers
– In C, use << and >> for arithmetic shifts, and &, |,
^, and ~ for bitwise and, or, xor, and NOT,
respectively
9
Review of Logic Operations
• The three main parts of a CPU
– ALU (Arithmetic and Logic Unit)
• Performs all logical, arithmetic, and shift
operations
– CU (Control Unit)
• Controls the CPU – performs load/store,
branch, and instruction fetch
– Registers
• Physical storage locations for data
10
Review of Logic Operations
• In this chapter, our goal is to learn how the
ALU is implemented
• The ALU is entirely constructed using
boolean functions as hardware building
blocks
– The 3 basic digital logic building blocks can be
used to construct any digital logic system: AND,
OR, and NOT
– These functions can be directly implemented
using electric circuits (wires and transistors)
11
Review of Logic Operations
• These “combinational” logic devices
can be assembled to create a much
more complex digital logic system
A
B
A AND B
A
B
A OR B
A
not A
0
0
0
0
0
0
0
1
0
1
0
0
1
1
1
0
1
0
0
1
0
1
1
1
1
1
1
1
12
Review of Logic Operations
• We need another device to build an ALU…
A
B
D
C (out)
0
0
0
0 (a)
0
0
1
0 (b)
0
1
0
0 (a)
0
1
1
1 (b)
1
0
0
1 (a)
1
0
1
0 (b)
1
1
0
1 (a)
1
1
1
1 (b)
• This is called a multiplexor… it
implements an if-then-else in hardware
13
A 1-bit ALU
• Perform logic operations in parellel
and mux the output
• Next, we want to include addition, so
let’s build a single-bit adder
– Called a full adder
14
Full Adder
•
From the following table, we can construct the circuit for a full adder and
link multiple full adders together to form a multi-bit adder
– We can also add this input to our ALU
– How do we give subtraction ability to our adder?
– How do we detect overflow and zero results?
Inputs
Outputs
Comments
A
B
CarryIn
CarryOut
Sum
0
0
0
0
0
0+0+0=00
0
0
1
0
1
0+0+1=01
0
1
0
0
1
0+1+0=1
0
1
1
1
0
0+1+1=10
1
0
0
0
1
1+0+0=01
1
0
1
1
0
1+0+1=10
1
1
0
1
0
1+1+0=10
1
1
1
1
1
1+1+1=11
15