Performance Modeling and Strategy for Staged Translation

3.3Performance Modeling and Strategy for Staged Translation

Clearly, M_BBT is a basic characteristic of the program’s execution and cannot be changed. Thus, a feasible way to reduce BBT overhead is to reduce Δ_BBT, and for this goal, we will propose hardware assists in Chapter 5. Regarding the SBT component, we argue that good hotspot optimizations are complex and need the flexibility advantages of software. A hardware implemented optimizer (at least for the optimizations we consider) would be both complex and expensive. Chapter 4 will strive for both efficient and effective translation algorithms. Fortunately, for most applications, the hotspot code is a small fraction of the total static instructions. Furthermore, the hotspot size, M_SBT, is sensitive to the hot threshold setting. Therefore, we need to explore a balanced trade-off regarding the hot threshold setting, which not only reduces SBT overhead by detecting true hotspots, but also collects optimized hotspot performance benefits via good hotspot code coverage.

Our evaluation of this trade-off uses a specialized version of the model proposed for the Jikes RVM java virtual machine [11]. Let p be the speedup an optimized superblock can achieve over the simple basic block code. Also let N be the number of times a given instruction executes and let t_b be the per instruction execution time for code generated by BBT. Then, to break even, the following equation holds. (This assumes that the optimizer is written in optimized code and its overhead Δ_SBT is measured in terms of architected ISA instructions.)

N * t_b = (N + Δ_SBT) * ( t_b / p)  N = Δ_SBT / (p - 1) (Eq.2)

That is, the breakeven point occurs when the number of times an instruction executes is equal to the translation overhead divided by the performance improvement. In practice, at a given point in time, we do not know how many times an instruction will execute in the future, however. So, this equation cannot be applied in an a priori fashion. In the Jikes system, it is assumed that if an instruction has already been executed N times, then it will be executed at least N times more. Hence, the value N as given in Equation 2 is used as the threshold value.

In our VM scheme, we set the hot threshold that triggers SBT translation based on Equation 2 and benchmark characteristics. To calculate the hot threshold based on the equation, we first determine the values of the equation parameters. For our VM system, we have measured Δ_SBT to be 1152 x86 instructions (approximately 1200) and p is 1.15 ~ 1.2 for the WinStone2004 traces. That is, SBT optimized code runs 15 to 20 percent faster than the code generated by BBT. Then to break even, Equation 2 suggests that N should be at least 1200/0.15 = 8000 for WinStone2004-like workloads.




Figure 3.9 Winstone2004 instruction execution frequency profile

(100M x86 instruction traces)

The right y-axis shows the distribution function of total dynamic x86 instructions. For example, the peak point of the distribution curve shows that 30+% of all dynamic instructions execute more than 10K times, but less than 100K times. This curve rises and then falls off because the total dynamic instruction count for the simulations is 100 million. If the programs run longer than 100 million instructions, then this curve would continue to rise and the peak would shift to the right toward higher execution frequency. It is clear from the figure that for a hot threshold on the order of thousands, the hotspot coverage (the percentage of instructions executed from the optimized hotspot code) is fairly modest for these short startup traces. However, the hotspot code coverage will be significantly improved once benchmarks are run much longer as in most realistic cases. For example, the hotspot coverage in these short traces is about 63%. The coverage will increase to 75+% for 500M instruction runs. And real applications run tri/billions of instructions.

Returning now to Equation 1, the average value of M_BBT is 150K static x86 instructions (this can be determined by adding the data points of the static instruction curve) and the average value of M_SBT is 3K (adding the data points of the static instruction curve that are to the right of the hot threshold line). Assuming Δ_BBT = 105 native instructions (as measured in our baseline VM system) and Δ_SBT = 1674 native instructions (equivalent to the 1152 x86 instructions above), then we infer that the BBT component is 105 * 150K = 15.75M native instructions, or equivalent to 10.86M x86 instructions, and the SBT component is 1674 * 3K = 5.02M native instructions, or equivalent to 3.46M x86 instructions. In other words, based on the fact that 100M workload x86 instructions are executed, the analytical model projects that the BBT overhead is roughly 10% and the SBT overhead is about 3%. Therefore, in our VM system, BBT causes the major translation overhead, and this is the overhead Chapter 5 will tackle with hardware accelerators. Also because BBT translation is a simpler operation, it offers more opportunities for hardware assists.

It is important to note that an advantage of the co-designed VM paradigm is its synergetic hardware/software collaboration. This unique capability shifts the trade-off for the translation strategy. And it is not always feasible to achieve this capability in VM systems that aim at porting user-mode software across different platforms. For example, the Intel IA-32 EL instruments extra code in BBT translations to collect program execution profile and apply certain translation rules to guarantee precise state can be easily recovered should an exception occur. This profiling code and rules cause significant extra overhead and slow down the BBT translations for emulation speed. In contract, a co-designed VM system employs cost-effective hardware assists to detect program hotspot and to accelerate the critical part of DBT translation. BBT translations in co-designed VM can be more efficient and the hotspot optimization overhead can thus be reduced by translating only confident hotspots. Once hardware assists for BBT are deployed, BBT translation becomes much cheaper and flushing the code cache for BBT becomes inexpensive. Then, using interpreters to filter out code that executes very infrequently (less than 20 times) becomes less attractive (Perhaps, Transmeta uses the first stage of interpretation to filter out the leftmost data point(s) in Figure 3.2, which stands for instructions that execute less than 10 times but take up a big section of the code cache).

In a co-designed VM system, the overall translation strategy strives for (1) balanced translation assignments among the major components and (2) an optimal division between the co-designed hardware and software. In our x86vm framework, the translation strategy for the two-stage translation system is based on the analytical model (Equations 1 and 2). Specifically, our translation strategy determines the hotspot threshold based on Equation 2 and application characteristics. This strategy also suggests that hardware primitives should significantly accelerate BBT translation, which is on the critical execution path.