基于运行时的程序执行模型研究
|
摘要
随着技术的不断进步和应用领域的不断扩大,计算机系统日益朝着硬件复杂化和软件抽象化的方向发展。硬件复杂化为软件提供了更多的性能优化的机会,而软件抽象化则提高了计算机软件工作者的生产效率。但是,随着硬件复杂化和软件抽象化的程度的提高,其间必然产生日益扩大的鸿沟。这个鸿沟在宏观上体现在高度抽象化的软件在高度复杂化的硬件平台上较低的执行效率,而软硬件之间的运行时环境则是这个鸿沟的物理载体。
为了优化高度抽象的软件在高度复杂的硬件上的执行效率,而同时又不损失抽象的软件本身在高生产率上的优势,我们就需要对程序执行模型进行研究。程序执行模型建立在具有指定特征的硬件之上,并服务于具有指定特征的应用程序。对程序执行模型的研究,可以分析硬件特征在程序优化中的实际有效性,可以指导程序的优化并预测程序优化后的执行效率和性能加速比,因此对硬件、应用软件以及运行时环境的设计、分析和优化都有着重要的理论和实际应用价值。
鉴于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程序的向量化优化,并能够对优化结果进行较为准确的预测。
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.
为了优化高度抽象的软件在高度复杂的硬件上的执行效率,而同时又不损失抽象的软件本身在高生产率上的优势,我们就需要对程序执行模型进行研究。程序执行模型建立在具有指定特征的硬件之上,并服务于具有指定特征的应用程序。对程序执行模型的研究,可以分析硬件特征在程序优化中的实际有效性,可以指导程序的优化并预测程序优化后的执行效率和性能加速比,因此对硬件、应用软件以及运行时环境的设计、分析和优化都有着重要的理论和实际应用价值。
鉴于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程序的向量化优化,并能够对优化结果进行较为准确的预测。
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.
引文
[1]M. Anton Ertl and David Gregg. Optimizing indirect branch prediction accu-racy in virtual machine interpreters.2003. URL http://www. complang. tuwien.ac.at/papers/ert1%26gregg03.ps.gz.
[2]陈国良,苗乾坤,孙广中,徐云,郑启龙.分层并行计算模型.中国科学技术大学学报,38(007)：841-847,2008.
[3]B. Parhami. SIMD machines:do they have a significant future? ACM SIGARCH Computer Architecture News,23(4):22,1995.
[4]MC August, GM Brost, CC Hsiung, AJ Schiffleger, C. Res, and C. Falls. Cray X-MP:The birth of a supercomputer. Computer,22(1):45-52,1989.
[5]M. Tremblay, JM O'Connor, S.M. Inc, and M. View. UltraSparc I:A four-issue processor supporting multimedia. IEEE Micro,16(2):42-50,1996.
[6]M. Tremblay, JM O'Connor, V. Narayanan, L. He, S.M. Inc, and CA Mountain View. VIS speeds new media processing. IEEE micro,16(4):10-20,1996.
[7]A. Peleg, S. Wilkie, and U. Weiser. Intel MMX for multimedia PCs. Communi-cations of the ACM,40(1):24-38,1997.
[8]K. Diefendorff, P.K. Dubey, R. Hochsprung, and H. Scales. AltiVec extension to PowerPC accelerates media processing. IEEE Micro,20(2):85-95,2000.
[9]HP Hofstee. Power efficient processor architecture and the Cell processor. In High-Performance Computer Architecture,2005. HPCA-11. 11th International Symposium on, pages 258-262,2005.
[10]M. Macedonia. The GPU enters computing's mainstream. Computer,36(10): 106-108,2003.
[11]L. Seiler, D. Carmean, E. Sprangle, T. Forsyth, M. Abrash, P. Dubey, S. Junkins, A. Lake, J. Sugerman, R. Cavin, et al. Larrabee:a many-core x86 architecture for visual computing. In ACM SIGGRAPH 2008papers, page 18. ACM,2008.
[12]Shreekant (Ticky) Thakkar and Tom Huff. Internet streaming simd exten-sions. Computer,32:26-34,1999. ISSN 0018-9162. doi:http://doi. ieeecomputersociety.org/10.1109/2.809248.
[13]Intel Corporation. IA32 Intel Architecture Software Developer's Manual.2004.
[14]Intel Corporation. Intel SSE4 Programming Reference.2007.
[15]N. Firasta, M. Buxton, P. Jinbo, K. Nasri, and S. Kuo. Intel avx:New frontiers in performance improvements and energy efficiency,2008.
[16]Intel Corporation. Intel C++Intrinsics Reference.2007.
[17]A.A. Gholoum, E. Sprangle, J. Fang, G. Wu, and X. Zhou. Ct:A Flexible Parallel Programming Model for Tera-scale-Intel Whitepaper,2007.
[18]NOVELL CORPORATION. Mono's simd support:Making mono safe for gaming.2008. URL http://tirania. org/blog/archive/2008/ Nov-03.html.
[19]T. Lindholm and F. Yellin. Java virtual machine specification. Addison-Wesley Longman Publishing Co., Inc. Boston, MA, USA,1999.
[20]D. Flanagan. JavaScript:the definitive guide. O'Reilly Media, Inc.,2006.
[21]G.L. Steele. Common LISP:the language. Digital Pr,1990.
[22]R.D. Greenblatt, T.F. Knight, J.T. Holloway, and D.A. Moon. A Lisp Machine. In Proceedings of the fifth workshop on Computer architecture for non-numeric processing, pages 137-138. ACM,1980.
[23]L. Wall and M. Loukides. Programming perl. O'Reilly & Associates, Inc. Se-bastopol, CA, USA,2000.
[24]R. Lerdorf, K. Tatroe, and P. MacIntyre. Programming Php. O'Reilly Media, Inc.,2006.
[25]M. Lutz. Programming python. O'Reilly Media, Inc.,2006.
[26]R. Ierusalimschy. Programming in Lua. Roberto Ierusalimschy,2006.
[27]E.L. Specification. Standard ecma-262. ECMA Standardizing Information and Communication Systems,3,1999.
[28]D. Goodman, M. Morrison, and B. Eich. Javascript(?) bible.2007.
[29]J. Rogers. Microsoft J script. Net Programming. Sams Publishing,2001.
[30]J. Noble, A. Taivalsaari, and I. Moore. Prototype-Based Programming:Con-cepts, Languages and Applications. Springer,1999.
[31]K.Thompson. Programming Techniques:Regular expression search algorithm. 1968.
[32]P. Foundation. Parrot virtual machine parrot homepage,2008.
[33]F. Fagerholm. Perl 6 and the Parrot Virtual Machine.2005.
[34]J. Gosling and H. McGilton. The Java language environment. Sun Microsystems Computer Company,1995.
[35]The Apache Software Foundation. Apache harmony.2010. URL http:// harmony.apache.org.
[36]WebKit Organization. Sunspider javascript benchmark.2010. URL http: //www2.webkit.org/perf/sunspider-0.9/sunspider.html.
[37]K. Shiv, K. Chow, Y. Wang, and D. Petrochenko. Specjvm2008 performance characterization. Computer Performance Evaluation and Benchmarking, pages 17-35,2009.
[38]R. Jones and R. Lins. Garbage collection:algorithms for automatic dynamic memory management. Wiley New York,1996.
[39]P. Wilson. Uniprocessor garbage collection techniques. Memory Management, pages 1-42,1992.
[40]L.P. Deutsch and D.G. Bobrow. An efficient, incremental, automatic garbage collector. Communications of the ACM,19(9):526,1976.
[41]D. Plainfosse and M. Shapiro. A survey of distributed garbage collection tech-niques. Memory Management, pages 211-249.
[42]R.D.L. RichardJones.垃圾收集,2004.
[43]吴廷鹏,张昱,刘玉宇.基于即时编译器辅助的并行垃圾收集器.计算机工程,35(010)：86-88,2009.
[44]Shaoshan Liu, Ligang Wang, Xiao-Feng Li, and Jean-Luc Gaudiot. Packer: An innovative space-time-efficient parallel garbage collection algorithm based on virtual spaces. Parallel and Distributed Processing Symposium, Interna-tional,0:1-11,2009. doi:http://doi.ieeecomputersociety.org/10.1109/IPDPS. 2009.5160989.
[45]W. uz Zaman, S.A. Ahmad, A. Abbas, and A. Qadeer. A novel design of a generational garbage collector.2002.
[46]A.W. Appel. Simple generational garbage collection and fast allocation. Soft- ware-Practice and Experience,19(2):171-183,1989.
[47]P.J. Caudill and A. Wirfs-Brock. A third generation Smalltalk-80 implementa-tion. ACM SIGPLAN Notices,21(11):130,1986.
[48]M. Hicks, L. Hornof, J.T. Moore, and S.M. Nettles. A study of large object spaces. ACM SIGPLAN Notices,34(3):145,1999.
[49]T. Endo, K. Taura, and A. Yonezawa. A scalable mark-sweep garbage collector on large-scale shared-memory machines. In Supercomputing, ACM/IEEE 1997 Conference, pages 48-48,1997.
[50]P.S. Aug. Combining copying and compacting garbage collection,” inProc Fourth Annual Glasgow Workshop on Functional Programming. SpringerVer-lag Workshops in Computer Science,1991.
[51]J. Cohen and A. Nicolau. Comparison of compacting algorithms for garbage col-lection. ACM Transactions on Programming Languages and Systems (TOPLAS), 5(4):532-553,1983.
[52]J. McCarthy. Recursive functions of symbolic expressions and their computation by machine, Part I. Communications of the ACM,3(4):195,1960.
[53]T. Endo, K. Taura, and A. Yonezawa. A scalable mark-sweep garbage collector on large-scale shared-memory machines. In Supercomputing, ACM/IEEE 1997 Conference, pages 48-48,1997.
[54]T. Domani, E.K. Kolodner, E. Lewis, E.E. Salant, K. Barabash, I. Lahan, Y. Lev-anoni, E. Petrank, and I. Yanorer. Implementing an on-the-fly garbage collector for Java. In Proceedings of the 2nd international symposium on Memory man-agement, pages 155-166. ACM,2000.
[55]J.H. McBeth. Letters to the editor:on the reference counter method. Communi-cations of the ACM,6(9):575,1963.
[56]E.L. Lawler. Sequencing jobs to minimize total weighted completion time sub-ject to precedence constraints. Algorithmic aspects of combinatorics,2:75-90, 1978.
[57]JD Ullman. NP-complete scheduling problems. Journal of Computer and Sys-tem Sciences,10(3):384-393,1975.
[58]CCS Cheng et al. A state-of-the-art review of parallel-machine scheduling re- search. European Journal of Operational Research,47(3):271-292,1990.
[59]DB Shmoys, J. Wein, and DP Williamson. Scheduling parallel machines on-line. 1991.
[60]G. Dosa and Y. He. Semi-online algorithms for parallel machine scheduling problems. Computing,72(3):355-363,2004.
[61]M.G. Speranza H. Kellerer and Z. Tuza. Semi on-line algorithms for the partition problem.1995.
[62]Guochuan Zhang. A simple semi on-line algorithm for p2//cmax with a buffer. Inf. Process. Lett.,61(3):145-148,1997. ISSN 0020-0190. doi:http://dx.doi. org/10.1016/S0020-0190(97)00006-9.
[63]S. Li, Y. Zhou, G. Sun, and G. Chen. Study on parallel machine scheduling problem with buffer. Computer and Computational Sciences,2007. IMSCCS 2007. Second International Multi-Symposiums on, pages 278-273,2007.
[64]A. Strey and M. Bange. Abstract The MMX and SSE extensions of current Intel Pentium processors. Relation,10(1.49):624,2007.
[65]A. Klimovitski. Using SSE and SSE2:Misconceptions and Reality. Intel Devel-oper UPDATE Magazine (March 2001).
[66]P. Intel. Processor on 90nm Technology SSE3 Instructions,2004.
[67]S. El-Shobaky, A. El-Mahdy, and A. El-Nahas. Automatic vectorization using dynamic compilation and tree pattern matching technique in Jikes RVM. In Pro-ceedings of the 4th workshop on the Implementation, Compilation, Optimization of Object-Oriented Languages and Programming Systems, pages 63-69. ACM, 2009.
[68]S. Larsen and S. Amarasinghe. Exploiting superword level parallelism with mul-timedia instruction sets. In Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, pages 145-156. ACM, 2000.
[69]D. Naishlos. Auto-Vectorization in GCC. Free Software Foundation,2004.
[70]Free Software Foundation. Gcc,2010. URL http://gcc. gnu. org.
[71]D. Naishlos. Autovectorization in GCC. In Proceedings of the 2004 GCC De-velopers Summit, pages 105-118. Citeseer,2004.
[72]D. Nuzman, I. Rosen, and A. Zaks. Auto-vectorization of interleaved data for SIMD. In Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, page 143. ACM,2006.
[73]D. Nuzman and A. Zaks. Autovectorization in GCC-two years later. In Pro-ceedings of the 2006 GCC Developers Summit, pages 145-158,2006.
[74]I. Rosen, D. Nuzman, and A. Zaks. Loop-aware SLP in GCC. In GCC Develop-ers'Summit, page 131. Citeseer,2008.
[75]NOVELL CORPORATION. The mono project.2004. URL http://www. mono-project.com.
[76]Google Corporation. Google desktop gadgets.2010. URL http:// desktop.google.com/plugins/.
[77]Adobe Corporation. Adobe flash.2010. URL http://www. adobe.com/ products/flashplayer/.
[78]N.C. Zakas. High Performance JavaScript. Oreilly & Associates Inc,2010.
[79]Google Corporation. Gmail.2010. URL http://gmail. com.
[80]Facebook Corporation. Facebook.2010. URL http://facebook.com.
[81]Christopher Anderson Paola, Christopher Anderson, Paola Giannini, and Sophia Drossopoulou. Towards type inference for javascript.2005. URL http://citeseerx.ist.psu.edu/viewdoc/summary?doi= 10.1.1.59.2285.
[82]D. Jang and K.M. Choe. Points-to analysis for JavaScript. In Proceedings of the 2009 ACM symposium on Applied Computing, pages 1930-1937. ACM,2009.
[83]B. Steensgaard. Points-to analysis in almost linear time. In Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming lan-guages, pages 32-41. ACM New York, NY, USA,1996.
[84]M. Shapiro and S. Horwitz. Fast and accurate flow-insensitive points-to analysis. In Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, pages 1-14. ACM,1997.
[85]Simon Holm Jensen, Anders Mφller, and Peter Thiemann. Type analysis for javascript. In SAS'09:Proceedings of the 16th International Symposium on Static Analysis, pages 238-255, Berlin, Heidelberg,2009. Springer-Verlag. ISBN 978-3-642-03236-3. doi:http://dx.doi.org/10.1007/978-3-642-03237-0_17.
[86]G. Balakrishnan and T. Reps. Recency-abstraction for heap-allocated storage. Static Analysis, pages 221-239,2006.
[87]Peter Thiemann. Towards a type system for analyzing javascript programs, pages 408-422.2005. URL http://www.springerlink.com/content/ nudp8rmw194glhqc.
[88]P.H.P. Thiemann. Recency Types for Dynamically-Typed, Object-Based Lan-guages.2009.
[89]Mozilla Rhino. Javascript for java.2010. URL http://www.mozilla. org/rhino/.
[90]A. Gal, B. Eich, M. Shaver, D. Anderson, D. Mandelin, M.R. Haghighat, B. Ka-plan, G. Hoare, B. Zbarsky, J. Orendorff, et al. Trace-based just-in-time type specialization for dynamic languages. In Proceedings of the 2009 ACM SIG-PLAN conference on Programming language design and implementation, pages 465-478. ACM,2009.
[91]Mozilla.org. Spidermonkey (javascript-c) engine.2010. URL http://www. mozilla.org/js/spidermonkey/.
[92]Mozilla Corporation. Spidermonkey internals.2010. URL https: //developer.mozilla.org/En/SpiderMonkey-/Internals/ Property_cache.
[93]Mads Sig Ager. V8 internals. In Google IO 2009,2009. URL http://dl.google.com/io/2009/pres/W_1230_V8BuildingaHighPerformanceJavaScriptEngine.pdf.
[94]A. Barth, C. Jackson, and C. Reis. The Google Chrome Team. The Security Architecture of the Chromium Browser. WWW2009, April,2009.
[95]J. Gray. Google Chrome:the making of a cross-platform browser. Linux Journal, 2009(185):1,2009.
[96]A. Eid and F. Al-Dhelaan. Google Chrome browser:a Security and Performance Study.2008.
[97]A. Koenig and BE Moo. Templates and duck typing. Dr. Dobbs Portal,2005.
[98]A. Koenig and B.E. Moo. COLUMNS-C++Made Easy-The distinction in C++ between duck typing and inheritance comes from C++s static type system, and is part of the price we pay for having C++programs run as quickly as they. C/C++Users Journal, pages 53-54,2005.
[99]Maciej Stachowiak and Surfin's Safari. Announcing squirrelfish extreme.2008. URL http://webkit.org/blog/214/ introducing-squirrelfish-extreme/.
[100]WM McKeeman. Peephole optimization. Communications of the ACM,8(7): 444,1965.
[101]D.H. Jung, S.M. Moon, and S.H. Bae. Design and Optimization of a Java Ahead-of-Time Compiler for Embedded Systems. In IEEE/IFIP International Confer-ence on Embedded and Ubiquitous Computing,2008. EUC'08, volume 1,2008.
[102]N. Shay lor. A just-in-time compiler for memory-constrained low-power devices. In Proceedings of the 2nd Java Virtual Machine Research and Technology Sym-posium, pages 119-126. USENIX Association,2002.
[103]T. Suganuma, T. Yasue, M. Kawahito, H. Komatsu, and T. Nakatani. A dynamic optimization framework for a Java just-in-time compiler. In Proceedings of the 16th ACM SIGPLAN conference on Object-oriented programming, systems, lan-guages, and applications, page 195. ACM,2001.
[104]Intel Corporation. Intel VTune Performance Analyser,2010.
[2]陈国良,苗乾坤,孙广中,徐云,郑启龙.分层并行计算模型.中国科学技术大学学报,38(007)：841-847,2008.
[3]B. Parhami. SIMD machines:do they have a significant future? ACM SIGARCH Computer Architecture News,23(4):22,1995.
[4]MC August, GM Brost, CC Hsiung, AJ Schiffleger, C. Res, and C. Falls. Cray X-MP:The birth of a supercomputer. Computer,22(1):45-52,1989.
[5]M. Tremblay, JM O'Connor, S.M. Inc, and M. View. UltraSparc I:A four-issue processor supporting multimedia. IEEE Micro,16(2):42-50,1996.
[6]M. Tremblay, JM O'Connor, V. Narayanan, L. He, S.M. Inc, and CA Mountain View. VIS speeds new media processing. IEEE micro,16(4):10-20,1996.
[7]A. Peleg, S. Wilkie, and U. Weiser. Intel MMX for multimedia PCs. Communi-cations of the ACM,40(1):24-38,1997.
[8]K. Diefendorff, P.K. Dubey, R. Hochsprung, and H. Scales. AltiVec extension to PowerPC accelerates media processing. IEEE Micro,20(2):85-95,2000.
[9]HP Hofstee. Power efficient processor architecture and the Cell processor. In High-Performance Computer Architecture,2005. HPCA-11. 11th International Symposium on, pages 258-262,2005.
[10]M. Macedonia. The GPU enters computing's mainstream. Computer,36(10): 106-108,2003.
[11]L. Seiler, D. Carmean, E. Sprangle, T. Forsyth, M. Abrash, P. Dubey, S. Junkins, A. Lake, J. Sugerman, R. Cavin, et al. Larrabee:a many-core x86 architecture for visual computing. In ACM SIGGRAPH 2008papers, page 18. ACM,2008.
[12]Shreekant (Ticky) Thakkar and Tom Huff. Internet streaming simd exten-sions. Computer,32:26-34,1999. ISSN 0018-9162. doi:http://doi. ieeecomputersociety.org/10.1109/2.809248.
[13]Intel Corporation. IA32 Intel Architecture Software Developer's Manual.2004.
[14]Intel Corporation. Intel SSE4 Programming Reference.2007.
[15]N. Firasta, M. Buxton, P. Jinbo, K. Nasri, and S. Kuo. Intel avx:New frontiers in performance improvements and energy efficiency,2008.
[16]Intel Corporation. Intel C++Intrinsics Reference.2007.
[17]A.A. Gholoum, E. Sprangle, J. Fang, G. Wu, and X. Zhou. Ct:A Flexible Parallel Programming Model for Tera-scale-Intel Whitepaper,2007.
[18]NOVELL CORPORATION. Mono's simd support:Making mono safe for gaming.2008. URL http://tirania. org/blog/archive/2008/ Nov-03.html.
[19]T. Lindholm and F. Yellin. Java virtual machine specification. Addison-Wesley Longman Publishing Co., Inc. Boston, MA, USA,1999.
[20]D. Flanagan. JavaScript:the definitive guide. O'Reilly Media, Inc.,2006.
[21]G.L. Steele. Common LISP:the language. Digital Pr,1990.
[22]R.D. Greenblatt, T.F. Knight, J.T. Holloway, and D.A. Moon. A Lisp Machine. In Proceedings of the fifth workshop on Computer architecture for non-numeric processing, pages 137-138. ACM,1980.
[23]L. Wall and M. Loukides. Programming perl. O'Reilly & Associates, Inc. Se-bastopol, CA, USA,2000.
[24]R. Lerdorf, K. Tatroe, and P. MacIntyre. Programming Php. O'Reilly Media, Inc.,2006.
[25]M. Lutz. Programming python. O'Reilly Media, Inc.,2006.
[26]R. Ierusalimschy. Programming in Lua. Roberto Ierusalimschy,2006.
[27]E.L. Specification. Standard ecma-262. ECMA Standardizing Information and Communication Systems,3,1999.
[28]D. Goodman, M. Morrison, and B. Eich. Javascript(?) bible.2007.
[29]J. Rogers. Microsoft J script. Net Programming. Sams Publishing,2001.
[30]J. Noble, A. Taivalsaari, and I. Moore. Prototype-Based Programming:Con-cepts, Languages and Applications. Springer,1999.
[31]K.Thompson. Programming Techniques:Regular expression search algorithm. 1968.
[32]P. Foundation. Parrot virtual machine parrot homepage,2008.
[33]F. Fagerholm. Perl 6 and the Parrot Virtual Machine.2005.
[34]J. Gosling and H. McGilton. The Java language environment. Sun Microsystems Computer Company,1995.
[35]The Apache Software Foundation. Apache harmony.2010. URL http:// harmony.apache.org.
[36]WebKit Organization. Sunspider javascript benchmark.2010. URL http: //www2.webkit.org/perf/sunspider-0.9/sunspider.html.
[37]K. Shiv, K. Chow, Y. Wang, and D. Petrochenko. Specjvm2008 performance characterization. Computer Performance Evaluation and Benchmarking, pages 17-35,2009.
[38]R. Jones and R. Lins. Garbage collection:algorithms for automatic dynamic memory management. Wiley New York,1996.
[39]P. Wilson. Uniprocessor garbage collection techniques. Memory Management, pages 1-42,1992.
[40]L.P. Deutsch and D.G. Bobrow. An efficient, incremental, automatic garbage collector. Communications of the ACM,19(9):526,1976.
[41]D. Plainfosse and M. Shapiro. A survey of distributed garbage collection tech-niques. Memory Management, pages 211-249.
[42]R.D.L. RichardJones.垃圾收集,2004.
[43]吴廷鹏,张昱,刘玉宇.基于即时编译器辅助的并行垃圾收集器.计算机工程,35(010)：86-88,2009.
[44]Shaoshan Liu, Ligang Wang, Xiao-Feng Li, and Jean-Luc Gaudiot. Packer: An innovative space-time-efficient parallel garbage collection algorithm based on virtual spaces. Parallel and Distributed Processing Symposium, Interna-tional,0:1-11,2009. doi:http://doi.ieeecomputersociety.org/10.1109/IPDPS. 2009.5160989.
[45]W. uz Zaman, S.A. Ahmad, A. Abbas, and A. Qadeer. A novel design of a generational garbage collector.2002.
[46]A.W. Appel. Simple generational garbage collection and fast allocation. Soft- ware-Practice and Experience,19(2):171-183,1989.
[47]P.J. Caudill and A. Wirfs-Brock. A third generation Smalltalk-80 implementa-tion. ACM SIGPLAN Notices,21(11):130,1986.
[48]M. Hicks, L. Hornof, J.T. Moore, and S.M. Nettles. A study of large object spaces. ACM SIGPLAN Notices,34(3):145,1999.
[49]T. Endo, K. Taura, and A. Yonezawa. A scalable mark-sweep garbage collector on large-scale shared-memory machines. In Supercomputing, ACM/IEEE 1997 Conference, pages 48-48,1997.
[50]P.S. Aug. Combining copying and compacting garbage collection,” inProc Fourth Annual Glasgow Workshop on Functional Programming. SpringerVer-lag Workshops in Computer Science,1991.
[51]J. Cohen and A. Nicolau. Comparison of compacting algorithms for garbage col-lection. ACM Transactions on Programming Languages and Systems (TOPLAS), 5(4):532-553,1983.
[52]J. McCarthy. Recursive functions of symbolic expressions and their computation by machine, Part I. Communications of the ACM,3(4):195,1960.
[53]T. Endo, K. Taura, and A. Yonezawa. A scalable mark-sweep garbage collector on large-scale shared-memory machines. In Supercomputing, ACM/IEEE 1997 Conference, pages 48-48,1997.
[54]T. Domani, E.K. Kolodner, E. Lewis, E.E. Salant, K. Barabash, I. Lahan, Y. Lev-anoni, E. Petrank, and I. Yanorer. Implementing an on-the-fly garbage collector for Java. In Proceedings of the 2nd international symposium on Memory man-agement, pages 155-166. ACM,2000.
[55]J.H. McBeth. Letters to the editor:on the reference counter method. Communi-cations of the ACM,6(9):575,1963.
[56]E.L. Lawler. Sequencing jobs to minimize total weighted completion time sub-ject to precedence constraints. Algorithmic aspects of combinatorics,2:75-90, 1978.
[57]JD Ullman. NP-complete scheduling problems. Journal of Computer and Sys-tem Sciences,10(3):384-393,1975.
[58]CCS Cheng et al. A state-of-the-art review of parallel-machine scheduling re- search. European Journal of Operational Research,47(3):271-292,1990.
[59]DB Shmoys, J. Wein, and DP Williamson. Scheduling parallel machines on-line. 1991.
[60]G. Dosa and Y. He. Semi-online algorithms for parallel machine scheduling problems. Computing,72(3):355-363,2004.
[61]M.G. Speranza H. Kellerer and Z. Tuza. Semi on-line algorithms for the partition problem.1995.
[62]Guochuan Zhang. A simple semi on-line algorithm for p2//cmax with a buffer. Inf. Process. Lett.,61(3):145-148,1997. ISSN 0020-0190. doi:http://dx.doi. org/10.1016/S0020-0190(97)00006-9.
[63]S. Li, Y. Zhou, G. Sun, and G. Chen. Study on parallel machine scheduling problem with buffer. Computer and Computational Sciences,2007. IMSCCS 2007. Second International Multi-Symposiums on, pages 278-273,2007.
[64]A. Strey and M. Bange. Abstract The MMX and SSE extensions of current Intel Pentium processors. Relation,10(1.49):624,2007.
[65]A. Klimovitski. Using SSE and SSE2:Misconceptions and Reality. Intel Devel-oper UPDATE Magazine (March 2001).
[66]P. Intel. Processor on 90nm Technology SSE3 Instructions,2004.
[67]S. El-Shobaky, A. El-Mahdy, and A. El-Nahas. Automatic vectorization using dynamic compilation and tree pattern matching technique in Jikes RVM. In Pro-ceedings of the 4th workshop on the Implementation, Compilation, Optimization of Object-Oriented Languages and Programming Systems, pages 63-69. ACM, 2009.
[68]S. Larsen and S. Amarasinghe. Exploiting superword level parallelism with mul-timedia instruction sets. In Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, pages 145-156. ACM, 2000.
[69]D. Naishlos. Auto-Vectorization in GCC. Free Software Foundation,2004.
[70]Free Software Foundation. Gcc,2010. URL http://gcc. gnu. org.
[71]D. Naishlos. Autovectorization in GCC. In Proceedings of the 2004 GCC De-velopers Summit, pages 105-118. Citeseer,2004.
[72]D. Nuzman, I. Rosen, and A. Zaks. Auto-vectorization of interleaved data for SIMD. In Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, page 143. ACM,2006.
[73]D. Nuzman and A. Zaks. Autovectorization in GCC-two years later. In Pro-ceedings of the 2006 GCC Developers Summit, pages 145-158,2006.
[74]I. Rosen, D. Nuzman, and A. Zaks. Loop-aware SLP in GCC. In GCC Develop-ers'Summit, page 131. Citeseer,2008.
[75]NOVELL CORPORATION. The mono project.2004. URL http://www. mono-project.com.
[76]Google Corporation. Google desktop gadgets.2010. URL http:// desktop.google.com/plugins/.
[77]Adobe Corporation. Adobe flash.2010. URL http://www. adobe.com/ products/flashplayer/.
[78]N.C. Zakas. High Performance JavaScript. Oreilly & Associates Inc,2010.
[79]Google Corporation. Gmail.2010. URL http://gmail. com.
[80]Facebook Corporation. Facebook.2010. URL http://facebook.com.
[81]Christopher Anderson Paola, Christopher Anderson, Paola Giannini, and Sophia Drossopoulou. Towards type inference for javascript.2005. URL http://citeseerx.ist.psu.edu/viewdoc/summary?doi= 10.1.1.59.2285.
[82]D. Jang and K.M. Choe. Points-to analysis for JavaScript. In Proceedings of the 2009 ACM symposium on Applied Computing, pages 1930-1937. ACM,2009.
[83]B. Steensgaard. Points-to analysis in almost linear time. In Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming lan-guages, pages 32-41. ACM New York, NY, USA,1996.
[84]M. Shapiro and S. Horwitz. Fast and accurate flow-insensitive points-to analysis. In Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, pages 1-14. ACM,1997.
[85]Simon Holm Jensen, Anders Mφller, and Peter Thiemann. Type analysis for javascript. In SAS'09:Proceedings of the 16th International Symposium on Static Analysis, pages 238-255, Berlin, Heidelberg,2009. Springer-Verlag. ISBN 978-3-642-03236-3. doi:http://dx.doi.org/10.1007/978-3-642-03237-0_17.
[86]G. Balakrishnan and T. Reps. Recency-abstraction for heap-allocated storage. Static Analysis, pages 221-239,2006.
[87]Peter Thiemann. Towards a type system for analyzing javascript programs, pages 408-422.2005. URL http://www.springerlink.com/content/ nudp8rmw194glhqc.
[88]P.H.P. Thiemann. Recency Types for Dynamically-Typed, Object-Based Lan-guages.2009.
[89]Mozilla Rhino. Javascript for java.2010. URL http://www.mozilla. org/rhino/.
[90]A. Gal, B. Eich, M. Shaver, D. Anderson, D. Mandelin, M.R. Haghighat, B. Ka-plan, G. Hoare, B. Zbarsky, J. Orendorff, et al. Trace-based just-in-time type specialization for dynamic languages. In Proceedings of the 2009 ACM SIG-PLAN conference on Programming language design and implementation, pages 465-478. ACM,2009.
[91]Mozilla.org. Spidermonkey (javascript-c) engine.2010. URL http://www. mozilla.org/js/spidermonkey/.
[92]Mozilla Corporation. Spidermonkey internals.2010. URL https: //developer.mozilla.org/En/SpiderMonkey-/Internals/ Property_cache.
[93]Mads Sig Ager. V8 internals. In Google IO 2009,2009. URL http://dl.google.com/io/2009/pres/W_1230_V8BuildingaHighPerformanceJavaScriptEngine.pdf.
[94]A. Barth, C. Jackson, and C. Reis. The Google Chrome Team. The Security Architecture of the Chromium Browser. WWW2009, April,2009.
[95]J. Gray. Google Chrome:the making of a cross-platform browser. Linux Journal, 2009(185):1,2009.
[96]A. Eid and F. Al-Dhelaan. Google Chrome browser:a Security and Performance Study.2008.
[97]A. Koenig and BE Moo. Templates and duck typing. Dr. Dobbs Portal,2005.
[98]A. Koenig and B.E. Moo. COLUMNS-C++Made Easy-The distinction in C++ between duck typing and inheritance comes from C++s static type system, and is part of the price we pay for having C++programs run as quickly as they. C/C++Users Journal, pages 53-54,2005.
[99]Maciej Stachowiak and Surfin's Safari. Announcing squirrelfish extreme.2008. URL http://webkit.org/blog/214/ introducing-squirrelfish-extreme/.
[100]WM McKeeman. Peephole optimization. Communications of the ACM,8(7): 444,1965.
[101]D.H. Jung, S.M. Moon, and S.H. Bae. Design and Optimization of a Java Ahead-of-Time Compiler for Embedded Systems. In IEEE/IFIP International Confer-ence on Embedded and Ubiquitous Computing,2008. EUC'08, volume 1,2008.
[102]N. Shay lor. A just-in-time compiler for memory-constrained low-power devices. In Proceedings of the 2nd Java Virtual Machine Research and Technology Sym-posium, pages 119-126. USENIX Association,2002.
[103]T. Suganuma, T. Yasue, M. Kawahito, H. Komatsu, and T. Nakatani. A dynamic optimization framework for a Java just-in-time compiler. In Proceedings of the 16th ACM SIGPLAN conference on Object-oriented programming, systems, lan-guages, and applications, page 195. ACM,2001.
[104]Intel Corporation. Intel VTune Performance Analyser,2010.