EP0109655A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Instruction prefetching device with prediction of a branch destination address
Assignee: NEC Corp
•
Filing: 1983-11-15
•
Granted: —
•
Expires: 2003-11-15
Abstract
Abstract An instruction prefetching device of a data processing system prefetches an instruction sequence, usually before decoding of a branch instruction being prefetched, by predicting a branch destination address which is preliminari, ly stored in a branch history table (46) and retrieved by an instruction address of the branch instruction. Preferably, a prediction evaluating circuit (66) evaluates the predicted destination address with attention directed to a result which is obtained by actually executing the branch instruction and indicates whether the branch instruction indicates "no go" or "go" to the branch. When the prediction is incorrect, the prefetch is suspended. Furthermore, the branch destination address is renewed to a new address obtained by decoding of the branch instruction. More preferably, a discriminator (73) discriminates whether or not the instruction being prefetched is really a branch instruction. If not. the predicted destination address is neglected.
Inventors
- 👤 Syuichi Hanatani
- 👤 Masanobu Akagi
- 👤 Kouemon Nigo
- 👤 Ritsuo Sugaya
- 👤 Toshiteru Shibuya
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-10-23 17:19
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/30; G06F9/38; G06F9/3802; G06F9/3804; G06F9/3806; G06F9/3836; G06F9/3842; G06F9/3844
Claims Analysis
Total Claims: 11
Claim 1
Independent Claim
163 words
An instruction prefetching device for use in carrying out prefetch of an instruction sequence in a data processing system which includes an executing unit, said instruction prefetching device comprising: ! a branch history table for memorizing a plurality of entry pairs, each entry pair comprising a first entry specifying an instruction address of a branch instruction executed by said executing unit prior to said prefetch and a second entry specifying branch information which comprises a branch destination address obtained by execution of said branch instruction, said second entry corresponding to said first entry as regards each branch instruction; retrieving means for retrieving said branch history table for one of the first entries of said entry pairs in response to a current instruction address of a current instruction being prefetched to make said branch history table produce a corresponding second entry when said one of the first entries is located; and prefetching means responsive to said corresponding second entry for carrying out said prefetch.
Claim 2
Dependent Claim
163 words
An instruction prefetching device for use in carrying out prefetch of an instruction sequence in a data processing system which includes an executing unit, said instruction prefetching device comprising: ! a branch history table for memorizing a plurality of entry pairs, each entry pair comprising a first entry specifying an instruction address of a branch instruction executed by said executing unit prior to said prefetch and a second entry specifying branch information which comprises a branch destination address obtained by execution of said branch instruction, said second entry corresponding to said first entry as regards each branch instruction; retrieving means for retrieving said branch history table for one of the first entries of said entry pairs in response to a current instruction address of a current instruction being prefetched to make said branch history table produce a corresponding second entry when said one of the first entries is located; and prefetching means responsive to said corresponding second entry for carrying out said prefetch.
Claim 3
Dependent Claim
155 words
An instruction prefetching device as claimed in Claim 1, wherein: said branch history table is for memorizing the second entries specifying the branch information, which comprises the branch destination addresses, in correspondence to the instruction addresses of the respective branch instructions; said retrieving means comprising: (Claim 2 continued) first means responsive to said current instruction address for locating one of the first entries that specifies the instruction address of a branch instruction as a branch instruction address; second means for selecting one of the branch instruction addresses as a selected instruction address when said one of the first entries specifies a plurality of branch instruction addresses, said selected instruction address being for a branch instruction which should be prefetched next subsequent to said current instruction; and third means responsive to said selected instruction address for selecting that one of the branch destination addresses from the corresponding second entry which corresponds to said selected instruction address.
Claim 4
Dependent Claim
25 words
An instruction prefetching device as claimed in Claim 1, further comprising an instruction buffer for storing a queue of instructions prefetched by said prefetching means.
Claim 5
Dependent Claim
125 words
An. instruction prefetching device as claimed in Claim 1, wherein said prefetching means comprises: prediction evaluating means responsive to said corresponding second entry and a result of execution of said current instruction for evaluating said corresponding second entry to produce a prediction evaluation signal indicative of whether the branch destination address of the branch information specified by said corresponding second entry is correct or incorrect in view of said result; and (Claim 4 continued) controlling means responsive to said prediction evaluation signal for controlling said prefetch to be continued in response to said corresponding second entry and said result when said prediction evaluation signal indicates that the branch destination address of the branch information specified by said corresponding second entry is correct and incorrect, respectively.
Claim 6
Dependent Claim
81 words
An instruction prefetching device as claimed in Claim 4, wherein said controlling means comprises: means responsive to the prediction evaluation signal indicative of correctness of said branch destination address for continuing said prefetch; renewing means responsive to the prediction evaluation signal indicative of incorrectness of said branch destination address for renewing the branch information specified by said corresponding second entry to new branch information according to said result; and means responsive to said new branch information for carrying out said prefetch.
Claim 7
Dependent Claim
144 words
An instruction prefetching device as claimed in Claim 4, wherein: said branch history table is for memorizing the entry pairs in which the branch information specified by each second entry further comprises a branch direction obtained by execution of said branch instruction; said prediction evaluating means being for producing the prediction evaluation signal which additionally indicates whether the branch direction of the branch information specified (Claim 6 continued) by said corresponding second entry is correct or incorrect in view of said result; said controlling means being for controlling said prefetch in response to said corresponding second entry and said result when said prediction evaluation signal indicates that both of the branch destination address and the branch direction of the branch information specified by said corresponding second entry are correct and that either of the last-mentioned branch destination address and branch direction is incorrect, respectively.
Claim 8
Dependent Claim
134 words
An instruction prefetching device as claimed in Claim 6, wherein said controlling means comprises: means responsive to the prediction evaluation signal indicative of correctness of both of the branch destination address and the branch direction for continuing said prefetch; first renewing means responsive to the prediction evaluation signal indicative of incorrectness of said branch direction for renewing the branch direction to a new branch direction according to said result; second renewing means responsive to the prediction evaluation signal indicative of incorrectness of the branch destination address for renewing the branch destination address to a new branch destination address according to said result; and means responsive to said new branch direction and said new branch destination address for carrying out said prefetch when said first and said second renewing means are put into operation, respectively,
Claim 9
Dependent Claim
75 words
An instruction prefetching device as claimed in Claim 4, said executing unit including an address translating circuit for translating a logical addressee to a real address, wherein said branch history table is for memorizing the entry pairs in which the first entry indicates a real address of said branch instruction and in which the branch information specified by the corresponding second entry indicates a real branch destination address obtained by execution of said branch instruction.
Claim 10
Dependent Claim
97 words
An instruction prefetching device as claimed in Claim 1, wherein: said branch history table comprises a directory memory having a predetermined number of directory blocks for memorizing the first entries of said entry pairs, respectively, and a data memory having a plurality of data blocks corresponding to the respective directory blocks, said data blocks being for memorizing the second entries of said entry pairs, respectively; said retrieving means being for locating one of said directory blocks in compliance with the instruction address of said current instruction to make the corresponding data block produce said corresponding second entry.
Claim 11
Dependent Claim
75 words
An instruction prefetching device as claimed in Claim 1, further comprising! discriminating means coupled to said prefetching means for discriminating each prefetched instruction to produce a discrimination signal which indicates whether or not each prefetched instruction is a branch instruction; and controlling means responsive to said discrimination signal for making said prefetching means neglect said corresponding (Claim 10 continued) second entry when said discrimination signal indicates that each prefetched instruction is not a branch instruction.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.