基于分布式部分计值的Web服务优化

基于分布式部分计值的Web服务优化1毛宏燕，黄林鹏，孙永强（上海交通大学 计算机科学与工程系 上海 200030）（mhy@）摘 要 为适应分布式计算环境的变化特性，采用中间件和模块化设计是当前流行的研发方式．这种流行设计常会引出低效和复杂性等问题．为保持通用设计和高效程序执行的一致性，本文提出利用分布式部分计值技术优化Web服务的新方法．基于字节代码的例化，给出网络环境中分布式部分计值器DJmix的架构和实现机制，通过光线跟踪服务实例的研究和实验结果，论述了部分计值对改进Web服务的性能和提高流行方法效率的重要作用．关键词 部分计值；例化；Web服务；字节代码1 引言当前的计算环境大都具有分布式和异构性的主要特点，如网络中异构型机器，计算任务的迁移、不断变化的软件服务等．为了适应这些特性，Web服务设计常采用模块化或中间件的思想和方法，以此来提高系统的通用性、复用性和扩展性．以上性能的提高和对应用方面带来的灵活适应却引出了运行效率方面的副作用，特别是对那些涉及大量计算的特殊应用领域，程序变得十分庞大，增加了执行时间，降低了运行效率．部分计值技术的引入将在很大程度上解决效率问题，并能对流行方法提供有力支持．部分计值（Partial Evaluation）是一种程序转换和程序例化技术，该技术可针对给定的部分输入参数例化应用程序，以一种高效的剩余代码来完成尽可能多的计算．许多应用领域曾采用过部分计值技术进行程序优化，象科学计算，编译器生成，计算机图形学等．早期的部分计值主要针对函数式或逻辑语言，它们具有良好的代数基础，相对容易实现计值过程．当前，面向对象语言和分布式计算已成为主流技术，但对这些方面的部分计值研究却较少．Java语言是当前最流行的纯面向对象语言，她不依赖于任何操作系统和体系结构成了大型项目研发的首选工具．但因其解释性特点，使得基于Java的应用在速度方面往往成了系统平颈．为了提高Java程序的执行效率，可将部分计值引入到Java虚拟机，通过字节代码的例化，提高Java程序的运行效率．我们提出了优化Web服务的分布式部分计值器DJmix的架构，及基于SOAP和WSDL等Web服务基础上的相应实现机制．为检验分布式部分计值如何改善应用程序运行效率及性能结果，实验采用了分布式光线跟踪应用程序．该试验运行在位于上海张江高科技园的超级计算机中心，获得的性能加速比说明了DJmix能够提高应用程序的性能和效率，并且对分布式软件开发技术提供了有力支持．2 部分计值2.1 部分计值部分计值是在输入已知的情况下，对程序进行例化，执行尽可能多的运算，生成更高效的程序代码．利用部分计值和程序中已知的参数，可以导出一给定程序的剩余程序，剩余程序含有部分未知参数[3，4]．部分计值器PE是采用部分计值技术的程序，给定程序p和它的输入I，I分为静态（已知）部分s和动态（未知）部分d．部分计值器例化程序p，产生包含动态参数的剩余程序P s，满足〖PE〗[p, s] ＝p s〖p〗[s, d] ＝〖p s〗[d]程序p和剩余程序p s的运行在满足某个条件都能终止时，产生的最终结果相同．所不同的是运行p s的速度快，尤其在多次调用p s时，运行时间会大大减少：Time（〖PE〗[p, s]）+ n * Time（p s）< n * Time（〖p〗[s, d]））假定x n的幂函数power（n, x），在循环中对给定值n＝5和不同的x值进行计算，利用部分计值可以得到剩余函数power_5（x）．对任意的x值，运行power（5,x）和power_5（x）得到的结果都是一样的．但是，剩余函数中所有的判断条件和与n有关的算术操作都被消除了，在原始函数中的控制流需要由静态参数n确定．在部分计值器中，可以通过预先计算常量表达式，消除冗余代码，改变算法或数据结构等方法来提高程序的性能．部分计值器分为在线（online）和离线（offline）两类．在线部分计值器是一非标准的解释器，每个表达式的处理都是在例化过程中动态确定的．在线部分计值器得到的结果比较精确，但花费的解释开销较大．离线部分计值器包括预处理（PE）和处理（PE）两个阶段．PE包含约束时间分析（BTA，Binding Time Analysis）和标注原始程序．PE根据PE 的标注信息执行部分计值生成剩余程序．由于约束时间分析是近似的，因此，利用离线计值器的结果不精确，但却能节省解释开销．2.2 基于字节代码的部分计值器在对面向对象语言和面向对象技术研究的热门话题中，关于部分计值方面的研究较少．其中涉及到对象的抽象性，继承性，和虚调用等一些特性，这使得对这类语言的部分计值研究工作比函数式、命令式和逻辑语言复杂得多．Java语言属于纯面向对象语言，基于Java的程序运行速度较慢．将部分计值与Java 虚拟机（JVM，Java Virtual Machine）相结合，通过对字节码的例化（BCS，Byte Code Specialization）[6]，可以提高指令的执行效率，从而加快程序的运行速度．BCS最早由Masuhara和Yonezawa提出的，他们给出了基于JVM指令子集的实时例化系统，但只包含7条指令，且不能处理转移指令．参考这一设计思路，我们设计了基于Java字节代码的部分计值器Jmix，给出了表达式、语法及相应的形式化计值规则，参见图1．图1 表达式的语法其中，ConstExp表示iconst<i>把常量i压入堆栈，VarExp把变量的索引压入堆栈．PreIncExp先把表达式的值压入堆栈，然后对表达式执行＋＋操作．PostIncExp是先对表达式执行＋＋操作，然后将结果压入堆栈．AssignExp先计算表达式并将其值压栈，然后复制栈顶的值并拷贝到变量e中．UnaryExp对表达式进行一元运算，BinaryExp将对两个表达式进行二元运算．CondExp和InvokeExp为控制转移操作，根据满足条件的表达式来执行相应的分支运算．以类似形式，给出的相应语法规范为Stmt::= EmptyStmt| MultiStmt| IncStmt| AssignStmt|IfThenStmt| IfThenElseStmt|WhileStmt| DoStmt| InvokeStmt针对语法规则，可以得到相应的语义[7]．若没有语法规则，很难确定条件转移指令序列，也难以保证计值的一致性．Jmix能对不确定条件下的控制转移指令进行例化．结合字节码例化的计值规则，用λ演算易证计值的正确性．图2 Jmix模型图2给出了Jmix例化的过程，字节代码程序作为计值对象．Jmix采用online计值方法，记录每个变量、指令、堆栈的状态及变化情况，通过解析class文件结构得到常量池，并将状态信息保存在Vector向量中．最后，得到class文件中例化后的指令序列．与[7]中的字节代码例化（BCS）相比，Jmix还能对虚函数调用，堆栈，数组，内嵌方法及不确定条件下控制转移指令进行例化．Jmix不仅可以计值某个方法和单个对象，还可以计值多个对象．3 基于Web服务的分布式部分计值3.1 分布式部分计值随着分布式应用越来越广泛，分布式部分计值也得到了相应关注．为提高现代计算环境中应用程序的性能，将部分计值技术，面向对象技术和分布式计算相结合，设计并实现分布式部分计值器DJmix是Jmix工作的必然延续和扩展．DJmix的重要意义首先是为Java语言的高效运行改进运行环境，其次是能更好地优化基于Java的分布式应用程序，特别是DJmix 对当前流行技术的有力支持，其作用和影响不可低估．Jmix只能在单机上进行例化，通过增添计值规则和通讯机制，DJmix的功能可以扩展到例化远程对象及异构环境的通信．图3 分布式部分计值模型网络计算中某台主机使用本机服务计值，或调用远程服务进行计值．例化的服务包括需要例化的方法或类，若服务在本机，则执行本地例化．若服务驻留于服务器a，则在服务器a 对服务进行计值并将例化后的结果返回给客户端．否则由服务器b进行计值并返回例化后的结果．远程服务器a或b先对服务进行例化，一方面减轻了客户端的负担，采用并行方式处理同时也改善了系统的性能．3.2 Web服务优化的部分计值器架构当前流行的方法主要采用中间件技术J2EE或CORBA等来适应网络环境下商业和科学应用中的变化现状，为了解决这种架构的效率和复杂性问题，将部分计值应用到Web服务，必然会对流行架构有所改进．网络中的任何服务都可称之为Web服务，它使得网络应用的组件化和复用变得更加容易．基于EJB的服务能够通过XML定义的接口方便地访问基于CORBA的服务，从而简化了分布式应用的开发．DJmix封装为一个Web服务，其它服务可以通过接口访问和使用DJmix．图4 网络中的DJmix架构图4是基于Web服务的DJmix架构，DJmix架构描述了服务注册，服务提供者和服务请求者之间的交互关系．它们通过基于XML的SOAP消息通讯，SOAP提供一种消息传递和远程方法调用机制，它屏蔽了网络环境中的异构性[1]．● DJmix将自身的服务描述在UDDI（统一描述，发现和注册）进行注册和发布．●服务请求者也是Web服务，使用Web服务描述语言（WSDL）在服务注册中查询所需要的服务，并与服务建立联系．●服务注册返回服务请求者所需的服务描述．Web服务运行时，根据上下文信息向服务注册发送消息，然后利用DJmix，生成该服务的例化程序．图5实现机制3.3 DJmix实现机制应用于异构环境中的分布式部分计值器DJmix满足Web服务的要求．不同站点的DJmix 协同例化应用服务．DJmix的安全性依赖于HTTP的安全机制．DJmix采用Web服务提供的标准接口和机制，如WSDL，UDDI，SOAP．DJmix是平台无关的，可以安装在任意PC机，工作站和超级计算机上，系统可选Unix，Windows，Solaris．网络中有名字服务器，客户端和例化服务器（见图5）．名字服务器保存一张服务表，其中记录了每个服务器和服务的配置信息．客户端和服务器都装有分派器和执行例化的本机部分计值器Jmix，另外服务器还装有注册程序和配置文件．其中，分派器是DJmix的核心，负责分发例化任务及与名字服务器和例化服务器的通讯．分派器发送包含需例化的服务和相应参数的消息给名字服务器，名字服务器返回查询结果．若需例化的服务在本地，则调用本地Jmix进行例化，否则由远程服务器进行例化．远程Jmix根据已知参数和运行时环境例化服务，然后远程分派器将例化后结果返回给请求的分派器．每个服务器中的配置文件是对自身服务的索引和名空间等一些服务信息的描述，这些描述采用基于XML的服务描述语言给出．注册程序将配置文件中的服务描述发布和注册到名字服务器的服务表中．具体实现过程采用Weblogic环境下的EJB技术，并对每个文件进行字节码指令分析和例化．采用基于XML的服务描述语言描述服务及服务接口,同时,用Apache SOAP2.2工具包处理服务间的请求和响应，由分派器构造相应的SOAP消息．4 实例研究4.1 光线跟踪及例化分析结合产生真实感图像的光线跟踪算法，说明DJmix能够例化Web服务，改善Web服务的性能．光线跟踪是一种图像合成的对象渲染技术，其算法因原理简单、实现方便，且能生成各种逼真视觉效果等特点，被广泛应用于广告、服装设计、虚拟现实和一些图像学应用中．光线跟踪方法是基于几何光学原理，通过模拟光的传播路径来确定反射，折射和阴影[8, 9]．光线跟踪算法通过计算屏幕上每个象素来展示曲面细节，从而产生真实感图像；缺陷是算法的递归过程计算量巨大，生成的图像显示速度也很慢．光线跟踪算法中的核心是求交运算，生成一幅图像时75％的时间用于求交，对复杂图像的求交时间可高达95％．一些研究者提出加速搜索最近交叉点以减少求交计算量．光线跟踪程序适于用部分计值优化的原因是这种程序满足以下条件：（1）每个象素，每条光线的处理过程相同，且彼此独立，因此可以利用部分计值例化相同的处理过程，并结合分布式计算模型，提高运行速度．（2）光线跟踪算法涉及大量计算．用部分计值对程序进行转换和约简，提前计算常量表达式，消除判断条件和冗余代码，得到剩余程序．当多次调用剩余程序时，运行时间会大大减少．（3）光线跟踪算法中，视点和光源是变化的，场景中的对象是固定的．部分计值将跟踪算法raytracing（scene, light, viewpoint）例化为raytracing_scene（light, viewpoint），对象间的求交只计算一次，计算结果多次复用．4.2 性能结果根据图4的架构，光线跟踪器向服务注册中心发送包含所需服务的SOAP消息，注册中心返回该服务的句柄信息．光线跟踪器再向DJmix发送XML格式的请求消息，DJmix返回响应消息，双方至此建立联系，建立连接和响应通过图形界面来完成．运行光线跟踪程序，通过部分计值器，原始程序变换为例化程序．给定某场景下，光线与球体求交函数为：interact_sphere(sphereType sphere, rayType ray){ ……x = sphere.c.x – ray.p.x;……}对第24个对象求交，有如下例化函数：interact_sphere_24(sphereType sphere, rayType ray){ ……x = 1.0 – ray.p.x;……}通过常量传递，函数展开，数据结构变换等方法简约原始程序，提高多次重复执行同一程序的效率．基于Java的光线跟踪程序生成Golf，Snowgoon，Chess图像．每幅图像由几千个球体，三角形，柱体和锥体组成．有两个照明光源，屏幕象素大小是640*640．光线跟踪程序曾在上海超级计算机中心的神威Ⅰ号超级计算机（384个CPU，48G内存，1.28T磁盘存储容量）上做过实验，分别在单机环境，没有DJmix的分布式环境，及有DJmix的分布式环境三种情况下运行，实验结果见图6．在实验中，由于图形并不复杂，且机器运行状态良好，故网络传输开销可忽略不计．为比较原始程序与例化后程序的性能，加速比定义为例化程序执行时间原始程序执行时间加速比＝图6 实验结果 分别运行原始光线跟踪程序，和有DJmix 的光线跟踪程序，获得的性能加速比见图6，其中最大加速比为5.23．应用DJmix 时，程序运行时间明显降低，生成的图形越复杂，得到的加速比越大．DJmix 对光线跟踪算法的加速是明显的．5 结束语保持软件系统灵活性，并提高软件性能是软件设计开发的重要标准．Web 服务优化是目前的热门研究话题．Sato ，Saito 和Mitsui 提出利用并行服务调用来优化合成Web 服务[12]．Mark Nottingham 提出基于中介的Web 服务优化[13]．利用部分计值优化Web 服务，不仅可改善性能，还可从理论上证明例化过程的正确性．DJmix 是第一个应用于Web 服务的分布式部分计值器．结合DJmix 运行分布式光线跟踪应用，获得了一定的性能加速比．对其它应用程序的例化正在研究实施中．本文介绍了一种新的、用部分计值技术例化Web 服务的方法．结合DJmix 的实现机制及对字节码的例化，提出并讨论了基于DJmix 架构优化Web 服务的方法．进一步地给出了运行光线跟踪应用的实验效果．网络服务和部分计值相结合是崭新的研究领域，本文利用DJmix 实现了应用服务的例化．更进一步，还可将DJmix 应用于例化网络系统服务的注册、监控、SOAP-RMI 和数据访问等，以改善和优化整个网络服务的性能．参 考 文 献[1] W3C.Simple Object Access Protocol, 2000[2] W3C.Web Services Description Language 1.1, 2001[3] C. Consel and O. Danvy “Tutorial notes on partial evaluation”, in ACM Symposium on Principles of Program-ming Languages, Pages 493-501,1993.[4] D. Neil, C. Jones, K. Gomard and P. Sestoft, “Partial Evaluation and Automatic Program Generation”, Prentice Hall, 1993.[5] M. Sperber, H. Klaeren and P. Thiemann “Distributed Partial Evaluation”.[6] C. Consel, L. Hornof, R. Marlet, G . Muller and S. Thibault, “Tempo: Specializing Systems Applications andBeyond”, ACM Computing Survey, V ol. 30, Issue 3es(September 1998).[7] H. Masuhara and A. Yonezawa, “Generating optimized residual code in run-time specialization”, Proceedings of International Colloquium on Partial Evaluation and Program Transformation, 1999, pp. 215-225.[8] A.S. Glassner(Ed.), “An Introduction to Raytracing”, Academic Press, 1989.[9] Y. Hou, “the Design and Implementation of Jmix-a Java Partial Evaluator”, graduate thesis, SJTU, China, Sep-tember 2002.[10] P. H. Andersen, “Partial Evaluation Applied to Ray Tracing”, Software Engineering in Scientific Computing, pp. 78-85, DIKU report D-289(1996).[11] K. Asai “Can partial evaluation improve the performance of ray tracing” Natural Science Report, V ol.53, No.1 (2002).[12] N.Sato, S.Saito and K.Mitsui “Optimizing Composite Web Services through Parallelization of Service Invoca-tions” in Proceeding of the Sixth International Enterprise Distributed Object Computing Conference, 2002. [13] Mark Nottingham “Optimizing Web Services with Intermediaries”.Specializing Web Services with Distributed Partial Evaluation MAO Hong-Yan, HUANG Lin-Peng, and SUN Yong-Qiang(Department of Computer Science and Engineering，Shanghai Jiaotong University，Shanghai 200030)AbstractCurrently middleware and modularity technologies are the prevalent trends adopted to comply with the changing characteristics of distributed computing environments, however, which gives rise to some inefficiency for generic design. In order to alleviate the conflict between generic design and efficient implementation, this paper proposes a new approach based on distributed partial evalua-tion to optimize Web services. It presents the architecture and realization mechanism of distributed partial evaluator, DJmix, which is built on the byte code specialization and Web services environ-ments. By means of a case study about the ray tracing service, the performance results show that partial evaluation is effective to improve the performance and flexibility of Web services.Key words：Partial Evaluation; Specialization; Web Services; Byte code作者简介毛宏燕女，1977年生，博士生，主要研究方向为分布式计算，程序语言．黄林鹏男，1964年生，博士，教授，博士生导师，主要研究方向为程序语言，并行计算，人工智能．孙永强男，1931年生，教授，博士生导师，主要研究方向为并行理论，函数式语言．。