Memory and buffer arrangement for digital computers

In a digital, stored program computer having a central processing unit for handling data and instructions, a memory system comprising:

• a plurality of random access memories having different access speeds and capacities, a memory of the plurality of relatively high access speed having relatively low capacity, a memory of the plurality having relatively lower access speed having higher capacity accordingly;
• means included in each and all memories and respectively capable of responding to the same address signal when a location so defined is represented in the respective memory, and providing access to such a location when the respective address signal is received;
• means for controlling the loading of memories of the plurality so that each memory of the plurality having lower capacity than at least one other memory of the plurality contains a subset of the information of that other memory of the plurality having larger capacity;
• means for controlling access to the cascaded memory system, by causing an address signal defining a location to be applied sequentially to the means responding to address signals in the several memories, beginning with the memory of fastest access speed and seeking access to the same information in a memory of the plurality of lower access speed if all memories of the plurality of higher access speed do not contain the information sought;
• and
• means connecting all memories to the central processing unit whereby the information demanded by the processing unit may be provided directly to the unit from the particular memory of the plurality of highest access speed of those having the information available.

In a digital, stored program computer having a random accessible memory and a central processing facility with an information flow path to and from memory, from and to the processing facility including a path for memory addresses to the memory and paths for other information taken from and to be provided to memory locations, the improvement comprising:

• a random accessible buffer having a plurality of blocks, each block having a plurality of multi-bit storage locations, each block further having means for storing addresses for identifying the locations in the block each as a location corresponding to an address and location in the memory, the buffer upon receiving addressing signals corresponding to an address identifying a location in the buffer by its addressing signals providing access to that location, the buffer having significantly less storage space than the memory but significantly faster access to each location than to any memory location;
• a random accessible cache having a plurality of blocks, each block having a plurality of multi-bit storage locations, each block further having means for storing addresses for identifying the locations in the block each as a location, corresponding to an address and locations in the memory and in the buffer as stored therein, the cache upon receiving addressing signals corresponding to an address identifying a location in the cache by its addressing signals providing access to that location, the cache having significantly less storage space than the buffer but significantly faster access to each location than the buffer;
• means connecting the cache to the processing facility for transmitting first to the cache memory addresses as access requests to locations in the cache, for reading in each instance the content of a location whose stored address corresponds to such cache memory address, the cache having means for transferring the content of a successfully accessed cache location to the processing facility;
• means for causing the memory address provided by the processing facility to be transferred to the buffer if a corresponding location was not found in the cache;
• means connected to the buffer for receiving the said memory address as transferred by the last-mentioned means and for transferring the content of a successfully accessed buffer location to the processing facility, said means also capable of receiving from the processing facility information for storage in a successfully accessed buffer location as defined by the address irrespective of whether or not that location is also represented in the cache;
• means for causing the memory address provided by the processing facility to be transferred to the memory if a corresponding location is not represented in the cache and in the buffer, so that the particular memory location provides information to the processing facility;
• means for selectively replacing the content and address information of locations in the cache and in the buffer with information taken from the memory;
• and
• means for transferring the content of a buffer location which received information from the processing facility, to the memory subsequently to receiving such information.

In a digital, stored program computer having a random access memory system and a central processing facility with an information flow path to and from the memory system, from and to the processing facility including a path for memory addresses to the memory system and paths for other information taken from and to be provided to locations in the memory systems, the computer having additional facilities for updating the information in the memory system independently from the central processing facility, the improvement comprising:

• a random accessible cache having a plurality of blocks, each block having a plurality of multi-bit locations, each block further having means for storing addresses for identifying the locations in the block each as a location corresponding to an address and locations in the memory system, the cache upon receiving addressing signals corresponding to an address identifying a location in the cache by its addressing signals providing access to that location, the cache having significantly less storage space than the memory system but significantly faster access to each location than the memory system;
• first means connecting the cache to the processing facility for transmitting to the adress storage means in the cache memory addresses as access requests to locations in the cache, for reading in each instance the content of a location whose stored address corresponds to such memory address, the cache having means for transferring the content of a successfully accessed cache location to the processing facility;
• second means for causing the memory address provided by the processing facility to be transferred to the memory system if a corresponding location is not represented in the cache, for accessing the location so that the particular memory location having said latter address provides information it contains to the processing facility;
• third means for replacing the content of locations in the cache with a subset of information taken only from the memory by operation of the second means;
• fourth means connected to the memory for receiving a memory address and for receiving from the processing facility information for storage in a memory location as defined by the address, independently from whether or not that location is represented in the cache;
• and
• means for limiting the number of accesses to a location in the cache and upon indication that the limit has been reached forcing access instead to the corresponding location in the memory system by operation of the first means.

In a digital, stored program computer having a random access memory, a central processing facility and additional processing facilities each having information flow paths to and from memory, including a path for memory addresses to the memory and paths for other information taken from and to be provided to memory locations, further including a port system for controlling access to the memory, the processing facilities connected to the port system for seeking access to the memory independently from one another, the improvement comprising:

