Compiling Smalltalk-80to a RISCrWilliam R.Bush,A.Dain Samples,David Ungar*,Paul N.Hilfinge Computer Science DivisioneDepartment of Electrical Engineering and Computer Scienc University of California,Berkeley CA 94720E *Computer Systems Laboratorylectrical Engineering Department5P Stanford University,Stanford CA 9430roceedings of the Second International Conference onsArchitectural Support for Programming Languages and Operating System (ASPLOS II)7p October 198ages 112-116d l The Smalltalk On A RISC project at U.C.Berkeley proves that a high-level object-oriente anguage can attain high performance on a modified reduced instruction set architecture.The sin-b gle most important optimization is the removal of a layer of interpretation,compiling the ytecoded virtual machine instructions into low-level,register-based,hardware instructions.This -p paper describes the compiler and how it was affected by SOAR architectural features.The com iler generates code of reasonable density and speed.Because of Smalltalk-80’s semantics,rela-t t tively few optimizations are possible,but hardware and software mechanisms at runtime offse hese limitations.Register allocation for an architecture with register windows comprises the ;s major task of the compiler.Performance analysis suggests that SOAR is not simple enough everal hardware features could be efficiently replaced by instruction sequences constructed by the 1compiler..IntroductionThe goal of the Smalltalk On A RISC (SOAR)project at U.C.Berkeley was to produce a a high-performance execution engine for the Smalltalk-80language.The heart of the effort is 1-t Berkeley RISC processor extended to support Smalltalk.The processor was designed in conjunc ion with the runtime system,which together have yielded substantial performance improvements f over conventional Smalltalk-80implementations.An extensive performance evaluation can be ound in Ungar’s dissertation [1];results with an instruction-level simulator using large bench-marks indicate that the SOAR system could run Smalltalk roughly 2.5times as fast as a Motorola.1Smalltalk-80is a trademark of Xerox Corporatione w 68010with a similar cycle time,or about the same speed as the Xerox Dorado high-performanc orkstation.One reason for the SOAR system’s speed is its compilation of Smalltalk.It has been p o estimated that compiling Smalltalk to the SOAR instruction set produces a factor of two speedu ver conventional interpreted systems,making compilation the single most important Smalltalk e d speedup technique of the SOAR system.This paper describes the SOAR compiler.We hav etailed the processor [2]and runtime system [3]elsewhere,and will assume some familiarity with g a these,as well as with the Smalltalk-80language.An overview of the SOAR project,emphasizin rchitectural results,is available [4].2.The Nature of the CompilerThe Smalltalk-80language is defined operationally in terms of a virtual machine that executes i stack-based instructions called bytecodes.The Smalltalk-80programming environment is a binary mage that runs on the virtual machine.This virtual machine can be inefficient if naively imple-a mented.It is commonly realized as a bytecode interpreter,which requires special hardware (such s that possessed by the Dorado)to avoid interposing a layer of overhead between the virtual machine and the native machine.An alternative is to compile bytecodes to native machine instructions,an approach success-t fully taken by Deutsch and Schiffman [5].The Deutsch and Schiffman system dynamically ranslates procedures (called methods in Smalltalk)as needed,keeping a cache of native-code f methods and flushing the least-recently-used ones.The SOAR system takes this approach a step urther and compiles all methods from bytecodes into SOAR instructions,discarding the bytecodes.t Where caching is done for space efficiency,compiling everything simplifies and speeds up the sys-em for a moderate cost in space.We considered compiling Smalltalk directly to SOAR,avoiding bytecodes entirely,but we e l did not take this path for two reasons.First,the virtual machine is the semantic definition of th anguage.This implies that a correct bytecode compiler and correct runtime system functions,con-i stitute a correct Smalltalk implementation.Second,the standard virtual image is a bytecode-based mage;to produce a SOAR-based native image those bytecodes must be translated to SOAR d a instructions.Rather than develop two separate compilers,one for taking bytecodes to SOAR an nother for compiling Smalltalk to SOAR,we implemented one bytecode compiler with two imple-i mentations:a C version for image conversion,and a Smalltalk version for use with the converted mage.We have discussed image conversion in a previous paper [3].T 2he basic task of the compiler is to translate stack-oriented bytecodes into RISC-style loads,l stores,and other register-based instructions.It does this by assigning Smalltalk variables and stack ocations to registers and memory locations,and then simulating at compile time the bytecode stack c s operations on a symbolic stack,converting the operations into SOAR instructions.The symboli tack is used to remember value sources and operations;when a value destination is encountered e a the code to load,compute,and store the value is generated.If the Smalltalk variables A and B ar ssigned to registers,for example,a push of A and a pop-and-store into B is translated into a B register-to-register move;the symbolic stack is used to remember the source A until the destination is encountered.Debugging Smalltalk programs in a converted image,in which the standard virtual image debugger does not w 2ork,is addressed in Lee’s report [6].In a more complete example,Figure 1presents the contents of the symbolic stack and the e a resulting emitted code as the four bytecodes to evaluate ‘C A +B’are scanned in order.Th ngle brackets indicate the bytecode being scanned and the current top of the symbolic stack.The e s variables are local variables assigned to registers.After the ‘+’operator has been scanned th tack contains one entry,the result of the operation.The operation is symbolic and so are its argu-ments.The Smalltalk bytecodes perform the same compilation function as any stack-based intermedi-l d ate language such as,for example,UCODE [7].Bytecodes are unlike UCODE in that,as we wil iscuss later,they restrict the compiler writer,particularly in implementing optimizations that s would result in code motion or that require type information to perform.For example,common ubexpression elimination is exceptionally difficult to do in Smalltalk.f S Given the restrictive semantics of the Smalltalk bytecodes and the simple architecture o OAR,the compiler falls or stands on its success in mapping Smalltalk variables to registers and memory.>BYTECODES SYMBOLIC STACKEMITTED CODE pushVar:A >1:A-s pushVar:B 2:-end:+popIntoVar:C-------------------------------------------------------------------->pushVar:A 1:ApushVar:B >2:Bp send:+opIntoVar:C--------------------------------------------------------------------p pushVar:A >1:plus A BushVar:B 2:->send:+popIntoVar:C-------------------------------------------------------------------Cp pushVar:A 1:-add rA,rB,r ushVar:B 2:->send:+popIntoVar:C Figure 1:An Example of Bytecode-Based Compilation3.SOAR Register WindowsOne feature of the Berkeley RISC architectures is a register file of overlapping register win-p dows,each window corresponding to a procedure activation frame.The windows are allocated on rocedure call in a stack discipline,using the registers in the window overlap to pass parameters.t The advantage of register windows is fast procedure call and return,avoiding the saving and res-oring of registers.Tests with benchmarks indicate that SOAR Smalltalk would be 46%slower without them.3It is crucial that the size of these register windows be chosen wisely.If a method requires p more storage than can fit in a window,the extra values are spilled to memory,slowing down the rocedure call and the method’s execution as well as increasing its code size.If windows are too .O small,an excessive number of methods will spill,degrading the performance of the whole system n the other hand,if windows are too large,registers will be wasted and fewer windows can be accommodated on the processor chip.For SOAR,the goal was to have 90%to 95%of all activation frames fit in SOAR windows.b Preliminary studies [9]indicated that a window size of 16registers with 8-register overlap was est.The SOAR windows are smaller than those of other RISC designs such as RISC II,which l i has 32,because Smalltalk methods are correspondingly smaller than procedures in more traditiona mperative-style languages.An alternative would have been to use variable-size windows at some expense in hardware -d (see,for example,Katevenis’dissertation [10]).For SOAR,we concluded that variable-size win ows would not result in significant enough improvement to offset the additional hardware com-plexity.The SOAR hardware divides each window into two identical sets of 8registers,a high set u (15-8)and a low set (7-0).Each set contains 6general purpose registers and 2dedicated registers sed for return addresses (15and 7)and return values (14and 6).e h The currently executing method receives its parameters and stores its local variables in th igh register set.It sets up parameters for any methods that it calls in the low set.Unlike other b RISC designs,the SOAR architecture has no registers dedicated solely to local use --all are shared etween two activation records.This allows the compiler flexibility in register allocation;registers t m can be used for arguments or local values depending on what is appropriate.Temporaries tha ust persist through calls to other methods (‘retained’temporaries)are put in free high registers.r ‘Transitory’temporaries (those whose life spans do not cross procedure calls,such as intermediate esults from compiler-generated expressions)can be put in the lows.Figure 2presents this categorization pictorially.Allocating variables and temporaries to registers is complicated by the fact that it is possible .W to write a Smalltalk method whose variables and temporaries will not all fit in a register window hen more registers are required than are available,spilling is necessary.There are two rules used s t to determine what and when to spill to memory.The first rule of assignment by category specifie hat entire categories of variables are spilled --if not all of the arguments fit in the registers,for m example,all are spilled.The second rule of permanent assignment means that a variable cannot be oved once it has been allocated a location --if,for example,a local variable has been put in aAll results quoted in this paper are found in either Ungar’s dissertation [4]or Bush’s report [8],unless stated oth-3.erwise------------------------------------------15Receiver and Return Address14------------------------------------------13Arguments and Locals------------------------------------------Retained Temporaries8------------------------------------------7Callee and Return Address6------------------------------------------5Callee Arguments------------------------------------------Transitory Temporaries------------------------------------------Figure 2:Register Allocation in a Register Windowr egister,it will not later be spilled to make room for a temporary.Neither of these rules result in a m minimal register usage or minimal memory traffic,but they are reasonable and simple.Since ajor goal of the SOAR architectural design was to minimize spills at a reasonable cost,their infrequent occurrence justified an easily modifiable,simple spilling strategy.The details of our allocation and assignment strategy are straightforward.The compiler -t assigns up to four arguments and locals to a method’s high registers,and the remaining high regis ers are used for retained temporaries.If there are more arguments than will fit in four registers,w all arguments are put in memory.If the arguments will fit in four registers,but the local variables ill not fit with the arguments,all of the locals are stored in memory.Transitory temporaries can t i be stored in the lows.Retained temporaries are stored in registers if any are available at that poin n the computation,and in memory otherwise.A nice benefit of the above rules is that for most Smalltalk methods,code can be generated r r in one pass over the bytecodes by making some initial assumptions about the method’s registe equirements.If the assumptions turn out to be false,a second pass can be made with the new information.Only 9%of all methods in the Smalltalk-80system require the second pass.4n s Spills can be implemented in one of two ways.First,space can be allocated from a commo pill pool,or a separate spill object can be allocated for each activation frame that spills.The e former has complications for garbage collection and processes,and the latter eats up a register in ach spilling frame.Both techniques have been tried in SOAR;neither has shown itself to be 4clearly superior over the other..The SOAR Architecture Simplifies the Compilerr S Register windows and spills complicate the compiler;SOAR architectural support fo malltalk has in the main simplified it.An important architectural feature allows the compiler to y b generate standard arithmetic and comparison instructions in spite of the fact that the operations ma e on non-integer objects.Since Smalltalk is polymorphic and variable types are not known at compile time,it is never d safe to generate integer instructions without runtime type checking.The virtual machine requires a ynamic method lookup on each operator,including ‘+’.Implementing this lookup naively is very -m expensive.Studies at Apple [11]and Hewlett-Packard [12]have shown that in fact most arith etic operations in Smalltalk involve only integers.SOAR takes advantage of this fact by assum-i ing that all simple arithmetic operations (plus,minus,comparisons,etc.)will be performed only on ntegers.The compiler thus treats all such operations as if they were on integers,and generates o integer code.If,say,an add instruction is initiated on two objects,and one or both of them turn ut to be non-integers,the hardware will trap and transfer to a handler that will look up the correct t method for the intended operation.When the execution of the looked-up method is complete,the rap handler will return to the instruction immediately following the one that caused the trap.,b It would not be difficult for the compiler to generate code to test explicitly for integer tags ut it would slow down system performance by an estimated 26%and would increase image size by 15%.The tag mechanism is also used to provide hardware assistance for garbage collection,thus -i further simplifying the task of code generation.SOAR uses a generation scavenging scheme,divid ng memory into regions of old and new objects,and uses generation tags on pointers to detect h when pointers to new objects are stored into old ones.The tag check is performed in the ardware,and a trap handler records the necessary information if a trap is taken.However,bench-t t mark results indicate that tagged stores are so rare that the compiler could in fact generate explici ests and only slow the system about 1%and expand the image 2%.d t The compiler also takes advantage of hardware that maps registers to memory addresses,an hus allows pointers to registers.Since a Smalltalk program can access any object in memory,and .U activation records are just another kind of object,it is necessary to handle references to them nfortunately,some activation records exist as on-chip register windows.The pointer to register -e feature permits the compiler to ignore complications that would otherwise be caused by overt refer nces to activation records.Once again,however,it turns out that checking for pointers toThe Smalltalk and the C versions of the compiler differ in this regard:the C version effectively makes two passes o 4ver each method.However,speed was not as critical for the C version as for the Smalltalk version.activation records is not as severe a problem as it was initially feared to be.The instances requir-o ing such a check do not occur often,and Ungar concluded that the feature could be removed with nly a 3%performance penalty.r5.Bytecode Compilation Restricts the Compile Both language and pragmatic considerations limited the optimizations we could perform.a S First,Smalltalk is a polymorphic language.That is,the same ‘A+B’expression within malltalk method could on one instantiation add two integers and on the next concatenate two s i strings.In the latter case it is not true that ‘A+B’equals ‘B+A’.Furthermore,which method i nvoked is,by definition,a function of the leftmost operand (‘A’in our example).Together these facts preclude almost all expression evaluation optimization.Second,the fact that activation frames are full-fledged Smalltalk objects requires a relatively s s straightforward mapping between bytecode frames and compiled ones,eliminating optimization uch as method integration.Third,our pragmatic goal was to bring up a working Smalltalk-80image for the SOAR pro-d cessor.This made us fundamentally conservative in our approach to the language.Correctness,as efined by the bytecodes and the image,was more important than efficiency.Because of this we f a were loath to change the image (including the standard Smalltalk-80compiler)or take advantage o mbiguities in the language specification.We were not in the normal position of a compiler writer.b There is one optimization that has been employed successfully by Deutsch and Schiffman and y the SOAR system.Although the language permits polymorphic expressions,the fact of the t c matter is that 96%of the time the method invoked by a particular message send operation does no hange.Thus,for example,if ‘A+B’added complex numbers the last time it was evaluated,it is s o highly likely that it will be used to add complex numbers the next time it is ing thi bservation we cache the last method called.When it is called again,we merely check that the f t type of the leftmost operand this call matches the type of the leftmost operand from the last call.I hey do not match the standard method lookup mechanism is re-invoked.Ungar estimated that 6removing this caching strategy would slow down our system by 33%..ResultsThree types of performance measurements were made with the SOAR compiler:compilation speed,code expansion,and register window utilization.Since the SOAR compiler is an extra stage added to the bytecode compiler,it can only slow s r compilation down.However,on a Dorado (equivalent in performance to SOAR)the compiler i easonably fast both objectively and subjectively.Results from compiling the entire Smalltalk-80l c image of 4770methods indicate that it adds a mean time of 50milliseconds to a method’s tota ompilation time.This lengthens compilation by 70%.Subjectively,the compiler does not intrude l c on system use since it is usually invoked interactively on one method at a time.A mean tota ompilation time of about 120milliseconds per method does not noticeably affect response time.-j One of the virtues of bytecodes is their compactness.A major concern at the start of the pro ect was an anticipated explosion in method size that could result from moving to four-byte word--t sized instructions.Preliminary estimates indicated potential expansion of up to 1000%[13].For unately,observed expansion with the actual implementation is considerably lower.For the5d e Smalltalk-80image the expansion factor for methods is 3.78--one byte of bytecode metho xpands to an average 3.78SOAR bytes.These expansion results compare favorably to the expan--l sion factor of 5.03reported by Deutsch and Schiffman [5]for their comparable translator with in ine caching.To put these averages in perspective,in a 1,240,000byte Smalltalk-80image there are .F 155,025bytes of virtual machine bytecodes,which expand to 573,593bytes of SOAR instructions or current workstations with memories in the four to eight megabyte range,this increase of roughly 420,000bytes for SOAR instructions is acceptable.A major goal of the SOAR design was to have over 90%of the methods fit all their storage l m into registers.Static results from the compiler support the current window size.Only 9%of al ethods spill.Examining total register requirements also supports the 16register window.These c a numbers are expressed in terms of the number of high registers used,because all method-specifillocation is done in the high registers.6#of high registersmethods using no more than that #4229%65%%1892699%%32100e t Dynamic results from benchmarks confirm the static results,and more emphatically endors he chosen window size.Dynamically,less than 3%of methods spill.The above figures show -t that if we increased the register window set size to 32from 8,all methods in the Smalltalk-80sys em would fit in register windows,and spilling could effectively be eliminated.However,since f r less than 3%of all calls require spilling,even if we could (somehow)keep the same number o egister windows on the chip,increasing the window size from 16to 64registers would not be a cost effective use of chip area,given current VLSI technology.Static results also indicate that the current spill rules are reasonable.categorymean size maximum size arguments0.83139r local variables0.681etained temporaries0.82108total registers2.322spill area 0.4522e a Argument,local variable,and temporary demands are small on the average,but in the worst cas ll exceed the window size.The method lengths include literals and method headers.65These numbers include the 2special receiver and return address registers.Note that the percentage of methods i that spill is higher than the percentage of methods that require more than 8registers because the registers are divided up nto two separate regions which are not treated as one continuous space.7.ConclusionsThe Smalltalk-80language and its bytecode representation restrict the conventional optimiza--m tions available to the SOAR compiler.Nevertheless,the compiler generates efficient code,pri arily due to register windows,integer tags and traps,and in-line method caches.Experience with -d the compiler has verified the architectural design decision to use a 16-register fully overlapped win ow.Several features supported by the SOAR hardware could easily be performed by the compiler 8at marginal increased time and space costs..AcknowledgmentsThis project was sponsored by Defense Advance Research Projects Agency (DoD)ARPA -0Order No.3803,monitored by Naval Electronic System Command under Contract No.N00034-K 251.It was also sponsored by Defense Advance Research Projects Agency (DoD)Arpa Order .D No.4871,monitored by Naval Electronic Systems Command under contract N00039-84-C-0089ain Samples is supported in part by an AT&T Bell Laboratories Scholarship.Glenn Krasner and Xerox PARC provided support in the development of the compiler.References;[1]‘The Design and Evaluation of a High Performance Smalltalk System’;David Michael Ungar U.C.Berkeley Computer Science Division Report UCB /CSD 86/287,March 1986..[2]‘Architecture of SOAR:Smalltalk on a RISC’;David Ungar,Ricki Blau,Peter Foley,A Dain Samples,David Patterson;11th Annual International Symposium on Computer Architec-[ture,Ann Arbor,Michigan,June 1984.3]‘SOAR:Smalltalk Without Bytecodes’; A.Dain Samples,David Ungar,Paul Hilfinger;,N CACM Object-Oriented Programming Systems,Languages and Applications Proceedings ovember 1986,pp 107-118.[4]‘What Price Smalltalk?’;David Ungar and David Patterson;IEEE Computer ,January 1987,[pp 67-74.5]‘Efficient Implementation of the Smalltalk-80System’;L.Peter Deutsch,Allan M.,p Schiffman;11th ACM Symposium on Principles of Programming Languages ,January 1984p 297-302.[6]‘The Design of a Debugger for SOAR’;Peter K.Lee;Master’s Report,U.C.Berkeley,1984.-[7]‘Machine Independent Pascal Code Optimization’;D.R.Perkins and R.L.Sites;CCC SIG PLAN 14,8,August 1979,pp 201-207.[8]‘Smalltalk-80to SOAR Code’;William R.Bush;U.C.Berkeley Computer Science Division [Report UCB /CSD 86/297,June 1986.9]‘Register Windows for SOAR’;John Blakken;Smalltalk On A RISC --Proceedings of [CS929R ,April 1983,pp 126-140.10]‘Reduced Instruction Set Computer Architectures for VLSI’;Manolis G.H.Katevenis;U.C.Berkeley Computer Science Division Report UCB /CSD 83/141,October 1983.n [11]‘An MC68000-Based Smalltalk-80System’;Richard Meyers and David Casseres;iSmalltalk-80Bits of History,Words of Advice;Glenn Krasner,Editor;Addison-Wesley,1983,[pp175-187.12]‘The Analysis of the Smalltalk-80System at Hewlett-Packard’;Joseph R.Falcone;in, pSmalltalk-80Bits of History,Words of Advice;Glenn Krasner,Editor;Addison-Wesley,1983 p207-237.[13]‘Implementing a Smalltalk Compiler’;Wayne Citrin,Carl Ponder;Smalltalk On A RISC--Proceedings of CS929R,April1983,pp167-185.。
高级编程语言的一般流程English.The General Flow of High-Level Programming Languages.High-level programming languages are designed to be easier for humans to read and write than low-level languages, such as assembly language or machine code. They are also more portable, meaning that they can be used on different types of computers with little or no modification.The general flow of a high-level programming languageis as follows:1. The programmer writes a program in the high-level language.2. The program is compiled into an intermediate representation, such as bytecode or assembly code.3. The intermediate representation is executed by an interpreter or a virtual machine.Compilation.Compilation is the process of translating a high-level program into an intermediate representation. This is doneby a compiler, which is a special program that understands the syntax of the high-level language. The compiler checks the program for errors and, if there are no errors, generates the intermediate representation.Interpretation.Interpretation is the process of executing an intermediate representation. This is done by an interpreter, which is a special program that understands theintermediate representation. The interpreter reads the intermediate representation and executes it one instruction at a time.Virtual Machines.A virtual machine is a software program that simulates a computer. This allows the intermediate representation to be executed on any computer that has the virtual machine installed. Virtual machines are often used to run programs on different types of computers, such as running Windows programs on a Mac.The Advantages of High-Level Programming Languages.High-level programming languages offer a number of advantages over low-level languages, including:Ease of use: High-level languages are easier to read and write than low-level languages. This is because they use a more natural syntax that is closer to human language.Portability: High-level languages are more portable than low-level languages. This is because they are not tied to a specific type of computer architecture.Maintainability: High-level languages are easier tomaintain than low-level languages. This is because they are more modular and structured.The Disadvantages of High-Level Programming Languages.High-level programming languages also have some disadvantages, including:Performance: High-level languages are typically slower than low-level languages. This is because the intermediate representation must be interpreted or executed by a virtual machine.Memory usage: High-level languages typically use more memory than low-level languages. This is because they store more information in the intermediate representation.Choosing a High-Level Programming Language.The choice of a high-level programming language depends on the specific needs of the project. Some factors to consider include:The platform: The language must be able to run on the target platform.The performance requirements: The language must be able to meet the performance requirements of the project.The development team: The language must be familiar to the development team.中文回答：高级编程语言的一般流程。
收稿日期:2006206213 基金项目:国家“八六三”计划项目(2002AA 104310)资助;教育部新世纪优秀人才计划项目(N CET 20520829)资助;国家自然科学基金项目(60273085,90612004)资助. 作者简介:徐玉文,男,1982年生,硕士研究生,研究方向为网格计算;桂小林,男,1966年生,教授,博士生导师,研究方向为网格计算技术和网络安全技术;吕继树,男,1983年生,硕士研究生,研究方向为网格计算.SGPL :一种面向服务组合的结构化网格编程语言徐玉文,桂小林,吕继树(西安交通大学计算机科学与技术系,陕西西安710049)E 2m ail :xuyuw en @stu .xjtu .edu .cn摘 要:现有的网格编程语言与环境可以分为两大类,一类是对现有语言扩充,引入网格特征,一类是使用工作流技术,支持服务定制.论文提出了一种面向服务组合的结构化网格编程语言SGPL ,并在此基础上,设计了一个可视化的网格编程环境V GPE .V GPE 结合了现行网格编程环境的优点,具有结构化、可定制性和可视化等特点.论文对SGPL 的主要语言要素(活动、转移和关联等)和主要结构体(顺序、条件、循环、并行和宏等)进行了定义,论述了SGPL 的中间代码生成规则,给出了分支结构和宏结构的解析算法.最后论文在校园网格环境下,实现了SGPL 和V GPE ,并通过实验验证了SGPL 可以一次性定制和组合复杂的或重复的网格服务请求,简化了服务过程,提高了工作效率.关键词:编程语言;服务组合;可视化;结构化;网格计算中图分类号:T P 393,T P 312 文献标识码:A 文章编号:100021220(2007)0921624206SGPL :a Structured Gr id Programm i ng Language for Aggrega ti ng Gr id Serv icesXU Yu 2w en ,GU I X iao 2lin ,LV J i 2shu(D ep a rt m en t of Co mp u ter S cience and T echnology ,X i ′an J iaotong U n iversity ,X i ′an 710049,Ch ina )Abstract :Existing grid p rogramm ing language and environm ent can be classified into tw o catego ries :one is to extend existing language and introduce grid features ;the o ther is to use w o rkflow techno logy and suppo rt services custom izati on .T h is paper introduces a structured grid p rogramm ing language (nam ed as SGPL )to custom ize and aggregate Grid Services .A nd based on the SGPL ,a visual grid p rogramm ing environm ent (V GPE )is established .T he V GPE com bines the advantages of existing grid p rogramm ing environm ent ,fo r examp le it bears features of structure ,custom izati on and visualizati on .T h is article firstly defines the elem ents (such as activity ,transfer and conjuncti on etc .)and structures (such as sequence ,branch ,circle ,parallel and m acro etc .)of the SGPL ,and then exp lains the rule of inter m ediate code generati on ,and gives parse algo rithm s of branch structure and m acro .F inally ,in the campus grid environm ent ,the SGPL and the V GPE are i m p lem ented ,and an experi m ent is done to test the SGPL on the V GPE .T he result of the experi m ent demonstrates that to compo se comp lex o r repetitive grid service the SGPL just need one 2ti m e custom izati on ,it is obvi ous that the SGPL si m p lifies service p rocess and i m p roves efficien 2cy .Key words :p rogramm ing language ;service compo siti on ;visualizati on ;structure ;grid compute1 引 言网格的本质就是为用户提供快捷、方便的高性能计算与信息共享服务.随着服务需求的增加,用户的服务请求变得更加复杂,用户需要一种更加直观、更加灵活的方式来使用网格服务.尽管O GSA [1]提供了网格服务发布和使用方法,给出了服务组合的描述,但并没有实现有效、友好的网格编程环境和使用界面工具.因此,有必要研究一种网格编程语言或环境,支持用户复杂的服务请求、服务定制与组合,实现网格系统的"按需透明服务".目前,支持网格服务的编程环境包括两种类型.一种是在传统编程语言基础之上,引入网格特征.例如,GridR PC [2]是对传统的远程过程调用(R PC )的扩展;M P I CH 2G 2[3]是对并行编程环境M P I CH 的扩展;J 2Grid [4]是对J ini 的扩展.使用这些编程环境需要了解网格环境的结构甚至调度细节,缺乏通用性,而且不能满足O GSA 框架下对网格服务组合的要求.另一种是以工作流的方式来实现网格编程.例如,Grid 2F low [5]是一个基于代理的网格工作流系统,它把网格工作流分为全局工作流和本地工作流,便于用户定制服务但缺少结构化特征;GridA nt [6]是一个客户端网格工作流定制和管理工具,便于用户定制处理流程和管理运行过程,但缺少服务组合和结构化编程能力;GSFL [7]是O GSA 框架下的网格服务工作流语言,方便用户定制和操作工作流程,缺少结构性、可维护性和可视化.另外GS M L [8]采用了标记语言来实现网格编程,降低了网格编程的难度,但缺乏一般编程语言的结构化表达能力.小型微型计算机系统Journal of Ch inese Computer System s 2007年9月第9期V o l 128N o .92007 论文基于传统编程语言的结构化特征,设计了一种支持网格服务组合的结构化网格编程语言(SGPL),并利用工作流技术,设计了支持SGPL的可视化网格编程环境(V GPE). SGPL的设计目标是为用户提供具有传统编程语言结构化特点、工作流可定制化特征的网格编程语言;V GPE是利用SG2 PL实现的一种网格编程图形化工作环境,它通过拖拽方式进行网格编程,并能实时地返回网格程序执行信息.本文第2节介绍了SGPL的定义,包括SGPL语言元素和SGPL的语法规则.第3节介绍为了实现SGPL程序的编译与运行,进行了中间代码设计和结构解析算法设计.第4节论文首先介绍了V GPE的实现,然后在校园网格环境下对SGPL和V GPE进行了实验和分析.第5节进行概括和总结,并阐述了下一步将要深入研究的方向.2 SGPL的定义SGPL除了支持通常的顺序、条件、循环结构之外,还引入了一些适应网格环境的新的元素和结构,例如并行结构和归并结构方便定制网格环境下的并行网格服务调用,而宏的引入使得整个网格程序成为一个树型分层结构,方便了用户进行复杂的和大规模的编程.下面首先对SGPL的语言元素进行定义,然后给出SGPL的编程的语法规则.2.1 SGPLSGPL的语言元素主要包括活动、转移、结构和关联等,下面给出这些元素的具体定义.定义1.在SGPL中,活动a(activity)对应网格服务,一个活动就是一次网格服务请求.在网格系统中间件中网格服务被抽象成类似传统编程语言A P I的编程接口,活动通过调用编程接口来实现网格服务调用.一个活动a可以用一个三元组进行定义:a=<Id,A p i N am e,P araL ist>其中,Id∈N(N是自然数)是活动的标识号,一个网格程序中,每个活动有唯一的标识号;A p i N am e是活动被请求网格服务对应的编程接口名,P araL ist是编程接口的入口参数与出口参数表,而且相邻后一个活动的P araL ist包含相邻前一个活动产生的结果.定义2.转移t=<S t,Con>是一个二元组,说明程序实现转移时的条件集合.其中,启动条件S t是检查上个活动是否正确完成的一组条件,转移条件Con是判断上一个活动结束后程序的流向的一组条件;要使t成立,要求启动条件S t和转移条件Con同时满足;当转移t1和t2的启动条件相同,转移条件互补时,称t1,t2互补,用t1=!t2表示.定义3.在SGPL中,结构s(structure)包括一个或多个转移,用于控制程序的流程,以实现程序的各种结构方式.结构s可以用一个三元组进行定义:s=<Id,Typ e,T>其中,Id∈N(N是自然数)是结构的标识号,一个网格程序中,每个结构有唯一的标识号;Typ e为结构类型,用一个字符串表示;T是转移t的集合.定义4.序偶(l,m)是由两个元素l,m组成,其中l为m 的前继,m为l的后继.定义5.关联关系函数f(a1,t,a2),表示两个活动的关系.当t为真时,活动a1执行完成后,将a1的结果作为a2的入口参数,然后继续执行活动a2.两个关联函数间,我们定义了如下三种运算:(1)f(a11,t1,a12)+f(a21,t2,a22).运算式成立的条件为a12=a21且t1和t2都成立,表示依次执行a11,a12,a22,这中间a11的结果会传递给a12,而a12的结果将传递给a22.(2)f(a11,t1,a12)∧f(a21,t2,a22)运算式成立的条件有两种,・当a11=a21,a12≠a22且t1和t2都成立,则表示a11执行完后,将a11的结果同时传递给a12和a22,然后同时执行a12和a22;・当a11≠a21,a12=a22且t1和t2都成立,则表示a11,a21都执行完后,将a11和a21的结果都传递给a22,并且执行a22.(3)f(a11,t1,a12)∨f(a21,t2,a22).该运算式成立的条件也有两种,・当a11=a21,a12≠a22且t1或t2成立,表示a11执行完后,如果t1成立则将a11的结果传递给a12,并执行a12;如果t2成立则将a11的结果传递给a22,并执行a22;・当a11≠a21,a12=a22且t1或t2成立,表示当t1成立时执行a11,并将结果传递给a22,然后执行a22;当t2成立时执行a21,并将结果传递给a22,然后执行a22.定义6.关联关系表达式e的定义如下:(1)f(a1,t,a2)是关联关系表达式;(2)e+f(a1,t,a2),e∧f(a1,t,a2),e∨f(a1,t,a2)也是关联关系表达式.(3){e}″也是关联关系表达式,表示e重复n次.即e+e+…+en.在SGPL中,共有8类结构,用关联关系表达式来描述结构S和其前后继活动的关联关系.在定义(1)～(6)中,A表示结构S前后继活动集合.(1)顺序结构:顺序结构所连接的两个活动具有顺序运行的关系.用a1表示S的前继活动,a2表示S的后继活动,则有,A={a1,a2},s=<Id,seq,{t}>,e=f(a1,t,a2)(2)并行结构:由并行结构所指向的两个后继活动可以同时得到运行.用a1表示S的前继活动,a2和a3表示S的后继活动,则有,A={a1,a2,a3},s=<Id,P aral,{t}>,e=f(a1,t,a2)∧f(a1,t,a3)(3)条件结构:根据对转移条件的判断,程序在两个后继活动中选择一个后继活动运行.用a1表示S的前继活动,a2和a3表示S的后继活动,则有,A={a1,a2,a3},s=<Id,If,{t}>,e=f(a1,t,a2)∨f(a1,!t,a3)(4)循环结构:循环结构中t1用于判断是否进入循环,t252619期 徐玉文等:SGPL:一种面向服务组合的结构化网格编程语言 为循环条件,控制循环次数n,当t2不满足时,则跳出循环.用a1表示S的前继活动,a2表示循环体,a3表示跳出循环后执行的活动,则有,A={a1,a2,a3},s=<Id,W h ile,{t1,t2}>,e1=f(a2,t2,a2)∨f(a2,!t2,a3)e=f(a1,t1,a2)+{e}n-1∨f(a1,!t1,a3)(5)选择结构:选择结构包括两个转移,他们的启动条件不同,而且选择结构的两个前继活动形成了一种"或"关系.用a1和a2表示S的前继活动,a3表示S的后继活动,则有, A={a1,a2,a3},s=<Id,O r,{t1,t2}>,e=f(a1,t1,a3)∨f(a2,t2,a3)(6)归并结构:归并结构包括两个转移,他们的启动条件也不同,但归并结构的两个前继活动构成了一种"与"关系.用a1和a2表示S的前继活动,a3表示S的后继活动,则有, A={a1,a2,a3},s=<Id,A nd,{t1,t2}>,e=f(a1,t1,a3)∧f(a2,t2,a3)另外,还有两个特殊的结构S tart=<Id,S tart,{t}>和E nd=<Id,E nd,{t}>.Start结构用来标示SGPL程序的开始,它包含了一组条件,表示了SGPL程序的运行对网格环境的要求;End结构用来标示SGPL程序的结束,它包含一组程序终止条件,表示了SGPL程序成功结束所需要满足的条件.定义7.宏m acro包括一组有关联关系的活动和结构,是一个小型的SGPL程序.宏可以像活动一样成为结构的前继和后继,并允许嵌套定义.一个宏是满足如下条件的四元组:m acro=<A,M,S,e>.这里,(1)A≠(2)A∩M∩S=(3)F<((A∪M)×S)∪(S×(A∪M))(其中"×"为笛卡尔积)(4)DOM(F)∪COD(F)=A∪S∪M其中,A是宏的活动集合,M是宏的宏集合,S是宏的结构集合,e是宏的关联关系表达式,由S中所有结构对应的关联关系表达式相加得到.F是宏的序偶集合.其中DOM(F)={x ϖy:(x,y)∈F}称为F关系中的前继,COD(F)={y ϖx:(x,y)∈F},称为F关系中的后继.在SGPL程序中,宏可以嵌套宏,所以整个SGPL程序结构可以看作是一个树型结构,其中树根可以命名为起始宏.2.2 SGPL的语法规则根据2.1节的SGPL语言的定义,以及程序设计方便性的考虑,一个宏必须满足如下语法规则:(1)ϖ!S tart使得S tart∈S,ϖ!E nd,使得E nd∈S且A ≠ ;(2)如果c∈A∪M,那么Πc1∈A∪M,(c1,c),(c,c1)不成立;如果s∈S,那么Πs1∈S,(s1,s),(s,s1)不成立;(3)在具有两个指向的结构中,至多只能有1个为NULL活动;(4)条件结构的两个后继分支不能在归并结构处会合;(5)并行结构的两个后继分支不能在选择结构处会合;(6)A中活动个数最多为M A X a,M中宏个数最多为M A X m.3 SGPL语言的解析算法SGPL是一种编译性语言,当SGPL程序定制完成后,可以一次性生成中间代码,中间代码交付网格中间件进行解释执行.下面首先讨论SGPL程序的中间代码的设计方法,然后给出SGPL的两种典型结构的解析算法,其它结构的解析算法与此类似.3.1 中间代码设计中间代码采用表结构进行设计.根据不同的功能需求, SGPL中间代码共包括如下四个表:用户变量表、服务调用表、条件表和执行语句表.用户变量表中保存了用户自定义变量;服务调用表中按顺序保存了SGPL程序中所有活动对应的网格服务调用;条件表中按顺序保存了SGPL程序中每个结构中所包含的启动条件和转移条件;执行语句表是中间代码的核心部分,用来保存SGPL程序运行时的语句,这些语句构成了SGPL程序的整个运行流程.SGPL的一条程序语句生成的执行语句表可以用一个四元组<type,3index,j m p1,j m p2>表示.其中:(1)"type"字段用来表示语句的类型,分为三大类,分别是服务调用,条件跳转和程序结束.具体含义如表1所示.表1 执行语句"type"字段的含义T able1 M eanings of"type"in the executable sentence type值含义1服务调用2相邻语句为并行的服务调用3条件跳转4相邻语句为或关系的条件跳转5强制跳转6程序结束(2)"3index"标明了被调用的服务在服务调用表中或条件在条件表中的位置.(3)"j m p1"和"j m p2"只对条件跳转语句有效,它们分别指示了条件为真和条件为假时应当跳转到的语句序号.此外,条件跳转语句序号为0表示继续下一条指令;条件跳转语句序号为21表示程序出错,需退出.例如,语句<1,1,0,0>表明这是一个服务调用语句,它调用的服务在服务调用表中的索引为1;语句<3,1,0,21>表明这是一个条件跳转语句,其包含的条件在条件表中的索引为1,如果条件为真,则继续下一条语句的执行,否则程序出错,中断执行.3.2 典型结构的解析算法结构的解析算法是SGPL编译器的核心部分.我们设计了SGPL语言中的全部结构的解析算法.下面介绍其中宏和分支这两个典型结构的解析算法(注:我们将宏看成一种特殊结构).3.2.1 宏的解析算法6261 小 型 微 型 计 算 机 系 统 2007年在SGPL程序中,因为宏可以嵌套宏,所以整个SGPL程序结构可以看作是一个树型结构,这棵数的根可以称作为起始宏.在每个宏中,活动的解析会先于执行语句的生成,而不同的宏里的活动可能有相同的编号,所以需要实现一种机制,用来保证解析算法在生成执行语句时能够正确找到该语句所指向的活动.本文采用如下方法来保证活动编号的唯一性: 在SGPL程序中,共有三类编号—程序编号,相对编号和绝对编号.程序编号是当活动和宏初始化时,程序为活动和宏分配的编号,分别用a id和m id表示,而且a id取值从1到M A X a,m id取值从M A X a+1到M A X a+M A X m+1.相对编号是指在同一个宏中,活动相对于其他活动、宏相对于其他宏的编号,分别用k和j表示.绝对编号是SGPL程序展开后程序为活动和宏分配的编号,也是活动和宏的在整个网格程序中的唯一标志号.这三类编号的关系如下:k=a id,j=m id-M A X a(1)第i层的第j个宏中的相对编号为k的活动的绝对编号计算式为,activ ity id=M A X i-1mM A X m-1M A X a+(j-1)M A X a+k(2)第i层的第j个宏中的相对编号为j的宏的绝对编号计算式为,m acro id=M A X i-1m-1M A X m-1M A X m+(j-1)M A X m+j(3)基于上述宏编号和宏内活动编号的计算方法,下面给出宏的解释算法:第1步.依次解析宏中A的每个活动.利用宏所处的层级i,宏的程序编号m id和这些活动的程序编号a id,用公式1和2计算出这些活动的绝对编号activ ity id,并以这些绝对编号作为这些活动的唯一标记构造活动对象,然后将这些活动对象按顺序添加到服务调用表中.第2步.调用Start结构的解析算法解析宏中的Start元素.然后获得其后继节点的程序编号,如果这个编号小于M A X a,则该节点为活动,根据该活动的绝对编号activ ity id从服务调用表中获取该活动的索引a1-index,并产生四元式< 1,a1-index,0,0>;否则该节点应为宏,以该宏的程序编号为参数调用宏解析程序解析该宏;第3步.根据第一个活动的后继结构的Id,在GPL程序中取出该结构的定义;第4步.如果该结构为End结构,转第5步;否则按照该结构的解析算法解析该结构,并获取出下一个相邻的结构的Id,在GPL程序中取出该结构定义,转第4步;第5步:调用End结构的解析算法解析End结构,如果含有终止条件,则将该条件加入到条件表中,取得在条件表中的索引c-index,产生四元式<3,c-index,0,21>;否则转第6步;第6步:指定宏中最后一个活动的后继结构为宏的后继结构,然后继续解析宏的后继结构.3.2.2 条件结构的解析算法第1步:获取t的S t,如果启动条件S t不为空,则将该启动条件加入到条件表中,然后取得该条件在条件表中的索引c1-index,产生四元式<3,c1-index,0,21>;第2步:获取t的转移条件Con,如果这个转移条件不为空,则将它加入到条件表中,取得在条件表中的索引c2-in2 dex,因为后续语句还没有产生,此时尚不能确定当转移条件失败时转向的位置,所以只能在后续语句生成之后回填“j m p2”字段.故产生四元式<3,c2-index,0,->,将该四元式的地址记为back-fill1;第3步:获取t中后继节点的程序编号id1.如果id1< M A X a,则该节点为活动,用公式3计算出该活动的绝对编号activ ity id,并根据activ ity id从服务调用表中获取该活动的索引a1-index,并产生四元式<1,a1-index,0,0>;否则该节点应为宏,以该宏的程序编号id1为参数调用宏解析程序解析该宏;第4步:因为t执行完毕后应该跳过!t的执行,所以必须产生一条强制跳转语句,强制跳转语句不需要条件,所以产生四元式<5,-,-,->,因为后续语句还没有产生,强制跳转的转向未知,只能在后续语句生成之后回填“j m p2”字段,故将该四元式的地址记为back-fill2;第5步:此时可以确定下一条语句就是t中转移条件不满足时的跳转地址,所以将下一条语句的地址回填到back-fill1的“j m p2”字段中去;第6步:获取!t中后继节点的程序编号id2.如果该id2< M A X a,则该节点为活动,用公式3计算出该活动的绝对编号activ ity id,并根据activ ity id从服务调用表中获取该活动的索引a2-index,产生四元式<1,a2-index,0,0>;否则该节点为宏,以该id2为参数调用宏解析程序解析该宏.第7步:此时可以确定下一条语句就是强制跳转语句back-fill2的跳转地址,所以将下一条语句的地址回填到back-fill2的“j m p2”字段中去.4 SGPL的应用和测试为了应用SGPL,论文在校园网格中间件Grid W ader的基础上,建立了一个可视化网格编程环境(V GPE).V GPE系统为用户提供了友好方便的可视化编程界面,它使用了可视化组件来帮助用户定制SGPL程序,还可以实时地反馈SG2 PL程序运行信息给用户,并且允许用户上传和下载文件.4.1 VGPE的系统结构V GPE系统包括V GPE客户端和V GPE运行环境两部分.V GPE客户端完成和用户的交互,用户通过V GPE客户端来定制SGPL程序,监控运行状况和上传下载文件.V GPE 运行环境的主要目标是实现SGPL源程序的编译和运行.它包括SGPL编译器、SGPL执行器,以及和用户、网格的交互组件.V GPE系统的总体结构图如图1(见下页)所示.4.1.1 V GPE客户端V GPE客户端参考了基于Java的图形化工作流编辑器Jaw e,利用了图形编程工具包JGraph[6],并且依照SGPL语72619期 徐玉文等:SGPL:一种面向服务组合的结构化网格编程语言 言的定义和规则来实现的.可视化网格编程接口定义了一个edito r .这个edito r 将创建一个graph ,这个graph 基于图论和java 的Sw ing .基于图论是说activity ,structure ,B lock 这些对应SGPL 元素的图1 V GPE 的结构图F ig .1 V GPE arch itecturegraph 组件对应于图论中的节点,边将这些节点连接,同时为了符合SGPL 语法,我们对每类节点的入度和出度做了严格的限制;基于Sw ing 是说graph 及其graph 中的各种组件的实现采用了Sw ing 的M V C 模型,用户在edito r 中创建各个graph 组件时,模型中会创建相应的GPL 元素对象,用户对graph 组件的操作也将会转化为相应SGPL 元素对象的操作.4.1.2 SGPL 编译器SGPL 编译器功能是通过一系列的编译算法将用户编辑的SGPL 程序转换为可执行中间代码.因为SGPL 程序使用了X M L 文档格式,所以SGPL 编译器使用了A pache X M L 项目的Xerces 解析器.4.1.3 SGPL 执行器SGPL 执行器的主要任务是执行SGPL 编译器产生的中间代码.根据执行语句表中的四元式,SGPL 执行器对条件表,变量表或服务调用表进行调用.SGPL 执行器并不直接执行服务调用表中的网格服务,而是通过调用在网格交互的组件中的编程接口去请求网格服务.4.2 基于VGPE 的SGPL 应用测试我们已经将SGPL 集成到了V GPE 内.下面通过V GPE 来求解大矩阵乘法问题,以此来测试SGPL 的可行性和有效性.4.2.1 实验过程m atrix 和readm atrix 是两个运行在Grid W ader 上的服务,其中m atrix 完成矩阵相乘功能,其输入为两个相乘矩阵,输出为结果矩阵result .R eadm atrix 能读出并显示一个矩阵中的数据.另外Grid W ader 上还有一系列的变量操作服务,用来完成整型数据的加减乘除.现在用户需要在Grid W ader 平台上使用m atrix 和read 2m atrix 计算并显示如下矩阵相乘的结果:D ×E 3×F ,其中,D 、E 、F 都是100×100的矩阵.在SGPL 程序执行过程中,相邻前一个活动会自动将产生的结果作为编程接口的入口参数传递给相邻下一个活动.所以虽然m atrix 产生的结果都用re 2sult 表示,但可以保证这个result 是前一次m atrix 运算的输出.SGPL 程序的定制分析包括活动分析和结构分析.(1)活动分析:将D ×E 3×F 完全和m atrix 对应,需要调用4次m atrix 服务.第一次调用m atrix 来完成运算D ×E ,它的输入参数为D 和E ,用活动m atrix 1表示这次服务调用;然后是两次result ×E 操作,用活动m atrix 2和m atrix 3来表示,这两次服务的输入参数同为result 和E ;最后一次是完成re 2sult ×F ,得到的结果保存在result 中,用活动m atrix 4来完成.最后通过调用服务readm atrix 来显示最终的结果,用活动readm atrix 来表示这次服务的调用.(2)结构分析:将上述服务组合成SGPL 程序既可以用顺序结构将上述活动依次联结,也可以通过比较复杂的结构连接,这个试验用循环结构和顺序结构来连接这些活动.在活动分析中,m atrix 2和m atrix 3相邻且输入参数相同,可以将这部分替换为一个循环结构,用其中循环体包括一个表示re 2sult XE 的活动和一个表示循环次数减一的活动,前一个活动用m atrix 5表示,后一个活动用varsub 表示.将m atrix 5和varsub 用顺序结构连接,就组成了循环体.为了使程序结构更加清晰,可以将这个循环体放入到宏m acro 中.基于上述分析,我们在V GPE 可视化窗口内最终定制的SGPL 程序结构如图2所示.图2 SGPL 程序结构的可视化定制图F ig .2 Custom ed SGPL p rogram这个SGPL 程序产生的中间代码如图3(见下页)所示.这些中间代码分为四部分,用户变量表有一个自定义变量,用来控制循环次数;服务调用表有5个活动对应的服务调用;条件表包含所有结构中的条件;中间代码表的语句描述了程序的执行过程.下图的中间代码表示的程序执行的过程如下:首先是<1,0,0,0>它调用的服务在服务调用表中的索引为0,执行D ×E ,输出结果为result ;然后是<3,0,0,21>,它调用的条件在条件表中的索引为0,如果条件为真,则执行下一条语句,否则程序出错,中断执行;<3,1,0,7>它调用的条件在条件表中的索引为1,根据变量var 的大小,判断是否要继续循环;<1,3,0,0>调用索引为3的服务,执行result ×E ;<3,2,0,21>判断result ×E 是否执行完;<1,4,0,0>将变量var 减1;<3,3,2,21>,如果result 存在,则循环执行索引为2的语句,否则程序出错,中断执行,循环两次后输出中间结果result =D ×E 3;<1,1,0,0>执行result ×F ;<3,4,0,21>判断result 是否存在;<1,2,0,0>将result 显示出来;<6,0,0,0>程序结束.最后得到的计算结果和采用W eb 接口计算得到的结果一致.8261 小 型 微 型 计 算 机 系 统 2007年4.2.2 实验结果分析从上述实验可以看到,在可视化网格编程环境上,用户可以方便地编写出结构清晰的网格应用程序,并且得到正确的计算结果.the var-list is:0:(var,2)the ap i-list is:0:(1,1,mp irun2np5mp i m atrix D E)1:(2,1,mp irun2np5mp i m atrix result F)2:(3,1,M P I readm atrix result)3:(101,1,mp irun2np5mp i m atrix result E)4:(102,2,var21)the conditi on-list is:0:(if result exists)1:(if var>0)2:(if result exists)3:(if result exists)4:(if result exists)the p rog contains11sentences:0:(1,0,0,0)1:(3,0,0,21)2:(3,1,0,7)3:(1,3,0,0)4:(3,2,0,21)5:(1,4,0,0)6:(3,3,2,21)7:(1,1,0,0)8:(3,4,0,21)9:(1,2,0,0)10:(6,0,0,0)图3 中间代码图F ig.3 M iddle code根据上述问题描述,用户如果使用W eb接口来完成上述工作,则需要进行4次输入文件提交,还需要手工处理中间结果.而使用SGPL和V GPE系统来求解上述问题,因为采用服务组合的方法,只需一次就能得到执行结果.同时在上述试验的执行过程中,V GPE系统比直接使用W eb接口多了解析SGPL程序的过程,但是SGPL的解析时间为47m s,比起1968m s的总计算时间,解析时间只占了总消耗时间的2%,所以解析代价可以忽略不计.5 结 论结构化网格编程语言SGPL是一种支持网格服务组合的网格编程解决方案,它通过对网格服务的抽象实现了网格高层和网格中间件的分离,SGPL的中间代码通过网格中间件所提供的编程接口,可以方便快捷地在网格计算系统上运行. SGPL提供了丰富的语法元素和结构来增强表达能力,方便了用户按需编程,同时SGPL采用了特殊结构宏,方便了用户进行复杂的和大规模的编程.应用实验表明,采用集成SGPL 的V GPE系统可以较大地降低网格应用的难度,提高了网格编程的灵活性,方便非专业用户编写网格应用程序.目前SG2 PL只对网格中提供的网格服务进行了抽象,服务安全性依赖于网格平台本身,需要进一步考虑网格服务定制与组合过程中的安全机制问题.References:[1]Fo ster I,Kessel m an C,N ick J,et al.T he physi o logy of thegrid:an open grid services arch itecture fo r distributed system sintegrati on[EB OL].A vailable:h ttp: www.globus.o rg al2 liance publicati ons papers ogsa.pdf,2002.[2]Keith Seymour,H idemo to N akada,Sato sh i M atsuoka,et al.O verview of GridR PC:a remo te p rocedure call A P I fo r gridcomputing[A].L ecture N o tes in Computer Science,Grid Com2 puting2GR I D2002[C],H eidelberg,Ger m any:Sp ringer2V er2lag,2002,2536,2742278.[3]Karonis N,Toonen B,Fo ster I.M P I CH2G2:a gridenabled i m2p lem entati on of the m essage passing interface[J].Journal ofParallel and D istributed Computing,2003,63(5):5512563.[4]Ish ikaw a Y,M atsuda M,Kudoh T,et al.T he design of a la2tency2aw are mp i comm unicati on library[C OL].In:P roceed2 ings of S W O PP03,A vailable:h ttp: www.gridmp i.o rg publi2 cati ons s wopp032gridmp i.pdf,2003.[5]M athe J,Kuntner K,Po ta S,et al.T he use of jini techno logyin distributed and grid m ulti m edia system s[C].In:P roc.M IPRO2003,H yper m edia and Grid System s,1482151.[6]Cao J,Jarvis S A,Saini S,et al.Gridflow:wo rkflow m anage2m ent fo r grid computing[C].In:P roceedings of the3rd IEEEA CM Internati onal Sympo sium on C luster Computing and theGrid(CCGR I D′03),2003,1982205.[7]G.var L aszew sk i,Am in K,H ategan M,et al.GridA nt:aclient2contro llable grid wo rkflow system[C OL].In:P roc.ofthe37th H aw aii Int’l Conf.on System Sciences(H I CSS237),A vailable:h ttp: www.m ～grego r papers von2L aszew sk i22gridant2h ics.pdf,2004,70210c.[8]K rishnan S,W agstrom P,G.von L aszew sk i.GSFL:a wo rk2flow fram ewo rk fo r grid services[R OL].In:P rep rint ANL M CS2P98020802,A rgonne N ati onal L abo rato ry,9700S.CassA venue,A rgonne,I L60439,U.S.A.,A vailable:h ttp:www2unix.globus.o rg cog papers gsfl2paper.pdf,2002.[9]L i B ing2chen,Xu Zh i2w ei.I mp lem entati on issues of the GS M Lgrid p rogramm ing language[J].Journal of Computer R esearchand D evelopm ent,2003,40(12):171521719.[10]Gui X iao2lin,Q ian D e2pei,H e Ge.D esign and i m p lem entati onof a campus2w ide[J].Journal of Computer R esearch and D evel2 opm ent,2002,39(7):8882894.附中文参考文献:[9]李丙辰,徐志伟.GS M L网格编程语言的一种实现方法[J].计算机研究与发展,2003,40(12):171521719.[10]桂小林,钱德沛,何 戈.基于校园网络的元计算实验系统W AD E的设计与实现[J].计算机研究与发展,2002,39(7):8882 894.92619期 徐玉文等:SGPL:一种面向服务组合的结构化网格编程语言 。
