HIGH-PERFORMANCE CACHE SYSTEM AND METHOD

• US 20110238917A1
• Filed: 12/22/2010
• Published: 09/29/2011
• Est. Priority Date: 12/25/2009
• Status: Active Grant

• Current Assignee: Shanghai Xin Hao Micro Electronics Co., Ltd.
• Original Assignee: Shanghai Xin Hao Micro Electronics Co., Ltd.
• Inventors: Lin, Kenneth Chenghao, Ren, Haoqi
• Granted Patent: US 8,527,707 B2
• Time in Patent Office: Days
• US Class Current: 711/125
• CPC Class Codes: G06F 12/0875 with dedicated cache, e.g. instruction or stack
• CPC Class Codes: G06F 9/3802 Instruction prefetching
• CPC Class Codes: G06F 9/3804 for branches, e.g. hedging, branch folding
• CPC Class Codes: G06F 9/3806 using address prediction, e.g. return stack, branch history buffer
• CPC Class Codes: G06F 9/3808 for instruction reuse, e.g. trace cache, branch target cache
• CPC Class Codes: G06F 9/382 Pipelined decoding, e.g. using predecoding
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

A digital system is provided for high-performance cache systems. The digital system includes a processor core and a cache control unit. The processor core is capable of being coupled to a first memory containing executable instructions and a second memory with a faster speed than the first memory. Further, the processor core is configured to execute one or more instructions of the executable instructions from the second memory. The cache control unit is configured to be couple to the first memory, the second memory, and the processor core to fill at least the one or more instructions from the first memory to the second memory before the processor core executes the one or more instructions, Further, the cache control unit is also configured to examine instructions being filled from the first memory to the second memory to extract instruction information containing at least branch information, to create a plurality of tracks based on the extracted instruction information; and to fill the at least one or more instructions based on one or more tracks from the plurality of instruction tracks,

Claims

1. A digital system, comprising:

a processor core capable of being coupled to a first memory containing executable instructions and a second memory with a faster speed than the first memory, and configured to execute one or more instructions of the executable instructions from the second memory; and

a cache control unit configured to be coupled to the first memory, the second memory, and the processor core to fill at least the one or more instructions from the first memory to the second memory before the processor core executes the one or more instructions,

wherein the cache control unit is further configured to;

examine instructions being filled from the first memory to the second memory to extract instruction information containing at least branch information;

create a plurality of tracks based on the extracted instruction information; and

fill the at least one or more instructions based on one or more tracks from the plurality of instruction tracks.

2. The digital system according to claim 1, wherein:

the instruction information further includes an instruction type as one of a branch instruction and a non-branch instruction.

3. The digital system according to claim 1, wherein:

the branch information further includes a branch source address and a branch target address.

4. The digital system according to claim 1, wherein:

the plurality of tracks are arranged in an address tree configuration where a tree trunk corresponds to a track, and a tree branch corresponds to a branch instruction.

5. The digital system according to claim 4, wherein:

the executable instructions in the first memory are arranged in a plurality of instruction blocks;

the second memory includes a plurality of memory blocks corresponding to the plurality of tracks, each memory block being capable of storing an instruction block; and

before the processor core executes the branch instruction, a first instruction block corresponding to the new track and a second instruction block corresponding to a next instruction in sequence to the branch instruction, if not already in the second memory, are filled in corresponding memory blocks of the second memory from the first memory.

6. The digital system according to claim 5, wherein:

a third instruction block corresponding to a branch target instruction of a first branch point of the new track or to a branch target instruction of a first branch point following the next instruction is also filled in a corresponding memory block of the second memory from the first memory.

7. The digital system according to claim 5, wherein:

before the processor core executes the branch instruction, a plurality of third instruction blocks corresponding to tracks determined by a predetermined number of instructions following the branch instruction, whether or not a branch condition of the branch point is satisfied, are filled in the second memory from the first memory.

8. The digital system according to claim 2, wherein:

the cache control unit includes a track table containing a plurality of track table rows, each table row corresponding to a track.

9. The digital system according to claim 8, wherein:

