Related Work on DBT Modeling and Strategy

3.5Related Work on DBT Modeling and Strategy

Transmeta published limited information about their co-designed x86 processors [82, 83, 122], which are probably the only co-designed VM products currently being delivered. Performance modeling of the Transmeta CMS system is not disclosed. The translation strategy [82, 83] is described as a four-stage emulation system that starts with an interpreter. The trade-offs regarding setting the hot thresholds (for triggering the higher stages for more advanced optimizations), however, are not disclosed. The CMS translation strategy also adopted a hardware assist scheme [83] that accelerates the first stage, the interpreter in the Efficeon CMS system. There are no official benchmark results for the Transmeta x86 processors.

IBM DAISY/BOA project(s) published performance data [3, 41] for SPEC CPU and TPC-C benchmarks. Since SPEC CPU benchmarks have very good code reuse behavior, especially for full reference runs, the translation overhead is negligible. TPC-C is one of the few benchmarks in their results that demonstrate significant translation overhead. Performance modeling and consequently reducing translation overhead was not emphasized in the DAISY/BOA research. DAISY also used interpretation for initial emulation and the hot threshold for invoking the binary translator is set on the order of tens due to the slow emulation speed of an interpreter.

The ILDP co-designed VM research [76~79] takes a similar (to DAISY) translation strategy and simply assumes translation overhead is negligible for most applications.

The situation is similar for other VMs similar to the co-designed VM domain. For example, developers of commercial products (such as the Intel IA-32 EL [15]) have not published their translation trade-off, modeling, and strategies. However, the IBM Jikes RVM java virtual machine research [11] proposed a similar method to set the thresholds that trigger more advanced optimizations for hot java methods. Their equation T_j = T_i * S_i / S_j is essentially the same as our Equation 2, except that it is expressed for dynamic java compilation setting.

Chapter 4

Efficient Dynamic Binary Translation Software

In this chapter, I discuss specifically how x86 instructions are translated (and optimized) by software DBT to the fusible ISA code. First, the translation procedure is described in Section 4.1. Then, I elaborate on the translation unit formation in Section 4.2 and machine state mapping from the x86 to the fusible ISA architected state in Section 4.3. The key translation algorithms that discover appropriate dependent instruction pairs for fusing and schedule these dependent pairs together are detailed in Section 4.4 and 4.5. Section 4.6 discusses how to perform simple and straightforward BBT translation targeting fast VM startup. Finally, Section 4.7 evaluates software translators and Section 4.8 discusses related work on software dynamic binary translation.

4.1Translation Procedure

Dynamic translation algorithms are highly dependent on the particular combination of the architected ISA and the implementation ISA. In the x86vm framework, with a fusible ISA and macro-op execution pipeline, the binary translator includes the following steps.

1. 
   Translation unit formation. The translation unit selected in the framework is the superblock [65]. Program hotspots are detected by simple hardware profiler, for example as that proposed by Merten et al. [98], and are formed into superblocks.
   
2. 
   IR Generation. The x86 instructions in a superblock are decoded and cracked into a RISC style intermediate representation (IR). Memory access (load / store) instructions and other instructions with embedded long (32-bit) immediate values are transformed into an IR form that preserves the long immediate values. The purpose is to keep the original semantics of the x86 instructions without concern for encoding artifacts.
   
3. 
   Machine state mapping. All frequently-used x86 register names are mapped to the fusible ISA registers in a straightforward way (Section 4.3). This mapping is employed in the previous step in fact. Additionally, the translator scans superblocks for long immediate values and counts frequencies in a small temporary table. Then, it performs a value clustering/locality analysis to allocate frequent immediate values to registers as described in Section 4.3.
   
4. 
   Dependent Graph Construction. Register value dependence is analyzed; this includes x86 condition code dependences. A simple dynamic dependence graph is then constructed for the superblock and is maintained in place with its IR data structure.
   
5. 
   Macro-op Fusing. Appropriate dependent instructions are discovered and paired together to form fused macro-ops (Section 4.4 and 4.5). Dependent instruction pairs are not fused across conditional branches (and indirect jumps implied by superblock formation). However, dependent instructions across direct jumps or calls can be fused. Dependences due to x86 condition codes are handled as normal data dependences and many fused pairs are in fact formed around condition codes.
   
6. 
   Register Allocation. Before this step all registers are identified with pseudo register numbers. To allow precise state recovery as described by Le [85], actual register allocation needs to be done at this point. As instructions are reordered, register live ranges are extended to allow precise state recovery. Permanent register state mapping (Section 4.3) is maintained at all superblock boundaries.
   
7. 
   Code Generation. The fusible ISA instructions with fusing information are generated and encoded. Then, the translated superblock is stored in the code cache and registered with the VMM for native execution.
   

The above translation and optimization procedure is typically performed only for program hotspots. Otherwise, a simpler light-weight translator (Section 4.6) is applied in order to avoid excessive runtime translation overhead.

Download 0.61 Mb.

Share with your friends: