Arithmetic for Computers 1
CS 154: Computer Architecture Lecture #8
Winter 2020
Ziad Matni, Ph.D.
Dept. of Computer Science, UCSB
Administrative
• Lab 4 underway…
• Syllabus (Schedule Section) has been updated
2/3/2020 Matni, CS154, Wi20 2
Midterm Exam (Wed. 2/12)
What’s on It?
• Everything we’ve covered in lecture from start to Monday, 2/10
What Else?
• Closed book – some notes (details to follow)
• Random seat assignments – come to class EARLY!
2/3/2020 Matni, CS154, Wi20 3
Lecture Outline
• MIPS Instructions: Arrays vs. Pointers
• Arithmetic
• Addition / Subtraction
• Multiplication / Division
2/3/2020 Matni, CS154, Wi20 4
Arrays vs. Pointers
• Array indexing involves
• Multiplying index by element size • Adding to array base address
• Pointers correspond directly to memory addresses • Can avoid indexing complexity
2/3/2020 Matni, CS154, Wi20 5
Example: Clearing an Array (the classic way)
2/3/2020 Matni, CS154, Wi20 6
Example: Clearing an Array (using a pointer)
2/3/2020 Matni, CS154, Wi20 7
Comparison of the Two…
• Version on the left must have the “multiply” and add inside the loop
• Memory pointer version on the right increments the pointer p directly.
• Moves the scaling shift and the array bound addition outside the loop
• It reduces instructions executed per iteration from 6 to 4.
• This is how a lot of compilers optimize code like this.
2/3/2020 Matni, CS154, Wi20 8
Arithmetic Overview 1
• Addition / subtraction
• Carry out vs. Overflow – remember the difference!
Examples in 8-bit adders:
• 0x24 + 0xB0 • 0x7F + 0x66 • 0x15 + 0xFB • 0x87 + 0xAA
2/3/2020
Matni, CS154, Wi20 9
0xD4, C = 0, V = 0 0xE5, C = 0, V = 1 0x10, C = 1, V = 0 0x31, C = 1, V = 1
Dealing with Overflow in C/C++
• Some languages (e.g., C/C++, Java) ignore overflow • What happens when you do:
0x87000000 + 0xAA000000 in C++? (i.e. –2,030,043,136 + –1,442,840,576?)
• You get 822,083,584… discuss… • In MIPS, you’d use
addu, addui, subu instructions to not trigger overflow (this is what a C/C++ compiler would issue)
• Why?
• Checking for overflow for every calculation can be demanding on CPU run time
2/3/2020
Matni, CS154, Wi20 10
Dealing with Overflow in Other Languages
• Other languages (e.g., Ada, Fortran – older ones) require raising an exception
• In MIPS, you’d use MIPS add, addi, sub instructions
• What actually happens?
• On overflow, an “exception handler” is invoked
• PC is saved in exception program counter (EPC) register
• Jump executed to predefined handler address
• mfc0 (move from coprocessor reg) instruction can retrieve EPC value, to return after corrective action
2/3/2020
Matni, CS154, Wi20 11
Arithmetic Overview 2
• Multiplication
• Left bit shifting by N bitsMultiplying by 2N • Using mult / multu and mflo (or mfhi)
• Division
• Right bit shifting by N bitsInteger divide by 2N
• Using div / divu (again, with mflo or mfhi) • No checking for overflow or divide-by-zero
• Raises questions about floating point… • Will be coming up…
2/3/2020
Matni, CS154, Wi20 12
Multiplication in Computers:
The Algorithm using a Decimal Example
• Let P be the partial product,
M be the multiplicand,
and N be the multiplier • i.e. P eventually will be = M * N
Initially, P is 0 Loop:
If N is 0, then P = the result, exit Loop
Else, P += (the rightmost digit of N) times M Shift N right once, and M left once
Repeat Loop
2/3/2020
Matni, CS154, Wi20 13
Example with Decimals
803 * 151 (which we expect to be 121,253)
P
M
N
0
803
151
803 8030 15
803*1
40953 80300 1
803+8030*5
121253 803000 0
40953+80300*1
1. N is not 0
2. P += (rightmost digit of N[1]) * M[803] Shift N right once, M left once
N is not 0
3. P += (rightmost digit of N[5]) * M[8030] Shift N right once, M left once
N is not 0
4. P += (rightmost digit of N[1]) * M[80300] Shift N right once, M left once
N IS 0 ; END
2/3/2020
Matni, CS154, Wi20 14
Example with Decimals
803 * 151 (which we expect to be 121,253)
P
M
N
0
803
151
803
8030
15
40953
80300
1
121253
803000
0
1. N is not 0
2. P += (rightmost digit of N[1]) * M[803] Shift N right once, M left once
N is not 0
3. P += (rightmost digit of N[5]) * M[8030] Shift N right once, M left once
N is not 0
4. P += (rightmost digit of N[1]) * M[80300] Shift N right once, M left once
N IS 0 ; END
2/3/2020
Matni, CS154, Wi20 15
Multiplication in Computers:
The Algorithm using a Binary Example
• …Even easier than the decimal example: Shown here for 32 bits
Initially, P is 0 Loop 32 times:
IfNbit0 =1,thenP+=M
Shift N right once, and M left once
2/3/2020
Matni, CS154, Wi20 16
Simple Example using 8 bits
M = 0x04 = 0000 0100 (multiplicand) N = 0x05 = 0000 0101 (multiplier)
•P=0
•N0 =1P+=0x04=0x04, N=00000010, M=00001000 • N0 = 0P = 0x04 (unchanged), N = 0000 0001, M = 0001 0000 •N0 =1P+=0x10=0x14, N=00000000, M=00100000 • Exit with P = 0x14 (correct answer, since 0x14 = 20)
2/3/2020 Matni, CS154, Wi20 17
Multiplication Hardware
2/3/2020 Matni, CS154, Wi20 18
Can be further optimized with added HW
Optimization of HW for Multiplication
• You can perform some steps in parallel: add/shift
• One cycle per partial-product addition is ok to do, if frequency of multiplications in program is low
2/3/2020
Matni, CS154, Wi20 19
Division in Computers: The Algorithm
• Dividend (N) ÷ Divisor (D)= Quotient, Remainder
2/3/2020
Matni, CS154, Wi20 20
Initially, R = N Loop 32 times:
R = R– D
If R ≥ 0, then
shift Q to left 1 bit
set LSB to 1 (that is, Q | 1)
Else
shift Q to left 1 bit Shift D 1 bit to right,
R=R+D
Division Hardware
2/3/2020 Matni, CS154, Wi20 21
Optimization of HW for Division
• One cycle per partial-remainder subtraction
• Looks a lot like a multiplier!
• In fact, we can use the same hardware for both…
2/3/2020 Matni, CS154, Wi20 22
Floating Point
• Representation for non-integral numbers
• Including very small and very large numbers
• Usually follows some ”normalized” form of scientific notation • Example: –2.34 x 106 (ok) vs. –234 x 104 (not ok)
• In binary, the form is: ± 1.xxxxxxx(base 2) x 2yyyy • Types float and double in C/C++
• More in next lecture…
2/3/2020 Matni, CS154, Wi20
23
YOUR TO-DOs for the Week
• Readings! •Work on Lab 4!
2/3/2020 Matni, CS154, Wi20 24
2/3/2020 Matni, CS154, Wi20 25