Prefetching mechanism for a high speed buffer store

Claim 2

A procedure for prefetching blocks of information from main storage to a high speed buffer store in a data processing system, in which addresses of information blocks contained in said high speed buffer store are stored in a directory, characterized in that the following steps are executed for each access of an appropriate subset of accesses to stored information blocks by the processor of the system: - storing a parent identifier which is derived from the respective current-access block address, in a first-level position of an additional shadow directory if it is not stored therein already, and the address of a subsequently accessed block as a descendant address in a second-level position of said shadow directory, which is associated to said first-level position, or - if a parent identifier derived from the respective current-access block address is already stored in a first-level position of said shadow directory, obtaining from the respective associated second-level position a descendant address if validly stored therein, and fetching the information block identified by said obtained descendant address from main storage into said high speed buffer store if it is not resident therein already.

Claim 3

Procedure in accordance with claim 1, characterized in that - if the parent identifier derived from a current-access block address is not found in a first-level position of said shadow directory, it is entered in the first-level position having the least-recently used entry, and - a subsequent block address actually used after said current-access block address is stored in a subsequent access cycle in that second-level position of the shadow directory which is associated with the first-level position where said parent identifier was stored. 3. Procedure in accordance with claim 1 or 2, characterized in that - a confirmation bit is stored in said shadow directory in association with each parent identifier in a first-level position, and that - in dependence of the binary value of said confirmation bit, a descendant address stored in a respective associated second-level position is either used as valid address for prefetching, or is ignored thus avoiding a prefetch operation with that descendant address. 4. Procedure in accordance with claim 3, characterized in that - if a prefetch operation is made using a validly stored descendant address from a second-level position of the shadow directory, the respective descendant address and its associated parent identifier from the associated first-level position are registered separately, - a determination is made subsequently whether the prefetched information block is actually accessed in the high speed buffer store, and - if the prefetched information block was not used, the confirmation bit associated with the respective parent identifier is reset to a value that prevents further use of the respective descendant address for prefetching. 5. Procedure in accordance with claim 4, characterized in that - a plurality of descendant addresses which were used for a prefetch operation, and their respective associated parent addresses are stored as prefetch address pairs in a prefetch confirmation buffer having a plurality of entries, - a usage indicator bit associated with each entry in said prefetch confirmation buffer is reset to a first binary value when a prefetch address pair is stored in the respective entry, - the usage indicator bit of any stored prefetch pair is set to a second binary value if the information block which was prefetched with the descendant address of the respective prefetch address pair is actually accessed in the high speed buffer. 6. Procedure in accordance with claim 5, characterized in that - if an old prefetch address pair is replaced in the prefetch confirmation buffer by a new prefetch address pair, the value of the usage indicator bit of the old prefetch pair is tested and, - if the usage bit of a replaced old prefetch address pair still had the first binary value, the confirmation bit associated with the parent identifier of the respective replaced prefetch address pair, is reset in the shadow directory to a binary value that prevents further use of the descendant address stored in the associated second-level entry for prefetching. 7. Procedure in accordance with claim 1, characterized in that - in the shadow directory, more parent identifiers are maintained in first-level positions than information blocks are stored in the high speed buffer store, so that parent identifiers derived from the block addresses of information blocks that were replaced already in the high speed buffer store are still present in the shadow directory. 8. Procedure in accordance with claim 1, characterized in that for each access to the high speed buffer store by an information block address, a determination is made whether the access is for instructions or operands, and - only if the access is for instructions, an updating of the shadow directory and a prefetching operation are effected, whereas for an access to operands, no addresses are stored in the shadow directory and no prefetch operations are made. 9. Procedure in accordance with claim 1, characterized in that in a system in which usage-age indication is maintained for entries in the high-speed buffer store and its directory, - a determination is made for each access to an information block in the high speed buffer store, whether the respective information block is the most-recently used, and that. - in case of access to a most-recently used information block, no updating of the shadow directory and no prefetching operation are effected. 10. Procedure in accordance with any one of the preceding claims, characterized in that in a system in which the directory of the high-speed buffer is separated into set-associative classes, also the shadow directory is separated into the same number of classes. 11. Procedure in accordance with claim 2, characterized in that - the subsequent block address stored in the second-level position of the shadow directory is the address of the information block actually next accessed after the information block from whose address the parent identifier was derived. 12. Procedure in accordance with claim 2, characterized in that in a system in which a usage-age indication is maintained for entries in the high-speed buffer store and in its directory - the subsequent block address stored in the second-level position of the shadow directory is the address of the first information block whose access changes said usage-age indication. 13. Procedure in accordance with claim 2, characterized in that - the subsequent block address stored in the second-level position of the shadow directory is the address of the next block which is not in the high-speed buffer and must be fetched from main storage when access is attempted. 14. Procedure in accordance with claim 1, characterized in that - for each access to an information block by the processor, a determination is made whether the access is for an instruction or for an operand, and - if the access is for an instruction, the parent identifier derived is the information block address actually used for that access, but - if the access is for an operand, the parent identifier derived is a concatenation of a portion of the address of the information block containing the currently executed instruction, and of a portion of the address of the information block containing the operand to be accessed. 15. Cache buffer storage arrangement in a data processing system, for enabling prefetching of information lines from main store to a high speed cache buffer store, characterized in that it includes besides the cache buffer store (Fig. 2A) and its real cache directory (11, Fig. 1; 11, Fig. 2B): - a secondary cache directory (13, 15, Fig. 1; 23, Fig. 3) comprising a plurality of entry position pairs (P, Q, Fig. 1; 25, Fig. 3; 25, 27, 29, Fig. 4), each pair including a first-level entry position (P, 27) for a parent identifier and an associated second-level entry position (Q, 29) for a descendant address, whereby the addresses of any two information blocks which where accessed in sequence can be stored as a parent- identifier/descendant-address pair in an entry position pair of said secondary cache directory, for later use in a prefetch operation. 16. Arrangement in accordance with claim 15, characterized in that - the number of said entry position pairs (25, Fig. 3; 25, 27, 29, Fig. 4) in said secondary cache directory (23, Fig. 3) is at least twice as large as the number of entry positions (21, Fig. 2B) in said real cache directory (11, Fig. 2B) which in turn corresponds to the number of information block storage areas (17, Fig. 2A) in said cache buffer store (Fig. 2A), whereby said first-level entry positions in said secondary cache directory are sufficient in number to hold as parent identifiers, addresses of information blocks that are presently stored in cache as well as of information blocks that are no more stored in cache. 17. Arrangement in accordance with claim 15, characterized in that - for each said entry position pair (P, Q, 25, 27) in said secondary cache directory (13, 15, Fig. 1; 25, 27, 29, Fig. 4), an additional field (CF, 31) is provided for a confirmation indication, whereby the address pair contained in the respective entry position pair can be designated as valid or invalid in dependence of actually occuring address sequences. 18. A procedure for prefetching blocks of information from main storage to a high speed buffer store in a data processing system, in which addresses of information blocks contained in said high speed buffer store are stored in a directory, characterized by: - storing the addresses of pairs of information blocks of which one is accessed subsequently to the other, as associated pairs of parent address and descendant address, respectively, in an additional shadow directory, and - when an address that is used by the processor for accessing a block of information is already stored as parent address in the shadow directory, prefetching the information block identified by the associated descendant address to the high speed buffer store if it is not resident therein already.

Claim 4

Procedure in accordance with claim 18, characterized in that - the high speed buffer store and its directory as well as the shadow directory are operated in set-associative sections, - for the shadow directory, a usage based replacement mechanism is provided which is separate from the replacement mechanism of the directory, and which is separate for each set-associative section, and - an associative searching mechanism is provided only for the parent addresses of said associated address pairs in the shadow directory.