PostAddsense


Chapter 3 : Arithmetic for Computers Computer Organization


Figures



FIGURE 3.4  The first multiplication algorithm, using the hardware shown in Figure 3.3.
If the least significant bit of the multiplier is 1, add the multiplicand to the product. If not, go to the next step. Shift the multiplicand left and the multiplier right in the next two steps. These three steps are repeated 32 times.




FIGURE 3.5  Refined version of the multiplication hardware.
Compare with the first version in Figure 3.3. The Multiplicand register, ALU, and Multiplier register are all 32 bits wide, with only the Product register left at 64 bits. Now the product is shifted right. The separate Multiplier register also disappeared. The multiplier is placed instead in the right half of the Product register. These changes are highlighted in color. (The Product register should really be 65 bits to hold the carry out of the adder, but it’s shown here as 64 bits to highlight the evolution from Figure 3.3.)




FIGURE 3.6  Multiply example using algorithm in Figure 3.4.
The bit examined to determine the next step is circled in color.




FIGURE 3.7  Fast multiplication hardware.
Rather than use a single 32-bit adder 31 times, this hardware “unrolls the loop” to use 31 adders and then organizes them to minimize delay.


FIGURE 3.8  First version of the division hardware.
The Divisor register, ALU, and Remainder register are all 64 bits wide, with only the Quotient register being 32 bits. The 32-bit divisor starts in the left half of the Divisor register and is shifted right 1 bit each iteration. The remainder is initialized with the dividend. Control decides when to shift the Divisor and Quotient registers and when to write the new value into the Remainder register.


FIGURE 3.10  Division example using the algorithm in Figure 3.9.
The bit examined to determine the next step is circled in color.


FIGURE 3.11  An improved version of the division hardware.
The Divisor register, ALU, and Quotient register are all 32 bits wide, with only the Remainder register left at 64 bits. Compared to Figure 3.8, the ALU and Divisor registers are halved and the remainder is shifted left. This version also combines the Quotient register with the right half of the Remainder register. (As in Figure 3.5, the Remainder register should really be 65 bits to make sure the carry out of the adder is not lost.)








Exercises


Never give in, never give in, never, never, never—in nothing, great or small, large or petty—never give in.

Winston Churchill, address at Harrow School, 1941


3.1. [5] <§3.2> What is 5ED4–07A4 when these values represent unsigned 16-bit hexadecimal numbers? The result should be written in hexadecimal. Show your work.

5ED4 0101 1110 1101 0100
- 07A4 - 0000 0111 1010 0100
5730 0101 0111 0011 0000





3.2. [5] <§3.2> What is 5ED4–07A4 when these values represent signed 16-bit hexadecimal numbers stored in sign-magnitude format? The result should be written in hexadecimal. Show your work.

5ED4 0101 1110 1101 0100
- 07A4 + 1111 1000 0101 1100
5730 0101 0111 0011 0000





3.3. [10] <§3.2> Convert 5ED4 into a binary number. What makes base 16 (hexadecimal) an attractive numbering system for representing values in computers?

5ED4 => 0101 1110 1101 0100

Hex is a very useful numerical system.  It is the primary representation of memory addresses in computers as modern computers operate at a base of 16, my computer, for example, is 64 bit, so 16*4.  This makes representation accurate and easy.  In addition it allows large numbers to be displayed in less digits, for example, Hex Dword(32 bits) is written as FFFFFFFF, just 8 digits, but in decimal is represented as 4294967295, 10 digits.





3.4. [5] <§3.2> What is 4365–3412 when these values represent unsigned 12-bit octal numbers? The result should be written in octal. Show your work.

4365 100 011 110 101
- 3412 - 011 100 001 010
0753 000 111 101 011





3.5. [5] <§3.2> What is 4365–3412 when these values represent signed 12-bit octal numbers stored in sign-magnitude format? The result should be written in octal. Show your work.

4365 100 011 110 101
- 3412 + 100 011 110 110
0753 000 111 101 011





3.6. [5] <§3.2> Assume 185 and 122 are unsigned 8-bit decimal integers. Calculate 185–122. Is there overflow, underflow, or neither?

185 1011 1001
- 122 - 0111 1010
063 0011 1111

Since unsigned 8-bit integers range is 0~255, they are all in range.





3.7. [5] <§3.2> Assume 185 and 122 are signed 8-bit decimal integers stored in sign-magnitude format. Calculate 185+122. Is there overflow, underflow, or neither?

185 1011 1001 (-71)
+ 122 + 0111 1010
051 0011 0011

Since signed 8-bit integers range is -128~127, they are all in range.





3.8. [5] <§3.2> Assume 185 and 122 are signed 8-bit decimal integers stored in sign-magnitude format. Calculate 185–122. Is there overflow, underflow, or neither?

