Fair sharing of a cache in a multi-core/multi-threaded processor by dynamically partitioning of the cache

• US 20060143390A1
• Filed: 12/29/2004
• Published: 06/29/2006
• Est. Priority Date: 12/29/2004
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Kottapalli, Sailesh
• Granted Patent: US 7,996,644 B2
• Time in Patent Office: Days
• US Class Current: 711/130
• CPC Class Codes: G06F 12/084 with a shared cache
• CPC Class Codes: G06F 12/0864 using pseudo-associative means, e.g. set-associative or hashing
• CPC Class Codes: G06F 12/126 with special data handling, e.g. priority of data or instructions, handling errors or pinning

Abstract

An apparatus and method for fairly accessing a shared cache with multiple resources, such as multiple cores, multiple threads, or both are herein described. A resource within a microprocessor sharing access to a cache is assigned a static portion of the cache and a dynamic portion. The resource is blocked from victimizing static portions assigned to other resources, yet, allowed to victimize the static portion assigned to the resource and the dynamically shared portion. If the resource does not access the cache enough times over a period of time, the static portion assigned to the resource is reassigned to the dynamically shared portion.

Claims

1. An integrated circuit comprising:

a cache having a plurality of static portions and a dynamically shared portion; and

a first number of computing resources, each computing resource operable to victimize one of the static portions of the cache assigned to the computing resource and the dynamically shared portion.

2. The integrated circuit of claim 1, wherein the first number of computing resources are a first number of cores.

3. The integrated circuit of claim 1, wherein the first number of computing resources are a first number of threads.

4. The integrated circuit of claim 1, wherein the first number of computing resources comprise at least one core and at least one thread.

5. The integrated circuit of claim 1, wherein each computing resource is also operable to victimize at least one of the plurality of static portions assigned to another computing resource, of the first number of computing resources.

6. The integrated circuit of claim 1, further comprising a counter, the counter to count the number of times each computing resource accesses the cache over a period of time.

7. The integrated circuit of claim 6, further comprising logic coupled to the counter, the logic to reassign at least one way within a first static portion, of the plurality of static portions assigned to a first computing resource of the first number of computing resources, to the dynamically shared portion, if the number of times the counter counted the first computing resource accessing the cache over the period of time is less than a predetermined number.

8. The integrated circuit of claim 7, wherein accessing the cache comprises

requesting an element from the cache, the element having an associated address.

9. The integrated circuit of claim 7, wherein accessing the cache comprises

requesting an element from an address that results in a cache miss.

10. The integrated circuit of claim 1, wherein each computing resource operable to victimize one of the static portions of the cache assigned to the computing resource and the dynamically shared portion comprises:

each computing resource being operable to replace a line of the cache, upon a miss, only in the one static portion of the cache assigned to the computing resource and the dynamically shared portion, and not operable to replace a line of the cache, upon a miss, in one of the static portions assigned to another computing resource.

11. The integrated circuit of claim 10, wherein each computing resource is also operable to hit a line of cache present in the one static portion of the cache assigned to the computing resource, one of the static portions assigned to another computing resource, and the dynamically shared portion.

12. The integrated circuit of claim 1, wherein the plurality of static portions are equal in number to the first number of computing resources, and wherein the dynamically shared portion of the cache has a size in ways equal to the first number of computing resources.

13. The integrated circuit of claim 12, wherein the cache has a size of 16 ways, the first number of computing resources is equal to 8, the dynamically shared portion has a size equal to 8 ways of the cache, and wherein there are 8 total static portions, each static portion having a size equal to 1 way of the cache.

54. The method of claim 51, wherein the plurality of computing resources are selected from a group consisting of single threaded cores, multi-threaded cores, and threads.

14. A microprocessor comprising:

a first resource having an associated first resource identifier (ID);

a second resource having an associated second resource ID;

a cache logically organized into a plurality of ways; and

a blocking mechanism

to block the second resource from victimizing a first number of ways, of the plurality of ways, based at least in part on the second processor ID,

to block the first resource from victimizing a second number of ways, of the plurality of ways, based at least in part on the first processor ID, and

to allow the first and second resources to victimize a third number of ways, of the plurality of ways.

15. The microprocessor of claim 14, wherein the first and second resources are cores, and wherein the first and second resource IDs are core IDs associated with the first and second cores, respectively.

