Storage Unsharing

• US 20110307663A1
• Filed: 06/09/2011
• Published: 12/15/2011
• Est. Priority Date: 06/10/2010
• Status: Active Grant

• Current Assignee: Global Supercomputing Corporation
• Original Assignee: Global Supercomputing Corporation
• Inventors: Ebcioglu, Kemal, Kultursay, Emre, Kandemir, Mahmut Taylan
• Granted Patent: US 8,825,982 B2
• Time in Patent Office: Days
• US Class Current: 711/125
• CPC Class Codes: G06F 12/0806 Multiuser, multiprocessor or multiprocessing cache systems
• CPC Class Codes: G06F 2115/10 Processors
• CPC Class Codes: G06F 30/30 Circuit design
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

A method is described to partition the memory of application-specific hardware compiled from a software program. Applying the invention generates multiple small memories that need not be kept coherent and are defined over a specific region of the program. The invention creates application specific hardware which preserves the memory image and addressing model of the original software program. The memories are dynamically initialized and flushed at the entries and exits of the program region they are defined in.

Claims

1. A method to extract a hierarchy of memories from a software program, the method comprising:

Performing compiler dependence analysis over the memory instructions in the program;

Finding the smallest groups of memory instructions, where the groups are not dependent on each other. Assigning each such group to a separate new memory, which is accessed using the original memory addresses of the program;

Modifying the memory instructions of each group to make them access the new memory the group was assigned to; and

At run time, initializing each new memory from the original memory at the entries of the program. Storing the changes made in each new memory back to the original memory at the exits of the program.

2. The method in claim 1 further comprising:

using caches in place of memories.

3. The method of claim 1 further comprising:

creating an application-specific hardware accelerator comprising one or more new memories, from a given program fragment within a given software application, where the said hardware accelerator communicates with the said software application as follows;

a) At the beginning of the original program fragment, the software application signals the hardware accelerator to start.

b) The accelerator initializes its new memories from the software application memory.

c) The accelerator operates on the new memories, performing the computation specified by the original program fragment

d) The accelerator flushes the changes it made in the new memories back to the software application memory and notifies the software application that the accelerator has completed.

e) The software application continues execution from the end of the original program fragment.

4. The method in claim 2 further comprising:

valid and dirty bits to eliminate false sharing in cache blocks.

5. The method of claim 1 wherein a symbolic execution based compiler data flow analysis is used to generate information to be used in dependence analysis.

6. Recursive application of the method in claim 1 over various program granularities.

7. The method in claim 2 further comprising:

initialization of cache blocks to an all-invalid state in case of a write miss.

8. The method in claim 2 further comprising:

using dependence analysis to prove that no false sharing occurs on a cache.

9. The method in claim 2 further comprising:

using dependence analysis to detect the largest cache block size that can be used with no false sharing on a cache.

10. The method in claim 1 further comprising:

using tagless memory structures.

11. The method in claim 1 further comprising:

optimizing the performance of memory initialization and flushing, by flushing the changes made in a new memory to the NULL memory, and initializing a new memory from the NULL memory.

12. The method in claim 2 further comprising:

improving spatial locality in a new memory, by using an address transformation function to convert an original program memory address to the corresponding new memory address when reading, writing or initializing the new memory. Using the inverse of the said address transformation function to convert a new memory address to the corresponding original memory address, when flushing the changes in the new memory.

13. The method in claim 1 further comprising:

performing code duplication modifications before applying memory separation, to enhance its effectiveness.

14. The method in claim 1 further comprising:

reducing the number of memory ports by enabling port sharing in the memory unit.

15. The method in claim 1 further comprising:

avoiding the flushing and initialization overhead of memories during a loop'"'"'s execution, by re-using the data already fetched or stored by an earlier iteration of the loop, in a later iteration of the same loop.

16. The method of claim 1 further comprising:

separating memories of store instructions which may refer to the same address, whenever the stores also write the same data.

17. The method of claim 1 further comprising:

separating memories of commutative-associative memory update instructions which may refer to the same address.

18. The method in claim 1 further comprising:

delaying storage separation decisions until runtime, based on profiler directed feedback.

19. The method in claim 1 further comprising:

Assigning different memories to two groups of memory access instructions based on a speculative assumption that the two groups of instructions will not depend on each other at runtime.

Monitoring actual dependences between the speculatively separated groups of instructions at run time

Raising an error and canceling the changes to the software application memory when the said speculative assumption is found to be incorrect at runtime.

Correcting the incorrect speculative assumption by merging the offending two groups into one, during a subsequent re-compilation.

20. The method in claim 19, extended to more than two groups of speculatively separated instructions that might depend on each other at runtime.

21. The method of claim 19, extended to a recursive hierarchy of speculatively-separated instruction groups/memories.

22. The method of claim 1 further comprising:

selectively preventing the compiler decisions to create new memories, in order to meet resource constraints.

23. The method of claim 1 further comprising:

sharing hardware resources between two memories, when the two memories will not be accessed at the same time.