a table row includes a plurality of entries, each entry corresponding to a track point, which corresponds to at least one instruction.

10. The digital system according to claim 9, wherein:

the track point is addressed by a first address for determining a track number, and a second address for determining an offset within the track.

11. The digital system according to claim 10, wherein:

when the processor core executes an instruction corresponding to the track point, the cache control unit provides the first address to determine a memory block containing the instruction, and

the processor core provides an offset within the memory block to fetch the instruction from the second memory.

12. The digital system according to claim 10, wherein:

an entry corresponding to a branch track point stores the first address and the second address indicating a new track point determined by a target branch address of a branch target instruction of the branch point

13. The digital system according to claim 12, wherein:

the target branch address is calculated as a summation of a block address of an instruction block corresponding to the branch track point, the offset of the branch track point, and a branch offset of the branch target instruction.

14. The digital system according to claim 10, wherein:

the cache control unit further includes a tracker configured to provide the first address and the second address from one of a plurality of sources including the track table and an address incrementer.

15. The digital system according to claim 14, wherein:

the plurality of sources further include at least one stack and an exception handler register.

16. The digital system according to claim 14, wherein, to provide the first address and the second address, the tracker is further configured to:

determine whether a current track point has a branch;

when the current track point does not have a branch, keep a current first address unchanged as a next first address, and increase a current second address by one using the address incrementer as a next second address to reach a next track point.

17. The digital system according to claim 16, wherein the tracker is further configured to:

when the current track point has a branch, wait for a control signal from the processor core to indicate whether the branch is taken by the processor core; and

when the branch is taken, provide the first address and the second address from the entry of the branch track point as the next first address and the next second address, respectively.

18. The digital system according to claim 17, wherein the tracker is further configured to:

when the branch is not taken, keep the current first address unchanged as the next first address, and increase the current second address by one using the address incrementer as the next second address to reach the next track point.

21. The method according to claim 1.9, wherein:

the branch information further includes a branch source address and a branch target address.

26. The method according to claim 21, further including:

creating a track table containing a plurality of track table rows corresponding to the plurality of tracks, each table row corresponding to a track.

27. The method according to claim 26, wherein:

a table row includes a plurality of entries, each entry corresponding to a track point, which corresponds to at least one instruction.

28. The method according to claim 27, further including:

addressing the track point by a first address for determining a track number, and a second address for determining an offset within the track.

29. The method according to claim 28, further including:

when the processor core executes an instruction corresponding to the track point, providing the first address to determine a memory block containing the instruction, wherein the processor core provides an offset within the memory block to fetch the instruction from the second memory.

30. The method according to claim 29, further including:

storing in an entry corresponding to a branch point the first address and the second address indicating a new track point determined by a target branch address of a branch target instruction of the branch point.

31. The method according to claim 30, further including:

calculating the target branch address is calculated as a summation of a block address of an instruction block corresponding to the branch track point, the offset of the branch track point, and a branch offset of the branch target instruction.

32. The method according to claim 28, further including:

providing the first address and the second address from one of a plurality of sources including the track table and an address incrementer.

33. The method according to claim 32, wherein:

the plurality of sources further include at least one stack and an exception handler register.

34. The method according to claim 32, wherein providing the first address and the second address further includes:

determining whether a current track point has a branch;

when the current track point does not have a branch, keeping a current first address unchanged as a next first address, and increasing a current second address by one as a next second address to reach a next track point.

35. The method according to claim 34, further including:

when the current track point has a branch, waiting for a control signal from the processor core to indicate whether the branch is taken by the processor core;

when the branch is taken, providing the first address and the second address from the entry of the branch track point as the next first address and the next second address, respectively.

36. The method according to claim 35, further including:

when the branch is not taken, keeping the current first address unchanged as the next first address, and increasing the current second address by one as the next second address to reach the next track point.

19. A method for facilitating operation of a processor core coupled to a first memory containing executable instructions and a second memory faster than the first memory, the method comprising:

examining instructions being filled from the first memory to the second memory to extract instruction information containing at least branch information;

creating a plurality of tracks based on the extracted instruction information; and

