US2002124162A1PendingUtilityA1
Computer system and method for fetching a next instruction
Est. expiryAug 31, 2012(expired)· nominal 20-yr term from priority
G06F 12/08G06F 9/3844
43
PatentIndex Score
0
Cited by
0
References
0
Claims
Abstract
N instruction class (IClass) fields, m branch prediction (BRPD) and k next fetch address fields are added to each instruction set of n instructions of a cache line of an instruction cache, where m and k are less than or equal to n. The BRPD and NFAPD fields of a cache line are initialized in accordance to a pre-established initialization policy of a branch and next fetch address prediction algorithm while the cache line is first brought into the instruction cache. The sets of IClasses, BRPDS, and NFAPDs of a cache line are accessed concurrently with the corresponding sets of instructions of the cache line. One BRPD and one NFAPD is selected from the set of BRPDs and NFAPDs corresponding to the selected set of instructions. The selected BRPD and NFAPD are updated in accordance to a pre-established update policy of the branch and next fetch address prediction algorithm when the actual branch direction and next fetch address are resolved. Additionally, in one embodiment, m and k are equal to 1, and the selected NFAPD is stored immediately into the NFA register of the instruction prefetch and dispatch unit, allowing the selected NFAPD to be used as the fetch address for the next instruction cache access to achieve zero fetch latency for both control transfer and sequential next fetch.
Claims
exact text as granted — not AI-modifiedWhat is claimed is
1 . In a computer system comprising at least one execution unit for executing instructions, a method for rapidly dispatching instructions to said at least one execution unit for execution, said method comprising the steps of:
a) storing a plurality of sets of instructions in a plurality of cache lines of an instruction cache array; b) storing a plurality of corresponding sets of tag and associated control information in a plurality of corresponding tag entries of a corresponding tag array; c) storing a plurality of corresponding sets of instruction classes in a plurality of corresponding instruction class entries of a corresponding instruction class array, each of said set of instruction classes comprising a plurality of instruction classes for said instructions of said corresponding set of instructions; d) storing a plurality of corresponding sets of predictive annotations in a plurality of corresponding predictive annotation entries of a corresponding predictive annotation array, each of said set of predictive annotations comprising at least one branch prediction for said instructions of said corresponding set of instructions; and e) fetching and prefetching repeatedly selected ones of said stored sets of instructions for dispatch to said at least one execution unit for execution using said stored corresponding instruction classes and branch predictions.
2 . The method as set forth in claim 1 , wherein, said instruction class and predictive annotation entries are stored into said corresponding instruction class and predictive annotation arrays in said steps c) and d) one instruction class and corresponding predictive annotation entry at a time, each of said instruction class and corresponding predictive annotation entries being stored into said instruction class and predictive annotation arrays when their corresponding cache line of instructions is stored into said instruction cache array, each of said branch predictions of said predictive annotation entries being initialized in accordance with an initialization policy of a branch prediction algorithm when its predictive annotation entry is stored into said predictive annotation array.
3 . The method as set forth in claim 2 , wherein, each of said at least one branch prediction of each of said sets of predictive annotations is initialized to predict “branch will not be taken”.
4 . The method as set forth in claim 1 , wherein, each of said fetchings and prefetchings in said step e) comprises the steps of:
e.1) accessing one of said cache line of instructions and its corresponding tag, instruction class and predictive annotation entries concurrently using a fetch address; e.2) selecting one of said sets of instructions from said accessed cache line and a branch prediction from said selected set of instructions' corresponding set of predictive annotations in said accessed cache line's corresponding predictive annotation entry; e.3) determining a next fetch address from said selected branch prediction; e.4) determining subsequently whether said selected branch prediction predicts correctly; and e.5) updating said selected branch prediction in accordance to an update policy of a branch prediction algorithm based on said prediction correctness determination.
5 . The method as set forth in claim 4 , wherein, said update policy in said step
e.5) updates each of said selected branch predictions as follows: Branch Prediction, Update Class Actual Policy PC-relative branch PT, ANT PNT −> BRPD[A] PC-relative branch PNT, AT PT −> BRPD[A] PC-relative branch PT, AT No Action PC-relative branch PNT, ANT No Action Register indirect PNT, AT PT −> BRPD[A] control transfer Register indirect PT, AT No Action control transfer Unconditional PC PNT, AT PT −> BRPD[A] control transfer Unconditional PC PT, AT No Action control transfer
6 . The method as set forth in claim 1 , wherein,
each of said set of predictive annotations in said step d) further comprises at least one next fetch address prediction for said instructions of said corresponding set of instructions; and said fetchings and prefetchings in said step e) use said stored corresponding next fetch address predictions as well as said instruction classes and branch predictions.
7 . The method as set forth in claim 6 , wherein, said next fetch address predictions are initialized, accessed, selected, and updated in substantially the same manner as said branch predictions.
8 . The method as set forth in claim 7 , wherein, each of said at least one next fetch address prediction of each of said sets of predictive annotations is initialized to predict an address that equals to a sum of a program counter and a next sequential fetch block size, said program counter indicating a current fetch address and said next fetch sequential block size indicating a next sequential fetch block's block size.
9 . The method as set forth in claim 7 , wherein, each of said selected next fetch address predictions is updated as follows:
Next Fetch
Branch
Prediction,
Addr Hit/
Update
Type
Actual
Miss
Policy
PC relative branch
PT, ANT
A + FS = NFAPD[A]
PC relative branch
PT, AT
Miss
TA −> NFAPD[A]
PC relative branch
PNT, AT
TA −> NFAPD[A]
PC relative branch
PNT, ANT
Miss
A + FS = NFAPD[A]
PC relative branch
PT, AT
Hit
No Action
PC relative branch
PNT, ANT
Hit
No Action
Register indirect
PNT, AT
TA −> NFAPD[A]
control transfer
Register indirect
PT, AT
Miss
TA −> NFAPD[A]
control transfer
Register indirect
PT, AT
Hit
No Action
control transfer
Unconditional PC
PNT, AT
TA −> NFAPD[A]
control transfer
Unconditional PC
PT, AT
Miss
TA −> NFAPD[A]
control transfer
Unconditional PC
PT, AT
No Action
control transfer
10 . The method as set forth in claim 7 , wherein,
each set of said predictive annotations comprises one branch prediction and one next fetch address prediction, said one branch and next fetch address predictions predicting branch direction and next fetch address for a dominant instruction of its corresponding set of instructions; said method further comprises the step of f) storing each of said selected next fetch address predictions in a register, said register being used for storing a next fetch address for a next set of instructions to be fetched, said stored next fetch address being also used for selecting said branch prediction and said next fetch address prediction for said next set of instructions to be fetched.
11 . In a computer system comprising at least one execution unit for executing instructions, an apparatus for rapidly dispatching instructions to said at least one execution unit for execution, said apparatus comprising:
a) instruction array means comprising a plurality of cache lines for storing a plurality of sets of instructions; b) tag array means comprising a plurality of tag entries for storing a plurality of corresponding sets of tag and associated control information; c) instruction class array means comprising a plurality of instruction class entries for storing a plurality of corresponding sets of instruction classes, each of said set of instruction classes comprising a plurality of instruction classes for said instructions of said corresponding set of instructions; d) predictive annotation array means comprising a plurality of predictive annotation entries for storing a plurality of corresponding sets of predictive annotations, each of said set of predictive annotations comprising at least one branch prediction for said instructions of said corresponding set of instructions; and e) fetching and prefetching means coupled to said instruction array means, said tag array means, said instruction class array means, and said predictive annotation array means for fetching and prefetching repeatedly selected ones of said stored sets of instructions for dispatch to said at least one execution unit for execution using said stored corresponding instruction classes and branch predictions.
12 . The apparatus as set forth in claim 11 , wherein,
said instruction class and said predictive annotation array means store each of said instruction class and corresponding predictive annotation entries one instruction class and corresponding predictive annotation entry at a time, said instruction class and predictive annotation array means store each of said instruction class and corresponding predictive annotation entries into said instruction class and predictive annotation array means when said instruction array means stores its corresponding cache line of instructions into itself, said predictive annotation array means initializes each of said branch predictions of said predictive annotation entries in accordance to an initialization policy of a branch prediction algorithm when said predictive annotation array means stores its predictive annotation entries into itself.
13 . The apparatus as set forth in claim 12 , wherein, said predictive annotation array means initializes each of said at least one branch prediction of each of said sets of predictive annotations to predict “branch will not be taken”.
14 . The apparatus as set forth in claim 11 , wherein, said fetching and prefetching means comprises:
e.1) accessing means for accessing one of said cache line of instructions and its corresponding tag, instruction class and predictive annotation entries stored in said instruction, tag, instruction class and predictive annotation array means concurrently using a fetch address; e.2) selection means coupled to said instruction, tag, instruction class and predictive annotation array means for selecting one of said sets of instructions from said accessed cache line and a branch prediction from said selected set of instructions' corresponding set of predictive annotations in said accessed cache line's corresponding predictive annotation entry; e.3) first determination means coupled to said selection means for determining a next fetch address from said selected branch prediction; e.4) second determination means coupled to said selection means and said execution means for determining subsequently whether said selected branch prediction predicts correctly; and e.5) update means coupled to said second determination means and said instruction, tag and predictive annotation array means for updating said selected branch prediction in accordance with an update policy of a branch prediction algorithm based on said prediction correctness determination.
15 . The apparatus as set forth in claim 14 , wherein, said update means updates each of said selected branch predictions as follows:
Branch
Prediction,
Update
Type
Actual
Policy
PC relative branch
PT, ANT
PNT −> BRPD[A]
PC relative branch
PNT, AT
PT −> BRPD[A]
PC relative branch
PT, AT
No Action
PC relative branch
PNT, ANT
No Action
Register Indirect
PNT, AT
PT −> BRPD[A]
control transfer
Register Indirect
PT, AT
No Action
control transfer
Unconditional PC
PNT, AT
PT −> BRPD[A]
control transfer
Unconditional PC
PT, AT
No Action
control transfer
16 . The apparatus as set forth in claim 11 , wherein,
each of said set of predictive annotations further comprises at least one next fetch address prediction for said instructions of said corresponding set of instructions; and said fetching and prefetching means uses said stored corresponding next fetch address predictions as well as said instruction classes and branch predictions.
17 . The apparatus as set forth in claim 16 , wherein,
said fetching and prefetching means comprises accessing mean, selection means and update means for accessing, selecting and updating said branch predictions, said predictive annotation array means, said accessing means, said selection means, and said update means initializes, accesses, selects, and updates said next fetch address predictions in substantially the same manner as said branch predictions.
18 . The apparatus as set forth in claim 17 , wherein, said predictive annotation array means initializes each of said at least one next fetch address prediction of each of said sets of predictive annotations to predict an address that equals to a sum of a program counter and a next sequential fetch block size, said program counter indicating a current fetch address and said next sequential fetch block size indicating a next sequential fetch block's block size.
19 . The apparatus as set forth in claim 17 , wherein, said update means update each of said selected next fetch address predictions as follows:
Next Fetch
Branch
Prediction,
Addr Hit/
Update
Type
Actual
Miss
Policy
PC relative branch
PT, ANT
A + FS = NFAPD[A]
PC relative branch
PT, AT
Miss
TA −> NFAPD[A]
PC relative branch
PNT, AT
TA −> NFAPD[A]
PC relative branch
PNT, ANT
Miss
A + FS = NFAPD[A]
PC relative branch
PT, AT
Hit
No Action
PC relative branch
PNT, ANT
Hit
No Action
Register Indirect
PNT, AT
TA −> NFAPD[A]
control transfer
Register Indirect
PT, AT
Miss
TA −> NFAPD[A]
control transfer
Register Indirect
PT, AT
Hit
No Action
control transfer
Unconditional PC
PNT, AT
TA −> NFAPD[A]
control transfer
Unconditional PC
PT, AT
Miss
TA −> NFAPD[A]
control transfer
Unconditional PC
PT, AT
No Action
control transfer
20 . The apparatus as set forth in claim 17 , wherein,
each set of said predictive annotations comprises one branch prediction and one next fetch address prediction, said one branch and next fetch address predictions predicting branch direction and next fetch address for a dominant instruction of its corresponding set of instructions; said apparatus further comprises e) register means coupled to said fetching and prefetching means for storing each of said selected next fetch address predictions, said register being used for storing a next fetch address for a next set of instructions to be fetched, said stored next fetch address being also used for selecting said branch prediction and said next fetch address prediction for said next set of instructions to be fetched.Cited by (0)
No later patents cite this yet.
References (0)
No backward citations on record.