System and method for partitioning of memory units into non-conflicting sets

• US 10,037,282 B2
• Filed: 09/23/2016
• Issued: 07/31/2018
• Est. Priority Date: 09/05/2013
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Waldspurger, Carl A., Horovitz, Oded, Weis, Stephen A., Rihan, Sahil
• Primary Examiner(s): Rones, Charles
• Assistant Examiner(s): DOAN, HAN V
• Application Number:
  US15/274,981
• Publication Number:
  US 20170206167A1
• Time in Patent Office: 676 Days
• CPC Class Codes: G06F 12/0815 Cache consistency protocols
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 12/0868 Data transfer between cache memory and other subsystems, e.g. storage devices or host systems
• CPC Class Codes: G06F 12/0891 using clearing, invalidating or resetting means
• CPC Class Codes: G06F 12/0895 of parts of caches, e.g. directory or tag array
• CPC Class Codes: G06F 12/126 with special data handling, e.g. priority of data or instructions, handling errors or pinning
• CPC Class Codes: G06F 2212/621 Coherency control relating to peripheral accessing, e.g. from DMA or I/O device

Abstract

A system and method of operation exploit the limited associativity of a single cache set to force observable cache evictions and discover conflicts. Loads are issued to input memory addresses, one at a time, until a cache eviction is detected. After observing a cache eviction on a load from an address, that address is added to a data structure representing the current conflict set. The cache is then flushed, and loads are issued to all addresses in the current conflict set, so that all known conflicting addresses are accessed first, ensuring that the next cache miss will occur on a different conflicting address. The process is repeated, issuing loads from all input memory addresses, incrementally finding conflicting addresses, one by one. Memory addresses that conflict in the cache belong to the same partition, whereas memory addresses belonging to different partitions do not conflict.

Claims

1. A method for managing memory in a computer comprising:

using known memory-address constraints to identify at least one input set of potentially conflicting memory addresses; and

for each of the at least one input set of potentially conflicting memory addresses, and iteratively for each of the memory addresses in the at least one input set;

loading a current memory address, belonging to the at least one input set, into a processor cache;

detecting whether an eviction occurs from the processor cache as a result of the loading of the current memory address into the processor cache;

if an eviction is detected;

adding the current memory address to a conflict set of memory addresses;

flushing the processor cache; and

loading the conflict set into the processor cache;

if no eviction is detected, determining whether all of the input set of potentially conflicting memory addresses has been loaded into the processor cache and, if not, loading a next one of the input set of potentially conflicting memory addresses into the processor cache;

whereby the input set of potentially conflicting memory addresses is determined to be partitioned into a plurality of partitions such that memory addresses that conflict in the processor cache belong to the same partition, whereas memory addresses belonging to different partitions do not conflict in the processor cache.

2. The method of claim 1, wherein each of the at least one input set of potentially conflicting memory addresses is a subset of all memory addresses.

3. The method of claim 1, further comprising:

marking the current memory address as being used after it has been loaded; and

loading as current memory addresses of subsequent input sets only memory addresses not marked as used.

4. The method of claim 1, further comprising detecting whether an eviction occurs by detecting a change in a hardware performance counter.

5. The method of claim 1, further comprising:

configuring a hardware performance counter to count cache misses;

detecting whether an eviction occurs as a result of accessing a newly loaded memory address by reloading into the processor cache, one by one and in order, previously loaded memory addresses, examining the hardware performance counter after each reloading, and determining the eviction as being the result of loading the newly loaded memory address if the hardware performance counter indicates a cache miss upon loading of the newly loaded memory address.

6. The method of claim 1, further comprising detecting whether an eviction occurs as a function of access latency for each respective current memory address.

7. The method as in claim 1, in which the partitions have a cache-line granularity.

8. The method of claim 1, further comprising:

selecting a memory address from the conflict set;

removing the selected memory address from the conflict set;

adding the selected memory address to an auxiliary overflow data structure associated with the conflict set; and

removing the selected memory address from the input set of potentially conflicting memory addresses.

