Cache directory look-up re-use as conflict check mechanism for speculative memory requests

In a cache memory, energy and other efficiencies can be realized by saving a result of a cache directory lookup for sequential accesses to a same memory address. Where the cache is a point of coherence for speculative execution in a multiprocessor system, with directory lookups serving as the point of conflict detection, such saving becomes particularly advantageous.

BACKGROUND

The field of the invention is the use of cache memory, and in particular directory lookups in cache memories.

Cache memories have long served to make computers more efficient, by providing a relatively small and relatively fast local storage in a processing device. The cache allows currently active data to be accessed conveniently by an associated processor without accesses to the relatively larger and slower main memory—or worse still, the even larger and slower disk. In multi-processor systems with speculative execution, caching has become quite elaborate. The prior generation of IBM® Blue Gene® supercomputer system had three levels of caches, denoted L1, L2, and L3.

One common technique for organizing a cache is to make it set associative. This means that the cache is organized into pieces. Each piece is called a set. Each set includes a number of ways, each including a cache line. A memory access request accesses a set stored in a cache directory, and selects a way and thus a line of the cache.

For more information on caches, the reader is directed to the article entitled “CPU Cache” in Wikipedia.

Due to the requirements of such systems, and due to the decreasing cost of memory, caches have become much larger and more numerous. In a supercomputer, there may be thousands of cache memories each having more than 10 MB of data. These supercomputers can draw electrical power on the order of megawatts. Each component must be scrutinized for possible energy efficiency improvement

SUMMARY

The inventor here has discovered, that, surprisingly, given the extraordinary size of this type of supercomputer system, the caches, originally sources of efficiency and power reduction, have become significant power consumers—so that they themselves must be scrutinized to see how they can be improved.

The architecture of the current version of IBM® Blue Gene® supercomputer includes coordinating speculative execution at the level of the L2 cache, with results of speculative execution being stored by hashing a physical main memory address to a specific cache set—and using a software thread identification number along with upper address bits to direct memory accesses to corresponding ways of the set. The directory lookup for the cache becomes the conflict checking mechanism for speculative execution.

In a cache that has 16 ways, each memory access request for a given cache line, requires searching all 16 ways of the selected set along with elaborate conflict checking. When multiplied by the thousands of caches in the system, these lookups become energy inefficient—especially in the case where several sequential, or nearly sequential, lookups access the same line.

Thus the new generation of supercomputer gave rise to an environment where directory lookup becomes a significant component of the energy efficiency of the system. Accordingly, it would be desirable to save results of lookups in case they are needed by subsequent memory access requests.

In one embodiment, in a cache memory of a data processing system, a method includes:receiving a plurality of memory access requests;queuing the requests;checking a given one of requests against at least one entry in a cache directory to yield a memory access request related result;storing at least one such result; andresponsive to a subsequent one of the requests, using the stored result rather than checking the cache directory to find the result.

In another embodiment, within a cache memory control unit, apparatus includes:at least one input adapted to receive at least one memory access request;at least one directory unit adapted to retrieve data from cache lines responsive to the memory access request; andat least one storage unit adapted to retain an indication responsive to the memory access request, so that the indication can be used in a subsequent memory access request.

In another embodiment, a system includes

at least one processor;

a cache memory shared by the processors, comprising:a directory unit, for retrieving data responsive to memory access requests from the processorslines for storing data; anda sub-cache adapted to store at least one address or data result related to a prior memory access request.

Objects and advantages will be apparent in the following.

DETAILED DESCRIPTION

The following document relates to write piggybacking in the context of DRAM controllers:Shao, J. and Davis, B. T. 2007, “A Burst Scheduling Access Reordering Mechanism,” In Proceedings of the 2007 IEEE 13th international Symposium on High Performance Computer Architecture (Feb. 10-14, 2007). HPCA. IEEE Computer Society, Washington, D.C., 285-294. DOI=http://dx.doi.org/10.1109/HPCA.2007.346206
This article is incorporated by reference herein.

