Research On Program Execution Model Based On Runtime

Nowadays, computer hardware systems become more and more complex, and at the same time, computer software systems become more and more abstract. Complex hardware systems bring more optimization opportunities for software systems, and ab-stract software systems make programmers more productive. However, as hardware systems become more complex and software systems become more abstract, the gap between them will be larger. The direct result of such large gap is low performance for abstract software's running on complex hardware systems. The physic body of such gap is the so called runtime system.To optimize performance of software systems, and at the same keep the high pro-ductivity, we need to study program execution model. Program execution model is con-structed on some target hardware systems and serves for some target software systems. With more study on program execution model, we can analysis the real efficiency of hardware features in software performance optimization, guide the process of software optimization and predict the final speedup. As a result, study on program execution model has both theoretic and practical value for design, analysis, optimization of real hardware and software systems.Because of the popularity of SIMD instruction extension and dynamic program-ming language in both academic and industrial areas, in this dissertation, we mainly study on program execution model for dynamic language JavaScript on hardware sys-tems with SIMD instruction extension. We will focus on the constructing, analysis of such a model and use it to guide program optimization.The main contribution of this dissertation includes:1. Invent a new multi-threading scheduling algorithm and analysis its compe-tition ratio:In this dissertation, we study on the garbage collection algorithm implemented in the Harmony Java virtual machine. We model the object mov-ing problem in such algorithms as a scheduling problem. Then, we invent a new semi-online scheduling algorithm to process it and analysis the worst-case com-petitive ratio of it. We also prove a lower bound of the competitive ratio of all algorithms for the problem.2. Design and implement an efficient Java virtual machine SIMD program- ming interface JVI:Based on SIMD instruction extension of Intel X86 platform, we invent the programming interface JVI for Harmony Java virtual machine. We evaluate this interface via the SpecJVM2008 benchmark and the experiments show the good efficiency of the interface.3. Analysis the runtime behavior of JavaScript programs systematically:We invent several new algorithms to process the dynamic typing system for JavaScript. Based on the SunSpider benchmark suite, we systematically study the runtime behaviors for JavaScript programs on meta types, object structure and array struc-ture.4. Design and implement a high performance JavaScript engine TypeCastor: Based on the Harmony Java virtual machine, we design and implement the Type-Castor JavaScript engine. We implemented our new algorithms in TypeCastor to process the dynamic typing system. With experiments with the SunSpider benchmark suite, we measure the performance of TypeCastor and prove the high performance of it.5. Optimize JavaScript program with SIMD instructions:We invent the SIMD programming interface for JavaScript based on the JVI and TypeCastor engine. With such an interface, we optimize the performance of JavaScript programs.6. Construct and analysis the program execution model TPW for JavaScript programs on hardware systems with SIMD instructions:We construct the TPW program execution model, by analysis the dynamic behaviors, vectorization process and experiment data. This new model is used to describe the behaviors, guide the optimization process and predict the speedup of JavaScript programs.Our main innovation includes:1. We invent new algorithms for the scheduling problem on object moving in Java virtual machine. We analysis the worst-case competitive ratio for both the al-gorithm and the problem itself. Such analysis is useful when designing new algorithms for Java virtual machine garbage collecting.2. We invent the first practical SIMD programming interface JVI for Java. We prove its good efficiency with real applications. The new programming interface is of similar style of common Java programming, high portable. 3. We analysis the detailed dynamic behaviors of JavaScript programs systemati-cally. We summarize the main features as the static predictability. At the same time, based on such features, we design and implement a high performance JavaScript engine TypeCastor. The new engine is able to speed up performance of real JavaScript programs.4. We construct the first program execution model for JavaScript programs on hard-ware system with SIMD instruction extension. The new model can be used to guide the optimizing procedure of JavaScript programs and predict the result speedup.