京都大学 情報学研究科 通信情報システム専攻 2024年8月実施 専門基礎A [A-4]
Author
SUN, 祭音Myyura (assisted by ChatGPT 5.4 Thinking)
Description
English text in the image
Answer all the following questions.
(1)
Answer the following questions on the number representation on a computer.
(a) Give the decimal representations of the maximum number and the minimum number that can be represented by the 5-bit two’s complement binary number system.
(b) Show the results of the following additions in the 5-bit two’s complement binary number system. If the result overflows the range of the system, just write “Overflow”.
01001 + 0110111110 + 11001
(c) When the 4 Byte data ABCD1234 represented by hexadecimal numbers are stored in the memory system based on the byte order of the little-endian method, show the order of each byte data in the memory.
(2)
Consider the case of executing a part of a C language program (Code segment) shown in Fig. 1, on a processor with a branch prediction mechanism. In this question, when a branch is taken, the body of “for” statement or “if” statement (code enclosed in {}) is executed. Arrays A and B are declared with sufficient size, and each element is initialized with random integers. Also, during code execution, no exceptions or interrupts occur, and loop optimization is not performed.
Fig. 1 Code segment
int i;
for(i=0; i<N; i++){ /* L1 */
/* Taken path for L1 */
if(i%7 == 0){ /* L2 */
A[i] = B[i] + 1; /* Taken path for L2 */
}
if(i%7 == 1){ /* L3 */
A[i] = B[i] - 1; /* Taken path for L3 */
}
if(i%7 > 4){ /* L4 */
B[i] = B[i] * B[i]; /* Taken path for L4 */
}
}
(a) Consider executing the Code segment shown in Fig. 1 on a processor that adopts a dynamic branch predictor that predicts “whether a branch will be taken is the same as the result when the branch was last executed (it predicts not taken when the branch is executed for the first time)”. The branch histories of L1, L2, L3, and L4 are managed individually. Assuming that N is sufficiently large and can be considered infinite, calculate the branch prediction accuracy of L3 and L4, respectively.
(b) Consider executing the Code segment shown in Fig. 1 on a processor that adopts a 2-bit branch predictor. The 2-bit branch predictor uses a counter that follows the state transition diagram shown in Fig. 2 based on the branch result, remembers the branch history, and predicts “not taken” for states 00 and 01, and “taken” for states 10 and 11. Counters for managing the branch histories of L1, L2, L3, and L4 are prepared individually and the branch histories are managed individually. Also, the initial state of the 2-bit branch predictor is all 00. Assuming that N is sufficiently large and can be considered infinite, calculate the branch prediction accuracy of L3 and L4, respectively.
(c) In the case of previous question (b), if the branch histories of L2, L3, and L4 are managed with one counter without distinction (for example, when predicting the branch of L3 at i=M, the branch history of L2 at i=M and L4 at i=M-1 is used), calculate the branch prediction accuracy of L2, L3, and L4, respectively. Note that the initial state of the 2-bit branch predictor is 00.
Kai
(1)
(a) Range of 5-bit Two's Complement
- Maximum number:
- Minimum number:
(b) 5-bit Two's Complement Arithmetic
- (i) Overflow (Cannot represent result in 5 bits)
- (ii)
(Result is , correct)
(c) Hexadecimal Representation
34 12 CD AB
(2)
Use T for Taken, N for Not Taken.
(a) Branch Prediction (1-bit Predictor)
For L3:
| i | Prediction | Reality | Right/Wrong |
|---|---|---|---|
| 0 | N | N | R |
| 1 | N | T | W |
| 2 | T | N | W |
| 3 | N | N | R |
| 4 | N | N | R |
| 5 | N | N | R |
| 6 | N | N | R |
Accuracy: 5/7
For L4:
| i | Prediction | Reality | Right/Wrong |
|---|---|---|---|
| 0 | N | N | R |
| 1 | N | N | R |
| 2 | N | N | R |
| 3 | N | N | R |
| 4 | N | N | R |
| 5 | N | T | W |
| 6 | T | T | R |
| 7 | T | N | W |
| 8 | N | N | R |
Accuracy: 5/7
(b) Branch Prediction (2-bit Predictor)
For L3:
| i | i mod 7 | State | Prediction | Actual | Next State | Right/Wrong |
|---|---|---|---|---|---|---|
| 0 | 0 | 00 | N | N | 00 | R |
| 1 | 1 | 00 | N | T | 01 | W |
| 2 | 2 | 01 | N | N | 00 | R |
| 3 | 3 | 00 | N | N | 00 | R |
| 4 | 4 | 00 | N | N | 00 | R |
| 5 | 5 | 00 | N | N | 00 | R |
| 6 | 6 | 00 | N | N | 00 | R |
| 7 | 0 | 00 | N | N | 00 | R |
| 8 | 1 | 00 | N | T | 01 | W |
| 9 | 2 | 01 | N | N | 00 | R |
| 10 | 3 | 00 | N | N | 00 | R |
| 11 | 4 | 00 | N | N | 00 | R |
| 12 | 5 | 00 | N | N | 00 | R |
| 13 | 6 | 00 | N | N | 00 | R |
Accuracy: 6/7
For L4:
| i | i mod 7 | State | Prediction | Actual | Next State | Right/Wrong |
|---|---|---|---|---|---|---|
| 0 | 0 | 00 | N | N | 00 | R |
| 1 | 1 | 00 | N | N | 00 | R |
| 2 | 2 | 00 | N | N | 00 | R |
| 3 | 3 | 00 | N | N | 00 | R |
| 4 | 4 | 00 | N | N | 00 | R |
| 5 | 5 | 00 | N | T | 01 | W |
| 6 | 6 | 01 | N | T | 10 | W |
| 7 | 0 | 10 | T | N | 01 | W |
| 8 | 1 | 01 | N | N | 00 | R |
| 9 | 2 | 00 | N | N | 00 | R |
| 10 | 3 | 00 | N | N | 00 | R |
| 11 | 4 | 00 | N | N | 00 | R |
| 12 | 5 | 00 | N | T | 01 | W |
| 13 | 6 | 01 | N | T | 10 | W |
Accuracy: 4/7
(c) Branch Prediction (Detailed Trace)
| i | Branch | State | Prediction | Reality | Right/Wrong |
|---|---|---|---|---|---|
| 0 | L2 | 00 | N | T | W |
| L3 | 01 | N | N | R | |
| L4 | 00 | N | N | R | |
| 1 | L2 | 00 | N | N | R |
| L3 | 00 | N | T | W | |
| L4 | 01 | N | N | R | |
| 2 | L2 | 00 | N | N | R |
| L3 | 00 | N | N | R | |
| L4 | 00 | N | N | R | |
| i = 3: Same as i = 2 | |||||
| i = 4: Same as i = 2 | |||||
| 5 | L2 | 00 | N | N | R |
| L3 | 00 | N | N | R | |
| L4 | 00 | N | T | W | |
| 6 | L2 | 01 | N | N | R |
| L3 | 00 | N | N | R | |
| L4 | 00 | N | T | W | |
| 7 | L2 | 01 | N | T | W |
| L3 | 10 | T | N | W | |
| L4 | 01 | N | N | R | |
| 8 | L2 | 00 | N | N | R |
| L3 | 00 | N | T | W | |
| L4 | 01 | N | N | R | |
| 9 | L2 | 00 | N | N | R |
| L3 | 00 | N | N | R | |
| L4 | 00 | N | N | R | |
Accuracy Summary:
- L2: 6/7
- L3: 5/7
- L4: 5/7