16. The microprocessor of claim 14, wherein the first and second resources are threads, and wherein the first and second resource IDs are thread IDs associated with the first and second threads, respectively.

17. The microprocessor of claim 14, wherein the first resource is a core and the second resource is a thread, and wherein the first resource IDs is a core ID associated with the first core and the second resource ID is a thread ID associated with the second thread.

18. The microprocessor of claim 14, wherein the blocking mechanism comprises a mask generated upon a cache lookup based at least in part on:

the first resource ID, if the first resource initiates the cache lookup; and

the second resource ID, if the second resource initiates the cache lookup.

19. The microprocessor of claim 18, wherein the mask comprises a plurality of mask bits, each mask bit corresponding to one of the plurality of ways.

20. The microprocessor of claim 19, wherein each of the plurality of mask bits corresponding to the first number of ways, of the plurality of ways, have a first value to block the second resource from victimizing the first number of ways based at least in part on the second resource ID, if the second resource initiated the cache lookup.

21. The microprocessor of claim 20, wherein each of the plurality of mask bits corresponding to the second and third number of ways have a second value to allow the second resource to victimize the second and third number of ways based at least in part on the second resource ID, if the second resource initiated the cache lookup.

22. The microprocessor of claim 21, wherein the cache is logically organized into 8 ways, the first number of ways being 2, the second number of ways being 2, the third number of ways being 4, and wherein the mask comprises 8 mask bits.

23. The microprocessor of claim 22, wherein the two mask bits corresponding to the first number of 2 ways have a logical value of zero to block the second resource from victimizing the first number of 2 ways, the two mask bits corresponding to the second number of 2 ways have a logical value of one to allow the second resource to victimize the second number of 2 ways, and the four mask bits corresponding to the third number of 4 ways having a logical value of one to allow the second resource to victimize the third number of 4 ways, if the second resource initiated the cache lookup.

24. The microprocessor of claim 23, further comprising

a counter to count the number of accesses to the cache made by the second resource over a period of time, and

logic coupled to the counter to re-assign at least one way of the second number of 2 ways to the third number of 4 ways, if the number of accesses over the period of time is less than a programmable number.

25. An apparatus comprising:

a cache;

a first computing resource to access a first statically assigned portion of the cache and a dynamic portion of the cache;

a second computing resource to access a second statically assigned portion of the cache and the dynamic portion of the cache;

a counter to count a first number of accesses to the cache by the first computing resource over a period of time and a second number of accesses to the cache by the second computing resource over the period of time; and

logic operable to

decrease the first statically assigned portion of the cache by a size and increase the dynamic portion of the cache by the size, if at the end of the period of time, the first number of accesses is less than a predetermined number, and

decrease the second statically assigned portion of cache by the size and increase the dynamic portion of the cache by the size, if at the end of the period of time, the second number of accesses is less than the predetermined number.

26. The apparatus of claim 25, wherein the first and second computing resources are selected from a group consisting of a core, a hardware thread, and a software thread.

27. The apparatus of claim 25, wherein the cache is organized into a plurality of ways, and wherein the first statically assigned portion of the cache includes a first way, of the plurality of ways, and the second statically assigned portion of the cache includes a second way, of the plurality of ways.

28. The apparatus of claim 27, wherein decreasing the first statically assigned portion of the cache by a size and increasing the dynamic portion of the cache by the size comprises reassigning the first way to the dynamic portion of the cache, and wherein decreasing the second statically assigned portion of cache by the size and increasing the dynamic portion of the cache by the size comprises reassigning the second way to the dynamic portion of the cache.

29. The apparatus of claim 28, wherein the logic is also operable to assign the first way back to the first statically assigned portion of the cache, upon a predetermined number of misses to the cache by the first computing resource, and where the logic is further operable to assign the second way back to the second statically assigned portion of the cache, upon the predetermined number of misses to the cache by the second computing resource.

30. The apparatus of claim 25, wherein accessing the cache comprises generating an address of an element to be retrieved and comparing a portion of the address to a tag value in the cache.

31. The apparatus of claim 25, wherein accessing the cache comprises requesting an element from an address that results in a cache miss.

32. A system comprising:

