Target cache line arbitration within a processor cluster

A computer-implemented method for managing cache memory in a distributed symmetric multiprocessing computer is described. The method may include receiving, at a first central processor (CP) chip, a fetch request from a first chip. The method may further include determining via address compare mechanisms on the first CP chip whether one or more of a second CP chip and a third CP chip is requesting access to a target line. The first chip, the second chip, and the third chip are within the same chip cluster. The method further includes providing access to the target line if both of the second CP chip and the third CP chip have accessed the target line at least one time since the first CP chip has accessed the target line.

BACKGROUND

The present disclosure relates to symmetric multiprocessing systems (SMPs), and more specifically, to hot cache line arbitration within a processor cluster of multiple chip multiprocessors in a highly distributed SMP system.

In a highly distributed large symmetric multiprocessing (SMP) systems with decentralized cache line access arbitration, the amount of system time spent on cache to cache intervention for a common semaphore/lock address can be significantly higher than the lock time per processor, which may cause system responsiveness issues. As the SMP size continues to grow, this responsiveness issue will also grow.

It may be advantageous to ensure locking fairness across multiple processors and to improve locked time efficiency by minimizing the time an available semaphore/lock address is in transit between processors.

SUMMARY

According to an embodiment of the present invention, a computer-implemented method for managing cache memory in a distributed symmetric multiprocessing computer is described. The method may include receiving, via a storage controller, a fetch request from a first central processor (CP) chip. The method may further include determining whether one or more of a second CP chip and a third CP chip is requesting access to a target line, and providing access to the target line if both of the second CP chip and the third CP chip have accessed the target line at least one time since an earlier fetch from the first CP chip has accessed the target line.

According to other embodiments, a system for managing cache memory in a distributed symmetric multiprocessing computer is described. The system may include a chip cluster having a first CP chip, a second CP chip, and a third CP chip. The system is configured to receive a fetch request from the first CP. The system is configured to determine whether one or more of the second CP chip and the third CP chip is requesting access to a target line, and provide access to the target line if both of the second CP chip and the third CP chip have accessed the target line at least one time since an earlier fetch from the first CP has accessed the target line.

DETAILED DESCRIPTION

Symmetric multiprocessing (“SMP”) is the processing of computer instructions and/or programs by multiple processors under the control of a single operating system (“OS”) using a common memory and/or input/output (“I/O”) devices. By leveraging the processing power of multiple independent processors, such as sixty four processors for example, SMP systems may be able to generate significant computing power. As such, SMP systems can provide a more economical alternative to super computers or mainframes that typically rely on a small number of more expensive, custom-designed processors.

SMP systems employ multiple interconnected processors that cooperate and communicate with each other. There are a variety of factors, however, that can affect how efficiently the processors within an SMP system can communicate with each other, and, thus, how efficiently the SMP system can operate. One factor that affects the communication between the processors in an SMP system is the available data rate of the connections between the processors, which is referred to as the bandwidth. Higher bandwidth connections between processors enable more data to be communicated between two processors in a given period of time as compared to lower bandwidth connections.

Historically system architects have used various means to achieve high performance in large tightly coupled symmetrical multiprocessor (SMP) computer systems. They range from coupling individual processors or processor clusters via a single shared system bus, to coupling processors together in a cluster, whereby the clusters communicate using a cluster-to-cluster interface, to a centrally interconnected network where parallel systems built around a large number (ie. 32 to 1024) of processors are interconnected via a central switch (i.e. a cross-bar switch).

The shared bus method usually provides the most cost efficient system design since a single bus protocol can service multiple types of resources. Furthermore, additional processors, clusters or peripheral devices can be attached economically to the bus to grow the system. However, in large systems the congestion on the system bus coupled with the arbitration overhead tends to degrade overall system performance and yield low SMP efficiency. These problems can be formidable for symmetric multiprocessor systems employing processors running at frequencies in excess of 500 MHz.

The centrally interconnected system usually offers the advantage of equal latency to shared resources for all processors in the system. In an ideal system, equal latency allows multiple applications, or parallel threads within an application, to be distributed among the available processors without any foreknowledge of the system structure or memory hierarchy. These types of systems are generally implemented using one or more large cross-bar switches to route data between the processors and memory. The underlying design often translates into large pin packaging requirements and the need for expensive component packaging. In addition, it can be difficult to implement an effective shared cache structure.