It would be desirable to reduce directory SRAM accesses to reduce power and increase throughput in accordance with one or both of the following methods:1. On hit, store cache address and selected way in a registera. Match subsequent incoming requests and addresses of line evictions against the registerb. If encountering a matching request and no eviction has been encountered yet, use way from register without directory SRAM look-up2. Reorder requests pending in the request queue such that same set accesses will execute in subsequent cycles3. Reuse directory SRAM look-up information for subsequent access using bypass

These methods are especially effective if the memory access request generating unit can provide a hint whether this location might be accessed soon or if the access request type implies that other cores will access this location soon, e.g., atomic operation requests for barriers

Throughout this disclosure a particular embodiment of a multi-processor system will be discussed. This discussion may include various numerical values. These numerical values are not intended to be limiting, but only examples. One of ordinary skill in the art might devise other examples as a matter of design choice.

The present invention arose in the context of the IBM® Blue Gene® project, which is further described in the applications incorporated by reference above.FIG. 1is a schematic diagram of an overall architecture of a multiprocessor system in accordance with this project, and in which the invention may be implemented. At101, there are a plurality of processors operating in parallel along with associated prefetch units and L1 caches. At102, there is a switch. At103, there are a plurality of L2 slices. At104, there is a main memory unit. It is envisioned, for the preferred embodiment, that the L2 cache should be the point of coherence.

FIG. 2shows a cache slice. It includes arrays of data storage201, and a central control portion202.

FIG. 3shows features of an embodiment of the control section102of a cache slice72.

Coherence tracking unit301issues invalidations, when necessary. These invalidations are issued centrally, while in the prior generation of the Blue Gene® project, invalidations were achieved by snooping.

The request queue302buffers incoming read and write requests. In this embodiment, it is 16 entries deep, though other request buffers might have more or less entries. The addresses of incoming requests are matched against all pending requests to determine ordering restrictions. The queue presents the requests to the directory pipeline308based on ordering requirements.

The write data buffer303stores data associated with write requests. This buffer passes the data to the eDRAM pipeline305in case of a write hit or after a write miss resolution.

The directory pipeline308accepts requests from the request queue302, retrieves the corresponding directory set from the directory SRAM309, matches and updates the tag information, writes the data back to the SRAM and signals the outcome of the request (hit, miss, conflict detected, etc.).

The L2 implements four parallel eDRAM pipelines305that operate independently. They may be referred to as eDRAM bank 0 to eDRAM bank 3. The eDRAM pipeline controls the eDRAM access and the dataflow from and to this macro. If writing only subcomponents of a doubleword or for load-and-increment or store-add operations, it is responsible to schedule the necessary RMW cycles and provide the dataflow for insertion and increment.

The read return buffer304buffers read data from eDRAM or the memory controller78and is responsible for scheduling the data return using the switch60. In this embodiment it has a 32B wide data interface to the switch. It is used only as a staging buffer to compensate for backpressure from the switch. It is not serving as a cache.

The miss handler307takes over processing of misses determined by the directory. It provides the interface to the DRAM controller and implements a data buffer for write and read return data from the memory controller.

The reservation table306registers and invalidates reservation requests.

In the current embodiment of the multi-processor, the bus between the L1 to the L2 is narrower than the cache line width by a factor of 8. Therefore each write of an entire L2 line, for instance, will require 8 separate transmissions to the L2 and therefore 8 separate lookups. Since there are 16 ways, that means a total of 128 way data retrievals and matches. Each lookup potentially involves all this conflict checking that was just discussed, which can be very energy-consuming and resource intensive.

Therefore it can be anticipated that—at least in this case—an access will need to be retained. A prefetch unit can annotate its request indicating that it is going to access the same line again to inform the L2 slice of this anticipated requirement.

Certain instruction types, such as atomic operations for barriers, might result in an ability to anticipate sequential memory access requests using the same data.

