International Business Machines Corporation

Lishing Liu

Russell Dean Hoover

Joseph L Temple, Iii

John Christopher Willis

Michael Ignatowski

Matthew A Krygowski

Gregory Salyer

Frederick Jacob Ziegler

Donald W Price

Patrick M Gannon

Yee-Ming Ting

David R Pruett

William K Rodiger

Donald Francis Baldus

Jih-Kwon Peir

Anderson H Hunt

Michael P Witt

Joseph O Celtruda

Kein A Hua

A multiprocessor in which processing units have local private caches and records are stored on at least a first global storage control unit. An interconnection system provides node to node data and synchronization communications between processing units and the first global storage control unit. The global storage control unit includes a coherency controller for tracking each instance of records owned by the global storage control unit currently resident on the processing units. Each processing unit executes a cache management process for freeing intervals of the local cache for the processing unit. Upon identification of an interval, the processing unit sends empty notification to the global storage control unit owning the record an instance of which was resident in the interval. Thereafter the interval is marked as invalid in a cache directory for the processing unit and indicia for the instance is deleted from a coherency directory for the global storage control unit.

System and method for empty notification from peer cache units to global

An improved history table is disclosed in which at least some of the entries are stored and accessed based upon the address of an instruction which historically preceeds the branch instruction itself. The access address may be used to determine the location of the entry in the table and/or may be stored in whole or in part in the entry itself. Furthermore, the improved history table may be of any known type including but not limited to branch history table types and decode history table types. The entries in the improved history table preferably are stored and accessed by the address of the preceeding taken branch target and preferably contain a number indicative of the number of instructions between the access address and the address of the branch instruction or its target.

History based branch prediction accessed via a history based earlier

A cache control maintains a history table SETLAT for the prediction of line entry (i.e., set member) within a congruence class for cache accessing. For a given cache access, a SETLAT entry can be selected based on the requesting logical address bits directly. The selection of a SETLAT entry may also be based on the hashing of such logical address bits together with other information in order to achieve sufficient randomization. A similar hashing history table may be devised to predict virtual address translation information with high accuracy. Such prediction mechanisms not only allow efficient implementation of the cache access path but also offer the opportunity of achieving multiple accesses per cycle. The proposed prediction method also provides a generic approach to efficient implementations for various directory based table accesses.

History table for set prediction for accessing a set associative cache

A 1-dimensional history table, which has been named a TLBLAT, is used to predict some or all of the real address bits that correspond to (i.e., translate from) any given virtual page address in order to provisionally access a real address based cache. The selection of a TLBLAT entry from given virtual address is based on certain address bits in the virtual address. The selection of a TLBLAT entry may also be based on the hashing of such virtual address bits together with other information in order to achieve sufficient randomization. At the minimum, each TLBLAT history table entry records the bits (one or more) necessary for prediction of the congruence class in a real address based cache. The set-associativity of the cache may be as low as one (i.e., a direct-mapped cache). More information may be included in each TLBLAT entry in order to facilitate various design considerations and it is possible even to combine a translation lookaside buffer (TLB) function with the TLBLAT function into a single physical table that provides the functions of both.

History table for prediction of virtual address translation for cache

A method for increasing cache concurrency in a multiprocessor system. In a multiprocessor system having a plurality of processors each having a local cache in order to increase concurrency the directory entry for a line in local cache will be assigned an LCH bit for locally changed status. If the last cache to hold the line had made a change to it this bit will be set on. If not, the bit will be off and thereby allow the receiving or requesting cache to make change to the line without requiring a main storage castout.

Multiple caches using state information indicating if cache line was

Apparatus, and accompanying methods for use therein, for translating virtual page addresses in one address space, e.g. virtual, to page addresses in a second address space, e.g. real, and specifically for increasing the speed of such translations by translating multiple contiguous virtual page addresses upon the occurrence of a miss in a translation lookaside buffer (TLB). In response to a TLB miss, the address of each virtual page in a pre-defined block of, e.g. four, contiguous virtual pages, is separately translated through segment and/or page table lookup operations to yield corresponding page frame addresses. The virtual and corresponding page frame addresses for this block are then stored within a single TLB entry. Inasmuch as successive virtual page addresses can be constructed through simple incrementation of a starting virtual page address for this block, a TLB entry contains the first virtual page address for the block followed by the separate page frame address, and its associated invalid and page protection bit fields, for each of the contiguous virtual pages in that block. Since segment and block values are the same for all the page frame addresses in each block, these values are only stored once within the corresponding TLB entry for that block.

Translation of multiple virtual pages upon a TLB miss

A coherence directory and its methods of operation are disclosed for private processor caches in a multiple processor system to control data coherence in the system. It provides cross-invalidate (XI) controls for the assignment of exclusive and public ownership to data units in the processor caches, including required cross-invalidation of data units among the processor caches to obtain data coherence in the system in an efficient manner. The coherence directory can be used in a multiple processor system with or without any shared second level (L2) cache, shared or private. When a shared L2 cache is used to improve system access time, the coherence directory can also be used as the second level directory for the shared L2 cache and eliminate the need for any additional L2 directory(s).

Coherence control by data invalidation in selected processor caches

