Sharing Pattern-Based Directory Coherence for Multicore Scalability ("SPACE")

• US 20140032848A1
• Filed: 09/07/2012
• Published: 01/30/2014
• Est. Priority Date: 09/09/2011
• Status: Active Grant

• Current Assignee: University of Rochester
• Original Assignee: University of Rochester
• Inventors: DWARKADAS, Sandhya, ZHAO, Hongzhou, SHRIRAMAN, Arrvindh
• Granted Patent: US 9,411,733 B2
• Time in Patent Office: Days
• US Class Current: 711/130
• CPC Class Codes: G06F 12/082 Associative directories G06F12/0822 takes precedence
• CPC Class Codes: G06F 12/0826 Limited pointers directories; State-only directories without pointers
• CPC Class Codes: G06F 12/084 with a shared cache
• CPC Class Codes: G06F 2212/1044 Space efficiency improvement

Abstract

A method and directory system that recognizes and represents the subset of sharing patterns present in an application is provided. As used herein, the term sharing pattern refers to a group of processors accessing a single memory location in an application. The sharing pattern is decoupled from each cache line and held in a separate directory table. The sharing pattern of a cache block is the bit vector representing the processors that share the block. Multiple cache lines that have the same sharing pattern point to a common entry in the directory table. In addition, when the table capacity is exceeded, patterns that are similar to each other are dynamically collated into a single entry.

Claims

1. A system for decoupling the metadata representing sharing patterns from the address tags representing the data blocks, in a cache coherent shared memory computer comprising:

a directory table for storing in each entry of the directory table a unique sharing pattern that an application exhibits when it is executing; and

a cache having a pointer associated with the address tag of each of its data blocks (cache lines), where each pointer points to an entry in the directory table.

2. A method of decoupling the metadata representing sharing patterns from the address tags representing the data blocks, in a cache coherent shared memory computer comprising:

providing a directory table for storing in each entry of the directory table a unique sharing pattern that an application exhibits when it is executing; and

providing a cache having a pointer associated with the address tag of each of its data blocks (cache lines), where each pointer points to an entry in the directory table.

3. The method of claim 2 further comprising determining when a sharing pattern in the directory table is no longer is use in the pattern table.

4. The method of claim 3, wherein determining when a sharing pattern in the directory table is no longer is use in the pattern table comprises:

providing a reference counter associated with every entry in the directory table that counts the actual number of data blocks that refer to the sharing pattern; and

determining that the entry is no longer in use when the reference counter is zero.

5. The method of claim 2 further comprising inserting a new sharing pattern that has emerged in the application into the directory table.

6. The method of claim 5, wherein inserting a new sharing pattern that has emerged in the application into the directory table comprises:

decrementing the reference count of the sharing pattern to which the block currently points;

using a hashing function to identify any entries in the pattern table with the same sharing pattern;

modifying an available entry that is no longer in use to contain the sharing pattern if none exists;

changing the pointer associated with the data block to point to the entry containing the sharing pattern; and

incrementing the reference count of the sharing pattern entry pointed to.

7. The method of claim 2 further comprising comparing and merging with existing patterns.

8. The method of claim 7, wherein comparing and merging with existing patterns comprises:

using the hashing function to find existing patterns to compare against the new sharing pattern;

using a cost function to compare the new pattern with existing patterns and determine the cost of introducing false sharers; and

determining which entry in the sharing pattern table to merge with the incoming pattern based on the cost function.

9. A system for comparing and merging with existing patterns comprising:

a hashing function to find existing patterns to compare against the new sharing pattern;

a cost function to compare the new pattern with existing patterns and determine the cost of introducing false sharers; and

logic for determining which entry in the sharing pattern table to merge with the incoming pattern based on the cost function.