185 1011 1001 (-71)
- 122 + 1000 0110
- 193

Since signed 8-bit integers range is -128~127, there is underflow.





3.9. [10] <§3.2> Assume 151 and 214 are signed 8-bit decimal integers stored in two’s complement format. Calculate 151+214 using saturating arithmetic. The result should be written in decimal. Show your work.


151 0110 1001 (105)
+ 214 + 0010 1010 (42)
127 0111 1111

Since signed 8-bit integers range is -128~127, the result using saturating arithmetic is 127, not 365.





3.10. [10] <§3.2> Assume 151 and 214 are signed 8-bit decimal integers stored in two’s complement format. Calculate 151–214 using saturating arithmetic. The result should be written in decimal. Show your work.

151 0110 1001 (105)
- 214 - 0010 1010 (42)
063 0011 1111

Since signed 8-bit integers range is -128~127, the result using saturating arithmetic is 63.





3.11. [10] <§3.2> Assume 151 and 214 are unsigned 8-bit integers. Calculate 151+214 using saturating arithmetic. The result should be written in decimal. Show your work.

151 1001 0111
+ 214 + 1101 0110
255 1111 1111

Since unsigned 8-bit integers range is 0 ~ 255, 
the result using saturating arithmetic is 255.





3.12. [20] <§3.3> Using a table similar to that shown in Figure 3.7, calculate the product of the octal unsigned 6-bit integers 62 and 12 using the hardware described in Figure 3.4. You should show the contents of each register on each step.






062 000 110 010
* 012 * 000 001 010
764 111 110 100





3.13. [20] <§3.3> Using a table similar to that shown in Figure 3.6, calculate the product of the hexadecimal unsigned 8-bit integers 62 and 12 using the hardware described in Figure 3.5. You should show the contents of each register on each step.

062 0000 0110 0010
* 012 * 0000 0001 0010
6E4 0110 1110 0100

IterationStepMultiplier
(lower 32bits)
MultiplicandProduct
(upper 32bits)
0initial values0001 00100000 0110 00100000 0000 | 0000 0000
11: 0 ⇒ No operation
2: Shift left Multiplicand
3: Shift right Product
0001 0010
0001 0010
0000 1001
0000 0110 0010
0000 1100 0100
0000 1100 0100
0000 0000 | 0000 0000
0000 0000 | 0000 0000
0000 0000 | 0000 0000
21a: 1 ⇒ Prod = Prod+Mcand
2: Shift left Multiplicand
3: Shift right Product
0000 1001
0000 1001
0000 0100
0000 1100 0100
0001 1000 1000
0001 1000 1000
0110 0010 | 0000 0000
0110 0010 | 0000 0000
0011 0001 | 0000 0000
3
1: 0 ⇒ No operation
2: Shift left Multiplicand
3: Shift right Product
0000 0100
0000 0100
0000 0010
0001 1000 1000
0011 0001 0000
0011 0001 0000
0011 0001 | 0000 0000
0011 0001 | 0000 0000
0001 1000 | 1000 0000
4
1: 0 ⇒ No operation
2: Shift left Multiplicand
3: Shift right Product
0000 0010
0000 0001
0000 0001
0011 0001 0000
0110 0010 0000
0110 0010 0000
0001 1000 | 1000 0000
0001 1000 | 1000 0000
0000 1100 | 010
0000
51a: 1 ⇒ Prod = Prod+Mcand
2: Shift left Multiplicand
3: Shift right Product
0000 0001
0000 0001
0000 0000
0110 0010 0000
1100 0100 0000
1100 0100 0000
0110 1110 | 0100 0000
0110 1110 | 0100 0000
0011 0111 | 0010 0000
// | is half of 64bits at the "product" header. thus, it is a position of 32-bit.
// the iteration should be executed to 32nd to calculate the product.








3.14. [10] <§3.3> Calculate the time necessary to perform a multiply using the approach given in Figures 3.4 and 3.5 if an integer is 8 bits wide and each step of the operation takes 4 time units. Assume that in step 1a an addition is always performed—either the multiplicand will be added, or a zero will be. Also assume that the registers have already been initialized (you are just counting how long it takes to do the multiplication loop itself). If this is being done in hardware, the shifts of the multiplicand and multiplier can be done simultaneously. If this is being done in software, they will have to be done one after the other. Solve for each case.

Given a bit width of 8, we know that the multiplicand and multiplier registers will need to be shifted that many times. The process would look similar to the tables simulating multiplication from the previous question.
i.e. one iteration would look like this -

(hardware implementation)
1a - 1 --> Product = product + multiplicand
2 - shift multiplicand left + multiplier right

