近幾年來，我們越來越關注在嵌入式系統上使用動態指令翻譯的技術。然而，在嵌入式系統上面使用這項技術時會遭遇到一些困難，因為在嵌入式系統上的記憶體資源往往是有限的，所以二進制指令被重新翻譯的次數也會相對增加，這種情況會造成系統效能嚴重下降。為了改善系統效能，異構記憶體指令快取架構被提出來去解決這個問題，他結合了主記憶體和快取記憶體去組成系統所需要的指令快取架構，雖然異構記憶體指令架構可以很好的被運作在一些應用程式上面，但是它忽略了程式執行的特性，將一些有可能會被大量執行的二進制指令放在主記憶體上，而不是放在快取記憶體上面，使得程式效能受到限制。為了解決這個問題，我們提出了增強異構記憶體指令快取的管理方法，這個方法可以有效的考慮程式執行的行為，進而去最佳化翻譯過的代碼在指令快取架構中的配置，實驗結果顯示，該管理方法可以有效地使快取命中率從 49.48%增加到95.06%，這也讓整體的系統效能有了42.68%的提升。

Recently, DBT has gained much attentions on embedded systems. However, the memory resource in embedded systems is often limited. This leads to the overhead of code re-translation and causes significant performance degradation. To reduce this overhead, Heterogeneous Code Cache (HCC), is proposed to split the code cache among SPM and main memory to avoid re-translation of code fragments. Although HCC is effective in handling applications with large working set, it ignores the execution frequencies of program fragments. Frequently executed program fragments can be stored in main memory and thus causes performance loss. To address this problem, an enhanced Heterogeneous Code Cache management scheme which considers program behaviors is proposed in this thesis. Experimental results show that the proposed management scheme can effectively improve the access ratio of SPM from 49.48% to 95.06%. This leads to 42.68% improvement of performance as compared with the management scheme proposed in the previous work.

1 Introduction 1
2 Background and Related Work 5
2.1 Background of Dynamic Binary Translation . . . . . . . . . . 5
2.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3 Motivation 10
4 Enhanced Heterogeneous Code Cache Management Scheme 15
4.1 Overview of Enhanced HCC Management Scheme . . . . . . . 17
4.2 Proposed HCC Structures and Management Policies . . . . . . 19
4.2.1 Management of Hash Tables . . . . . . . . . . . . . . . 20
4.2.2 Structures of L1-HCC and L2-HCC . . . . . . . . . . . 21
4.2.3 Adjustment of Boundary Line in L1-HCC . . . . . . . 25
5 Experiments 27
5.1 Experimental Setup . . . . . . . . . . . . . . . . . . . . . . . . 27
5.2 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . 29
6 Conclusions 35

