Hierarchical data store with look-ahead action

• US 4,086,629 A
• Filed: 06/28/1976
• Issued: 04/25/1978
• Est. Priority Date: 07/09/1975
• Status: Expired due to Term

• Current Assignee: International Computers Limited (Fujitsu Limited)
• Original Assignee: International Computers Limited (Fujitsu Limited)
• Inventors: Jones, John Austin, Procter, Brian John, Desyllas, Peter Leo Lawrence
• Primary Examiner(s): Zache, Raulfe B.
• Application Number:
  US05/700,720
• Time in Patent Office: 666 Days
• Field of Search: 340/172.5, 364/200 MS
• US Class Current: 711/213
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 2212/6026 Prefetching based on access pattern detection, e.g. stride based prefetch

Abstract

A hierarchical data storage system comprises a main store and a smaller, faster slave store containing data currently required for processing. The memory system responds to a store access command to retrieve an item of data. In addition, for certain types of store access command, the system performs a look-ahead action to ensure that the slave store is loaded with another data item which forms part of a possible sequence. In certain cases, a test is made to determine whether the possible sequence is in the ascending or descending direction, and the look-ahead access is then made in the appropriate direction.

Claims

1. A data storage system comprising a main store, a slave store of smaller size but faster access time than the main store, means responsive to a set of store access commands for accessing data items from the slave store, each said store access command having a store access address associated with it, and look-ahead logic comprising:

a. means responsive to one of a sub-set of said store access commands to generate an increment signal,

b. means for adding said increment signal to said store access address to produce a look-ahead address, and

c. means for applying the look-ahead address to the main store to access a data item from the main store for writing into the slave store.

2. A data storage system comprising a main store, a slave store of smaller size but faster access time than the main store, an address register, and means for applying the contents of the address register to the slave store in response to a store access command, to access a data item from the slave store, wherein the invention consists of look-ahead logic comprising:

a. means responsive to a store access command for determining the direction of a possible sequence of data items including the item currently being accessed, to produce a positive or negative increment signal representing said direction;

b. means for adding said increment signal to the contents of said address register, to produce a look-ahead address specifying a subsequent data item in said possible sequence; and

c. means for applying said look-ahead address to the main store to access said subsequent data item from the main store and for writing that data item into the slave store.

3. A system according to claim 2 wherein said means for determining the direction of a possible sequence comprises means for testing whether an item having an address displaced in a predetermined direction from the address currently in the address register is present in the slave store, and for generating said positive or negative increment signal in accordance with the result of that test.

4. A system according to claim 2 wherein the main store is divided into sections each containing four data items and the slave store is divided into cells each of which contains four data items (0,) (1,) (2,) (3) and which is mapped on to one section of the main store, and wherein said means for determining the direction of a possible sequence of data items comprises:

i. means responsive to a store access command addressing item (0) in one of said cells, for testing whether items (2) and (3) in that cell are valid and, if so, generating a negative increment signal;

ii. means responsive to a store access command addressing item (1) in a cell, for testing whether items (2) and (3) in that cell are invalid and, if so, generating a positive increment signal;

iii. means responsive to a store access command addressing item (2) in a cell, for testing whether items (0) and (1) in that cell are invalid and, if so, generating a negative increment signal; and

iv. means responsive to a store access command addressing item (3) in a cell, for testing whether items (0) and (1) in that cell are valid and, if so, generating a positive increment signal.

5. A data storage system comprising:

a. a main store;

b. a slave store of smaller size but faster access time than the main store;

c. an address register;

d. means responsive to a store access command of a first type, for utilising the contents of the address register to access a data item from the slave store, without any look-ahead action;

e. means responsive to a store access command of a second type, for utilising the contents of the address register to access a data item from the slave store and then incrementing the contents of the address register by a positive amount to produce a look-ahead address and utilising said look-ahead data item from the main store for writing into the slave store; and

f. means responsive to a store access command of a third type, for utilising the contents of the address register to access a data item from the slave store and then determining the direction of a possible sequence of data items including said item accessed from the slave store, incrementing the contents of the address register by a positive or negative amount according to said direction to produce a look-ahead address, and utilising said look-ahead address to access a look-ahead data item from the main store for writing into the slave store.