并行算法中基于移动Agent的数据集均衡策略的研究
|
摘要
解决并行算法中的数据分配问题，目前采用的主要方法是在各个计算结点上平均分配数据。如果并行系统是同构的，采用这种方法设计的算法具有很高的运行效率。但是在异构系统下，由于各个计算结点的性能不同，平均分配数据集的方法就有可能导致系统的负载失衡。
本文提出了在并行算法中使用的基于移动agent的数据集负载均衡策略：基于移动Agent综合处理速度的数据集均衡策略DBSMAV(DataSet Balancing Strategy Based on Mobile Agent Velocity)和基于移动Agent调度的数据集均衡策略DBSMAS(DataSet Balancing Strategy Based on Mobile Agent Scheduling)。目前对如此细粒度的负载均衡问题所作的研究工作还很少，本文的工作借鉴了NASA所建立的IPG(Information Power Grid)网格上面的粗粒度负载均衡算法PLUM(Parallel Load balancing for Unstructured Meshes)、SBN(Symmetric Broadcast Network)、MinEX(Minimal Extra overhead)，也参考了接收者发起的分布式启发性算法，并结合了移动Agent的思想。
理论和实验证明，移动Agent综合处理速度MAV(Mobile Agent Velocity)在计算结点的内存足够大时能够比较准确地反映计算结点的计算能力。DBSMAV策略按照各个计算结点的MAV分配数据集，较好地克服了异构系统中平均分配数据集造成的失衡。为了解决由于内存的影响而导致的负载失衡现象，我们提出了DBSMAS策略。DBSMAS策略按照重负载优先调度和整体上减少系统执行时间的原则，命令一部分移动Agent携带数据集进行迁移，使系统重新达到了平衡状态。
实验证明，我们所研究的均衡策略，利用移动Agent的移动性，很好地解决了负载失衡问题，提高了程序的执行效率。较之于传统的算法，我们策略的特点是优先保证提高程序的执行速度(平衡负载的目的是为了提高并行算法的速度)，而不是优先保证系统的平衡。
To solve the problem of distributing data in parallel arithmetic, the method of dividing dataset into several equal parts and sending every part to a special computing node was adopted. If the system was constructed by the same type of computing nodes, then the method can work efficiently. On the other hand, it can make the system unbalanced.
In this thesis, the dataset balancing strategy based on mobile agent in parallel arithmetic was proposed. The mobility of mobile agent enabled the parallel computing to be true and the dataset balancing to be easy. The strategy consisted of two part, DBSMAV(DataSet Balancing Strategy Based on Mobile Agent Velocity ) and DBSMAS(DataSet Balancing Strategy Based on Mobile Agent Scheduling). By using PLUM (Parallel Load balancing for Unstructured Meshes), SBN (Symmetric Broadcast Network) , MinEX (Minimal Extra overhead) , the thinking in Mobile Agent for reference, we proposed this strategy.
It was proved that MAV(Mobile Agent Velocity) could reflect the performance of the computing node when the memory of the node was large enough. DBSMAV could balance the system when it divided the dataset according to MAV. In order to resolve the unbalanced problem led by the memory, the DBSMAS was proposed. In the DBSMAS strategy, the over load first scheduling principle was applied. When the DBSMAS strategy judged that scheduling a Mobile Agent could reduce the total time of the system, it scheduled the Mobile Agent to move to another node with it's dataset. By this way, the unbalanced system can be balanced.
In our experiment, the dataset balancing strategy based on mobile agent in parallel arithmetic show high performance.
本文提出了在并行算法中使用的基于移动agent的数据集负载均衡策略：基于移动Agent综合处理速度的数据集均衡策略DBSMAV(DataSet Balancing Strategy Based on Mobile Agent Velocity)和基于移动Agent调度的数据集均衡策略DBSMAS(DataSet Balancing Strategy Based on Mobile Agent Scheduling)。目前对如此细粒度的负载均衡问题所作的研究工作还很少，本文的工作借鉴了NASA所建立的IPG(Information Power Grid)网格上面的粗粒度负载均衡算法PLUM(Parallel Load balancing for Unstructured Meshes)、SBN(Symmetric Broadcast Network)、MinEX(Minimal Extra overhead)，也参考了接收者发起的分布式启发性算法，并结合了移动Agent的思想。
理论和实验证明，移动Agent综合处理速度MAV(Mobile Agent Velocity)在计算结点的内存足够大时能够比较准确地反映计算结点的计算能力。DBSMAV策略按照各个计算结点的MAV分配数据集，较好地克服了异构系统中平均分配数据集造成的失衡。为了解决由于内存的影响而导致的负载失衡现象，我们提出了DBSMAS策略。DBSMAS策略按照重负载优先调度和整体上减少系统执行时间的原则，命令一部分移动Agent携带数据集进行迁移，使系统重新达到了平衡状态。
实验证明，我们所研究的均衡策略，利用移动Agent的移动性，很好地解决了负载失衡问题，提高了程序的执行效率。较之于传统的算法，我们策略的特点是优先保证提高程序的执行速度(平衡负载的目的是为了提高并行算法的速度)，而不是优先保证系统的平衡。
To solve the problem of distributing data in parallel arithmetic, the method of dividing dataset into several equal parts and sending every part to a special computing node was adopted. If the system was constructed by the same type of computing nodes, then the method can work efficiently. On the other hand, it can make the system unbalanced.
In this thesis, the dataset balancing strategy based on mobile agent in parallel arithmetic was proposed. The mobility of mobile agent enabled the parallel computing to be true and the dataset balancing to be easy. The strategy consisted of two part, DBSMAV(DataSet Balancing Strategy Based on Mobile Agent Velocity ) and DBSMAS(DataSet Balancing Strategy Based on Mobile Agent Scheduling). By using PLUM (Parallel Load balancing for Unstructured Meshes), SBN (Symmetric Broadcast Network) , MinEX (Minimal Extra overhead) , the thinking in Mobile Agent for reference, we proposed this strategy.
It was proved that MAV(Mobile Agent Velocity) could reflect the performance of the computing node when the memory of the node was large enough. DBSMAV could balance the system when it divided the dataset according to MAV. In order to resolve the unbalanced problem led by the memory, the DBSMAS was proposed. In the DBSMAS strategy, the over load first scheduling principle was applied. When the DBSMAS strategy judged that scheduling a Mobile Agent could reduce the total time of the system, it scheduled the Mobile Agent to move to another node with it's dataset. By this way, the unbalanced system can be balanced.
In our experiment, the dataset balancing strategy based on mobile agent in parallel arithmetic show high performance.
引文
[1] Charles A. Rendleman, Vincent E. Beckner, and Marc S. Day Mike Lijewski. Parallel performance of an adaptive mesh refinement method for low mach number combustion. In preparation, January 2001.
[2] T. Matthey and J. P. Hansen. Evaluation of MPI's one-sided communication mechanism for short-range molecular dynamics on the Origin2000. In PARA2000 and Workshop on Applied Parallel Computing, 2000.
[3] Charles A. Rendleman, Vincent E. Beckner, and John B. Bell. Parallelization of structured, hierarchical adaptive mesh refinement algorithms. Computing and Visualization in Science, 2000, 3(3): 147-157.
[4] L. Kal'e, R. Brunner, M. Bhandarkar. NAMD2: Greater scalability for parallel molecular dynamics. J. Comput. Phys, May 1, 1999, 151 (1): 283-312.
[5] D. W. Cheung and Y. Xiao. Effect of data distribution in parallel mining of associations. Data Mining and Knowledge Discovery, 1999.
[6] Hwang K, Xu Z W. Scalable parallel computing: technology, architecture, programming. [M] The M cGraw2H ill Companies, Inc. 1998
[7] Ghormley D P, Petrou D, Rodrigues S H, V ahdat A M ,Anderson T E. GLU nix: Global layer unix for a network of work stations. Software, Practice and Experience, 1998
[8] Ghormley D P, Rodrigues S H, Petrou D, Anderson T E. Interposition as an Operating System Extension Mechanism. Computer Science Division, Berkeley, CA 94720, 1997.9
[9] Inderjit S. Dhillon and Dharmendra S. Modha. A Data-Clustering Algorithm On Distributed Memory Multiprocessors. IEEE Transactions on Knowledge and Data Engineering.
[10] David E. Culler & Jaswinder Pal Singh with Anoop Gupta: Parallel Computer Architecture, A Hardware/Software Approach. Second Edition. Mongan Kaufmann Publishers,Inc. 1996
[11] Khalidi Y A, Bernabeu J M, Matena V, et al. SolarisMC: A MultiConference, 1996
[12] 刘兵．关于NSFCNET鉴定会报道：孕育下一代互联网[J]．计算机世界(网络新观察)，2001(29)：D1-D3．
[13] [美]Rajkumar Buyya。 高性能集群计算：结构与系统(第一卷)-郑伟民，石威，汪东升等译-北京：电子工业出版社，2001。
[14] 李国杰-高性能计算的未来-中国计算机报，2001(7)
[15] 黎康保，陶文正，许丽华，等．用PC机群组构并行超级计算机[J]．计算机工程，2000，26(9)：1-3．
[16] 周光召．中国科协全国学术年会论文集(信息科学与微电子技术)[C]．北京：中国科学技术出版社，2000．298-302．
[17] 沈志宇、廖湘科、胡子昂．并行程序设计．(M)长沙：国防科技大学出版社．1997
[18] 黄铠。并行系统结构。北京：机械工业出版社，1999
[19] 袁伟，孙永强。Dual—object：面相对象的并行程序设计。软件学报，1998(1)。
[20] Yong Yan et. Profit-effective parallel computing. IEEE Concurrency Parallel, distributed & mobile computing, appil-june 1999.65-69
[21] Cristina Boeres et. A versatile cost modelling approach for multicomputer task scheduling. PARALLEL Computing 1999, 25.63-86
[22] J. Michalakes, J. Dudhia, D. Gill, J. Klemp, W. Skamarock, Design of a Next_Generation Regional Weather Research and Forecast Model, Towards Teracomputing, World Scientific, River Edge, New Jersey(1999), P117-123.
[23] P. Burton, A. Dichinson, Parallelising the Unified Model for the Cray T3E, Making Its Mark, World Scientific, River Edge, New Jersey(1997),P68-82.
[24] Ulrich Schattler, Model Development for Parallel Computers AT DWD, Making Its Mark. World Scientific, River Edge, New Jersey(1997),P83-99.
[25] B. Rodriguez, L. Hart, T. Henderson, A Library for Portable Parallelization of Operational Weather Forecast Models, Coming of Age, World Scientific, River Edge, New Jersey (1995), P148-161.
[26] Hwang Jing-Jang et al. Scheduling precedence graphs in systems with interprocessor communication times. SIAM Journal of Computing.1989, 18(2):244-257
[27] 张宏莉等．群机系统上单并发任务簇的近优分配算法．计算机研究与发展．1999．9：1076-1079
[28] 舒继武，郑纬民，沈美明等，大规模问题数据并行性能的分析，软件学报，2000，11(5)：628～633
[29] 曾国荪等．异构计算中的负载共享．软件学报．2000，11(4)：551-556
[30] 莫则尧等．工作站网络环境下的并行计算。计算机学报，1997，20(6)：510-517
[31] Wallach Dan Seth. A new approach to mobile code security. PhD Thesis, Department of Computer Science, University of Princeton, Jan. 1999
[32] Dean Richard Drews. Formal aspects of mobile code security. PhD Thesis, Department of Computer Science, University of Princeton, Jan. 1999
[33] Agha G and Jamali N. Concurrent Programming for Distributed Artificial Intelligence. In: Multiagent Systems: A Modem Approach to Distributed Artificial Intelligence, MIT Press, editor Gerhard Weiss, chap 12, 1999
[34] Ciancarini P, Franze F and Mascolo C. Using a Coordination Language to Specify and Analyze Systems containing Mobile Components, ACM Trans. on Software Engineering and Methodology,2000
[35] Cabri G, Leonardi L, and Zambonelli F. Mars: a programmable coordination architecture for mobile agents. IEEE Internet Computing, 2000
[36] Lange D B and Oshima M. Seven good reasons for mobile agents. Communications of the ACM, 1999, 42(3): 88-89
[37] Dasgupta P. Narasimhan N, Moser L E, Melliar-Smith P M. MAgNET: Mobile Agents for Net-worked Electronic Trading. IEEE Trans on Knowledge and Data Engineering, Special Issue on Web Applications, July-August 1999
[38] Hulaas J, Gannoune L. Francioli J, Chachkov S, Schutz F and Harms J. Electronic
Commerce of Internet Domain Names using Mobile Agents. In: Proceedings of the 2nd International Conference on Telecommunications and Electronic Commerce (ICTEC'99), Nashville, TN, USA, October 6-8, 1999
[39] Wu Gang, Wu Quanyuan and Wang Huaimin. A Novel Workflow Management Model Based on Mobile Agents for Internet Electronic Commerce. Proceedings of the 36th International Conference on Technology of Object-Oriented Languages and Systems,2000
[40] Silva Luis Moura, Batista Victor, Martins Paulo and Soares Guilherme. Using Mobile Agents for Parallel Processing. International Symposium on Distributed Objects and Applications, Edin-burgh, United Kingdom, September 5-7, 1999
[41] Panayiotou Chistoforos, Samaras George and Evripidou Paraskevas, Pitoura Evaggelia. Parallel Computing Using Java Mobile Agents. Proceedings of the 25th Euromicro Conference (EUROMI-CRO'99), 1999
[42] Puliafito A and Tomarchio O. Using Mobile Agents to implement flexible Network Management strategies. Computer Communication Journal, 2000, 23(8):708-719
[43] Griffin D, Pavlou G, Georgatsos P. Providing Customisable Network Management Services Through Mobile Agents. Proc. of the 7th International Conference on Intelligence in Services and Networks (IS&N'00), Athens, Greece, February 2000
[44] Bohoris C, Pavlou G, Cruickshank H. Using Mobile Agents for Network Performance Management. Proc. of the IEEE/IFIP Network Operations and Management Symposium (NOMS'00), Hawaii, pp. 637～652, IEEE, April 2000
[45] Kozt and Gray R S. Mobile Agents and the Future of the Internet. ACM Operating Systems Review, 1999, 33(3): 7-13
[46] Schoder Detlef and Eymann Torsten. The Real Challenges of Mobile Agents. Communications of the ACM, 2000,43(6): 111～112
[2] T. Matthey and J. P. Hansen. Evaluation of MPI's one-sided communication mechanism for short-range molecular dynamics on the Origin2000. In PARA2000 and Workshop on Applied Parallel Computing, 2000.
[3] Charles A. Rendleman, Vincent E. Beckner, and John B. Bell. Parallelization of structured, hierarchical adaptive mesh refinement algorithms. Computing and Visualization in Science, 2000, 3(3): 147-157.
[4] L. Kal'e, R. Brunner, M. Bhandarkar. NAMD2: Greater scalability for parallel molecular dynamics. J. Comput. Phys, May 1, 1999, 151 (1): 283-312.
[5] D. W. Cheung and Y. Xiao. Effect of data distribution in parallel mining of associations. Data Mining and Knowledge Discovery, 1999.
[6] Hwang K, Xu Z W. Scalable parallel computing: technology, architecture, programming. [M] The M cGraw2H ill Companies, Inc. 1998
[7] Ghormley D P, Petrou D, Rodrigues S H, V ahdat A M ,Anderson T E. GLU nix: Global layer unix for a network of work stations. Software, Practice and Experience, 1998
[8] Ghormley D P, Rodrigues S H, Petrou D, Anderson T E. Interposition as an Operating System Extension Mechanism. Computer Science Division, Berkeley, CA 94720, 1997.9
[9] Inderjit S. Dhillon and Dharmendra S. Modha. A Data-Clustering Algorithm On Distributed Memory Multiprocessors. IEEE Transactions on Knowledge and Data Engineering.
[10] David E. Culler & Jaswinder Pal Singh with Anoop Gupta: Parallel Computer Architecture, A Hardware/Software Approach. Second Edition. Mongan Kaufmann Publishers,Inc. 1996
[11] Khalidi Y A, Bernabeu J M, Matena V, et al. SolarisMC: A MultiConference, 1996
[12] 刘兵．关于NSFCNET鉴定会报道：孕育下一代互联网[J]．计算机世界(网络新观察)，2001(29)：D1-D3．
[13] [美]Rajkumar Buyya。 高性能集群计算：结构与系统(第一卷)-郑伟民，石威，汪东升等译-北京：电子工业出版社，2001。
[14] 李国杰-高性能计算的未来-中国计算机报，2001(7)
[15] 黎康保，陶文正，许丽华，等．用PC机群组构并行超级计算机[J]．计算机工程，2000，26(9)：1-3．
[16] 周光召．中国科协全国学术年会论文集(信息科学与微电子技术)[C]．北京：中国科学技术出版社，2000．298-302．
[17] 沈志宇、廖湘科、胡子昂．并行程序设计．(M)长沙：国防科技大学出版社．1997
[18] 黄铠。并行系统结构。北京：机械工业出版社，1999
[19] 袁伟，孙永强。Dual—object：面相对象的并行程序设计。软件学报，1998(1)。
[20] Yong Yan et. Profit-effective parallel computing. IEEE Concurrency Parallel, distributed & mobile computing, appil-june 1999.65-69
[21] Cristina Boeres et. A versatile cost modelling approach for multicomputer task scheduling. PARALLEL Computing 1999, 25.63-86
[22] J. Michalakes, J. Dudhia, D. Gill, J. Klemp, W. Skamarock, Design of a Next_Generation Regional Weather Research and Forecast Model, Towards Teracomputing, World Scientific, River Edge, New Jersey(1999), P117-123.
[23] P. Burton, A. Dichinson, Parallelising the Unified Model for the Cray T3E, Making Its Mark, World Scientific, River Edge, New Jersey(1997),P68-82.
[24] Ulrich Schattler, Model Development for Parallel Computers AT DWD, Making Its Mark. World Scientific, River Edge, New Jersey(1997),P83-99.
[25] B. Rodriguez, L. Hart, T. Henderson, A Library for Portable Parallelization of Operational Weather Forecast Models, Coming of Age, World Scientific, River Edge, New Jersey (1995), P148-161.
[26] Hwang Jing-Jang et al. Scheduling precedence graphs in systems with interprocessor communication times. SIAM Journal of Computing.1989, 18(2):244-257
[27] 张宏莉等．群机系统上单并发任务簇的近优分配算法．计算机研究与发展．1999．9：1076-1079
[28] 舒继武，郑纬民，沈美明等，大规模问题数据并行性能的分析，软件学报，2000，11(5)：628～633
[29] 曾国荪等．异构计算中的负载共享．软件学报．2000，11(4)：551-556
[30] 莫则尧等．工作站网络环境下的并行计算。计算机学报，1997，20(6)：510-517
[31] Wallach Dan Seth. A new approach to mobile code security. PhD Thesis, Department of Computer Science, University of Princeton, Jan. 1999
[32] Dean Richard Drews. Formal aspects of mobile code security. PhD Thesis, Department of Computer Science, University of Princeton, Jan. 1999
[33] Agha G and Jamali N. Concurrent Programming for Distributed Artificial Intelligence. In: Multiagent Systems: A Modem Approach to Distributed Artificial Intelligence, MIT Press, editor Gerhard Weiss, chap 12, 1999
[34] Ciancarini P, Franze F and Mascolo C. Using a Coordination Language to Specify and Analyze Systems containing Mobile Components, ACM Trans. on Software Engineering and Methodology,2000
[35] Cabri G, Leonardi L, and Zambonelli F. Mars: a programmable coordination architecture for mobile agents. IEEE Internet Computing, 2000
[36] Lange D B and Oshima M. Seven good reasons for mobile agents. Communications of the ACM, 1999, 42(3): 88-89
[37] Dasgupta P. Narasimhan N, Moser L E, Melliar-Smith P M. MAgNET: Mobile Agents for Net-worked Electronic Trading. IEEE Trans on Knowledge and Data Engineering, Special Issue on Web Applications, July-August 1999
[38] Hulaas J, Gannoune L. Francioli J, Chachkov S, Schutz F and Harms J. Electronic
Commerce of Internet Domain Names using Mobile Agents. In: Proceedings of the 2nd International Conference on Telecommunications and Electronic Commerce (ICTEC'99), Nashville, TN, USA, October 6-8, 1999
[39] Wu Gang, Wu Quanyuan and Wang Huaimin. A Novel Workflow Management Model Based on Mobile Agents for Internet Electronic Commerce. Proceedings of the 36th International Conference on Technology of Object-Oriented Languages and Systems,2000
[40] Silva Luis Moura, Batista Victor, Martins Paulo and Soares Guilherme. Using Mobile Agents for Parallel Processing. International Symposium on Distributed Objects and Applications, Edin-burgh, United Kingdom, September 5-7, 1999
[41] Panayiotou Chistoforos, Samaras George and Evripidou Paraskevas, Pitoura Evaggelia. Parallel Computing Using Java Mobile Agents. Proceedings of the 25th Euromicro Conference (EUROMI-CRO'99), 1999
[42] Puliafito A and Tomarchio O. Using Mobile Agents to implement flexible Network Management strategies. Computer Communication Journal, 2000, 23(8):708-719
[43] Griffin D, Pavlou G, Georgatsos P. Providing Customisable Network Management Services Through Mobile Agents. Proc. of the 7th International Conference on Intelligence in Services and Networks (IS&N'00), Athens, Greece, February 2000
[44] Bohoris C, Pavlou G, Cruickshank H. Using Mobile Agents for Network Performance Management. Proc. of the IEEE/IFIP Network Operations and Management Symposium (NOMS'00), Hawaii, pp. 637～652, IEEE, April 2000
[45] Kozt and Gray R S. Mobile Agents and the Future of the Internet. ACM Operating Systems Review, 1999, 33(3): 7-13
[46] Schoder Detlef and Eymann Torsten. The Real Challenges of Mobile Agents. Communications of the ACM, 2000,43(6): 111～112