9. A system for managing memory in a computer comprising:

a processor;

a processor cache;

a cache partitioning module being configured for;

using known memory-address constraints to identify at least one input set of potentially conflicting memory addresses; and

for each of the at least one input set of potentially conflicting memory addresses, and iteratively for each of the memory addresses in the at least one input set;

loading a current memory address, belonging to the at least one input set, into the processor cache;

detecting whether an eviction occurs from the processor cache as a result of the loading of the current memory address into the processor cache;

if an eviction is detected;

adding the current memory address to a conflict set of memory addresses;

flushing the processor cache; and

loading the conflict set into the processor cache;

if no eviction is detected, determining whether all of the input set of potentially conflicting memory addresses has been loaded into the processor cache and, if not, loading a next one of the input set of potentially conflicting memory addresses into the processor cache;

whereby the input set of potentially conflicting memory addresses is determined to be partitioned into a plurality of partitions such that memory addresses that conflict in the processor cache belong to the same partition, whereas memory addresses belonging to different partitions do not conflict in the processor cache.

10. The system of claim 9, wherein each of the at least one input set of potentially conflicting memory addresses is a subset of all memory addresses.

11. The system of claim 9, in which the processor cache partitioning module is further configured:

for marking the current memory address as being used after it has been loaded; and

for loading as current memory addresses of subsequent input sets only memory addresses not marked as used.

12. The system as in claim 9, further comprising a hardware performance counter, said cache partitioning module being configured for detecting whether an eviction occurs by detecting a change in the hardware performance counter.

13. The system of claim 9, further comprising:

a hardware cache miss counter,

wherein the processor cache partitioning module is configured for detecting whether an eviction occurs as a result of accessing a newly loaded memory address by reloading into the processor cache, one by one and in order, previously loaded memory addresses, examining the hardware cache miss counter after each reloading, and determining the eviction as being the result of loading the newly loaded memory address if the hardware cache miss counter indicates a cache miss upon loading of the newly loaded memory address.

14. The system of claim 9, in which the processor cache partitioning module is configured for detecting whether an eviction occurs as a function of access latency for each respective current memory address.

15. The system as in claim 9, in which the partitions have a cache-line granularity.

16. The system of claim 9, in which the processor cache partitioning module is further configured for:

selecting a memory address from the conflict set;

removing the selected memory address from the conflict set;

adding the selected memory address to an auxiliary overflow data structure associated with the conflict set; and

removing the selected memory address from the input set of potentially conflicting memory addresses.

17. A non-transitory computer-readable storage medium storing instructions, the instructions, when executed by a processor, causing the processor to:

use known memory-address constraints to identify at least one input set of potentially conflicting memory addresses; and

for each of the at least one input set of potentially conflicting memory addresses, and iteratively for each of the memory addresses in the at least one input set;

load a current memory address, belonging to the at least one input set, into a processor cache;

detect whether an eviction occurs from the processor cache as a result of the loading of the current memory address into the processor cache;

if an eviction is detected;

add the current memory address to a conflict set of memory addresses;

flush the processor cache; and

load the conflict set into the processor cache;

if no eviction is detected, determine whether all of the input set of potentially conflicting memory addresses has been loaded into the processor cache and, if not, load a next one of the input set of potentially conflicting memory addresses into a processor cache;

whereby the input set of potentially conflicting memory addresses is determined to be partitioned into a plurality of partitions such that memory addresses that conflict in the processor cache belong to the same partition, whereas memory addresses belonging to different partitions do not conflict in the processor cache.

18. The medium of claim 17, wherein each of the at least one input set of potentially conflicting memory addresses is a subset of all memory addresses.

19. The medium of claim 17, said instructions, upon execution by the processor, further causing the processor:

to mark the current memory addresses as being used after they have been loaded; and

to load as current memory addresses of subsequent input sets only memory addresses not marked as used.

20. The medium of claim 17, said instructions, upon execution by the processor, further causing the processor to detect whether an eviction occurs by detecting a change in a hardware performance counter.