(software implementation)
1a - 1 --> Product = product + multiplicand
2 - shift multiplicand left
3 - shift multiplier right

and we would need to iterate once for every bit, so 8 times. So for the hardware implementation, 64 time units(8 iterations * 2 operations per iteration * 4tu per operation) would be required.

the software implementation would take 94 time units(8 iterations * 3 operations per iteration * 4tu per operation) would be required.





3.15. [10] <§3.3> Calculate the time necessary to perform a multiply using the approach described in the text (31 adders stacked vertically) if an integer is 8 bits wide and an adder takes 4 time units.

With stacked adders, section 3.3 explains each takes as input, "the multiplicand ANDed with a multiplier bit, and the other is the output of a prior adder." Each bit of the multiplier register is checked before the multiplication so the hardware will know whether the multiplicand is to be added or not at each step. With this approach, the intermediate steps are skipped and we only need to wait on the add times for each bit

our total time would be 32 time units(8 adds * 4tu per instruction)





3.16. [20] <§3.3> Calculate the time necessary to perform a multiply using the approach given in Figure 3.7 if an integer is 8 bits wide and an adder takes 4 time units.

This approach unrolls the loop that 32 adders(or 8 in our case) in a stack, and instead runs them in parallel. Instead of each adder only being used 1/32 of the time, we get much higher utilization, and we only have to wait for a number of operations equal to the log of the total number of adders log(32) = 5. or in the case of a bit width of 8 -

total time = 28 (7 adders * 4tu per instruction)





3.17. [20] <§3.3> As discussed in the text, one possible performance enhancement is to do a shift and add instead of an actual multiplication. Since 9×6, for example, can be written (2×2×2+1)×6, we can calculate 9×6 by shifting 6 to the left 3 times and then adding 6 to that result. Show the best way to calculate (0x33) × (0x55) using shifts and adds/subtracts. Assume both inputs are 8-bit unsigned integers.

0x33 = 51(ten) 0x55 = 85(ten)

51x85 can be written (2x2x2x2x2x2+21)x51

51*64 =
1100 1100 0000 (by shifting 51 to the left 6 times)
51*21 0100 0010 1111

  1100 1100 0000
+   0100 0010 1111
1 0000 1110 1111 4335(ten)





3.18. [20] <§3.4> Using a table similar to that shown in Figure 3.10, calculate 74 divided by 21 using the hardware described in Figure 3.8. You should show the contents of each register on each step. Assume both inputs are unsigned 6-bit integers.

// I assume that 74 and 21 are octal.

IterationStepQuotientDivisorRemainder
0initial values000000010001 000000000000 111100
11: Rem = Rem - Div
2b: Rem < 0 
⇒ +Div, sll Q, Q0=0
3: Shift Div right
000000
000000
000000
010001 000000
010001 000000
001000 100000
101111 111100
000000 111100
000000 111100
21: Rem = Rem - Div
2b: Rem < 0 ⇒ +Div, sll Q, Q0=0
3: Shift Div right
000000
000000
000000
001000 100000
001000 100000
000100 010000
111000 011100
000000 111100
000000 111100
3
1: Rem = Rem - Div
2b: Rem < 0 ⇒ +Div, sll Q, Q0=0
3: Shift Div right
000000
000000
000000
000100 010000
000100 010000
000010 001000
111100 101100
000000 111100
000000 111100
4
1: Rem = Rem - Div
2b: Rem < 0 ⇒ +Div, sll Q, Q0=0
3: Shift Div right
000000
000000
000000
000010 001000
000010 001000
000001 000100
111110 110100
000000 111100
000000 111100
51: Rem = Rem - Div
2b: Rem < 0 ⇒ +Div, sll Q, Q0=0
3: Shift Div right
000000
000000

000000
000001 000100
000001 000100
000000 100010
111111 111000
000000 111100

000000 111100
6
1: Rem = Rem - Div
2a: Rem ≥ 0 ⇒ sll Q, Q0=1
3: Shift Div right
000000
000001
000001
000000 100010
000000 100010
000000 010001
000000 011010
000000 011010
000000 011010
71: Rem = Rem - Div
2a: Rem ≥ 0 ⇒ sll Q, Q0=1
3: Shift Div right
000001
000011

000011
000000 010001
000000 010001
000000 001000
000000 001001
000000 001001

000000 001001





3.19. [30] <§3.4> Using a table similar to that shown in Figure 3.10, calculate 74 divided by 21 using the hardware described in Figure 3.11. You should show the contents of each register on each step. Assume A and B are unsigned 6-bit integers. This algorithm requires a slightly different approach than that shown in Figure 3.9. You will want to think hard about this, do an experiment or two, or else go to the web to figure out how to make this work correctly. (Hint: one possible solution involves using the fact that Figure 3.11 implies the remainder register can be shifted either direction.)

