Accelerating cache state transfer on a directory-based multicore architecture

• US 9,760,486 B2
• Filed: 03/25/2016
• Issued: 09/12/2017
• Est. Priority Date: 12/29/2010
• Status: Active Grant

• Current Assignee: Mercury Kingdom Assets Limited
• Original Assignee: Empire Technology Development LLC (Allied Inventors Management, LLC)
• Inventors: Solihin, Yan
• Primary Examiner(s): Chappell, Daniel C
• Application Number:
  US15/080,605
• Publication Number:
  US 20160210229A1
• Time in Patent Office: 536 Days
• CPC Class Codes: G06F 12/0804 with main memory updating G06F12/0806 takes precedence
• CPC Class Codes: G06F 12/0806 Multiuser, multiprocessor or multiprocessing cache systems
• CPC Class Codes: G06F 12/0817 using directory methods
• CPC Class Codes: G06F 12/123 with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list
• CPC Class Codes: G06F 2212/62 Details of cache specific to multiprocessor cache arrangements
• CPC Class Codes: G06F 9/461 Saving or restoring of program or task context
• CPC Class Codes: G06F 9/4856 resumption being on a different machine, e.g. task migration, virtual machine migration G06F9/5088 takes precedence

Abstract

Technologies are generally described herein for accelerating a cache state transfer in a multicore processor. The multicore processor may include first, second, and third tiles. The multicore processor may initiate migration of a thread executing on the first core at the first tile from the first tile to the second tile. The multicore processor may determine block addresses of blocks to be transferred from a first cache at the first tile to a second cache at the second tile, and identify that a directory at the third tile corresponds to the block addresses. The multicore processor may update the directory to reflect that the second cache shares the blocks. The multicore processor may transfer the blocks from the first cache in the first tile to the second cache in the second tile effective to complete the migration of the thread from the first tile to the second tile.

Claims

1. A method to accelerate a cache state transfer in a multicore processor, the method comprising:

initiating a migration of a thread, which executes on a first core at a first tile in the multicore processor from the first tile to a second tile in the multicore processor, wherein the first tile includes the first core and a first directory that maps a first set of block addresses and a first cache that is in the first tile, and wherein the second tile includes a second core and a second directory that maps a second set of block addresses and a second cache that is in the second tile;

determining block addresses of blocks to be transferred from the first cache to the second cache based on the migration of the thread that executes on the first core at the first tile to the second tile in the multicore processor,

identifying a third tile in the multicore processor, wherein the third tile includes a third directory that maps a third set of block addresses of a third cache in the third tile;

updating the third directory to reflect that the second cache shares the blocks by sending a message from the first tile to the third tile;

transferring the blocks from the first cache in the first tile to the second cache in the second tile to complete the migration of the thread from the first tile to the second tile;

using a transfer status table to maintain first status information on the update of the third directory, and second status information on the transfer of the blocks from the first cache to the second cache; and

based on the first status information and the second status information maintained in the transfer status table, determining whether to send at least one of an invalidation request or an intervention request from the first tile to the second tile.

2. The method of claim 1, wherein prior to the update of the third directory, the third directory indicates that the first cache contains the blocks and the second cache does not share the blocks.

3. The method of claim 1, wherein determining the block addresses of the blocks to be transferred from the first cache to the second cache includes scanning a cache tag array associated with the first cache.

4. The method of claim 1, further comprising:

receiving, at the first tile, a successful directory update acknowledgement from the third tile prior to transferring the blocks from the first cache in the first tile to the second cache in the second tile.

5. The method of claim 1, wherein transferring the blocks from the first cache in the first tile to the second cache in the second tile includes transferring a portion of the blocks that are most recently used (MRU) from the first cache in the first tile to the second cache in the second tile.

6. The method of claim 5, further comprising:

determining the portion of the blocks that are MRU based on an access pattern of the thread that executes on the first core at the first tile, wherein the access pattern of the thread includes a temporal reuse behavior of the thread.

7. The method of claim 1, wherein updating the third directory to reflect that the second cache shares the blocks further comprises updating a bit vector to reflect that the second cache contains the blocks, and wherein the third directory comprises the bit vector.

8. The method of claim 7, wherein the bit vector includes bits, wherein each of the bits is associated with a corresponding tile in the multicore processor, and wherein a value of each of the bits specifies whether the corresponding tile includes a corresponding cache that contains the blocks.

9. The method of claim 1, wherein transferring the blocks from the first cache in the first tile to the second cache in the second tile includes moving blocks from the first cache to the second cache such that the second cache stores the blocks and the first cache does not store the blocks.

10. A multicore processor, comprising:

a first tile that comprises a first core, a first cache, and a first directory that maps a first set of block addresses of the first cache;

a second tile that comprises a second core, a second cache, and a second directory that maps a second set of block addresses of the second cache;

a third tile that comprises a third core, a third cache, and a third directory that maps a third set of block addresses of the third cache; and

a transfer status table operatively coupled to at least the first tile, wherein the multicore processor is configured to;

initiate a migration of a thread that executes on the first core at the first tile to the second tile;

determine block addresses of blocks to be transferred from the first cache to the second cache based on the migration of the thread that executes on the first core at the first tile to the second tile;

update the third directory to reflect that the second cache shares the blocks;

transfer the blocks from the first cache in the first tile to the second cache in the second tile to complete the migration of the thread from the first tile to the second tile;

use the transfer status table to maintain first status information on the update of the third directory, and second status information on the transfer of the blocks from the first cache to the second cache; and

based on the first status information and the second status information maintained in the transfer status table, determine whether to send at least one of an invalidation request or an intervention request from the first tile to the second tile.

11. The multicore processor of claim 10, wherein to update the third directory, the first tile is configured to send a message to the third tile, and wherein the message includes a list of the block addresses of the blocks to be transferred from the first cache to the second cache and an identifier of the second cache, to which the blocks are to be transferred.

12. The multicore processor of claim 10, wherein to transfer the blocks from the first cache in the first tile to the second cache in the second tile, the multicore processor is configured to:

replicate the blocks between the first cache and the second cache such that the first cache and the second cache store the blocks.

13. The multicore processor of claim 12, wherein the replication of the blocks between the first cache and the second cache includes sending an instruction to update a main memory to clean dirty entries in the blocks.

14. The multicore processor of claim 13, wherein:

the main memory includes a shared memory architecture, and

the main memory is configured to operate with a directory based coherence protocol.

15. The multicore processor of claim 10, wherein to transfer the blocks from the first cache in the first tile to the second cache in the second tile, the multicore processor is configured to:

transfer the blocks from the first cache to the second cache concurrently with the update of the third directory to reflect that the second cache shares the blocks.

16. The multicore processor of claim 10, wherein:

the third set of block addresses corresponds to the block addresses of the blocks to be transferred from the first cache to the second cache, and

prior to the update of the third directory, the third directory indicates that the first cache contains the blocks and the second cache does not share the blocks.

17. The multicore processor of claim 10, wherein the transfer of the blocks from the first cache in the first tile to the second cache in the second tile occurs subsequent to receipt, at the first tile, of a successful directory update acknowledgement from the third tile.

18. A non-transitory computer-readable storage device having instructions stored thereon to accelerate a cache state transfer in a multicore processor, the instructions being executable by the multicore processor to perform or cause to be performed operations comprising:

initiating a migration of a thread, which executes on a first core at a first tile in the multicore processor, from the first tile to a second tile in the multicore processor, wherein the first tile includes the first core and a first directory that maps a first set of block addresses and a first cache that is in the first tile, and wherein the second tile includes a second core and a second directory that maps a second set of block addresses, and a second cache that is in the second tile;

determining block addresses of blocks to be transferred from the first cache to the second cache based on the migration of the thread that executes on the first core at the first tile to the second tile in the multicore processor;

identifying a third tile in the multicore processor, wherein the third tile includes a third directory that maps a third set of block addresses of a third cache that is in the third tile;

updating the third directory to reflect that the second cache shares the blocks;

transferring the blocks from the first cache in the first tile to the second cache in the second tile;

using a transfer status table to maintain first status information on the update of the third directory and second status information on the transfer of the blocks from the first cache to the second cache; and

based on the first status information and the second status information maintained in the transfer status table, determining whether to send at least one of an invalidation request or an intervention request from the first tile to the second tile.

19. The non-transitory computer-readable storage device of claim 18, wherein the operations comprising transferring the blocks from the first cache in the first tile to the second cache in the second tile include operations that comprise:

transferring a portion of the blocks that are most recently used (MRU) from the first cache in the first tile to the second cache in the second tile; and

determining the portion of the blocks that are MRU based on an access pattern of the thread that executes on the first core at the first tile, wherein the access pattern of the thread includes a temporal reuse behavior of the thread.

20. The non-transitory computer-readable storage device of claim 18, wherein the operations comprising transferring the blocks from the first cache in the first tile to the second cache in the second tile include operations that comprise:

replicating the blocks between the first cache and the second cache such that the first cache and the second cache store the blocks; and

sending an instruction to update a main memory to clean dirty entries in the blocks, wherein the main memory includes a shared memory architecture, and wherein the main memory is configured to operate with a directory based coherence protocol.