Scratchpad Allocation for Data Aggregates in Superperfect Graphs
Existing methods place data or code in scratchpad memory, i.e., SPM by either relying on heuristics or resorting to integer programming or mapping it to a graph coloring problem. In this paper, the SPM allocation problem is formulated as an interval coloring problem. The key observation is that in many embedded applications, arrays are often related in the following way: for any two arrays, their live ranges are often such that one is either disjoint from or contains the other. As a result, array interference graphs are often superperfect graphs and optimal interval colorings for such array interference graphs are possible.