The tightly coupled clustering method serves as the compromise solution. In this application, the term cluster refers to a collection of processors sharing a single main memory, and whereby any processor in the system can access any portion of the main memory, regardless of its affinity to a particular cluster. Unlike Non-Uniform Memory Access (NUMA) architectures, the clusters referred to in our examples utilize dedicated hardware to maintain data coherency between the memory and second level caches located within each cluster, thus presenting a unified single image to the software, void of any memory hierarchy or physical partitions such as memory bank interleaves. One advantage of these systems is that the tightly coupled nature of the processors within a cluster provides excellent performance when the data remains in close proximity to the processors that need it. For example if the data resides in a cluster's second level cache or the memory bank interleaves attached to that cluster. In addition, it usually leads to more cost-efficient packaging when compared to the large N-way cross-bar switches found in the central interconnection systems. However, the clustering method can lead to poor performance if processors frequently require data from other clusters, and the ensuing latency is significant, or the bandwidth is inadequate.

FIG. 1depicts a distributed symmetric multiprocessing (SMP) system100(hereafter “system100”) in accordance with one or more embodiments. System100can include 4 processing units or “drawers.” Drawer102(described in greater detail with respect toFIG. 2) connects to drawer104, drawer106, and drawer108via a storage controller (SC) chip110. Drawers104,106, and108each have a respected SC chip (e.g., SC chip112, SC chip114, SC chip116). Bus lines118connect drawers102,104,106, and108.

FIG. 2depicts drawer102in greater detail, according to one or more embodiments. AlthoughFIG. 2depicts only drawer102, it should be appreciated that a similar configuration is contemplated for drawers104,106, and108, and/or other drawers in system100.

Referring now toFIG. 2, drawer102includes two central processor (CP) clusters202and204. A cluster includes three central processor (CP) chips operatively connected to a storage controller (SC) chip. For example, CP cluster202includes CP chip206, CP chip208, and CP chip210. Each respective CP chip is connected to a system memory (e.g., system memory212and system memory214). SC chip110is operatively connected with each of the other clusters via bus lines118. In other aspects, a CP cluster may include any number of CP chips, although embodiments are described as having only three.

Now considering a CP chip in greater detail,FIG. 3depicts a CP chip300, according to one or more embodiments. AlthoughFIG. 3depicts only one CP chip300, it should be appreciated that a similar configuration is contemplated for other CP chips in the system such as CP chips206,208, and210. Referring now toFIG. 3, CP chip300can include up to 10 processors302and a level 3 (L3) cache304. Processors302operatively connect to L3 cache304by cache bus lines306. L3 cache304may be configured with L3 cache logic308for cache line arbitration between CP chips within a chip cluster (e.g., CP chips206,208, and210within CP cluster202).

L3 cache logic may be configured to implement a decentralized cache line access arbitration system that implements locking fairness across multiple processors in the SMP system by minimizing the time an available lock address is in transit between processors. L3 cache logic308may include an LFAR logic (controller)310, which may perform arbitration functions between the CP chips like triggering the set of extended valid tags and broadcasting fetch requests, among other functions. L3 cache logic308may also include an RFAR logic (controller)312that may function as an on-chip cache that receives broadcasted requests from other CP chips in the cluster and manages the extended valid tags. CP chip300may exemplify CP chips206,208, and210as shown inFIG. 2.

Multiple CP chips in a common CP cluster may simultaneously request the same bus line. For example, in an SMP design as shown inFIG. 2where multiple CP chips are grouped within a cluster, a shared hot target cache line could be bounced back and forth between two CP chips on the cluster (e.g., CP chip206and CP chip208), while requests from a third CP chip (e.g., CP chip210) get disproportionately starved out. The bounce back and forth is sometimes referred to as a “food fight” between the CP chips. Embodiments of the present invention may improve locked time efficiency by minimizing the time an available semaphore/lock address is in transit between processors by forcing each CP chip in the same cluster to have access to the hot line (also referred herein as a “target line) once before allowing any CP chip a second access to the line.

For a hot cache line food fight in the system, if the cache line arbitration is biased for local processors first (e.g., CP chips206and208) the local processors may be in a fetch loop and this can create a system wide starvation where non-local processors (e.g., processors in CP cluster204) may take a very long time before being able to access the cache line or may time out. To avoid the starvation or time out, the arbitration logic was designed to bias toward the non-local operations first. The consequence of this bias is that moving the locked address from the owning processor to a non-local processor on another cluster takes thousands of cycles rather than tens of cycles if the cache line was moved to a nearer by local processor (i.e., a cluster of local CP chips).

Furthermore, when the semaphore is frequently used by 100's of processors, the total time spent moving the cache line from one processor to another would be the number of competing processors (of which there may be several hundred) multiplied by the 1000's of cycles per transfer (100's×1000's). This does not include the locked time which is the time the lock is set by the processor until when it is released.

