System and method for allocating a directory entry for use in multiprocessor-node data processing systems
First Claim
1. A data processing system comprising:
- a main memory;
a plurality of processor each having a respective cache capable of storing a plurality of cached lines;
a memory controller; and
a sparse directory, containing fewer memory lines than the main memory, for keeping track of states of the cached lines, each cache directory entry corresponding to data stored in the main memory;
wherein, upon a new request for a cache line, an algorithm uses said states of the cached lines stored in the sparse directory to allocate a cache directory entry for the requested cache line, and if the algorithm determines that all directory entries representing memory lines are in transitional states, then the algorithm retries the request.
1 Assignment
0 Petitions
Accused Products
Abstract
An algorithm for selecting a directory entry in a multiprocessor-node system. In response to a memory request from a processor in a processor node, the algorithm finds an available entry to store information about the requested memory line. If at least one entry is available, then the algorithm uses one of the available entries. Otherwise, the algorithm searches for a “shared” entry. If at least one shared entry is available, then the algorithm uses one of the shared entries. Otherwise, the algorithm searches for a “dirty” entry. If at least one dirty entry is available, then the algorithm uses one of the dirty entries. In selecting a directory entry, the algorithm uses a “least-recently-used” (LRU) algorithm because an entry that was not recently used is more likely to be stale. Further, to improve system performance, the algorithm preferably uses a shared entry before using a dirty entry. In the preferred embodiment, the processor node that utilizes the invention includes at least one processor having a respective cache connected via a bus to main memory.
26 Citations
24 Claims
-
1. A data processing system comprising:
-
a main memory;
a plurality of processor each having a respective cache capable of storing a plurality of cached lines;
a memory controller; and
a sparse directory, containing fewer memory lines than the main memory, for keeping track of states of the cached lines, each cache directory entry corresponding to data stored in the main memory;
wherein, upon a new request for a cache line, an algorithm uses said states of the cached lines stored in the sparse directory to allocate a cache directory entry for the requested cache line, and if the algorithm determines that all directory entries representing memory lines are in transitional states, then the algorithm retries the request. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)
a state information field for indicating the state of the data line, a bit vector field with one processor field for each processor, each processor field indicating whether it associated processor has a copy of the data line, and a tag field indicating a segment of the main memory with which the directory entry is associated. -
12. The data processing system of claim 1 further comprising a main memory address entry including a tag portion identifying a segment of main memory and a set number portion used to determine the location offset of a line within the segment.
-
13. The data processing system of claim 1 wherein each cache directory entry maps to multiple cache lines.
-
14. The data processing system of claim 1, wherein a shared cache line may have a stale directory entry that was not updated.
-
15. The data processing system of claim 1, wherein the algorithm uses the directory to identify stale data that is no longer needed and can be discarded.
-
-
16. A method or selecting a directory entry among a plurality of directory entries having state information, comprising the steps of:
-
receiving a request to select from among said plurality of directory entries;
using said state information to select said directory entry; and
allowing a re-request if it as been determined that all of said plurality of directory entries represent cached lines in transitional states. - View Dependent Claims (17, 18, 19, 20, 21, 22, 23, 24)
-
Specification
-
- Resources
-
Current AssigneeFujitsu Limited
-
Original AssigneeFujitsu Limited
-
InventorsWeber, Wolf-Dietrich, Masri, Nabil N.
-
Primary Examiner(s)Portka, Gary J
-
Application NumberUS09/304,432Publication NumberTime in Patent Office1,604 DaysField of Search711/133, 711/134, 711/135, 711/136, 711/144, 711/159, 711/160, 711/207, 711/208, 711/124US Class Current711/133CPC Class CodesG06F 12/082 Associative directories G06...G06F 12/121 using replacement algorithms
