Cache Conscious Object Packing and Placement

快取記憶體在分層式記憶體架構中扮演加速存取動作的角色。程式與資料物件在記憶體中的排列順序是影響快取錯失率的重要原因之一。先賢們的研究都集中在找出適用於直接映射式快取記憶體的方法，其方法是把這些物件錯置排列至各個快取關連組。錯置排列的方法有助於減少衝突性錯失。然而某些系統的記憶區塊大到可以容納許多程式或資料物件，而且被讀進快取記憶體的最小單位是記憶區塊，而非物件，因此所有物件只得互搶快取記憶體內有限的空間。論文提出一套方法論，旨於利用調整物件在記憶體中排列的方法來改善快取記憶體的效率。這套方法包含兩項重點：探索物件的組織，以及針對各種快取架構產生專屬的物件排列法。探索物件組織的方法涵蓋了解構資料或程式的成份，以及產生物件存取活動的軌跡。此外本文亦特別提出一個適用於虛擬機器（例如爪哇虛擬機器）的探索技術，其著眼點是基於此類程式具有特殊的軟體架構。論文的重點是尋求產生適用於各類快取記憶體的物件排列之法。前提是假定物件的尺寸小於記憶區塊。這意味著賦予物件地址編號必須統合兩項動作，一則是用於快取關連組錯置物件法，二則是將物件合併到記憶體區塊。本論文提出的辦法是藉由存取活動的軌跡來建立物件關連模型。在發展的過程中，文本分析了物件關連模型、快取架構、及快取錯失之間的因果關係。然而這些因果關係實際上十分困難而無法算出最佳解。因此本文也提出的頗具實用性的技術，用以產生適用於不同快取架構的物件排列法。本論文亦實作了相當繁複的實驗來驗證所提出來的方法。實驗的結果頗具有說服力，可以支持本文提出的技術的有效性。The cache provides acceleration in access through the memory hierarchy. The order of arranging code and data objects in the main memory is an important factor that affects cache miss rates. Prior related researches focus on arranging objects interleaved between cache sets for the direct mapped cache. Interleaving the address of each items helps to resolve conflict misses. However, there are computer systems that a memory block can be large to collect a number of code and data objects, and the unit to be loaded to the cache is a memory block, not an object. Therefore, objects contend spaces within cache blocks as well. his dissertation provides a methodology for optimizing cache memory utilization of applications in various fields by arranging their relocatable objects within the main memory. The methodology includes the exploration of object space and generation of object layouts for all kinds of cache organization. The object space exploration involves techniques in inspecting the data and program integrant and acquiring the profile of objects accesses. The exploration also contains a technique particular for the virtual machine, e.g., the Java virtual machine, because of its unique program structure.enerating object layout adapted for cache memory is the keystone in this dissertation. The presumption is that objects are smaller than a memory block. That means assigning addresses to objects must incorporate two movements into one. The first is interleaving objects to cache sets. The second is gathering these objects to fit one cache block. Our study suggests creating the object affinity model by profile information. This study analyzes the relationship between the object affinity model, cache configurations, and cache misses. The packing and placement problem turns to be hard to find an optimal solution. Thereafter, this study proposes practical techniques of generating object layouts for different cache organizations. This dissertation also includes experiments to evaluate the proposed techniques. The experiments provide convincible results and support the effectiveness of the proposed approaches.CHAPTER 1 INTRODUCTION 1.1 Motivation 1.2 Usefulness 4.3 Scope and Organization 6HAPTER 2 BACKGROUND 9.1 Memory Hierarchy 9.1.1 Cache Organization 10.1.2 XIP and NAND Flash 15.2 Graph and Combinatorial Algorithms 17.3 Related Works 21.3.1 Placements 21.3.2 XIP and NAND Flash 26.3.3 Locality 27.3.4 Other Related Topics 27HAPTER 3 PROBLEM MODELING 31.1 Object Access Trace 31.2 One Page Cache Model 38.3 Direct Mapped Cache 42.4 Fully Associative Cache 48HAPTER 4 PRACTICAL APPROACHES 57.1 Hardness of Packing and Placement for Direct Mapped Cache 57.2 Approaches for Direct Mapped Cache 63.2.1 Packing Followed by Placement 64.2.2 Placement Followed by Packing 69.3 Approaches for Fully Associative Cache 70.3.1 One-Page Cache Method 70.3.2 Two-Pass Partitioning Method 71.4 Approaches for Set Associative Cache 73HAPTER 5 EXPLORATIONS OF OBJECTS AND TRACES 75.1 Generic Data Objects 76.2 Generic Code Objects 77.2.1 Motivation 77.2.2 Control Flow Analysis and Basic Blocks 80.2.3 Benchmark Overview 85.3 Partial Arrangement on Performance Bottleneck 92.4 Virtual Machine Interpreters 94.4.1 KVM Internal 95.4.2 Analyzing Control Flow 100.4.2.1 Indirect Control Flow Graph 100.4.2.2 Tracing the Locality of the Interpreter 101.5 Discussion on Effectiveness and Impact of Profiling 105HAPTER 6 EVALUATIONS AND EXPERIMENTS 107.1 Experimental Setup 107.2 Direct Mapped Cache: Experimental Analysis 109.3 Fully Associative Cache: Experimental Analysis 129.4 Set Associative Cache: Experimental Analysis 139.5 Experiments on Partial Arrangement 148.5.1 Direct Mapped Cache Experiment 148.5.2 Fully Associative Cache Experiment 153.6 Virtual Machine Experiment 158.6.1 Evaluation Environment 158.6.2 Virtual Machine Modification Procedures 159.6.3 Experimental Result 163HAPTER 7 CONCLUSIONS 167IBLIOGRAPHY 17