Non-uniform cache apparatus, systems, and methods

• US 6,965,969 B2
• Filed: 10/08/2004
• Issued: 11/15/2005
• Est. Priority Date: 04/08/2002
• Status: Active Grant

• Current Assignee: Board of Regents of the University of Texas System (University of Texas System)
• Original Assignee: Board of Regents of the University of Texas System (University of Texas System)
• Inventors: Burger, Doug, Kim, Changkyu, Keckler, Stephen W.
• Primary Examiner(s): BRAGDON, REGINALD GLENWOOD
• Application Number:
  US10/962,295
• Publication Number:
  US 20050132140A1
• Time in Patent Office: 403 Days
• Field of Search: 711/128, 711/167, 711/5, 711/136
• US Class Current: 711/128
• CPC Class Codes: G06F 12/0846 Cache with multiple tag or data arrays being simultaneously accessible
• CPC Class Codes: G06F 12/0897 with two or more cache hierarchy levels with multilevel cache hierarchies G06F12/0811
• CPC Class Codes: G06F 12/12 Replacement control
• CPC Class Codes: G06F 2212/271 Non-uniform cache access [NUCA] architecture

Abstract

An apparatus or system may comprises cache control circuitry coupled to a processor, and a plurality of independently accessible memory banks (228) coupled to the cache control circuitry. Some of the banks may have non-uniform latencies, organized into two or more spread bank sets (246). A method may include accessing data in the banks, wherein selected banks are closer to the cache control circuitry and/or processor than others, and migrating a first datum (445) to a closer bank from a further bank upon determining that the first datum is accessed more frequently than a second datum, which may be migrated to the further bank (451).

Claims

1. An apparatus, comprising:

cache control circuitry; and

a plurality of independently accessible memory banks organized as spread bank sets and coupled to the cache control circuitry, wherein at least four of the plurality of independently accessible memory banks have non-uniform latencies.

2. The apparatus of claim 1, wherein a plurality of cache lines are statically mapped to at least one of the plurality of independently accessible memory banks.

3. The apparatus of claim 1, wherein each one of the plurality of independently accessible memory banks is coupled to the cache control circuitry using a private channel.

4. The apparatus of claim 1, wherein the cache control circuitry cannot send a second request to a selected one of the plurality of independently accessible memory banks until the selected one of the plurality of independently accessible memory banks has completed processing a first request from the cache control circuitry.

5. The apparatus of claim 1, wherein the plurality of independently accessible memory banks is formed as an array having a side, and wherein the cache control circuitry is located approximately at the side.

6. The apparatus of claim 1, wherein selected ones of the plurality of independently accessible memory banks are set-associative banks.

7. The apparatus of claim 1, wherein each one of the plurality of independently accessible memory banks is coupled to the cache control circuitry using a switched network.

8. The apparatus of claim 7, wherein the switched network is a switched two-dimensional mesh network.

9. The apparatus of claim 7, wherein selected ones of a plurality of point-to-point links included in the switched network are connected using bidirectional routing.

10. The apparatus of claim 7, wherein selected ones of a plurality of point-to-point links included in the switched network are connected using unidirectional routing.

11. The apparatus of claim 10, wherein the switched network includes a plurality of routers, and wherein selected ones of the plurality of routers are located at selected intersections of the plurality of independently accessible memory banks.

12. The apparatus of claim 11, wherein the plurality of routers is to route addresses.

13. The apparatus of claim 11, wherein the plurality of routers is to route read data.

14. The apparatus of claim 11, wherein the plurality of routers is to route write data.

15. The apparatus of claim 10, wherein selected ones of the plurality of independently accessible memory banks include a tag array.

16. The apparatus of claim 10, wherein selected ones of the plurality of independently accessible memory banks include a request buffer.

17. The apparatus of claim 10, further comprising:

a request buffer coupled to the cache controller circuitry, wherein a request from the cache controller circuitry to one of the plurality of independently accessible memory banks results in a conflict, and wherein the request is stored in the request buffer.

18. The apparatus of claim 10, wherein the switched network is an asynchronous network.

