【作者】 李世胜；

【导师】 陈国良；

【作者基本信息】 中国科学技术大学 ， 计算机软件与理论， 2010， 博士

【摘要】 随着技术的不断进步和应用领域的不断扩大,计算机系统日益朝着硬件复杂化和软件抽象化的方向发展。硬件复杂化为软件提供了更多的性能优化的机会,而软件抽象化则提高了计算机软件工作者的生产效率。但是,随着硬件复杂化和软件抽象化的程度的提高,其间必然产生日益扩大的鸿沟。这个鸿沟在宏观上体现在高度抽象化的软件在高度复杂化的硬件平台上较低的执行效率,而软硬件之间的运行时环境则是这个鸿沟的物理载体。为了优化高度抽象的软件在高度复杂的硬件上的执行效率,而同时又不损失抽象的软件本身在高生产率上的优势,我们就需要对程序执行模型进行研究。程序执行模型建立在具有指定特征的硬件之上,并服务于具有指定特征的应用程序。对程序执行模型的研究,可以分析硬件特征在程序优化中的实际有效性,可以指导程序的优化并预测程序优化后的执行效率和性能加速比,因此对硬件、应用软件以及运行时环境的设计、分析和优化都有着重要的理论和实际应用价值。鉴于SIMD指令以及动态程序设计语言在近些年来成为了学术界和工业界研究的热点,以及动态程序设计语言的高度抽象性,本文研究在具有SIMD指令集扩展的硬件之上,动态程序设计语言JavaScript的执行模型的建立、分析以及用之来指导对JavaScript程序的性能优化。本文研究成果主要包括：1.提出并分析了新的多线程调度算法：本文研究了Harmony Java虚拟机中的垃圾回收算法,抽象了其中的对象移动任务调度问题,提出了一个新的多线程半在线调度算法并分析了其竞争比。2.设计实现了高效的Java虚拟机SIMD编程接口：本文以Intel X86平台为基础,提出了Harmony Java虚拟机上的SIMD指令的编程接口JVI,并用SpecJVM2008测试程序集测量了JVI的性能,验证了其高效性。3.系统分析了JavaScript语言程序的执行行为：本文通过SunSpider测试程序集,以我们提出的针对JavaScript语言程序的动态类型系统处理算法为基础,系统的分析了JavaScript语言程序在其元数据类型、对象结构、数组结构等方面的执行行为。4.设计实现了高效的JavaScript执行引擎TypeCastor:本文以Harmony Java虚拟机为基础,设计实现了JavaScript语言程序的执行引擎TypeCastor,在其中实现了我们提出的针对JavaScript语言程序的动态类型系统处理算法,并以SunSpider测试程序集为基础测量了TypeCastor的性能,验证了其高效性。5.优化了JavaScript程序在SIMD指令集硬件上的执行性能：本文以我们提出的SIMD应用程序接口JVI以及JavaScript程序执行引擎TypeCastor为基础,设计了JavaScript语言的SIMD指令接口,并以此接口优化并测量了JavaScript程序的执行性能。6.建立并分析了带SIMD指令集硬件上的JavaScript程序的执行模型TPW：本文通过分析JavaScript的执行行为、向量化优化过程以及实验数据,建立一个TPW模型用于描述JavaScript程序的执行行为、指导SIMD优化的过程、并预测SIMD优化后程序的加速比和执行特征。本文的主要创新点有：1.提出了一个新的针对虚拟机垃圾回收中对象移动问题的多线程任务调度算法,并对其进行了严格的竞争比和问题复杂度分析,因此对垃圾回收中的线程调度算法的设计从理论上给出了指导方法。2.首次提出了在Java虚拟机上的SIMD指令的编程接口,并通过实际的应用程序验证了接口的高效性。该接口贴合Java语言的特征、可移植性强并且足够抽象,因此为程序员对Java等语言程序进行向量化优化提供了十分便利有效的工具。3.系统的分析了JavaScript语言的执行行为,总结出其动态类型系统的可静态预测性。同时,利用这一性质,我们设计并实现了一个高效的JavaScript执行引擎TypeCastor,使用这个引擎可以大大的提高实际的JavaScript程序的执行效率。4.建立了首个JavaScript程序在SIMD指令集硬件体系结构上的程序执行模型TPW。该模型可以用以指导对JavaScript程序的向量化优化,并能够对优化结果进行较为准确的预测。更多还原

【Abstract】 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.更多还原