Method and system for dynamically partitioning a shared cache

• US 6,493,800 B1
• Filed: 03/31/1999
• Issued: 12/10/2002
• Est. Priority Date: 03/31/1999
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Blumrich, Matthias Augustin
• Primary Examiner(s): Thai, Tuan V.
• Application Number:
  US09/281,934
• Time in Patent Office: 1,350 Days
• Field of Search: 711/129, 711/130, 711/131, 711/121, 711/171, 711/172, 711/100, 711/118
• US Class Current: 711/129
• CPC Class Codes: G06F 12/084 with a shared cache
• CPC Class Codes: G06F 12/0842 for multiprocessing or multitasking
• CPC Class Codes: G06F 12/0848 Partitioned cache, e.g. separate instruction and operand caches
• CPC Class Codes: G06F 12/0864 using pseudo-associative means, e.g. set-associative or hashing
• CPC Class Codes: G06F 2212/2542 Non-uniform memory access [NUMA] architecture

Abstract

A cache memory shared among a plurality of separate, disjoint entities each having a disjoint address space, includes a cache segregator for dynamically segregating a storage space allocated to each entity of the entities such that no interference occurs with respective ones of the entities. A multiprocessor system including the cache memory, a method and a signal bearing medium for storing a program embodying the method also are provided.

Claims

1. A cache memory shared among a plurality of separate, disjoint entities, said cache memory comprising:

means for receiving an access request from one of said entities; and

means for dynamically and physically segregating a storage space allocated to each entity of said entities, based on said access request, such that no interference occurs with respective ones of said entities,

wherein said segregating means comprises means for extending a cache tag of an access request to include a unique identifier for identifying individual ones of said entities.

2. The cache memory according to claim 1, wherein said entity comprises at least one processor.

3. The cache memory according to claim 1, wherein the cache comprises a set-associative cache.

4. The cache memory according to claim 1, wherein said unique identifier comprises a partition identifier (PID) included with said access request.

5. The cache memory according to claim 4, wherein said PID is different from others of said PID and is provided such that whenever the cache is accessed by an entity, the PID is included as part of a tag lookup, such that disjoint entities can use a same address to access the cache.

6. The cache memory according to claim 4, wherein varying a number of bits of said PID varies a number of segregated cache partitions, said number of partitions being independent of a number of entities.

7. The cache memory according to claim 4, wherein said PID is unique for each partition of said cache segregated by said segregating means.

8. The cache memory according to claim 1, wherein said cache memory comprises one of a disk cache memory and a file cache memory.

9. The cache memory according to claim 1, wherein said cache memory comprises a single cache memory shared among said plurality of entities, such that said cache memory is partitioned such that independent groups of said entities, each of which physically share the cache memory, are allocated independent cache partitions.

10. The cache memory according to claim 9, wherein each of the groups accesses its portion of the cache memory using a same set of physical addresses.

11. The cache memory according to claim 1, wherein said segregating means supports multiple, dynamically-selectable partition sizes, such that said cache memory selectively includes variable-sized partitions to satisfy caching requirements of the entity partitions.

12. The cache memory according to claim 1, wherein said cache segregator dynamically re-segregates the cache memory when a machine configuration changes or a sharing of cache partitions changes.

13. The cache memory according to claim 1, wherein a segregated entity selectively includes multiple address spaces.

14. A cache memory shared among a plurality of separate, disjoint entities, said cache memory comprising:

means for receiving an access request from one of said entities; and

means for dynamically and physically segregating a storage space allocated to each entity of said entities, based on said access request, such that no interference occurs with respective ones of said entities,

wherein said segregating means includes means for constraining, based on a unique identifier, a cache index of an access request to fall within a particular set of index sets.

15. The cache memory according to claim 14, wherein said constraining means assigns a guaranteed set of index sets to predetermined ones of said entities.

16. The cache memory according to claim 14, wherein the index sets of the cache are partitioned into disjoint groups of various sizes,

said disjoint groups being cache partitions, each cache partition being allocated a unique portion of the cache with a size meeting its requirements.

17. The cache memory according to claim 14, wherein sizes of the cache partitions can be varied dynamically to adjust to resource needs.

18. The cache memory according to claim 14, wherein said constraining means performs cache partitioning by forcing a predetermined number of index bits in an access request to particular values based upon the entity performing a reference, such that the index is constrained to a subset of the total sets in the cache.

19. The cache memory according to claim 14, further comprising:

a partition selector for performing said partitioning by replacing “

p”

high-order bits of an “

n”

-bit index, thereby reducing the index to the 2<sup>n−

p</sup> cache sets that have the partition selector as their high-order bits, wherein “

p”

is a non-negative integer.

20. The cache memory according to claim 19, wherein said replaced index bits are displaced, said displaced index bits being added to the tag, thereby extending said tag by “

p”

bits.

21. The cache memory according to claim 19, wherein a number of index bits replaced by the partition selector varies for each partition, to allocate cache partitions of varying sizes.

22. The cache memory according to claim 19, wherein said constraining means further comprises a partition selector mask which accompanies a partition selector in an access request,

said partition selector mask specifying which bits of the index are to be replaced by bits from the partition selector, thereby dynamically specifying a size for each cache partition by specifying the number of index bits to replace.

23. The cache memory according to claim 22, wherein said partition selector mask has a same number of bits as the partition selector, and its bits correspond to bit positions of the cache index beginning with the high-order bits, and