19. The apparatus of claim 1, wherein a plurality of cache lines are capable of being dynamically mapped to at least two of the plurality of independently accessible memory banks.

20. The apparatus of claim 19, further comprising:

a distributed tag store coupled to the cache controller circuitry.

21. The apparatus of claim 19, further comprising:

a centralized partial tag store coupled to the cache controller circuitry.

22. The apparatus of claim 21, further comprising:

a broadcast module coupled to the cache controller circuitry for broadcasting a tag to each one of the plurality of independently accessible memory banks.

23. The apparatus of claim 1, wherein the plurality of independently accessible memory banks are organized into at least two spread bank sets.

24. The apparatus of claim 23, wherein a selected bank of the plurality of independently accessible memory banks is closer to a processor coupled to the cache controller circuitry than another selected bank of the plurality of independently accessible memory banks.

25. The apparatus of claim 24, wherein the selected bank and the other selected bank are both located within a selected one of the at least two spread bank sets.

26. The apparatus of claim 23, wherein each bank in one of the at least two spread bank sets holds more than one associative way of the one of the at least two spread bank sets.

27. The apparatus of claim 26, wherein the one of the at least two spread bank sets includes at least two memory banks and wherein the at least one associative way of one of the at least two memory banks has a different access latency than another associative way of another one of the at least two memory banks.

28. The apparatus of claim 23, wherein the plurality of independently accessible memory banks are organized into the at least two spread bank sets by mapping a subset of the plurality of independently accessible banks to each one of the at least two spread bank sets.

29. The apparatus of claim 28, wherein the plurality of independently accessible memory banks are organized into the at least two spread bank sets by mapping a first group of banks of the plurality of independently accessible memory banks to one of the at least two spread bank sets and a second group of banks of the plurality of independently accessible memory banks to an other one of the at least two spread bank sets.

30. The apparatus of claim 29, wherein the first group of banks of the plurality of independently accessible memory banks comprises a first column, and wherein the second group of banks of the plurality of independently accessible memory banks comprises a second column.

31. The apparatus of claim 29, wherein the plurality of independently accessible memory banks are organized into the at least two spread bank sets by fair mapping selected ones of the plurality of independently accessible memory banks.

32. The apparatus of claim 29, wherein the plurality of independently accessible memory banks are organized into the at least two spread bank sets by fast shared mapping selected ones of the plurality of independently accessible memory banks.

33. The apparatus of claim 1, wherein the plurality of independently accessible memory banks is organized into an n-way set-associative cache memory including m-spread bank sets, wherein each spread bank set includes a subset of memory banks selected from the plurality of independently accessible memory banks, and wherein at least two of the n-ways has a different access latency.

34. The apparatus of claim 33, wherein each way of the n-ways has a different access latency.

35. A processor, comprising:

an arithmetic functional unit;

cache control circuitry coupled to the arithmetic logic unit; and

a plurality of independently accessible memory banks coupled to the cache control circuitry, wherein at least two of the plurality of independently accessible memory banks have non-uniform latencies, and wherein the plurality of independently accessible memory banks are organized into at least two spread bank sets.

36. A system, comprising:

a processor including cache control circuitry and a plurality of independently accessible memory banks coupled to the cache control circuitry, wherein at least two of the plurality of independently accessible memory banks have non-uniform latencies, and wherein the plurality of independently accessible memory banks are organized into at least two spread bank sets;

a bus operatively coupled to the processor; and

a random access memory operatively coupled to the bus.

37. A method, comprising:

accessing a first datum and a second datum in a plurality of independently accessible memory banks operatively coupled to a processor, wherein at least two of the plurality of independently accessible memory banks have non-uniform latencies, wherein the plurality of independently accessible memory banks are organized into at least two spread bank sets, and wherein a selected one of the plurality of independently accessible memory banks is closer to the processor than a selected other one of the plurality of independently accessible memory banks; and

migrating the first datum to the selected one of the plurality of independently accessible memory banks from the selected other one of the plurality of independently accessible memory banks upon determining that a selected criterion has been met.

