I'm revising for my BSc exam in "OS and computer architecture".
There's a question from a previous year's exam which I'm not sure how
to solve and it might come this year in some variation. As I'm aiming
for a 80% score, I want to be able to answer this one (as well as the
other one I posted on google answers). Please give a detailed
step-by-step guide on how you solved question (a)(ii) and (a)(iii). To
give an idea of the scope: it's a 2-hour exam and this question
represented 20% of the total exam mark when it occured. Each mark is a
percent.
Note that I have consulted my university's code of conduct and
guidelines on academic honesty and don't see anything preventing me
from seeking tutor help on past papers.
(a) The Intel Pentium I processor incorporates a Branch Target Buffer
(BTB). This BTB is a 4-way set associative cache with 256 sets; each
line in this cache can store a tag, the destination address of the
branch, and two history bits. Assuming that a branch receives an entry
in the BTB when it is taken for the first time, and its history bits
are then set to 11(binary), after which the history bits operate thus:
- each time the branch is not taken, the bits are decremented by 1
(but are never decremented below 0
- each time the branch is taken, the bits are incremented by 1 (but
are never incremented above 11 (binary)
- when a BTB miss occurs, the prediction is that the branch will not be taken
- when a BTB hit occurs, the prediction is that the branch will be
taken if the history bits are greater than 1, otherwise the prediction
is that the branch will not be taken.
(i) Briefly describe the purpose and operation of the BTB. [4 marks]
(ii) How many bits will be stored in the Tag field of each line of the
BTB ? [2 marks]
(iii) Assuming that the BTB is initially empty, and the processor then
encounters the conditional branch instructions shown in sequence in
the table below, copy and complete the table, showing your working.
[10 Marks]
Address of branch | Actual outcome of | BTB Hit | Prediction
instruction (hex) | branch instruction | or Miss? | Taken or Not
----------------------------------------------------------------------
00246802 | Taken | | |
00246804 | Taken | | |
00244202 | Taken | | |
00246802 | Not taken | | |
00240202 | Taken | | |
00246802 | Not taken | | |
00244202 | Taken | | |
00246804 | Taken | | |
00246802 | Not taken | | |
00246802 | Taken | | |
(iv) Discuss possible ways in which this BTB could be improved when
designing a new processor, in order to deliver superior branch
prediction performance. [4 Marks] |
