A memory system is disclosed which includes a large main memory having information block storage locations addressable by an address consisting of set and tag bits, two buffer memory banks each having storage locations addressable by the set bits for the storage of tags and associated information blocks, and a small content-addressed memory for the storage of associated tags, sets, and information blocks. Initially, all information blocks are in the main memory, and accessing an information block results in a transfer of the block with its tag to one or the other of the buffer memories at a location determined by the set bits. Later, when another information block belonging to the same set is accessed, it is stored in the other buffer memory bank. Subsequently, when a third information block of the same set is accessed, one of the information blocks is displaced from the buffer memory bank to the content-addressed memory where it is stored with its tag and set bits. The system operates so that there is a high probability that a desired information block will be present and rapidly accessible in one of the buffer memory banks or the content-addressed memory.
A buffer storage control apparatus selectively employs the conventional "least-recently-used" (LRU) algorithm or the "all-used" (AU) algorithm to determine which block of data in the buffer storage unit is to be replaced by new data. The AU algorithm relies on the fact that under certain conditions, such as the straight transfer of a block of data from a main memory to an output device under the control of an I/O supervisor, the block of data so transferred will no longer be needed. The control apparatus therefore detects such a data transfer and selectively allocates buffer storage in accordance with the AU or LRU algorithms.
Lookahead circuits for an address relocation translator containing stacks of segmentation registers (SR's), each of which may be loaded with an assigned address of a physical block in a main memory. An additional pair of bit positions are provided with each SR to receive lookahead bits from decoder loading circuits which decode a physical address being loaded into the SR to indicate the storage unit containing the addressed block. During each subsequent address translation, the loaded lookahead bits are outgated while the block address is being read from an SR. The lookahead bits are decoded for selecting the required storage unit component of the main memory, and a translator interface is switched to that unit. The lookahead bits are handled by parallel high-speed circuits which operate faster than the larger translation circuits handling the block address being read from the SR. As a result, the required storage unit is selected before a storage unit cycle is generated by the translator for accessing the addressed block.
The retrieval of stored data by means of a search word or search key by using, a hashing method. For this purpose, the search key is resolved into a polynomial having the form of ##EQU1## where i=control variable, k=its maximum value, w.sub.i =polynomial coefficient, p=a power of 2, m=number of search keys in an address table stored in the memory (7). The search process occurs by means of a recursive hashing function having the form of ##EQU2## using hashing function tables and address sub-tables stored in the memory. The address compared circuit, having three temporary memories for the polynomial coefficients w.sub.i, a multiplexer, the memory, an adder registers, a comparator, an edge-triggered JK-type flip-flop with an AND gate connected to its output, and a control unit makes it possible to achieve an inexpensive hardware implementation of the search method.
A data processing system having a main storage-buffer memory hierarchy in which various congruence mapping class configurations are dynamically provided by utilizing a fixed format main storage-buffer array unit. A directory is provided which generates buffer slot addresses in response to the class address portion of a main storage address word. Various block sizes of data may be associatively mapped into predefined areas of a buffer array. A single integrated circuit chip containing both main memory and buffer arrays may be used to implement various congruence classes by the selective application of input signals provided by the main storage address and a hierarchy directory.
Apparatus is disclosed for transferring data between multiple peripheral processors (PPs) which are operating under control of a host processor in a multi-processor computer system. In a high data rate application a number of dedicated special purpose PPs are arranged in fixed sequence to provide individual data processing steps. A data path is provided between each PP data memory and the next. A PP transfer unit associated with each PP data memory controls data transfer simultaneously between all PPs. Separate read/write address mapping is provided for each PP data memory. Control information may be associated with each mapped PP data memory location to provide logic functions and data rearrangements during the transfer process. Data from several PPs may be interleaved or may be logically or arithmetically combined with other PP data or constant information.
