正在加载图片...
第12期 郝卫东等：基于运行时间权矩阵的网格服务匹配问题的优化解 ,1285 因此，网格作业和网格服务的完备匹配是：甲完 匹配策略下网格作业的总完成时间分布曲线、 成C作业，乙完成B作业，丙完成D作业，丁完成A 由图1可见，最优策略的编号为22，其总运行 作业，此时总完成时间为： 时间为260ms,与基于权矩阵的服务匹配优化算法 的结果相同；而最差策略的编号是10，其总运行时 min220je=w14十02十031十w43= =1=1 间为470ms,不同的服务匹配策略之间的总运行时 40+40+80+100=260ms 间最大相差210ms·在穷举算法下各种策略的平均 多个作业并发运行时整个任务的完成时间为完 总运行时间为371.25ms,本文给出的优化算法与之 成D作业的时间100ms 相比使服务匹配系统性能改善42.78%. 事实上，在本实例中存在最多C1C3C2C1=24 当网格作业和网格服务的数量增加时，穷举算 种不同的匹配策略，图1是采用穷举搜索法时不同 法是低效的，而且可能产生组合爆炸。因此，考虑与 500 智能搜索策略一爬山法一相比较，并以运行时 400 间为爬山法的启发条件，计算从W(1,1)=D11开 300 200 始，此时运行时间为30ms,此后以运行时间增长最 100 小为目标进行搜索，计算结果如图2所示，此时的 优化策略是甲完成A作业，乙完成B作业，丙完成 10 1316 19 22 匹配策略编号 C作业，丁完成D作业，总运行时间为280ms·与本 文给出的优化算法相比，爬山法给出的是次优解，而 图1不同匹配策略运行结果分析 Fig.1 Result of different matchmaking strategies 最优解与之相比使服务匹配系统性能改善7,69% 1.1) 30+40-70m5 30+160=190m5s 30+130-160ms 2,2) 23) 2,4) 70+140-210m5 70+130=200m5 160+130-290ms 160+120-280ms 33) 3.4) 3,4) 3.2) 210+70-280ms 200+100=300ms290+80=370m5 280+70-350m5 肌4,4) 肌4,3) 4,2) 4,4) 图2爬山法的搜索结果 Fig.2 Result of the mountain climbing method 为了在网格系统上实现本文给出的优化算法， 数关系，因此上述优化算法可进一步推广并应用于 采用MATLAB COM Builder将程序编译为单独的 降低请求网格资源的经济成本，这对网格服务匹配 ActiveX对象，并由VB.Net语言编写程序调用该对 系统的商业化运营有潜在促进价值， 象.其硬件环境为：曙光天潮TC4000L超级计算机 系统作为网格计算集群系统，曙光天阔R220A服务 参考文献 器作为集群节点服务器，曙光天阔R220XP作为网 [1]Foster I.Kesselman C.The Grid 2:Blueprint for a New Com- 格集群管理服务器， puting Infrastructure.2nd ed.San Fransisco:Morgan Kaufmann Publishers Inc,2004:1 4结论 [2]Czajkowski K,Foster I,Karonis N,et al.A resource manage- ment architecture for metacomputing systems//4th workshop on 本文通过在网格服务模型中引入匹配器，使用 Job Scheduling Strategies for Parallel Processing.Heidelberg: 代表作业运行时间的权矩阵，给出了网格作业一网 Springer-Verlag Publishers Ine.1998:62 格服务匹配的优化解，基于图论证明了服务匹配存 [3]Czajkowski K.Foster I.Kesselman C.Co-allocation services for 在的充分必要条件，经仿真研究表明，与其他算法 computational Grids//8th IEEE International Symposium on High 相比，该优化算法可使服务匹配系统的性能取得较 Performance Distributed Computing.Los Alamitos:IEEE Com- puter Society Press.1999:553 为明显的改善 [4]Raman R.Livny M.Solomon M.Matchmaking:distributed re 考虑到作业完成时间与完成作业的费用存在函 source management for high throughput computing7th IEEE因此网格作业和网格服务的完备匹配是：甲完 成 C 作业乙完成 B 作业丙完成 D 作业丁完成 A 作业．此时总完成时间为： min ∑ t i＝1 ∑ t j＝1 wijeij＝ w14＋ w22＋ w31＋ w43＝ 40＋40＋80＋100＝260ms． 多个作业并发运行时整个任务的完成时间为完 成 D 作业的时间100ms． 事实上在本实例中存在最多 C 1 4C 1 3C 1 2C 1 1＝24 种不同的匹配策略图1是采用穷举搜索法时不同 图1 不同匹配策略运行结果分析 Fig．1 Result of different matchmaking strategies 匹配策略下网格作业的总完成时间分布曲线． 由图1可见最优策略的编号为22其总运行 时间为260ms与基于权矩阵的服务匹配优化算法 的结果相同；而最差策略的编号是10其总运行时 间为470ms不同的服务匹配策略之间的总运行时 间最大相差210ms．在穷举算法下各种策略的平均 总运行时间为371∙25ms本文给出的优化算法与之 相比使服务匹配系统性能改善42∙78％． 当网格作业和网格服务的数量增加时穷举算 法是低效的而且可能产生组合爆炸．因此考虑与 智能搜索策略———爬山法———相比较并以运行时 间为爬山法的启发条件计算从 W （11）＝ w11开 始此时运行时间为30ms此后以运行时间增长最 小为目标进行搜索计算结果如图2所示．此时的 优化策略是甲完成 A 作业乙完成 B 作业丙完成 C 作业丁完成 D 作业总运行时间为280ms．与本 文给出的优化算法相比爬山法给出的是次优解而 最优解与之相比使服务匹配系统性能改善7∙69％． 图2 爬山法的搜索结果 Fig．2 Result of the mountain climbing method 为了在网格系统上实现本文给出的优化算法 采用 MATLAB COM Builder 将程序编译为单独的 ActiveX 对象并由 VB．Net 语言编写程序调用该对 象．其硬件环境为：曙光天潮 TC4000L 超级计算机 系统作为网格计算集群系统曙光天阔 R220A 服务 器作为集群节点服务器曙光天阔 R220XP 作为网 格集群管理服务器． 4 结论 本文通过在网格服务模型中引入匹配器使用 代表作业运行时间的权矩阵给出了网格作业—网 格服务匹配的优化解基于图论证明了服务匹配存 在的充分必要条件．经仿真研究表明与其他算法 相比该优化算法可使服务匹配系统的性能取得较 为明显的改善． 考虑到作业完成时间与完成作业的费用存在函 数关系因此上述优化算法可进一步推广并应用于 降低请求网格资源的经济成本这对网格服务匹配 系统的商业化运营有潜在促进价值． 参 考 文 献 ［1］ Foster IKesselman C．The Grid2：Blueprint for a New Computing Infrastructure．2nd ed．San Fransisco：Morgan Kaufmann Publishers Inc2004：1 ［2］ Czajkowski KFoster IKaronis Net al．A resource management architecture for metacomputing systems∥4th workshop on Job Scheduling Strategies for Parallel Processing．Heidelberg： Springer-Verlag Publishers Inc1998：62 ［3］ Czajkowski KFoster IKesselman C．Co-allocation services for computational Grids∥8th IEEE International Symposium on High Performance Distributed Computing．Los Alamitos：IEEE Computer Society Press1999：553 ［4］ Raman RLivny MSolomon M．Matchmaking：distributed resource management for high throughput computing∥7th IEEE 第12期 郝卫东等： 基于运行时间权矩阵的网格服务匹配问题的优化解 ·1285·