Translation look ahead based cache access

Claim 2

Cache memory accessing apparatus, for use in a data processing system comprising instruction execution means, comprising: means, responsive to the execution means, for calculating the real cache address of data required for execution of a current instruction; characterised by: means for maintaining a table, listing, for each type of instruction, the cache address used in a previous execution of that type of instruction; prediction means for determining a predicted cache address from the table, the predicted address being the address used in said previous execution of the same type of instruction as the current instruction; first retrieval-means for retrieving data from the cache using the predicted cache address; means for comparing the calculated cache address and the predicted cache address; and second retrieval means responsive to the comparing means, for retrieving data from the cache using the calculated address when the calculated address is not equal to the predicted address.

Claim 3

Cache memory accessing apparatus as claimed in claim 1, in which said previous execution is the most recent execution of that type of instruction.

Claim 4

Cache memory accessing apparatus as claimed in claim 1 or claim 2, further comprising: means, responsive to the comparing means, for updating the cache address in the table entry corresponding to the current instruction when the predicted address is not equal to the calculated address, the updated cache address for that instruction type being the calculated cache address.

Claim 5

Cache memory accessing apparatus as claimed in any preceding claim in which: the prediction means and the first retrieval means operate during the operation of the calculating means.

Claim 10

A cache memory access system for a digital computer comprising: an instruction register, a virtual address register, a predicted real address register, a translation look-aside buffer, an arithmetic logic unit, a plurality of general purpose registers; a cache memory means for storing and supplying data for said digital computer; said plurality of general purpose registers being useable as base and index registers; a virtual address generation means for generating a virtual address from said instruction received by said instruction register; said virtual address generation means generating said virtual address from a current address within said base register, index register contents, and said instruction register displacement bits; a predicted real address generation means, for generating a predicted real address, which comprises a history table, containing a first plurality of real addresses corresponding to a first plurality of previously used current addresses from said base register, a comparison means for comparing said current address in said base register with said first plurality of previously used current addresses contained within said history table, and an update means for updating said history table; said real addresses, from said history table, being stored in said predicted real address register, when said predicted real address generation means matches said current address from said base register with one of said first plurality of previously used current addresses contained within said history table; said cache memory means having a receiving means for receiving said predicted real address from said pre-dicted real address register during a first machine cycle, said cache memory means having a retrieval means for retrieving said stored data from said predicted real address location before said first machine cycle is complete; said translation look-aside buffer having a second plurality of real addresses corresponding to a first plurality of virtual addresses, said translation look-aside buffer having a selection means for select ing a real address corresponding to said virtual address stored in said virtual address register; and a comparison means for comparing said predicted real address with said real address selected by said translation look-aside buffer, when said predicted real address matches said real address then said arithmetic logic unit receives said stored data retrieved from said predicted address location of said cache memory means during a second machine cycle, when said predict ed real address does not match said real address then said cache memory means receives said real address from said translation look-aside buffer, said cache memory means retrieves said stored data from said real address location during a second machine cycle, said arithmetic logic unit receives said stored data retrieved from said real address location of said cache memory means during a third machine cycle.

Claim 11

A cache memory access system for a digital computer comprising: an instruction register, a virtual address register, a predicted real address register, a translation look-aside buffer, an arithmetic logic unit, a plurality of general purpose registers; a cache memory means for storing and supplying data for said digital computer; said plurality of general purpose registers being useable as base and index registers; a virtual address generation means for generating a virtual address from said instruction received by said instruction register; said virtual address generation means generating said virtual address from a current address within said base register, index register contents, and said instruction register displacement bits; a predicted real address generation means, for generating a predicted real address, which comprises a history table, containing a first plurality of real addresses corresponding to a first plurality of previously used current addresses from said base register, a comparison means for comparing said current address in said base register with said first plurality of previously used current addresses contained within said history table, and an update means for updating said history table; said real addresses, from said history table, being stored in said predicted real address register, when said predicted real address generation means matches said current address from said base register with one of said first plurality of previously used current addresses contained within said history table; said cache memory means having a receiving means for receiving said predicted real address from said pre-dicted real address register during a first machine cycle, said cache memory means having a retrieval means for retrieving said stored data from said predicted real address location before said first machine cycle is complete; said translation look-aside buffer having a second plurality of real addresses corresponding to a first plurality of virtual addresses, said translation look-aside buffer having a selection means for select ing a real address corresponding to said virtual address stored in said virtual address register; and a comparison means for comparing said predicted real address with said real address selected by said translation look-aside buffer, when said predicted real address matches said real address then said arithmetic logic unit receives said stored data retrieved from said predicted address location of said cache memory means during a second machine cycle, when said predict ed real address does not match said real address then said cache memory means receives said real address from said translation look-aside buffer, said cache memory means retrieves said stored data from said real address location during a second machine cycle, said arithmetic logic unit receives said stored data retrieved from said real address location of said cache memory means during a third machine cycle.

