A Decoupled Local Memory Allocator

作者：Diouf Boubacar^*; Hantas Can; Cohen Albert; Ozturk Ozcan; Pal**erg Jens

来源：ACM Transactions on Architecture and Code Optimization, 2013, 9(4): 34.

DOI：10.1145/2400682.2400693

• Algorithms
• Performance
• Local memory
• scratchpad memory
• memory allocation
• compiler

Compilers use software-controlled local memories to provide fast, predictable, and power-efficient access to critical data. We show that the local memory allocation for straight-line, or linearized programs is equivalent to a weighted interval-graph coloring problem. This problem is new when allowing a color interval to %26quot;wrap around,%26quot; and we call it the submarine-building problem. This graph-theoretical decision problem differs slightly from the classical ship-building problem, and exhibits very interesting and unusual complexity properties. We demonstrate that the submarine-building problem is NP-complete, while it is solvable in linear time for not-so-proper interval graphs, an extension of the the class of proper interval graphs. We propose a clustering heuristic to approximate any interval graph into a not-so-proper interval graph, decoupling spill code generation from local memory assignment. We apply this heuristic to a large number of randomly generated interval graphs reproducing the statistical features of standard local memory allocation benchmarks, comparing with state-of-the-art heuristics.

• 出版日期2013-1