臺灣博碩士論文加值系統

在程式執行時，資料的存取花費相當的執行時間。我們在編譯程式時若能有效改善資料存取的時間，對於程式執行效能便能做有效的改善。有鑒於此，我們已設計一種程式資料區域性估測方法的軟體。運用此方法所估算出的程式資料區域性，提供給轉換程式，便能將程式做最佳化的轉換，降低主記憶區塊的存取次數。提高整體程式運行效率。在此研究中我們設計並實作此程式資料區域性估測方法的軟體設計，其設計部份分為下列二個主要模型：估測記憶區塊存取吻合次數、估測記憶區塊存取次數。我們並運用此軟體進行相關實驗，以驗證此方法在資料區域性估測的正確性。

Data accesses consume considerable execution time during program execution. If we can improve the data access time at compile time, overall program execution time can be improved effectively. Hence, we designed a software for a data locality estimation method for estimating data locality in program optimizer. The program optimizer can then reduce the number of main memory block access and enhance the overall program performance effectively. In this research, we implemented the software design of the data locality estimation method. It includes two estimation models for estimating the number of access matches in memory blocks and for estimating the number of memory block access. We carried out experiments to verify accuracy of the locality estimation method.

第一章 緒論...............................................................................................................1
1.1 研究動機.........................................................................................................2
1.2 研究背景.........................................................................................................4
1.3 問題敘述.........................................................................................................6
1.4 論文架構.........................................................................................................7
第二章 程式資料區域性估測方法.....................................................................8
2.1 估測方法介紹.................................................................................................8
2.2 估算記憶區塊存取吻合次數.......................................................................10
2.2.1線性限制條件......................................................................................11
2.2.2體積的計算.........................................................................................13
2.3 估算記憶區塊存取次數...............................................................................13
2.4 收斂區域性距離...........................................................................................19
第三章 程式資料區域性估測方法的軟體規劃...........................................20
3.1軟體設計規劃................................................................................................20
3.2 估算記憶區塊存取吻合次數的軟體設計...................................................21
3.2.1輸入資料參數定義.............................................................................21
3.2.2 VINCI輸入格式的轉換.....................................................................22
3.2.3 利用VINCI算出多維體積................................................................23
3.3估算記憶區塊存取次數與收斂區域性距離的軟體設計............................24
第四章 結論.............................................................................................................25
第五章 參考文獻...................................................................................................26

[1] Tsung Lee, A Loop Data Locality Estimation Method, Internal Research Memo, computing system Lab., Dept. of Electrical Engineering, National Sun Yat-Sen
University, June 2008
[2] Randy Allen, Ken Kennedy, “Optimizing compilers for modern architectures,”Morgan Kaufmann, 2002
[3] Sofiane Naci, “Optimizing Inter-Nest Data Locality Using Loop Splitting and Reordering,” Proc. of parallel and Distributed Processing Symposium, 2007
[4] Vincent Loechner, Benoît Meister and Philippe Clauss, “Precise Data Locality Optimization of Nested Loops,” The Journal of Supercomputing, Volume 21, Number 1, Jan. 2002
[5] Jesús Sánchez and Antonio González, “Fast, Accurate and Flexible Data Locality Analysis,” Proc. of parallel Architectures and Compilation Techniques, 1998
[6] Benno Büeler, Andreas Enge, Komei Fukuda, “Exact Volume Computation for Polytopes: A Practical Study,” CiteSeer.IST Scientific Literature Digital Library, Jan. 1998