38. The method of claim 37, wherein the selected criterion is met upon determining that the first datum is accessed more frequently than the second datum.

39. The method of claim 38, comprising:

migrating the second datum to the selected other one of the plurality of independently accessible memory banks from the selected one of the plurality of independently accessible memory banks upon determining that the selected criterion has been met.

40. The method of claim 37, wherein the plurality of independently accessible memory banks is organized into an n-way set-associative cache memory including m-spread bank sets, and wherein each spread bank set includes at least two memory banks selected from the plurality of independently accessible memory banks.

41. A method, comprising:

accessing a first datum and a second datum in a plurality of independently accessible memory banks operatively coupled to a processor, wherein at least two of the plurality of independently accessible memory banks have non-uniform latencies, wherein the plurality of independently accessible memory banks are organized into a plurality of spread bank sets, and wherein selected ones of the plurality of independently accessible memory banks are closer to the processor than selected other ones of the plurality of independently accessible memory banks; and

migrating the first datum progressively closer to the processor through preselected ones of the plurality of independently accessible memory banks from at least one of the selected other ones of the plurality of independently accessible memory banks to at least one of the selected ones of the plurality of independently accessible memory banks upon determining that the first datum is accessed more frequently than the second datum.

42. The method of claim 41, wherein accessing a first datum and a second datum in a plurality of independently accessible memory banks operatively coupled to a processor includes:

searching the plurality of independently accessible memory banks operatively coupled to a processor using a multicast search policy.

43. The method of claim 41, wherein accessing a first datum and a second datum in a plurality of independently accessible memory banks operatively coupled to a processor includes:

searching the plurality of independently accessible memory banks operatively coupled to a processor using a limited multicast search policy.

44. The method of claim 41, wherein accessing a first datum and a second datum in a plurality of independently accessible memory banks operatively coupled to a processor includes:

searching the plurality of independently accessible memory banks operatively coupled to a processor using an incremental search policy.

45. The method of claim 41, wherein accessing a first datum and a second datum in a plurality of independently accessible memory banks operatively coupled to a processor includes:

searching the plurality of independently accessible memory banks operatively coupled to a processor using a partitioned multicast search policy.

46. The method of claim 41, wherein accessing a first datum and a second datum in a plurality of independently accessible memory banks operatively coupled to a processor includes:

searching the plurality of independently accessible memory banks operatively coupled to a processor using a combination of policies selected from a group including;

a multicast policy, a limited multicast policy, an incremental search policy, and a partitioned multicast search policy.

47. The method of claim 41, wherein migrating the first datum progressively closer to the processor through preselected ones of the plurality of independently accessible memory banks includes:

evicting a cache line within a selected one of the plurality of spread bank sets based on a least-recently-used (LRU) bit policy.

48. The method of claim 41, wherein migrating the first datum progressively closer to the processor through preselected ones of the plurality of independently accessible memory banks includes:

moving a cache line within a selected one of the plurality of spread bank sets based on a generational promotion policy.

49. The method of claim 48, wherein moving a cache line within a selected one of the plurality of spread balk sets based on a generational promotion policy includes:

selecting a promotion distance for the generational promotion policy; and

selecting a promotion trigger for the generational promotion policy.

50. The method of claim 41, wherein migrating the first datum progressively closer to the processor through preselected ones of the plurality of independently accessible memory banks includes:

swapping the first datum with another datum located in a closer memory bank.

51. The method of claim 41, wherein migrating the first datum progressively closer to the processor through preselected ones of the plurality of independently accessible memory banks includes:

choosing a victim bank by accessing a central tag store.

52. The method of claim 41, wherein migrating the first datum progressively closer to the processor through preselected ones of the plurality of independently accessible memory banks includes:

accessing distributed tags included in the plurality of independently accessible memory banks.

53. The method of claim 41, wherein migrating the first datum progressively closer to the processor through preselected ones of the plurality of independently accessible memory banks includes:

accessing partial tags in a central tag store; and

accessing distributed tags included in the plurality of independently accessible memory banks.