International Business Machines Corporation

Kimming K So

Hoichi Cheong

Dwain Alan Hicks

Kai Cheng

Hung Qui Le

George McNeil Lattimore

Gregory Francis Pfister

Thomas R Puzak

Rudolph N Rechtschaffen

James H Pomerene

Wen-Hann Wang

Michael Thomas Dibrino

Vern A Norton

Jin Chin Wang

Shien-Tai Pan

Evelyn A Melton

Bao-Binh Truong

David Bernstein

Hanaa Youssef

An apparatus is disclosed which supports memory updates within a data processing system including a number of processors. The apparatus includes a memory hierarchy including one or more upper levels of memory. Each upper level within the memory hierarchy includes one or more memory units which each store a subset of all data stored within an associated memory unit at a lower level of the memory hierarchy. Each memory unit at the highest level within the memory hierarchy is associated with a selected processor. In addition, the apparatus includes a reservation indicator associated with each memory unit within the memory hierarchy. For memory units at the highest level within the memory hierarchy, the reservation indicator specifies an address for which the processor associated with that memory unit holds a reservation. At each lower level within the memory hierarchy, the reservation indicator specifies addresses for which associated memory units at higher levels within the memory hierarchy hold a reservation. A reservation for a selected address within a memory unit is resolved at a highest level within the memory hierarchy at which a memory unit stores data associated with the selected address exclusive of other memory units at that level, thereby enhancing reservation protocol efficiency.

Method and system for memory updates within a multiprocessor data

An information handling system includes a cache memory architecture which includes a means for performing a direct lookup by identifying the double word in the cache using the congruence class ID field, a set ID field and a double word ID field of the request address, and sending the double word to the CPU, and if the tag of the identified double word does not match the tag of the request address, sending a cancel signal to the CPU, and the double word with a matched tag in the congruence class, and if no match occurs, reloading the line l1 into the improved cache from a lower level cache or from main memory. The line in the set identified by the set ID field replaces the least recently used line in the congruence class and its place is taken by the missing line.

Information handling system including a direct access set associative

Two processor controls for supporting efficient Firm Consistency while allowing out-of-order execution of Load instructions is provided. The Touch control operates when the processor stores a subsequent Store in a pending Store buffer while awaiting any outstanding Loads or Stores. The efficiency of the pending Store is improved by issuing a Touch of the data which pre-loads the line of data in the cache that is the subject of the store. The processor can complete out-of-order execution of a subsequently issued Load relative to a prior Load, but only to its finished state. The subsequently issued Load is not allowed to complete until the prior Load is completed. The Finished Load Cancellation control ensures that Firm Consistency is maintained by canceling any finished Loads, and subsequent instructions, when the subject of the Load is the same as an invalidation request from a multiprocessor.

Efficient firm consistency support mechanisms in an out-of-order

A multi-processor data processing system has a multi-level cache wherein each processor has a split high level (e.g., level one or L1) cache composed of a data cache (DCache) and an instruction cache (ICache). A shared lower level (e.g., level two or L2) cache includes a cache array which is a superset of the cache lines in all L1 caches. There is a directory of L2 cache lines such that each line has a set of inclusion bits indicating if the line is residing in any of the L1 caches. A directory management system requires only N+2 inclusion bits per L2 line, where N is the number of processors having L1 caches sharing the L2 cache.

Shared L2 support for inclusion property in split L1 data and

An access hazard detection technique in a pipelined cache controller sustains high throughput in a frequently accessed cache but without the cost normally associated with such access hazard detection. If a previous request (request in the pipeline stages other than the first stage) has already resulted in a cache hit, and it matches the new request in both the Congruence Class Index and the Set Index fields and if the new request is also a hit, the address collision logic will signal a positive detection. This scheme makes use of the fact that (1) the hit condition, (2) the identical Congruence Class Index, and (3) the Set Index of two requests are sufficient to determine that they are referencing the same cache content. Implementation of this scheme results in a significant hardware saving and a significant performance boost.

High performance/low cost access hazard detection in pipelined cache

A system and method for identifying which incoming write data is valid and for insuring that stale data does not overwrite valid data within system memory within a symmetrical multiprocessor data processing system. Upon receipt of a Load Miss request from a processor, a stale bit is established and set equal to zero. A determination is then made of which other processor has ownership of the requested cache line. The requested cache line is then transferred in a cache-to-cache transfer from the second processor to the first processor. If the first processor further modifies the cache line and writes back the cache line to system memory before the original owner of the cache line writes back the stale data with an acknowledgment of the cache-to-cache transfer, the stale bit is set to one. Upon receipt from the acknowledgment from the original owner of the cache line, the stale data is dropped when it is determined that the stale bit has been set.

System and method for handling stale data in a multiprocessor system

The present invention provides balanced cache performance in a data processing system. The data processing system includes a first processor, a second processor, a first cache memory, a second memory and a control circuit. The first processor is connected to the first cache memory, which serves as a first level cache for the first processor. The second processor and the first cache memory are connected to the second cache memory, which serves as a second level cache for the first processor and as a first level cache for the second processor. Replacement of a set in the second cache memory results in the set being invalidated in the first cache memory. The control circuit is connected to the second level cache and prevents replacing from a second level cache congruence class all sets that are in the first cache.

Hierarchical cache arrangement wherein the replacement of an LRU entry