a system memory comprising a plurality of memory locations to store elements, each memory location referenced by a physical address; and

a microprocessor coupled to the system memory comprising

an address translation unit to translate virtual memory addresses to physical addresses, the physical addresses referencing the plurality of memory locations,

a cache logically organized into a plurality of ways to store recently fetched elements from the plurality of memory locations,

a plurality of resources assigned a dynamically shared first number of ways, of the plurality of ways, wherein each resource is also assigned a static second number of ways, of the plurality of ways, and

logic to reassign at least one of the static second number of ways assigned to a first resource, of the plurality of resources, to the dynamically shared first number of ways, if the first resource does not access the cache a predetermined number of times over a period of time.

33. The system of claim 32, wherein the system memory is a random access memory chip.

34. The system of claim 32, wherein the elements are selected from a group consisting of instructions, operands, and data operands.

35. The system of claim 32, wherein the address translation unit comprises a translation look-aside buffer (TLB).

36. The system of claim 32, wherein the cache is logically organized as a set associative cache.

37. The system of claim 32, wherein the plurality of resources are a plurality of multi-threaded cores.

38. The system of claim 37, wherein there are four multi-threaded cores and the cache has 8 ways.

39. The system of claim 38, wherein the dynamically shared first number of ways is equal to 4 and wherein the static second number of ways assigned to each of the four multi-threaded cores is equal to 1.

40. A method comprising:

generating an address associated with an instruction scheduled for execution on a first resource, the address referencing a memory location of an element;

requesting the element from a cache;

determining if the element is present in the cache; and

if the element is not present in the cache,

allowing the first resource to victimize at least a first way of the cache assigned to the first resource and at least a second way of the cache shared by at least the first and a second resource, and

blocking the first resource from victimizing at least a third way of the cache assigned to the second resource.

41. The method of claim 40, wherein allowing the first resource to victimize at least the first way and at least the second way is based at least in part on a first resource identifier (ID) associated with the first resource.

42. The method of claim 41, wherein blocking the first resource from victimizing at least a third way is based at least in part on the first resource ID.

43. The method of claim 42, wherein allowing the first resource to victimize at least the first way of and at least the second way based at least in part on the first resource ID comprises

determining if the first resource requested the element from the cache, based at least in part on the resource ID of the request;

generating at least a first and a second mask bit corresponding to the first and second way, respectively, the first and second mask bits having a first logical value to allow the first resource to victimize the first and second way, if the first resource requested the element.

44. The method of claim 43, wherein blocking the first resource from victimizing at least a third way of the cache assigned to the second resource, based at least in part on the first resource ID comprises:

generating a third mask bit corresponding to the third way, the third mask bit having a second logical value to block the first resource from victimizing the third way, if the first resource requested the element.

45. The method of claim 43, wherein blocking the first resource from victimizing the third way comprises not allowing the first resource to allocate a miss to the third way, and wherein allowing the first resource to victimize the first and the second way comprises allowing the first resource to allocate a miss to the first or the second way.

46. The method of claim 44, wherein the first value is a logical 1 and the second value is a logical 0.

47. The method of claim 40, wherein the first and second resources are cores.

48. The method of claim 40, wherein the first and second resources are threads.

49. The method of claim 40, further comprising returning the element to the first resource, if the element is present in the first, second, or third way.

50. The method of claim 40, wherein an element is selected from a group consisting of an instruction, an operand, a data operand, and a binary value.

51. A method comprising:

assigning a first way of a cache to a first computing resource of a plurality of computing resources, each computing resource being assigned at least one way of the cache;

assigning a dynamically shared portion of the cache to the plurality of computing resources;

counting the number of access to the cache made by the first computing resource over a first period of time;

re-assigning the first way to the dynamically shared portion of the cache, if the number of access made by the first computing resource over the first period of time is less than a predetermined number.

52. The method of claim 51, further comprising after re-assigning the first way to the dynamically shared portion of the cache, assigning the first way back from the dynamically shared portion to the first computing resource, if a first number of misses to the cache by the first computing resource occur during a second period of time.

53. The method of claim 52, wherein the first number of misses is one.

55. The method of claim 51, wherein an access to the cache comprises requesting an element from the cache.

56. The method of claim 51, wherein an access to the cache comprises a miss to the cache by the first computing resource.