filling at least one or more instructions based on one or more tracks from the plurality of instruction tracks from the first memory to the second memory before the processor core executes the at least one or more instructions from the second memory such that the processor core fetches the at least one or more instructions for execution from the second memory.

20. The method according to claim :

19, wherein;

the instruction information further includes an instruction type as one of a branch instruction and a non-branch instruction.

22. The method according to claim 19, further including:

arranging the plurality of tracks in an address tree configuration where a tree trunk corresponds to a track, and a tree branch corresponds to a branch instruction.

23. The method according to claim 22, wherein the executable instructions in the first memory are arranged in a plurality of instruction blocks, and the second memory includes a plurality of memory blocks corresponding to the plurality of tracks with each memory block is capable of storing an instruction block, the method further including:

before the processor core executes the branch instruction, filling an instruction block corresponding to the new track and an instruction block corresponding to a next instruction in sequence to the branch instruction, if not already in the second memory, in corresponding memory blocks of the second memory from the first memory.

24. The method according to claim 23, further including:

filling a third instruction block corresponding to a branch target instruction of a first branch point of the new track or to a branch target instruction of a first branch point following the next instruction in a corresponding memory block of the second memory from the first memory.

25. The method according to claim 23, further including:

before the processor core executes the branch instruction, filling a plurality of third instruction blocks corresponding to tracks determined by a predetermined number of instructions following the branch instruction whether or not a branch condition of the branch point is satisfied in the second memory from the first memory.

37. A method for use in a cache control device to control cache operation for a processor core capable of being coupled to a first memory containing executable instructions and a second memory with a faster speed than the first memory, and configured to execute one or more instructions of the executable instructions from the second memory, the method comprising:

examining instructions being filled from the first memory to the second memory;

extracting instruction information from the examined instructions;

determining a branch point before the processor core executes the branch point, based on the extracted instruction information; and

filling an instruction block corresponding to a branch target instruction of the branch point from the first memory to the second memory such that the processor core executes any instruction resulted from the branch point from the second memory.

38. The method according to claim 37, wherein filling further includes:

determining whether the instruction block is already in the second memory; and

when the instruction block is not already in the second memory, filling the instruction block corresponding the branch target instruction of the branch point from the first memory to the second memory such that the processor core executes any instruction resulted from the branch point from the second memory.

39. The method according to claim 37, further including:

using information on whether a branch of the branch point is taken by the processor core to determine a next branch point after the branch point executed by the processor core.

40. The method according to claim 37, further including:

creating a track table containing a plurality of track table rows corresponding to the plurality of tracks, each table row corresponding to a track and including a plurality of entries, each entry corresponding to a track point, which corresponds to at least one instruction; and

using a look-ahead pointer to move along a track corresponding to the branch point until reaching the table entry of the branch point.

41. The method according to claim 40, further including:

determining a base address pointer of a data block associated with one or more track points of the track table; and

filling the data block corresponding to the one or more track points based on the base address pointer in advance of execution of the one or more track points by the processor core.

42. The method according to claim 41, further including:

storing the base address pointer in a base address pointer storage unit corresponding to the track table, wherein the base address and an offset from the processor core are used to address data in the data block.

43. The method according to claim 40, further including:

using a tracker to provide an address of a next track point along the track, the address containing a first address corresponding to a track table row number and a second address corresponding to a track table column number,

wherein the look-ahead pointer corresponds to the second address.

44. The method according to claim 43, further including:

keeping a current first address unchanged;

increasing a current second address by one to reach a next track point;

determining whether the next track point is a branch track point; and

when the next track point is a branch track point, providing the first address and the second address of a branch target address of the branch track point,

45. The method according to claim 44, wherein:

the tracker includes at least one stack capable of multiple-level stack operations to support a series of subroutines of a computer program.

46. The method according to claim 45, wherein:

the at least one stack is configured to include a plurality of stacks to support a multi-thread programming operation, wherein each thread corresponds to a separate stack from the plurality of stacks.

47. The method according to claim 45, further including:

representing the first address of a first track point of the track table in a first format; and