A high performance shared cache is provided to support multiprocessor systems and allow maximum parallelism in accessing the cache by the processors, servicing one processor request in each machine cycle, reducing system response time and increasing system throughput. The shared cache of the present invention uses the additional performance optimization techniques of pipelining cache operations (loads and stores) and burst-mode data accesses. By including built-in pipeline stages, the cache is enabled to service one request every machine cycle from any processing element. This contributes to reduction in the system response time as well as the throughput. With regard to the burst-mode data accesses, the widest possible data out of the cache can be stored to, and retrieved from, the cache by one cache access operation. One portion of the data is held in logic in the cache (on the chip), while another portion (corresponding to the system bus width) gets transferred to the requesting element (processor or memory) in one cycle. The held portion of the data can then be transferred in the following machine cycle.

Multiprocessor system with shared cache and data input/output circuitry

Method and apparatus for predicting the outcome of branch instructions subject to execution in a multiple processor digital computer. Pipelining is a popular technique to accelerate the data processing rate of modern computers, and in particular the RISC architecture class of workstations. Accurate prediction of branch instructions is exceptionally important to the efficient use of pipelines, in that erroneous predictions require both the purge and reload of all affected processor pipelines. According to the present invention, branch prediction is based upon a correlation between a history of successive prior branches and a specified branch instruction. In a preferred practice, a branch prediction table is created. The fields in the table are derived and thereafter updated based upon the correlated combination of outcomes from prior branches and the branch address under consideration.

Correlation-based branch prediction in digital computers

Error correction code ('CECC') generation within a directory or memory controller is distributed between generation of an ECC for the tag and status portions of a directory entry and then summed to produce the ECC bits for the directory entry. The ECC generation may be performed for entries with respect to a cache for a uniprocessor or multiprocessor system or for system memory within such a data processing system. The ECC generation of the present invention reduces by one or more cycles the required time utilized for updating a directory entry.

System and method for error correction code generation

A system and method for managing caches in a multiprocessor having multiple levels of caches. An inclusion architecture and procedure are defined through which the L2 caches shield the L1 caches from extraneous communication at the L2, such as main memory and I/O read/write operations. Essential inclusion eliminates special communication from the L1 cache to the L2, yet maintains adequate knowledge at the L2, regarding the contents of the L1, to minimize L1 invalidations. Processor performance is improved by the reduced communication and the decreased number of invalidations. The processors and L1 caches practice a store-in policy. The L2 cache uses inclusion bits to designate by cache line a relationship between the line of data in the L2 cache and the corresponding lines as they exist in the associated L1 caches. Communication and invalidations are reduced through a selective setting/resetting of the inclusion bits and related L2 interrogation practice.

System and method for practicing essential inclusion in a multiprocessor

An electronic computer system including a central processor and a hierarchical memory system having a large relatively low speed random access system memory and a small high speed set-associative cache memory including a data store section for storing lines of data from the system memory and a cache directory for indicating, by means of line identifier fields at any time, the lines of the system memory data currently resident in cache, is provided with a way to improve the distribution of data across the congruence classes within the cache. A mechanism is provided for performing a permutation operation on an M bit portion (X) of the system memory address, which permutation determines the congruence class into which the address will map. The permutation mechanism performs a bit-matrix multiplication of said M-bit address with an M.times.M matrix (where M is a real positive integer greater than 1) to produce a permuted M-bit address (X'). The directory controls utilize the permuted M-bit address (X') to determine the congruence class of any given memory access and automatically access the congruence class of the permuted address (X') subsequent to the permutation operation to determine if one of the line identifiers which identifies, every member of a congruence class currently stored in the directory, matches an identifier field from the memory access request from the CPU. If the match is successful the data store portion of the cache is accessed at the permuted M-bit address (X') and the requested data line is accessed at the address field specified by the CPU.

Mechanism for improving the randomization of cache accesses utilizing

A serializatin debugging facility operates by assisting the computer programmer in the selection of parallel sections of the parallel program for single processor execution in order to locate errors in the program. Information is collected regarding parallel constructs in the source program. This information is used to establish program structure and to locate sections of the program in which parallel constructs are contained. Program structure and the locations of parallel constructs within a program are then displayed as a tree graph. Viewing this display, a programmer selects parallel sections for serialization. Object code for the program is then generated in accordance with the serialization instructions entered by the programmer. Once executed, the programmer can compare the results of execution of parallel sections of the program in a single processor and a multiprocessor environment. Differing execution results in each environment is indicative of a parallel programming error which can then be corrected by the programmer. The programmer can repeat these steps, each time selecting different sections of the program for serialization. In this way, erroneous sections of the program can be localized and identified.

Debugging parallel programs by serialization

A prefetching mechanism for a memory hierarchy which includes at least two levels of storage, with L1 being a high-speed low-capacity memory, and L2 being a low-speed high-capacity memory, with the units of L2 and L1 being blocks and sub-blocks respectively, with each block containing several sub-blocks in consecutive addresses. Each sub-block is provided an additional bit, called a r-bit, which indicates that the sub-block has been previously stored in L1 when the bit is 1, and has not been previously stored in L1 when the bit is 0. Initially when a block is loaded into L2 each of the r-bits in the sub-block are set to 0. When a sub-block is transferred from L1 to L2, its r-bit is then set to 1 in the L2 block, to indicate its previous storage in L1. When the CPU references a given sub-block which is not present in L1, and has to be fetched from L2 to L1, the remaining sub-blocks in this block having r-bits set to 1 are prefetched to L1. This prefetching of the other sub-blocks having r-bits set to 1 results in a more efficient utilization of the L1 storage capacity and results in a highter hit ratio.

Growing community of inventors

Austin, TX, United States of America

Kimming K So