Claim 12

A cache memory access system as in claim 7 wherein: said update means updates said history table when said predicted real address does not match said real address corresponding to said virtual address contained within said translation look-aside buffer, said update means retrieves said real address corre-sponding to said virtual address from said translation look-aside buffer, said update means retrieves said current address from said base register, said update means places said current address and said real address in said history table.

Claim 13

A cache memory access system as in claim 7 wherein: said update means updates said history table when said predicted real address does not match said real address corresponding to said virtual address contained within said translation look-aside buffer, said update means retrieves said real address corre-sponding to said virtual address from said translation look-aside buffer, said update means places said real address in said history table corresponding to said current address.

Claim 14

A cache memory access system as in claim 7 wherein: said comparison means of said predicted real address generation means compares a plurality of bits from said current address with a plurality of bits from current addresses contained within said first plurality of current addresses.

Claim 15

A cache memory access system as in claim 7 wherein: said predicted real address register receives said predicted real address before said first machine cycle begins; and said virtual address register receives said virtual address before said first machine cycle begins.

Claim 16

A cache memory access system as in claim 7 wherein: said selection of said real address corresponding to said virtual address by said translation look aside buffer being completed independently of said cache memory array receiving said predicted real address.

Claim 17

A cache memory access system as in claim 7 wherein: said comparison of said predicted real address with said real address being completed independently of said cache memory array receiving said predicted real address.

Claim 18

A cache memory access system as in claim 10 wherein: said update means updates said history table when said predicted real address does not match said real address corresponding to said virtual address contained within said translation look-aside buffer, said update means retrieves said real address corre-sponding to said virtual address from said translation look-aside buffer, said update means retrieves a plurality of bits from said current address, said update means places said plurality of bits and said real address in said history table.

Claim 19

A cache memory access system for a digital computer comprising: a virtual address register, a predicted real address register comprising low order bits and high order bits, a translation look-aside buffer, an arithmetic logic unit, a plurality of general purpose registers; a cache memory means for storing and supplying data for said digital computer; said plurality of general purpose registers being useable as base and index registers; a virtual address generation means for generating a virtual address from said instruction received by said instruction register; said virtual address being stored in said virtual address register, said virtual address comprising page offset bits and page address bits; said virtual address generation means comprising an added means for adding said instruction register displacement bits, to a current address contained within said base register specified by said instruction, and to said index register contents specified by said instruction; a predicted real address generation means, for generat ing a predicted real address, which comprises a history table containing a first plurality of real addresses corresponding to a first plurality of previously used current addresses from said base register, a transla tion look-ahead table containing a second plurality of real addresses corresponding to a second plurality of previously used current addresses from said base register, a selection means for selecting a real address from said translation look-ahead table corre sponding to said base register specified by said instruction, and an update means for updating said history table and said translation look-ahead table; said real address, from said translation look-ahead table, being stored in said predicted real address register, when said predicted real address generation means selects said real address from said translation look-ahead table; said cache memory means having a cache storage unit, a cache directory containing a plurality of real address-es, a receiving means for receiving said predicted real address from said predicted real address register during a first machine cycle and having a selection signal, and a retrieval means for retrieving said stored data from said predicted real address location before said first machine cycle is complete; said cache memory receiving means receives said predicted real address and subsequently transmits a plurality of real addresses and said selection signal to said cache memory retrieval means, said plurality of addresses being contained within said cache directory, said selection signal being generated by said receiving means from said predicted real address, said selection signal being transmitted independently of said plurality of addresses; said cache memory retrieval means retrieves data stored at each of said plurality of real addresses transmitted by said receiving means from said cache storage unit, said retrieval means selects said data associated with one of said plurality of addresses, said selection signal indicates said selection being made by said retrieval means; said cache memory retrieval means transmits said selected data to said arithmetic logic unit; said translation look-aside buffer having a third plurality of real addresses corresponding to a first plurality of virtual addresses, said translation look-aside buf fer having a selection means for selecting a real address corresponding to said virtual address stored in said virtual address register; and a comparison means for comparing said predicted real address with said real address selected by said trans ation look-aside buffer, when said predicted real address matches said real address then said arithmetic logic unit receives said stored data retrieved from said predicted address location of said cache memory means during a second machine cycle, when said predicted real address does not match said real address then said cache memory means receives said real address from said translation look-aside buffer, said cache memory means retrieves said stored data from said real address location during a second machine cycle, said arithmetic logic unit receives said stored data retrieved from said real address location of said cache memory means during a third machine cycle.