using an active list to provide a mapping relationship between a target track of the first track point and a first memory block address, wherein an instruction block corresponding to the first memory block address is filled in the second memory when the first track point is created in the track table in the first format.

48. The method according to claim 47, further including:

representing the first address in a second track point of the track table in a second format; and

using a reserve list to provide a mapping relationship between a target track of the second track point and a second memory block address, wherein an instruction block corresponding to the second memory block address is not filled in the second memory when the second track point is created in the track table in the second format.

49. The method according to claim 48, further including:

using an exchanger to convert between the first format and the second format.

50. The method according to claim 40, further including:

using a visiting frequency of an idle track stored in the track table to perform power management of the processor core,

51. The method according to claim 37, further including:

filling a plurality of instruction blocks related to the branch point from the first memory to the second memory, wherein;

each instruction block is divided into multiple segments;

each segment is assigned a priority; and

the multiple segments of the plurality of instruction blocks are filled in an interleaved scheme based on the priority of each segment.

52. The method according to claim 40, further including:

filling a plurality of data blocks related to one or more track points from the first memory to the second memory, wherein;

each data block is divided into multiple segments;

each segment is assigned a priority; and

the multiple segments of the plurality of data blocks are filled in an interleaved scheme based on the priority of each segment.

53. A method for use in a cache control device to control cache operation of a plurality of cache memories including a first memory and a second memory being coupled to a processor core and to the first memory, comprising:

respectively examining instructions being filled into the plurality of cache memories;

extracting instruction information from the examined instructions;

based on the extracted instruction information, creating a track point entry in a track table in which a target track point of the entry is represented by one of a low-level cache memory block number, and a high-level cache memory block number, wherein

when the target track point is represented by the low-level cache memory block number, an instruction block corresponding to the target track point is filled in the first memory, and

when the target track point is represented by the high-level cache memory block number, the instruction block corresponding to the target track is filled in the second memory instead of the first memory,

54. The method according to claim 53, further including:

using a table to create a mapping relationship between the low-level cache memory block number and a memory address of the instruction block, and between the low-level cache memory block number and a plurality high-level cache memory block numbers.

55. The method according to claim 54, further including:

determining whether a track point entry being analyzed includes a preset low-level cache memory block number; and

when the track point entry includes the preset low-level cache memory block number, determining whether a valid high-level cache memory block number is selected from the table indexed by the low-level cache memory block number.

56. The method according to claim 55, further including:

when the valid high-level cache memory block number is not selected, filling the instruction block from the first memory to the second memory;

generating the valid high-level cache memory block number; and

replacing the low-level cache memory block number in the track point entry with the high-level cache memory block number.

57. The method according to claim 56, wherein a third memory is coupled between the first memory and the second memory, the method further including:

when the track point entry includes the preset low-level cache memory block number, determining whether any of the valid high-level cache memory block number and a valid memory block number of the third memory is selected from the table indexed by the low-level cache memory block number,

58. The method according to claim 57, further including:

when the valid high-level cache memory block number is not selected and the valid memory block number of the third memory is selected, filling the instruction block from the third memory to the second memory; and

generating the valid high-level cache memory block number; and

replacing the low-level cache memory block number in the track point entry with the high-level cache memory block number.

59. The method according to claim 53, wherein the low-level cache memory block number is associated with a first list, and the high-level cache memory block number is associated with a second list, the method further including:

configuring the first list and the second list to ensure the instruction block is filled in either in the first memory or the second memory.

60. The method according to claim 53, wherein the low-level cache memory block number is associated with a first list, and the high-level cache memory block number is associated with a second list, the method further including:

configuring the first list and the second list to ensure the instruction block is filled in both in the first memory and the second memory.

61. A cache control device for controlling cache operation for a processor core capable of being coupled to a first memory containing executable instructions and a second memory with a faster speed than the first memory, and configured to execute one or more instructions of the executable instructions from the second memory, comprising:

a first fill and generator unit configured to examine instructions being filled from the first memory to the second memory, and to extract instruction information from the examined instructions;

