论文研究 在构件的多个实现间动态选择的算法.pdf

为了提高构件在处理多种类型请求时的效率，构件可以有多个不同的内部实现，每一个实现都是为一种特定类型的请求而优化的。提出了一种在构件的多个实现间动态选择的算法，算法尽可能地为每一种类型的请求挑选最优的实现，同时又尽量避免在不同的实现之间进行切换，从而使构件在处理一个请求序列时所花费的总开销尽可能少。第9期朱广蔚等:在构件的多个实现间动态选择的算法21int switch cost[ IMPL TYPE NUM][ IMPL TYPE NUMToptimized_impl- serial[j+1]-. optimized- impl- serailint process req cost[ ReQ TY PE NUMI[ IMPL TY PE NUM]:# leine REQ- NUM10/当前请求队列中请求的个数int req_ serial[REQ.NUM];/请求序列证明nt impl serial[REQ.NUM];//实现序列前提:req- serial[ j=req-era[j+1]1-…req- serial[k]int optimizd. impl serial[REQ_NUM];//取伏的实现序列zaiE: optimized_ impl- serial- timized_impl_ serial jint total_cost (+1=... optimized__ k]int sum =0optimized impl- serial[ j-1]为处理子请求序列时构件的∥/计算用某一个特定的实现处理请求时所花费的廾钔当前实现方法类型。for(int i =0;i REQ- NUM; i ++)tint req =req_serial[ i]情况1: optimized- impl_scrial l j-1]=req_ serially,当nt impl impl- serial[ i]前的实现方法的类型和即将要处理的从第j个请求到第k个sum sum process req cost[ req][ impl ]i请求的类型怡好相符合,即当前的实现方法对于接下来要处理∥/计算在不同的实现间切换所花费的川诮的请求来说是优化的。在些种情况下,如果在实现间进行切for(int i=0:i REQ NUM- 1; i++)i换首先增加了切换的开销,而且切换后的实现对于接下来要int current impl impl serial[ i]处理的请求来说不是优化的因此构件的当前实现应该保持不int next_impl impl- serial[ i +1//如果 current_ impl==net_iml, switch,Co丈则为0变sum sum switch costi current impl[ next impl]lw 2: optimized impl- serial [j-1]!-req- serial[ j]当前的实现方法的类型和即将要处理的从第j个请求到第kreturn sum个请求的类型不符合,即当前的实现方法对于接下来要处理的int min_cos;//记录当前找到的最好的实现序列的代价请求来说不是优化的。在此种情况下,如果子请求序列比较void process_req(irti)//处玛第j个请求短,实现应该保持不变尽管子请求序列中的每一个请求都是for (int j=0;j< IMPL_TYPE_ NUM; j++)t用非优化的方法来处理的,但此时进行切换带来的代价要超过impl serial[ i] =j用优化的方法和非优化的方法处理请求的差异;如果子请求序//尝试采用第j个实现去处理第ⅰ个请求列比较长,构件当前的实现则立刻切换为对于接下来要处理的if(i reQ- NUM-1)process_req(ⅰ+1);//处理下一个请求请求来说是优化的类型,之所以要立刻切换的原因是保证子请else t求序列中所有的请求都是用优化的方法来处理的current_cast tota_cost()我们以一个例子来说明如何利用该性质减小搜索的规模,if( current- cost min-cost)t假如数据访问构件的请求队列中有如下四个请求 Readread/找到了一个更好的实现序列min costWrite write。未优化的算法要在16(2的4次方)种可能的实/把∏前找到的最好的实现序列记录下来现序列中搜索,利用该性质实际上只要在如下的四种可能的for( intk 0;k req- NuM-1; k++)实现序列中搜索即可optimized impl serial[ k] impl seraill k](1) Sub scribe Su escribe normal normal(代表对第(1)和第(2)个Rcad请求采用订阋阅方式对第(3)和第(4)个 Write请求采用正常方式,以此类推);(2)Sub scribe Su scribe Su bscribe Subscribere.9md[ REQ_NUM]可以看作是算法的输入,当以0为(3)Normal Normal Subscribe Subscribe参数调用 prucess_reg(iti)的时候,算法的输出即最优实现序(4) Normal Normal Normal Norma lo列就会被保存在 opti mized- impl-serial[ REQ- NUM]中经过优化后的算法思路如下:①把长度为M的请求序列4算法的优化划分成N个子序列,每个子序列中的请求的类型全部都是相等的。②由请求序列的性质可以知道在最优的实现序列中,通过以上的分析可知当请求序列的长度是n的时候若必然是采用了相同的实现方法来处理子请求序列中的每个请要找到最优的实现序列则必须在 REQ TYPE- NUM的n次求,因此,优化的算法搜索的时候分N个步骤进行处理第方的状态空间中进行搜索。当n很大时寻找最优的实现序列个子请求序列时尝试用 REQ TYPE NUM种不同的实现方法所花费的开销可能会远远超过处理请求所花费的开销因此算(对子序列中的请求采用相同的实现方法来处理),处理第二法在没有优化的前提下有较大的局限性。对此问题的进一步个子请求序列时也尝试用 REQ- TYPE_NUM种不同的实现方研究,我们发现通过使用请求队列的如下性质可以有效地减小法等处理第N个子请求序列时也尝试用 REQ TYPE_NUM搜索的规模。种不同的实现方法。经过优化后.算法的时间复杂度由O性质在长度为n的请求序列{req- serial[ii从0到n-(2M)降低为O(2)。当构件经常接受连续类型的请求时,N}中,如果从第j个请求到第k个请求的请求类型都相同即会显著地小于M从而大幅度地提高了算法的效率。O当一个req- serial[j]= req-scrialL j+1]=… rcq- serial k],则在最构件工作负载很高的时候,构件的请求队列中的请求数目会很优实现序列中(假设已经求出来了)对从第j个请求到第k个大把此长度为M的请求序列划分成N个子序列后N仍然很请求必定釆用了同样的实现方法,即吧 p timized-inpl- serial[ jI大。针对这种情况算法同时对N设定一个最高(下转第24页)24计算机应用研究2004年同的函数或者模块屮,变量的名称可能是一样的;dype是用来标志使该变量的炎型,随着软件工程的发可能山现一些5结论新的使用形式,我们都可以对它进行扩充,只要给新的形式指在本文中,笔者为模板库中的程序流程提出了一个新的存定新的值就可以了。储结构,该结构使得程序的流程更加容易表示,更易于生成测为了方便变量的观测、分析,我们给每个变量的链表都加试用例。此外还对程序变量的观测和分析提出了一种结构体上一个头节点,它的具体形式如卜使得对程序变量的跟踪更加简单、方便。程序流程和变量链表struct variantFathernode已经在软件内建自测试"系统中得到了很好的运用,为该系e[30]该变量的名称统的进一步完善迈出了坚实的一步。模板的内容是整个系统int vBegnLineNurberi/变量首次起竹用所在的行的关键,它对整个系统的测试策略的产生,测试报告的可靠性int VEndLineNumber//该变量歧后起作用所在的行等诸多方面都将产生较大的影晌。相信随着本课题研究的不struct variant Node* first VariantNode断深入,模板的内容在整个系统中将发挥更加重要的作用。当//指向变量所衣链表的首节点然本文还有问题没有解决,如程序流程中一些其他格式的处需要说明的是:结构体中的变量 eginLineNun和变理、程序流程的优化都有待进一步的探索。EndLineNumber是为了得到变量实际起作用的范围。因为不参考文献同的模块或者函数中可能出现相同的变量名称,就是在模块或[1 shun l, dared c. or Fault simulation and basic Introduc两数不身变量实际起作用的范围不一定是模块或者函数的结tion to Test Generation Test Generation for vlSI Chips [m. new宋,而应该是变量最后出现的位置,所以我们引进了这两个变York: IEF F Computer Society Press, 1998.6.3-150量。从而我们就可以得到程序文件中每个变量的链表,这样就[2]凌良合徐拾义.基于软件内建自测试的模板和基准程序设计可以对其进行跟踪和监测。通过对程序文件的分析后,我们可[J.同济大学学报,2002,(10):1159-1163以得到每个变量的链表,如图3所示[3 reuer M A, Friendman A D. TEST/ 80: a Proposal for an Advanced变量1变星2Automatic Test Generation System[C. Proc. IEFE Autotestconl982.364-371…[4 uth P. A Nine- valued Circuit Model for Test Pattern Generation ofⅣ12n2Combination Digital Circuits[J. IEEE Transaction on Computers,1976,C-25(5):630-636图3跟踪程序变量的表作者简介邇过对程序变量链表的跟踪,可以得到所要跟踪变量的某王宗青(1978-),男.硕士研究生,研究领域为软件测试与可靠性分析个状态,与我们预期的结果进行比较,判断该变量是甭正常徐拾义(1942-),教授,研究领域为计算机容错测试。(上接第21页)的间值X,当N大于X时,则需要把这N个子序2001-04-26;2003-09-04列划分为NX个子序列,此时每个子序列的长度都小于X然3]1 BM Corporation. BM S Perspective on the State of Information Tech后对每个子序列再求出对应的最优实现序列,最后把分段求出nology[ebol.http:!/www-l.ibm.comindustries/government的最优实现序列合在一起。需要指出的是,尽管对于局部来doc/content/resource/thought/278606109 htm1, 2000-03-28/2003说,算法对每一个子请求序列都求出了对应的最优实现序列,09-24但对于整体来说此时求出的实现序列只是近似最优。[4 Jeffrey O Kephart, David M Chess. The Vision of Autonomic Compu-ting[ IF EE Computer, 2003, (36): 1-185总结[5IbMcOrporationAnatomyofAutonomicServerComponents[j.com-puteRC22637(W0202,(12):1-38.本文所提出的在构件的多个实现间动态选择的算法有[6 O Wolfson, s Jajodia. An Algorithm for Dynamic Data Distribution定的实用性具有一定的实用价值,但是,自主计算和自主构件[C]. Proceedin gs of the 2nd work shop on the Management of repli-技术的研究才刚刚起步,理论研究还很不完善,还有很长的路cated Data (WMRD-ID, Monterey, CA, 1992. 60-65要走不过我们相信自主计算技术将会是下一代计算系统的[7]王映辉分布构件模型技术比较研究[J计算机应用研究,200新纪元。0(7):3-9参考文献作者简介11 M Yellin. Compet itive algorithms for the dynamic selection of朱广蔚(1978-),男,硕土研究生主要研究方向为软件方法学自主计ComponentImplementationsEb/ol].http://www.researchibm算:谭建(1979-),男,硕士研究生,主要研究方向为软件方法学、自主计om/ journal sj/ 421/yellin. pdf, 2002-8-30/2003-09-04算;杨献春(1960-),男教授主要研究方向为自主计算、计算机系统结2] IBM Corp oration. An Architectural Blueprint for Au tonomic Comp utin构;许满武(1944-),男.教授,博士生导师,主要研究方向为软件方法[EB/OL].www-3.ibm.cum/ autonomic/r/ downloads/ blueprint/,学、新型程序设计。