[1] Leonid Baraz, Tevi Devor, Orna Etzion, Shalom Goldenberg, Alex
Skaletsky, Yun Wang and Yigal Zemach, IA-32 Execution Layer: a two-
phase dynamic translator designed to support IA-32 applications on
Itanium R
-based systems, in Proceedings of 36th Annual International
Symposium on Microarchitecture, Micro-36, December 2003.
[2] K. Scott and J. Davidson. Safe virtual execution using software dynamic
translation. In Annual Computer Security Applications Conf., 2002.
[3] K. Adams and O. Agesen. A comparison of software and hardware tech-
niques for x86 virtualization. In International Conference on Architectural
Support for Programming Languages and Operating Systems, 2006.
[4] V. Bala, E. Duesterwald, and S. Banerjia. Dynamo: a transparent dy-
namic optimization system. In Conf. on Programming Language Design
and Implementation (PLDI), 2000.
[5] V. Kiriansky, D. Bruening, and S. P. Amarasinghe. Secure execution via
program shepherding. In USENIX Security Symp., 2002.
[6] Q. Wu, M. Martonosi, D. W. Clark, V. J. Reddi, D. Connors, Y. Wu, J.
Lee, and D. Brooks. A dynamic compilation framework for controlling
microprocessor energy and performance. In Intl. Symp. on Microarchitecture
(MICRO), 2005.
[7] J. D. Hiser, D. Williams, W. Hu, J. W. Davidson, J. Mars, and B. R.
Childers. Evaluating indirect branch handling mechanisms in software
dynamic translation systems. In International Symposium on Code Generation
and Optimization, 2007.
[8] Rajeshwari Banakar, Stefan Steinke, Bo-Sik Lee, M. Balakrishnan and
Peter Marwedel, “Scratchpad Memory: Design Alternative for Cache
On-Chip Memory in Embedded Systems,” in Proceedings of the 10th
International Symposium on Hardware/Software Codesign, pp. 73-78,
2002.
[9] Kim Hazelwood and Michael D. Smith, “Code Cache Management
Schemes for Dynamic Optimizers,” in Proceedings of the Sixth Annual
Workshop on Interaction between Compilers and Computer Architectures,
2002.
[10] K. Hazelwood and J. E. Smith. Exploring Code Cache Eviction Gran-
ularities in Dynamic Optimization Systems. In Proceedings of the international
symposium on Code generation and optimization: feedbackdirected
and runtime optimization, 2004.
37
[11] K. Hazelwood and M. D. Smith. Managing Bounded Code Caches in
Dynamic Binary Optimization Systems. In ACMTrans. on Architecture
and Code Optimization, Vol. 3, No. 3, September 2006.
[12] J. E. Miller and A. Agarwal. Software-based instruction caching for em-
bedded processors. In International Conference on Architectural Support
for Programming Languages and Operating Systems, 2006.
[13] Jos’e A. Baiocchi, Bruce R. Childers, Jack W. Davidson, Jason D. Hiser,
and Jonathan Misurda, “Fragment Cache Management for Dynamic Bi-
nary Translators in Embedded Systems with Scratchpad,” in International
Conference on Compilers, Architecture and Synthesis for Embedded
Systems, pp. 75-84, 2007.
[14] J. A. Baiocchi, B. R. Childers, J. W. Davidson, and J. D. Hiser. Reducing
pressure in bounded DBT code caches. In International Conference on
Compilers, Architecture, and Synthesis for Embedded Systems, 2008.
[15] J. A. Baiocchi, B. R. Childers. Heterogeneous Code Cache: Using
Scratchpad and Main Memory in Dynamic Binary Translators. In Design
Automation Conference, 2009.
[16] A. Guha, K. Hazelwood, and M. L. Soffa. Code lifetime-based memory
reduction for virtual execution environments. In Workshop on Optimizations
for DSP and Embedded Systems, 2008.
[17] K. Scott, N. Kumar, S. Velusamy, B. Childers, J. W. Davidson, and
M. L. Soffa. Retargetable and reconfigurable software dynamic transla-
38
tion. In International Symposium on Code Generation and Optimization,
2003.
[18] Derek Bruening and Saman Amarasinghe, “Maintaining Consistency
and Bounding Capacity of Software Code Caches,” in Proceedings of
the International Symposium on Code Generation and Optimization,
pp. 74-85, 2005.
[19] John L. Hennessy, and David A. Patterson, ”Computer Architecture
:A Quantitative Approach,” 3rd edition, Morgan Kaufmann Publishing
Co., 2002.
[20] M. R. Guthaus, J. S. Ringenberg, D. Ernst, T. M. Austin, T. Mudge,
and R. B. Brown. Mibench: A free, commercially representative embed-
ded benchmark suite. In IEEE Workshop on Workload Characterization,
2001.
[21] Standard Performance Evaluation Corporation. SPEC CPU2000 bench-
mark suite. http://www.spec.org/cpu2000/, December 1999.
[22] E. Duesterwald, C. Cascaval, and S. Dwarkadas. Characterizing and pre-
dicting program behavior and its variability. In International Conference
on Parallel Architecture and Compilation Techniques, September 2003.
[23] T. Sherwood, E. Perelman, G. Hamerly, and B. Calder. Automatically
characterizing large scale program behavior. In 10th International Conference
on Architectural Support for Programming Languages, October
2002.