京都大学 情報学研究科 通信情報システム専攻 2023年8月実施 専門基礎A [A-4]

Author

SUN, 祭音Myyura (assisted by ChatGPT 5.4 Thinking)

Description

Answer all the following questions.

(1)

Consider an 8-bit binary floating-point format called FP8, which has the similar representation as IEEE 754 base-2 floating-point numbers. The bit fields of FP8 consist of, from MSB to LSB, a 1-bit sign bit, a 3-bit exponent using a biased representation of 3, and a 4-bit significand with implicit 1. The representation of infinity and denormalized numbers is also defined in the same way as IEEE 754. For example, if the sign bit is 0, the exponent is 7, and the significand is 0, it represents positive infinity. If the exponent is 0, it represents a denormalized number. In the following questions, the subscript in parentheses denotes the base of the number. Additionally, when rounding is necessary, use the round-to-nearest (ties to even) method.

(a) Express the number 00010110 represented in FP8 format in decimal.

(b) Provide the bit sequence in FP8 format that represents the number .

(c) Express the negative number closest to zero among the numbers representable by FP8, excluding negative zero, in decimal.

(d) Express the largest number among the numbers representable by FP8, excluding infinity, in decimal.

(2)

Answer the following questions about pipelined processors.

(a) Explain what a control hazard is in pipeline processing.

(b) Consider the following three schemes for branch prediction of branch instructions.

A: A scheme that predicts that the branch will always be not taken.

B: A scheme that predicts that the branch will always be taken.

C: A scheme that predicts that whether the branch will be taken or not is the same as the result of the last time the branch instruction was executed. (It predicts that the branch will be not taken the first time the branch instruction is executed.)

In either scheme, assume that there is no penalty if the prediction is correct, one cycle is incurred as penalty if the branch is predicted to be not taken and it actually is taken, and three cycles are incurred if the branch is predicted to be taken and it actually is not taken.

Suppose that there is a branch controlling a loop, and this branch is taken consecutive times and then not taken once (where is a non-negative integer).

For each of the three schemes A, B, and C, express the penalty for branch prediction incurred when this loop is first executed in terms of , and indicate which of the three schemes is superior in this case.

(c) Show a branch prediction scheme other than the three schemes shown in (b), describe its characteristics, and evaluate its penalty in the same loop as in (b). Assume that the penalty for branch prediction is the same as that was assumed for the three schemes A, B, and C in (b).

Kai

(1)

For a normalized number (exponent ):

For a denormalized number (exponent ):

Exponent with fraction is infinity.

(a)

0 | 001 | 0110

• Sign .
• Exponent .
• Fraction .

Answer: 0.34375

(b)

• Sign .
• Unbiased exponent .
• Fraction .

Answer: 11001011

(c)

Smallest magnitude nonzero is denormal with minimal fraction: 1 | 000 | 0001.

Answer: -0.015625

(d)

Max finite uses largest normal exponent (110) and max fraction 1111: 0 | 110 | 1111.

• Unbiased exponent .
• .

Answer: 15.5

(2)

(a)

A control hazard occurs when the next program counter (next instruction address) is uncertain due to a control-flow instruction (e.g., branch/jump). The pipeline may fetch along the wrong path, and if the branch outcome differs, it must stall and/or flush incorrectly fetched instructions, causing a performance penalty.

(b)

Scheme A (always not taken): first are taken mispredicts of type (N, T). Last is not taken correct.

Scheme B (always taken): first correct, last mispredict of type (T, N).

Scheme C (predict same as last time; first time predicts not taken):

• If : only one execution (not taken), predicted not taken 0 penalty.
• If : first taken mispredicted (1), last not-taken mispredicted as taken (3).

Best scheme:

• : A or C (0 penalty).
• : A (1 or 2 penalty).
• : A and B tie (3 penalty).
• : B (3 penalty).

(c) Another prediction scheme + its penalty

Example: BTFNT (Backward Taken, Forward Not Taken).

This is a static branch prediction scheme. It predicts a branch as taken if the branch target is at a lower address (a backward branch), and not taken if the branch target is at a higher address (a forward branch). Since a loop-closing branch is typically a backward branch, this scheme predicts the loop branch as taken every time.

Therefore, for a loop branch that is taken times and then not taken once:

• The first executions are predicted correctly.
• The final execution (loop exit) is mispredicted as taken, while it is actually not taken.

Thus, only one misprediction occurs, of type (T, N), whose penalty is 3 cycles.

So, for this loop, BTFNT has the same penalty as scheme B (always taken).