A multi-processor (MP) system having shared storage is provided with locking of exclusivity status and read only status in multi-processor caches. The multi-processor system includes a plurality of processors, a shared main storage and a storage control element (SCE). The storage control element includes a global access authorization table (GAAT). Locking of exclusivity status in multi-processor caches is accomplished by providing at each processor a local access authorization table (AAT) containing access status for recently used data blocks wherein the size of a data block is a multiple of cache line size. The access status of a block in the local access authorization table is checked when the block is to be accessed by a processor. Only if the access status for a block is not found in the local access authorization table is authorization to access the block requested from the storage control element.

Access authorization table for multi-processor caches

A mechanism using CH.sub.Loc (change-local) type information is used for data prefetch (D-prefetch) decision making. This information is stored in history tables H, there being one such table for each central processor (CP) at, for example, the buffer control element (BCE). For each line L, H[L] indicates the information for L in H. Two different types of histories may be kept at H:

Data prefetching based on store information in multi-processor caches

A tightly coupled multi-processor (MP) system is provided with large granularity locking of exclusivity in multi-processor caches. The unique access right for a processor P.sub.i is enforced by giving other central processors (CPs) a temporarily invalid (TI) state on block B, even though some lines in the block B may still be resident in the cache. Any CP trying to access a block in the TI state will need to talk to the storage control element (SCE) to obtain proper authorization (e.g., RO or EX state) on the block. Assuming that a CP may have three states on a block B, temporarily invalid TI.sub.B, read only RO.sub.B and exclusive EX.sub.B, TI.sub.B is the initial state for all B at all CPs.

Multi-processor caches with large granularity exclusivity locking

This invention implements a cache access system that shortens the address generation machine cycle of a digital computer, while simultaneously avoiding the synonym problem of logical addressing. The invention is based on the concept of predicting what the real address used in the cache memory will be, independent of the generation of the logical address. The prediction involves recalling the last real address used to access the cache memory for a particular instruction, and then using that real address to access the cache memory. Incorrect guesses are corrected and kept to a minimum through monitoring the history of instructions and real addresses called for in the computer. This allows the cache memory to retrieve the information faster than waiting for the virtual address to be generated and then translating the virtual address into a real address. The address generation machine cycle is faster because the delays associated with the adder of the virtual address generation means and the translation buffer are bypassed.

Translation look ahead based cache access

A store-in cache memory system for a multiprocessor computer system has a status entry in the cache directory which is RO (read-only) when a line of data is read-only, and thus accessible by all processors on the system, or EX (exclusive) when the line accessible for reading or writing but only by one processor. In addition, each directory has an entry, CH, which is set when data in the line is changed. The cache memory system includes two additional statuses, TEX, or temporary exclusive, and TRO, or temporary read-only. When a data fetch instruction results in a cache-miss, and a line containing the requested data is found in a remote cache with an EX status and with its CH bit set, the line is copied to the requesting cache and assigned a status of TEX. The line of data in the remote cache receives a status of TRO. If a store operation for the data occurs within a short time frame, the status in the requesting cache changes to EX and the line in the remote cache is invalidated. Otherwise, the data in the line is castout to main storage and the status of the line becomes RO in both the requesting and remote caches. The addition of these statuses allows the cache system to assign an exclusive status on an anticipatory basis without incurring penalties when this assignment is not appropriate.

Multiprocessor cache memory system using temporary access states and

A Fetch-Then-Confirm (FTC) policy is used for the handling of data fetch upon XIEX's in a tightly coupled multiprocessor environment. The fetch and/or use of a requested data line upon XIEX is allowed before the SCE receives the confirmation of validity (or invalidity) of the requested line through the clearing procedure. Whenever a line having uncertain validity is used by a CP the results of execution of instructions depending on the validity of the line should not be committed to the cache until a confirmation is received from the SCE. When the confirmation from the SCE indicates that a line L is known to be valid, all results depending on the validity of L can be processed as usual. If, however, the SCE indicates that a previously fetched line L having uncertain validity is in fact invalid, all operations performed based on L's contents should be aborted and restarted properly when a valid copy of L is received.

Method for reducing cross-interrogate delays in a multiprocessor system

A method for storing into a non-EX cache line in a multiprocessor system. Upon a store into a non-EX line the instruction execution and the processing of subsequent instructions will continue. The results of the current instruction, however, and any subsequent instruction whose decode and execution depends upon the result of the current instruction or that requires operand fetches, will not be released until the processing of the current instruction is resolved. The request to store into the non-EX line is simultaneously sent to the SCE to obtain the EX state for the line. The SCE serializes storage requests. When a request for EX state is processed, certain XI actions (e.g. XI-invalidates) may be invoked. Any instruction using fetched data XI-invalidated before the resolution of a preceding store at the same CP is considered likely to be invalid, and redone.

Method for storing into non-exclusive cache lines in multiprocessor

A computer memory management method for cache memory uses a deconfirmation technique to provide a simple sequential prefetching algorithm. Access sequentially is predicted based on simple histories. Each memory line in cache memory is associated with a bit in an S-vector, which is called the S-bit for the line. When the S-bit is on, sequentiality is predicted meaning that the sequentially next line is regarded as a good candidate for prefetching, if that line is not already in the cache memory. The key to the operation of the memory management method is the manipulation (turning on and off) the S-bits.

Growing community of inventors

Pleasantville, NY, United States of America

Lishing Liu