One way of retaining a lookup would be to have a special purpose register in the L2 slice that would retain an identification of the way in which the requested address was found. Alternatively, more registers might be used if it were desired to retain more accesses.

Another embodiment for retaining a lookup would be to actually retain data associated with a previous lookup to be used again.

An example of the former embodiment of retaining lookup information is shown inFIG. 3A. The L2 slice72includes a request queue302. At311, a cascade of modules tests whether pending memory access requests will require data associated with the address of a previous request, the address being stored at313. These tests might look for memory mapped flags from the L1 or for some other identification. A result of the cascade311is used to create a control input at314for selection of the next queue entry for lookup at315, which becomes an input for the directory look up module312. These mechanisms can be used for reordering, analogously to the Shao article above, i.e., selecting a matching request first. Such reordering, together with the storing of previous lookup results, can achieve additional efficiencies

FIG. 3Bshows more about the interaction between the directory pipe308and the directory SRAM309. The vertical lines in the pipe represent time intervals during which data passes through a cascade of registers in the directory pipe. In a first time interval T1, a read is signaled to the directory SRAM. In a second time interval T2, data is read from the directory SRAM. In a third time interval, T3, the directory matching phase may alter directory data and provide it via the Write and Write Data ports to the directory SRAM. In general, table lookup will govern the behavior of the directory SRAM to control cache accesses responsive to speculative execution. Only one table lookup is shown at T3, but more might be implemented. More detail about the lookup is to be found in the applications incorporated by reference herein, but, since coherence is primarily implemented in this lookup, it is an elaborate process. In particular, in the current embodiment, speculative results from different concurrent processes may be stored in different ways of the same set of the cache. Records of memory access requests and line evictions during concurrent speculative execution will be retained this directory. Moreover, information from cache lines, such as whether a line is shared by several cores, may be retained in the directory. Conflict checking will include checking these records and identifying an appropriate way to be used by a memory access request. Retaining lookup information can reduce use of this conflict checking mechanism.

Although the embodiments of the present invention have been described in detail, it should be understood that various changes and substitutions can be made therein without departing from spirit and scope of the inventions as defined by the appended claims. Variations described for the present invention can be realized in any combination desirable for each particular application. Thus particular limitations, and/or embodiment enhancements described herein, which may have particular advantages to a particular application need not be used for all applications. Also, not all limitations need be implemented in methods, systems and/or apparatus including one or more concepts of the present invention.

The word “comprising”, “comprise”, or “comprises” as used herein should not be viewed as excluding additional elements. The singular article “a” or “an” as used herein should not be viewed as excluding a plurality of elements. Unless the word “or” is expressly limited to mean only a single item exclusive from other items in reference to a list of at least two items, then the use of “or” in such a list is to be interpreted as including (a) any single item in the list, (b) all of the items in the list, or (c) any combination of the items in the list. Ordinal terms in the claims, such as “first” and “second” are used for distinguishing elements and do not necessarily imply order of operation.

Items illustrated as boxes in flowcharts herein might be implemented as software or hardware as a matter of design choice by the skilled artisan. Software might include sequential or parallel code, including objects and/or modules. Modules might be organized so that functions from more than one conceptual box are spread across more than one module or so that more than one conceptual box is incorporated in a single module. Data and computer program code illustrated as residing on a medium might in fact be distributed over several media, or vice versa, as a matter of design choice. Such media might be of any suitable type, such as magnetic, electronic, solid state, or optical

Any algorithms given herein can be implemented as computer program code and stored on a machine readable medium, to be performed on at least one processor. Alternatively, they may be implemented as hardware. They are not intended to be executed manually or mentally.

The use of variable names in describing operations in a computer does not preclude the use of other variable names for achieving the same function.

The present application may use language that is anthropomorphic in describing operations of a computer. Any such anthropomorphic language is not intended to imply that the claimed invention reads on a human being thinking or performing manual operations. The claims are intended to be interpreted as reading on operations of a machine.