Befintliga metoder placerar data eller kod i scratchpad minne, dvs SPM genom att antingen förlita sig på heuristik eller tillgripa heltal programmering eller kartlägga det till en graf färg problem. I detta arbete formuleras SPM:s fördelningsproblem som ett problem med intervallfärgning. Den viktigaste observationen är att i många inbyggda applikationer, matriser (inklusive structs som ett specialfall) ofta är relaterade på följande sätt: För två matriser, deras live intervall är ofta sådana att den ena är antingen separerade från eller innehåller den andra. Som ett resultat, array interference grafer är ofta superperfect grafer och optimala intervall färgningar för sådana array interference grafer är möjliga. Detta har lett till att två nya SPM-algoritmer har utvecklats. Även om båda algoritmerna skiljer sig åt i fråga om om split och spill görs sekventiellt eller tillsammans, placerar de matriser i SPM baserat på att undersöka klyftorna i en interferenskurva. I båda fallen garanterar vi optimalt att alla matriser i en interferensgraf kan placeras i SPM om dess storlek inte är mindre än grafens klicktal. I det fall SPM inte är tillräckligt stor förlitar vi oss på heuristik för att dela eller spilla ut en levande räckvidd tills grafen är färgbar. Våra experimentresultat med inbäddade riktmärken visar att våra algoritmer kan överträffa graffärgning när deras interferensgrafer är superperfekta eller nästan så även om graffärgning visserligen är mer generell och även kan vara effektiv för applikationer med godtyckliga interferensgrafer.
Li, Nguyen och Xue REF allokerar matriser till SPMs genom att ta ad-vantage av det faktum att IGs i många inbyggda applikationer är superperfect grafer eller nästan så.
Scratchpad allocation for data aggregates in superperfect graphs
{'venue': "LCTES '07", 'journal': None, 'mag_field_of_study': ['Computer Science']}