• a random accessible buffer located between the memory and the port system and having a plurality of blocks, each block having a plurality of locations, each block further having means for storing addresses for identifying the locations in the block each as a location corresponding to an address and location in the memory, the buffer upon receiving addressing signals corresponding to an address identifying a location in the buffer by its addressing signals providing access to that location, the buffer having significantly less storage space than the memory but significantly faster access to each location than to any memory location;
• first means for causing a memory address provided by either of the processing facilities to be transferred to the buffer through the port;
• second means connected to the buffer for receiving the said memory address as transferred by the last-mentioned means and for transferring the content of a successfully accessed buffer location to the respective processing facility, or for receiving from the respective processing facility information for storage in a successfully accessed buffer location as defined by the address;
• third means for causing the memory address provided by the processing facility for a demand of information from the location identified by that address to be transferred to the memory if a corresponding location is not represented in the buffer, so that the particular memory location provides information to the respective processing facility;
• fourth means for updating the content of a group of locations in the buffer with information taken from the memory when provided by the buffer to the respective processing facility by the third means;
• and
• means for transferring the content of a buffer location which received information from the processing facility, to the memory independently from the time of receiving such information.

In a digital, stored program computer having a random accessible memory and a central processing facility with an information flow path to and from memory, from and to the processing facility including a path for memory addresses to the memory and paths for other information taken from and to be provided to memory locations, the improvement comprising:

• a random accessible buffer having a plurality of storage blocks, each block having a plurality of storage locations, each block further having means for storing addresses for identifying the locations in the block each as a location corresponding to an address and location in the memory, the buffer upon receiving addressing signals corresponding to an address identifying a location in the buffer by its addressing signals providing access to that location, the buffer having significantly less storage space than the memory but significantly faster access to each of its location than to any memory location;
• a random accessible cache having a plurality of blocks, each block having a plurality of storage locations, each block further having means for storing addresses for identifying the locations in the block each as a location corresponding to an address and location in the memory and in the buffer as stored therein, the cache upon receiving addressing signals corresponding to an address identifying a location in the cache by its addressing signals providing access to that location, the cache having significantly less storage space than the buffer but significantly faster access to each location than the buffer;
• means connecting the cache to the processing facility for transmitting to the address storage means in the cache memory addresses for access request to locations in the cache and for purposes of reading in each instance the content of a location whose stored address corresponds to such memory address, the cache having means for transferring the content of a successfully accessed cache location to the processing facility;
• means for causing the memory address provided by the processing facility to be transferred to the buffer if a corresponding location was not found in the cache;
• means connected to the buffer for receiving the said memory address as transferred by the last-mentioned means and for applying such address to the address storage means in the buffer, for transferring the content of a successfully accessed buffer location having said address to the processing facility;
• or for receiving from the processing facility information for storage in a successfully accessed buffer location as defined by the address if represented in the buffer, a buffer location being made available for storage of the received information including storage of the respectively associated address;
• means for causing the memory address provided by the processing facility to be transferred to the memory if a corresponding location is represented neither in the cache nor the buffer for accessing the location, so that the particular memory location having said latter address provides information it contains to the processing facility;
• first and second means for establishing representation of availability of storage space respectively in the cache and in the buffer on the basis of frequency of usage and access to locations therein;
• means for providing information related to a location as provided by the buffer or by the memory together with information related to additional locations, to the cache to be stored in a block of locations of the cache determined on the basis of the operation of the first means for establishing, and including storing the address of such memory locations in the means for storing addresses in the cache in association with the latter cache locations to render each of the locations in that block addressible by corresponding address signals when provided by the processing facility;
• and
• means for providing information of a location as provided by the memory to the buffer to be stored in the buffer together with additional information for a buffer block and in locations therein as determined on the basis of the operation of the second means for establishing for storing an addressible block in the buffer accordingly.

In a digital, stored program computer having a random access memory, a central processing facility and additional processing facilities each having information flow paths to and from memory, from and to the processing facilities including a path for memory addresses to the memory and paths for other information taken from and to be provided to memory locations, further including a port system for controlling access to the memory, the processing facilities connected to the port system for seeking access to the memory independently from one another, the improvement comprising:

• a random accessible buffer located between the memory and the port system and having a plurality of blocks, each block having a plurality of locations, each block further having means for storing addresses for identifying the locations in the block each as a location corresponding to an address and location in the memory, the buffer upon receiving addressing signals corresponding to an address identifying a location in the buffer by its addressing signals providing access to that location, the buffer having significantly less storage space than the memory but significantly faster access to each location than to any memory location;
• first means for causing a memory address provided by either of the processing facilities to be transferred to the buffer through the port;
• second means connected to the buffer for receiving the said memory address as transferred by the lastmentioned means and for transferring the content of a successfully accessed buffer location to the respective processing facility;
• third means for receiving from the respective processing facility information for storage in an address independently of whether or not the location so identified is represented in the buffer;
• fourth means for causing information as received by the third means to be stored in the buffer in the location identified by the address in the buffer or if not present, in a location elsewhere in the memory system subsequently identified by that address;
• fifth means for causing the memory address provided by the processing facility for a demand of information from the location identified by that address to be transferred to the memory if a corresponding location is not represented in the buffer, so that the particular memory location provides information to the respective processing facility;
• sixth means for replacing the content of locations in the buffer with a subset of information taken from the memory when provided to the respective processing facility by the third means;
• and
• means for transferring the content of a buffer location which received information from the processing facility, to the memory subsequently to the time of receiving such information.