由執行資料引導的草稿記憶體動態載入程式之研究

Abstract

有效率的利用晶片上的記憶體一直是改進程式執行效能的重要方法。關於快取記憶體(Cache)的研究已經進行數十年，然而草稿記憶體 (Scratch-pad memory)由於其較快取記憶體低的功耗與成本，近年亦吸引許多研究者投入。由於草稿記憶體的特性使然，為使一般的程式 達到有效利用該記憶體，需要從軟體層次進行修改。因此，為了使已撰寫好的程式能夠利用草稿記憶體，許多編譯器的研究者提出從編譯器層次修改目的程式以利用草稿記憶體的方法。

在本論文中，我們提出一軟體協助之動態載入程式片段進入草稿記憶體以提升程式執行效能的方法。前人提出的動態方法雖可找出最適合動態載入的片段，但由於使用整數線性規劃的緣故，該方法並不適合較大規模的程式。因此在本論文中，我們提出並評估一個基於「分而治之」概念的「試探法」(Heuristic)，用以找出適於動態載入的程式片段。而本試探法中的「分」即將巢狀迴圈(Nested Loops)分解；而「治」的方法則是將問題建模(Model)為一維零/壹背包問題(One-dimensional 0/1 Knapsack Packing Problem)。

實驗結果顯示我們的試探法的表現超越前人所提出之靜態載入方法，並且其性能可與傳統I-Cache抗衡。因此我們認為本論文提出的乃是一個適合較大型程式動態、有效率的利用草稿記憶體的可行方法。

Effective utilization of on-chip memories has always been an important factor to improve the performance of a program. Caching techniques has been studied for decades, whilst recently scratch-pad memory is getting more and more focuses on it, because of its lower cost and lower power-consumption comparing to the cache.

Due to the nature of scratch-pad memory, it is required to modify current program to effeciently utilize the scratch-pad memory. Hence, for legacy programs, compiler researchers have proposed automatic modification methods of source program in compilers supporting scratch-pad memory.

In this thesis we focus on the dynamic loading of parts of program to on-chip scratchpad memory to improve the performance.

Previous dynamic approach applies the ILP framework to solve the problem deciding optimal set of dynamically-loaded program parts, but not feasible when program size grows. Hence, a heuristic to solve the problem of deciding dynamically loading parts of a program into scratch-pad memory is proposed and evaluated in this thesis. Our heuristic is based on the idea of ‘divide-and-conquer’, here ‘divide’ corresponds to the decomposition of nested loops and ‘conquer’ corresponds to an one-dimensional 0/1 knapsack-packing method.

Evaluation results showed that our heuristic outperformed the static approach, and the performance of software-controlled dynamically-loaded code in scratch-pad memory produced by our method is comparable to traditional I-cache. This suggests a viable path for larger applications to efficiently utilize the scratch-pad memory.