在此篇論文中，我們提出了一個分頁式高速暫存記憶體之管理方法。我們的系統為一個將快取記憶體置換為高速暫存記憶體之嵌入式系統，經常被使用的分頁資料將會被搬進高速暫存記憶體中。為了決定高速暫存記憶體的配置，一些特殊的標籤會被加入到應用程式之原始碼中以分辨程式基本區塊的起始位置。在事先執行過一次應用程式之後，根據這些標籤，可紀錄每個程式基本區塊的記憶體存取模式，並加以分析後可決定高速暫存記憶體之配置。有許多其他可以將不同大小的記憶體區塊搬進高速暫存記憶體中的方法，然而我們的方法不同的地方在於，我們所搬動的記憶體區塊大小是固定的，因此可以避免掉記憶體區段碎裂的問題。此外，為了防止資料頻繁地搬進與搬出高速暫存記憶體而導致效能下降，我們提出了一個合併的方法，將一些程式基本區塊合併成較大的幾個區域，並給予每個區域一個高速暫存記憶體的配置。模擬的結果也顯示出，以這樣的方法來管理高速暫存記憶體可以獲得較快取記憶體高出最多6.7倍的效能。

In this thesis, we propose a page-based SPM management approach. The target system is an embedded system with a scratch-pad memory instead of cache. The pages which are frequently used are copied into the scratch-pad memory. In order to determine the scratch-pad memory allocations, special labels are attached into the application source code to identify each basic block. According to these labels, the memory access patterns of each basic block can be logged after pre-running the application. With this memory access log, the SPM allocation can be determined after analysis. Different from variable granularity approaches, we copied the data into to the SPM by pages which size is fixed. Therefore, there is no fragmentation problem after several times of swapping pages into and out of the SPM. Moreover, for preventing the poor performance from thrashing, a merge process is proposed in our work. Basic blocks are merging into several regions to avoid the frequently swapping the pages between the SPM and DRAM. The simulation results indicate that SPM managed with our approach can observably improve the performance and outperforms cache about 6.7 times at most.

[1] Oren Avissar, Rajeev Barua, and Dave Stewart, "An Optimal Memory Allocation Scheme for Scratch-Pad Based Embedded Systems," ACM Transactions on Embedded Computing Systems (TECS), 1(1), 2002
[2] John Hennessy and David Patterson, "Computer Architecture A Quantitative Approach," Morgan Kaufmann, Palo Alto, CA, third edition, 2002.
[3] Rajeshwari Banakar et.al., "Scratchpad Memory: A Design Alternative for Cache On-chip memory in Embedded Systems," Proceedings of the 10th International Workshop on Hardware/Software Codesign, Estes Park, Colorado, USA. May 6, 2002, pp.73-78.
[4] Preeti Ranjan Panda, Nikil D. Dutt, and Alexandru Nicolau, “Efficient Utilization of Scratch-Pad Memory in Embedded Processor Applications," In European Design Automation and Test Conference, March 1997.
[5] Federico Angiolini, Luca Benini, and Alberto Caprara, "Polynomial-Time Algorithm for On-Chip Scratchpad Memory Partitioning," Proceedings of the 2003 international conference on Compilers, architecture and synthesis for embedded systems, San Jose, CA, USA., Oct. 30 - Nov. 1, 2003, pp. 318-326.
[6] Stefan Steinke et.al., “Assigning Program and Data Objects to Scratchpad for Energy Reduction,” Proceedings of 5th ACM/IEEE Design and Test in Europe Conference (DATE), Paris, France, April 2002, pp. 409-415.
[7] Andhi Janapsatya, Sri Parameswaran, and Aleksandar Ignjatovic, "Hardware/software Managed Scratchpad Memory for Embedded System," Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design (ICCAD'04), San Jose, CA, USA., November 7-11, 2004, pp. 370-377.
[8] Bernhard Egger, Jaejin Lee, and Heonshik Shin, "Dynamic Scratchpad Memory Management for Code in Portable Systems with an MMU," ACM Transactions on Embedded Computing Systems, Vol. 7, No. 2, Article 11, February 2008.
[9] Sumesh Udayakumaran and Rajeev Barua, "Compiler-Decided Dynamic Memory Allocation for ScratchPad Based Embedded Systems," Proceedings of the 2003 international conference on Compilers, architecture and synthesis for embedded systems, San Jose, CA, USA., Oct. 30 - Nov. 1, 2003, pp. 276-286.
[10] Sumesh Udayakumaran, Angel Dominguez, and Rajeev Barua, "Dynamic Allocation for Scratch-Pad Memory using Compile-Time Decisions," ACM Transactions on Embedded Computing Systems (TECS), Volume 5, Issue 2, May 2006. pp. 472-511.
[11] Angel Dominguez, Sumesh Udayakumaran and Rajeev Barua, “Heap Data Allocation to Scratch-Pad Memory in Embedded Systems,” Journal of Embedded Computing, Volume 1, Issue 4, 2005.
[12] Stefan Steinke et.al., “Reducing energy consumption by dynamic copying of instructions onto onchip memory,” Proceedings of the 15th international symposium on System Synthesis (ISSS 2002), Kyoto, Japan, October 2-4, pp. 213-218.
[13] Lian Li, LinGao, and Jingling Xue, "Memory Coloring: A Compiler Approach for Scratchpad Memory Management," Proceedings of the 14th International Conference on Parallel Architectures and Compilation Techniques, St. Louis, MO, USA., 17-21 September 2005, pp.329-338.
[14] M. Kandemir et.al., "Dynamic management of scratch-pad memory space," Proceedings of the 38th conference on Design automation, Las Vegas, Nevada, United States, June 18-22, 2001, pp.690-695.
[15] Mahmut Kandemir, lsmail Kadayif, and Ugur Sezer, "Exploiting Scratch-Pad Memory Using Presburger Formulas," Proceedings of the 14th international symposium on Systems synthesis, Montreal, Quebec, Canada, October 1-3, 2001, pp.7-12.
[16] Manish Verma, Lars Wehmeyer, and Peter Marwedel, "Dynamic Overlay of Scratchpad Memory for Energy Minimization," Proceedings of the 2nd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, Stockholm, Sweden, September 8–10, 2004, pp.104-109.
[17] Bernhard Egger, Jaejin Lee, and Heonshik Shin, "Scratchpad Memory Management for Portable Systems with a Memory Management Unit," Proceedings of the 6th ACM & IEEE International conference on Embedded software (EMSOFT'06), Seoul, Korea, October 22-25, 2006, pp. 321-330.
[18] MiBench, http://www.eecs.umich.edu/mibench/