Claim 20

A cache memory access system for a digital computer comprising: a virtual address register, a predicted real address register comprising low order bits and high order bits, a translation look-aside buffer, an arithmetic logic unit, a plurality of general purpose registers; a cache memory means for storing and supplying data for said digital computer; said plurality of general purpose registers being useable as base and index registers; a virtual address generation means for generating a virtual address from said instruction received by said instruction register; said virtual address being stored in said virtual address register, said virtual address comprising page offset bits and page address bits; said virtual address generation means comprising an added means for adding said instruction register displacement bits, to a current address contained within said base register specified by said instruction, and to said index register contents specified by said instruction; a predicted real address generation means, for generat ing a predicted real address, which comprises a history table containing a first plurality of real addresses corresponding to a first plurality of previously used current addresses from said base register, a transla tion look-ahead table containing a second plurality of real addresses corresponding to a second plurality of previously used current addresses from said base register, a selection means for selecting a real address from said translation look-ahead table corre sponding to said base register specified by said instruction, and an update means for updating said history table and said translation look-ahead table; said real address, from said translation look-ahead table, being stored in said predicted real address register, when said predicted real address generation means selects said real address from said translation look-ahead table; said cache memory means having a cache storage unit, a cache directory containing a plurality of real address-es, a receiving means for receiving said predicted real address from said predicted real address register during a first machine cycle and having a selection signal, and a retrieval means for retrieving said stored data from said predicted real address location before said first machine cycle is complete; said cache memory receiving means receives said predicted real address and subsequently transmits a plurality of real addresses and said selection signal to said cache memory retrieval means, said plurality of addresses being contained within said cache directory, said selection signal being generated by said receiving means from said predicted real address, said selection signal being transmitted independently of said plurality of addresses; said cache memory retrieval means retrieves data stored at each of said plurality of real addresses transmitted by said receiving means from said cache storage unit, said retrieval means selects said data associated with one of said plurality of addresses, said selection signal indicates said selection being made by said retrieval means; said cache memory retrieval means transmits said selected data to said arithmetic logic unit; said translation look-aside buffer having a third plurality of real addresses corresponding to a first plurality of virtual addresses, said translation look-aside buf fer having a selection means for selecting a real address corresponding to said virtual address stored in said virtual address register; and a comparison means for comparing said predicted real address with said real address selected by said trans ation look-aside buffer, when said predicted real address matches said real address then said arithmetic logic unit receives said stored data retrieved from said predicted address location of said cache memory means during a second machine cycle, when said predicted real address does not match said real address then said cache memory means receives said real address from said translation look-aside buffer, said cache memory means retrieves said stored data from said real address location during a second machine cycle, said arithmetic logic unit receives said stored data retrieved from said real address location of said cache memory means during a third machine cycle.

Claim 21

A cache memory access system as in claim 15 wherein: said update means updates said history table when said predicted real address does not match said real address corresponding to said virtual address contained within said translation look-aside buffer, said update means retrieves said real address corresponding to said virtual address from said translation look-aside buffer, said update means retrieves said current address from said base register, said update means places said current address and said real address in said history table.

Claim 22

A cache memory access system as in claim 15 wherein: said update means updates said history table when said predicted real address does not match said real address corresponding to said virtual address contained within said translation look-aside buffer, said update means retrieves said real address corre-sponding to said virtual address from said translation look-aside buffer, said update means places said real address in said history table corresponding to said current address.

Claim 23

A cache memory access system as in claim 15 wherein: said predicted real address generation means updates said translation look-ahead table after any modifica-tion of general purpose register contents, said update means matches an address from a modified general purpose register to one of said plurality of previously used current addresses from said history table; said update means places said real addresses, from said history table, corresponding to said matched previously used current address in said translation look ahead table; said real address from said history table corresponds to said modified general purpose register in said translation look-ahead table after said placement by said update means. 1

Claim 24

A cache memory access system as in claim 15 wherein: said predicted real address generation means updates said history table when said predicted real address does not match said real address corresponding to said virtual address contained within said translation look-aside buffer, said update means retrieves said real address corre sponding to said virtual address from said translation ook-aside buffer, said update means retrieves a plurality of bits from said current address, said update means places said plurality of bits from said base register and said real address in said history table.

Claim 25

A cache memory access system as in claim 15 wherein: said predicted real address generation means updates said history table when said predicted real address does not match said real address corresponding to said virtual address contained within said translation look-aside buffer, said update means retrieves said real address corresponding to said virtual address from said translation look-aside buffer, said update means places said real address in said history table, said real address corresponds to said current address in said history table.