Browse Prior Art Database

Mechanism for Recording Prefetching History in BHT

IP.com Disclosure Number: IPCOM000038902D
Original Publication Date: 1987-Mar-01
Included in the Prior Art Database: 2005-Feb-01
Document File: 2 page(s) / 15K

Publishing Venue

IBM

Related People

Bennett, BT: AUTHOR [+2]

Abstract

In future high performance processors, prefetching of instruction cache lines is important for reducing instruction supply disruptions. The use of a Branch History Table (BHT) is a powerful mechanism for branch prediction and may be used to prefetch I-lines. Straightforward I-prefetching based on BHT decisions may, however, not reach decisions fast enough in order to overlap the time required to fetch a missed cache line. In this invention a mechanism is described in which the decision on which line is to be used next can be reached before an I-line is entered. The technique is to record prefetch information in BHT. In a typical BHT in which each entry records information, such as , where Branch represents a (taken ) Branch and Target represents the instruction (address) the branch is taken to.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 45% of the total text.

Page 1 of 2

Mechanism for Recording Prefetching History in BHT

In future high performance processors, prefetching of instruction cache lines is important for reducing instruction supply disruptions. The use of a Branch History Table (BHT) is a powerful mechanism for branch prediction and may be used to prefetch I-lines. Straightforward I-prefetching based on BHT decisions may, however, not reach decisions fast enough in order to overlap the time required to fetch a missed cache line. In this invention a mechanism is described in which the decision on which line is to be used next can be reached before an I- line is entered. The technique is to record prefetch information in BHT. In a typical BHT in which each entry records information, such as <Branch, Target>, where Branch represents a (taken ) Branch and Target represents the instruction (address) the branch is taken to. Each entry of the BHT is enhanced with one more field <NextLine>. Each NextLine field is associated with a V-bit, indicating whether the information is valid (or, confirmed). For a given entry <Branch, Target, NextLine> the (valid) NextLine represents the next different line to be brought into the cache (if it is missing there). The basic steps for setting NextLine fields are as follows. For purposes of illustration, first assume that BHT always finds at least one taken branch within a line whenever the line is searched by BHT. Consider a consecutive sequence Li T Lj T Lk of I-lines accessed during execution. At the BHT entry for the last taken branch executed (or guessed) in Li, the information (in the NextLine field) that Lk is likely to be accessed soon is recorded. In BHT control two internal registers LTBR1 and LTBR2 (where LTB means Last-Taken-Branch) are assumed in which each points to the BHT entry for the last taken branch executed in a line. As BHT (or execution) moves along to locate branches, the LTBR1 register will point to the BHT entry that represents the last found taken branch in Li, although the BHT is currently guessing along branches in Lj . At the same time, while BHT is guessing branches in Lj, LTBR2 is updated to point to the BHT entry for the last found taken branch in Lj . As soon as the line switch Lj T Lk is identified by BHT (at this time instructions in Li might have been exected already) the NextLine field of the BHT entry pointed to by LTBR1 is updated with information representing Lk, and the assignments LTBR1 E LTBR2 and LTBR2 E ×/ are carried out (i.e., LTBR1 gets the current contents of LTBR2, and LTBR2 is made empty) and BHT starts working on branches in Lk . Normally LTBR1 and LTBR2 do not represent branches within the same line. Now consider the confirmation step in the above example. When the NextLine information is updated (with Lk) the old contents are compared to the new value to see if they are identical. If so, the NextLine field is made valid (by turning its V-bit ON); otherwise, it is made invalid. The algorithm for prefetching...