Browse Prior Art Database

An Algorithm to Resolve Multiple-Copy Cache Conflicts in Multi-Node Systems with Ring Topology Disclosure Number: IPCOM000016200D
Original Publication Date: 2002-Sep-01
Included in the Prior Art Database: 2003-Jun-21
Document File: 5 page(s) / 75K

Publishing Venue



Background of the Invention Field of the Invention

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 28% of the total text.

Page 1 of 5

  An Algorithm to Resolve Multiple-Copy Cache Conflicts in Multi-Node Systems with Ring Topology

Background of the Invention Field of the Invention

    Disclosed is an algorithm based methodology to resolve multiple-copy cache conflicts in multi-node computer systems with ring topology.

    A multi-node computer system is a cluster of multi-processor (MP) computer nodes with a common view to storage hierarchy. The processors at each node share one common level 2 cache (L2) and each node owns and manages a local portion of the common memory [Fig 1]. A common view to all the caches and memories distributed across the various nodes is provided by the cache coherence protocol.

    The invention relates to clusters where the buses connecting the individual MP nodes form a ring. As shown in [Fig 2], the ring connection is assumed to consist of two sets of uni-directional ring buses in opposite direction each set comprising address/command and data buses. Address/command and data buses may be separate or combined to one bus. Such bi-directional ring structures are usually preferred over one-directional ring structures because they have far better cache-to-cache and memory-to-cache data transfer latencies between nodes. To exploit the bi-directional structure, ring requests are launched in both directions.

Problem Description and Disadvantages of Prior Solutions

    The major challenge to the cache coherence protocol in such an environment is to resolve multiple-copy cache conflicts: If a processor needs data which are not cached in its own local L1 nor in its node's local L2 cache but of which several (shared) copies are available in the L2 caches of other nodes, the cache coherence protocol has to make sure that one and only one of the remote L2 caches sources the requested data.

    One strategy used by prior art ring protocols is the intervention master (IM) concept [Ref 1]: The node which requested the data most recently is the node which will provide the data to the next requestor. That's why this node is tagged intervention master for the respective cache line. But who should take over in case a cache line has aged out of its intervention master's L2 cache? Several other copies of the data might still exist in other node caches and the ring protocol has to pick one and only one node to provide the data.

    Prior art implementations circumvent the multiple-copy conflict by ignoring all cache copies of the requested data and instead reading them from the owning memory. Thus, cache miss resolution times increase and system performance may be impacted. In current computer systems, memory and cache accesses typically differ by a factor of
10. In the future, the delta will increase to a factor of about 50. The impact on system performance of fetching cached non-IM data from memory instead of from cache will then be in the percent range.

Objectives and Advantages of the Inventive Solution

    This invention presents a method which resolves multiple-copy cache conflic...