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)
Whats on It?
Everything weve 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, youd 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, youd 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
1212538030000
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
Reviews
There are no reviews yet.