a tracker configured to use a look-ahead pointer to determine a branch point before the processor core executes the branch point, based on the extracted instruction information; and

an allocator configured to fill an instruction block corresponding a branch target instruction of the branch point from the first memory to the second memory such that the processor core executes any instruction resulted from the branch point from the second memory.

62. The cache control device according to claim 61, wherein the allocator is further configured to:

determine whether the instruction ck is already in the second memory; and

when the instruction block is not already in the second memory, control the first fill and generator unit to fill the instruction block corresponding the branch target instruction of the branch point from the first memory to the second memory such that the processor core executes any instruction resulted from the branch point from the second memory.

63. The cache control device according to claim 62, wherein:

the first fill and generator unit includes a virtual to physical address translation unit.

64. The cache control device according to claim 61, wherein the tracker is further configured to:

use information on whether a branch of the branch point is taken by the processor core for the look-ahead pointer to determine a next branch point after the branch point executed by the processor core.

65. The cache control device according to claim 62, further including:

a track table configured to contain a plurality of track table rows corresponding to the plurality of tracks, each table row corresponding to a track and including a plurality of entries, each entry corresponding to a track point, which corresponds to at least one instruction,

wherein the tracker moves the look-ahead pointer along a track corresponding to the branch point until reaching the table entry of the branch point.

66. The cache control device according to claim 65, wherein the fill and generator unit is further configured to:

determine a base address pointer of a data block associated with one or more track points of the track table; and

fill the data block corresponding to the one or more track points based on the base address pointer in advance of execution of the one or more track points by the processor core.

67. The cache control device according to claim 66, further including:

a base address pointer storage unit configured to store the base address pointer in corresponding to the track table, wherein the base address pointer and an offset from the processor core are used to address data in the data block.

68. The cache control device according to claim 63, wherein the tracker is further configured to:

provide an address of a next track point along the track, the address containing a first address corresponding to a track table row number and a second address corresponding to a track table column number, wherein the look-ahead pointer corresponds to the second address.

69. The cache control device according to claim 68, wherein the tracker is further configured to:

keep a current first address unchanged;

increase a current second address by one to reach a next track point;

determine whether the next track point is a branch track point; and

when the next track point is a branch track point, provide the first address and the second address of a branch target address of the branch track point.

70. The cache control device according to claim 69, wherein the tracker further includes a plurality of stacks configured to support a multi-thread programming operation, wherein each thread corresponds to a separate stack of the plurality of stacks.

71. The cache control device according to claim 68 wherein:

the track table represents the first address of a first track point in a first format; and

the allocator includes an active list configured to provide a mapping relationship between a target track of the first track point and a first memory block address, wherein an instruction block corresponding to the first memory block address is filled in the second memory when the first track point is created in the track table in the first format,

72. The cache control device according to claim 71, wherein:

the track table represents the first address in a second track point in a second format; and

the allocator includes a reserve list configured to provide a mapping relationship between a target track of the second track point and a second memory block address, wherein an instruction block corresponding to the second memory block address is not filled in the second memory when the second track point is created in the track table in the second format.

73. The cache control device according to claim 72, wherein:

the allocator implements at least one of a least recently used (LRU) replacement policy and a least frequently used (LFU) replacement policy for the second memory based on the active list and a clear window defined by a main pointer and a clear pointer for entries on the active list.

74. The cache control device according to claim 72, further including:

an exchanger configured to convert between the first format and the second format in the track table.

75. The cache control device according to claim 72, wherein:

when the instruction block corresponding to the first memory block address is replaced by a new instruction block in the second memory, a corresponding entry is created in the reserve list; and

the exchanger changes target addresses associated with the replaced instruction block in the track table from the first format to the second format.

76. The cache control device according to claim 72, further including:

a second fill and generator unit coupled between the first memory and a third memory, wherein the second fill and generator unit includes a virtual to physical address translation unit.

77. The cache control device according to claim 72, wherein:

the second memory is managed by the active list; and

the first memory is managed by the reserve list.

78. The cache control device according to claim 65, wherein:

the track table is configured to store an idle track, a visiting frequency of which is used to perform power management of the processor core.