In some aspects, a majority of the fetch requests come from the local Fetch/Store controllers at each CP chip (e.g., L3 cache207,209, and211). These requests are broken down into fetch requests known as LFAR requests (originating from LFAR logic218,220, and222, for example) and store requests known as LSAR requests (originating from the RFAR logic219,224, and226for example). CFAR are fetch requests originating from the CFAR logic216. According to some embodiments, cache line arbitration amongst the three CP chips in a cluster is managed by CFAR logic216operating in the SC chip110, and LFAR logic218,220and222operating in the L3 cache207,209, and211of each of CP chips206,208, and210(respectively).

Embodiments of the present invention may include a mechanism to ensure on-cluster fairness by allowing each CP chip request in the cluster to complete once before line is evicted to an off-cluster requestor. Embodiments of the present invention may insure that each of the chips on the cluster are allowed access to a hot line once before one of the those chips on the same cluster is allowed to access the shared line a second time.

FIG. 4depicts a flow diagram of a method400for managing cache memory in the distributed symmetric multiprocessing system ofFIG. 1, according to one or more embodiments. Referring now toFIG. 4, SC chip110may receive a fetch request from CP chip206, as shown in block402. A fetch request may be, for example, a local core or IO request, or some other request for exclusive access to one or more bus lines118. In some cases, access is not granted by SC chip110because the line may be in use by another CP cluster, or another chip in the same chip cluster202as CP chip208. When a CP chip (e.g., CP chip206) requests access to a target line (e.g., one of bus lines118) and the local core or IO request misses in the local (on chip) L3 cache, CP chip206may load the request into an L3 LFAR logic218, which is operating in local L3 cache of CP chip206. LFAR logic218may be configured to act as a controller.

As shown in decision block404, CP chip206may determine whether one or more other CP chips (e.g., CP chip210and CP chip208) within CP cluster202are requesting access (sending one or more fetch requests) to a target line118. In some embodiments, CP chip206broadcasts the fetch request to L4 cache located on SC chip112and the L3 cache209and211, respectively on the two other CP chips208and210. Accordingly, SC chip112acts as the on-cluster coherency master. The SC chip112processes the first request for a hot line it receives first. Subsequent requests from other CP chips on the cluster are rejected by SC chip112until the first is completed. The broadcasted request is loaded into CFAR logic216on SC chip112and into remote RFAR logic (controllers)224and226on the two other adjacent CP chips208and210, respectively, in the CP cluster202.

A special “extended valid” tag is set by RFAR logic224and RFAR logic226in the adjacent CP chips via a snoop broadcast from CP chip206. The system may detect, via CP chip208and CP chip210, the extended valid tag, and access the target line based on the extended valid tag. In some aspects, RFAR logic224and RFAR logic226may respectively execute a full address compare against a local fetch/local store (LF/LS) (not shown) on that respective chip. This compare operation may detect a condition indicative that this particular CP chip already has an outstanding miss request to the same target line being requested by another chip in the cluster.

As shown in block406, CP chip206will wait for all three CP chips in the common cluster to access the target line. To ensure that another requesting chip (e.g., CP chip206and/or CP chip208) on this same CP cluster202will not attempt to re-access the line before the other clusters (e.g., CP cluster204) have a chance to access it, subsequent local core and IO request misses that encounter full address compares against RFARs with an “extended valid” tag will set and wait for that RFAR to either complete or drop the ‘extended valid’ pending before proceeding. According to some embodiments, the extended valid tag is indicative of whether the first CP chip already has an outstanding fetch request that has not accessed the target line based on an extended valid tag. This prevents new misses to the same address from broadcasting a second off-chip/cluster request for the same line until the currently outstanding fetches from the other chip or chips in the cluster have had a chance to access the hot line once.

This “extended valid” tag is maintained by the remote L3 RFAR logic219and224in CP chips206and208, respectively. Subsequent new misses to the target line will set a “needs to wait” value from the remote L3 RFAR in219and224, even if CP chip210received a reject response from the off-chip broadcast. A reject response indicates that another CP chip will access the line first before the remote RFAR226on CP chip210is given access.

As shown in block408, system100will reset the “extended valid” tag when either 1) the respective L3 RFAR on a CP chip gains access to the target line and finishes the operation, 2) when a non-reject miss response is returned for the L3 RFAR's fetch, or 3) when a snoop request from SC chip112(or another SC chip such as SC chip114and/or SC chip116) for an exclusive fetch indicates that the target line is being pulled off the cluster.