IterationStepDivisorRemainder
0initial values
Shift Rem left
010001
010001
000000 111100
000001 111000
11: Rem = Rem - Div
2b: Rem < 0 
⇒ +Div, sll R, R0=0
010001
010001
110000 111000
000011 110000
21: Rem = Rem - Div
2b: Rem < 0 ⇒ +Div, sll R, R0=0
010001
010001
110010 110000
000111 100000
3
1: Rem = Rem - Div
2b: Rem < 0 ⇒ +Div, sll R, R0=0
010001
010001
110110 100000
001111 000000
4
1: Rem = Rem - Div
2b: Rem < 0 ⇒ +Div, sll R, R0=0
010001
010001
111110 000000
011110 000000
51: Rem = Rem - Div
2a: Rem ≥ 0 ⇒ sll R, R0=1
010001
010001
001101 000000
011010 000001
6
1: Rem = Rem - Div
2a: Rem ≥ 0 ⇒ sll R, R0=1
010001
010001
001001 000001
010010 000011
doneShift left half of Rem right010001
001001 000011





3.20. [5] <§3.5> What decimal number does the bit pattern 0×0C000000 represent if it is a two’s complement integer? An unsigned integer?

two's complement integer : 201,326,592
unsigned integer : 201.326.592





3.21. [10] <§3.5> If the bit pattern 0×0C000000 is placed into the Instruction Register, what MIPS instruction will be executed?

jal 0





3.22. [10] <§3.5> What decimal number does the bit pattern 0×0C000000 represent if it is a floating point number? Use the IEEE 754 standard.

1.0 x 2-103

0 00011000 00000000000000000000000





3.23. [10] <§3.5> Write down the binary representation of the decimal number 63.25 assuming the IEEE 754 single precision format.

63.25 = 253 x 2-2 = 1.1111101 x 25 

01000010011111010000000000000000





3.24. [10] <§3.5> Write down the binary representation of the decimal number 63.25 assuming the IEEE 754 double precision format.

0100000001001111101000000000000000000000000000000000000000000000





3.25. [10] <§3.5> Write down the binary representation of the decimal number assuming it was stored using the single precision IBM format (base 16, instead of base 2, with 7 bits of exponent).

01000100111110100000000000000000




3.26. [20] <§3.5> Write down the binary bit pattern to represent −1.5625×10−1 assuming a format similar to that employed by the DEC PDP-8 (the leftmost 12 bits are the exponent stored as a two’s complement number, and the rightmost 24 bits are the mantissa stored as a two’s complement number). No hidden 1 is used. Comment on how the range and accuracy of this 36-bit pattern compares to the single and double precision IEEE 754 standards.

0111 1111 11000110 0000 0000 0000 0000 0000








References





3.19




덧글

  • kili0616 2015/11/25 23:35 # 삭제

    혹시 그뒷장 연습문제들은 안올려주시는건가요???

    도움많이받고있습니다 감사합니다.
  • 불타는 아이스크림 2015/11/26 04:47 #

    음.. 일을 하고 있어서 공부하지 못하고 잇네요. 조속히 올리도록 하겠습니다. ㅠ 사실 제일 중요한 부분인데..
  • 익명 2016/04/18 03:18 # 삭제

    감사합니다 :) 도움 진짜 많이 받고 있습니다 짱짱!
  • 불타는 아이스크림 2016/04/18 08:30 #

    허허.. 감사합니다. 도움이 된다니 굉장히 기쁘네요.:)
  • der 2016/11/06 02:31 # 삭제

    3.27.28.29 는 없나요?
  • 불타는 아이스크림 2016/11/08 12:14 #

    네. 3장 연습 문제는 반복되는 부분이 많아서 나머지 부분은 풀지 않았습니다. 원리 이해만 하셔도 충분할 듯 합니다.
  • won 2016/11/14 13:04 # 삭제

    3.16에서 tu per instruction이 의미하는게 무엇인가요??
    제가 푼거든 4tu를 곱하지 않았는데
  • 불타는 아이스크림 2016/11/15 15:39 #

    tu는 time unit 즉 시간단위이구요. tu per unstruction은 명령어 당 시간단위. 즉 adder 한 번 사용할 때마다 걸리는 시간을 의미해요.
    일단 제가 답을 잘못 적어놔서 총 걸리는 시간은 28 이에요. 문제에서 adder 한 번 사용할 때 4 tu 가 걸린다고 써놨어요.
    Integer 8bit에서는 adder가 7개 필요므로 7*4 = 28 이 되네요.
※ 로그인 사용자만 덧글을 남길 수 있습니다.