wherein when a mask bit is set, the corresponding index bit is replaced by a partition selector bit having a same bit position as a set mask bit.

24. The cache memory according to claim 14, wherein a minimal access time required of the cache memory is maintained while providing segregating by index sets.

25. A multiprocessor system having a plurality of separate, disjoint entities each having a disjoint address space, said multiprocessor system comprising:

a cache memory shared among said plurality of separate, disjoint entities, said cache memory including;

an access request portion for receiving an access request from any of said plurality of entities and providing a unique identifier for identifying individual ones of said entities,

wherein said unique identifier dynamically and physically segregates the storage space allocated to each entity of said entities, based on said access request, such that no interference occurs with respective ones of said entities,

wherein said unique identifier extends a cache tag of an access request to include a unique identifier for identifying individual ones of said entities.

26. A multiprocessor system having a plurality of separate, disjoint entities each having a disjoint address space, said multiprocessor system comprising:

a cache memory shared among said plurality of separate, disjoint entities, said cache memory including;

an access request portion for receiving an access request from any of said plurality of entities and providing a unique identifier for identifying individual ones of said entities,

wherein said unique identifier dynamically and physically segregates the storage space allocated to each entity of said entities, based on said access request, such that no interference occurs with respective ones of said entities,

wherein said cache memory includes a plurality of tag storage arrays and a plurality of data storage arrays, and said tag storage arrays and data storage arrays receive the index of the access request, said system further comprising;

a comparator, coupled to said tag storage arrays, for receiving said unique identifier and a tag of said access request; and

a multiplexer, coupled to said comparator and to said data storage arrays, to provide data externally thereto based on an output from said comparator.

27. The multiprocessor system according to claim 26, wherein said unique identifier comprises a partition identifier (PID) for identifying a partition of said cache memory, and said PID is provided with said access request when said cache memory is referenced by an entity.

28. The multiprocessor system according to claim 26, wherein each of the tag storage arrays is widened by a predetermined number of bits to accommodate the unique identifier, and wherein when data is stored into the cache, the unique identifier is stored along with the tag.

29. A multiprocessor system having a plurality of separate, disjoint entities, said multiprocessor system comprising:

a cache memory shared among said plurality of separate, disjoint entities, said cache memory including;

an access request portion for receiving an access request from any of said plurality of entities and a unique identifier, said unique identifier constraining a cache index of said access request to fall within a particular set of index sets from one of said entities,

wherein a storage space allocated to each entity of said entities is based on said access request including said unique identifier, such that no interference occurs with respective ones of said entities.

30. The multiprocessor system of claim 29, wherein said cache memory includes tag storage arrays and data storage arrays, and said tag storage arrays and data storage arrays receive the cache index of the access request, and wherein said unique identifier comprises a partition selector, said system further comprising:

a comparator, coupled to said tag storage arrays, for receiving said partition selector and a tag of said access request;

a plurality of multiplexers, coupled to receive respective bits of said partition selector, and providing an input to said tag storage arrays and to said data storage arrays; and

a multiplexer, coupled to said comparator and to said data storage arrays, to provide data externally thereto based on an output from said comparator.

31. A method of partitioning a cache memory shared among a plurality of separate, disjoint entities each having a disjoint address space, said method comprising:

receiving an access request from one of said entities; and

dynamically and physically segregating the storage space allocated to each entity of said entities, based on said access request, such that no interference occurs with respective ones of said entities,

wherein said segregating comprises extending a cache tag of an access request to include a unique identifier for identifying individual ones of said entities.

32. A signal-bearing medium tangibly embodying a program of machine-readable instructions executable by a processing apparatus to perform a method of dynamically partitioning a cache memory shared among a plurality of separate, disjoint entities each having a disjoint address space, said method comprising:

receiving an access request from one of said entities; and

dynamically and physically segregating the storage space allocated to each entity of said entities, based on said access request, such that no interference occurs with respective ones of said entities,

wherein said segregating comprises extending a cache tag of an access request to include a unique identifier for identifying individual ones of said entities.

33. A cache memory shared among a plurality of separate, disjoint entities, said cache memory comprising:

a storage space; and

a cache segregator for dynamically and physically segregating said storage space based on access requests received from said entities, such that no interference occurs with respective ones of said entities,

wherein said segregator includes a constraining unit for constraining, based on a unique identifier, a cache index of an access request to fall within a particular set of index sets.

34. A method of partitioning a cache memory shared among a plurality of separate, disjoint entities each having a disjoint address space, said method comprising:

receiving an access request from one of said entities; and

dynamically and physically segregating the storage space allocated to each entity of said entities, based on said access request, such that no interference occurs with respective ones of said entities,

wherein said dynamically segregating includes constraining, based on a unique identifier, a cache index of an access request to fall within a particular set of index sets.

35. A signal-bearing medium tangibly embodying a program of machine-readable instructions executable by a processing apparatus to perform a method of dynamically partitioning a cache memory shared among a plurality of separate, disjoint entities each having a disjoint address space, said method comprising:

receiving an access request from one of said entities; and

dynamically and physically segregating the storage space allocated to each entity of said entities, based on said access request, such that no interference occurs with respective ones of said entities,

wherein said dynamically segregating includes constraining, based on a unique identifier, a cache index of an access request to fall within a particular set of index sets.