Lecture Notes in Computer Science Commenced Publication in 1973 Founding and Former Series Editors: Gerhard Goos, Juris Hartmanis, and Jan van Leeuwen
Editorial Board Takeo Kanade Carnegie Mellon University, Pittsburgh, PA, USA Josef Kittler University of Surrey, Guildford, UK Jon M. Kleinberg Cornell University, Ithaca, NY, USA Friedemann Mattern ETH Zurich, Switzerland John C. Mitchell Stanford University, CA, USA Oscar Nierstrasz University of Bern, Switzerland C. Pandu Rangan Indian Institute of Technology, Madras, India Bernhard Steffen University of Dortmund, Germany Madhu Sudan Massachusetts Institute of Technology, MA, USA Demetri Terzopoulos New York University, NY, USA Doug Tygar University of California, Berkeley, CA, USA Moshe Y. Vardi Rice University, Houston, TX, USA Gerhard Weikum Max-Planck Institute of Computer Science, Saarbruecken, Germany
3033
Springer Berlin Heidelberg New York Hong Kong London Milan Paris Tokyo
Minglu Li Xian-He Sun Qianni Deng Jun Ni (Eds.)
Grid and Cooperative Computing Second International Workshop, GCC 2003 Shanghai, China, December 7-10, 2003 Revised Papers, Part II
Springer
eBook ISBN: Print ISBN:
3-540-24680-0 3-540-21993-5
©2005 Springer Science + Business Media, Inc. Print ©2004 Springer-Verlag Berlin Heidelberg All rights reserved No part of this eBook may be reproduced or transmitted in any form or by any means, electronic, mechanical, recording, or otherwise, without written consent from the Publisher Created in the United States of America
Visit Springer's eBookstore at: and the Springer Global Website Online at:
http://ebooks.springerlink.com http://www.springeronline.com
Preface
Grid and cooperative computing has emerged as a new frontier of information technology. It aims to share and coordinate distributed and heterogeneous network resources for better performance and functionality that can otherwise not be achieved. This volume contains the papers presented at the 2nd International Workshop on Grid and Cooperative Computing, GCC 2003, which was held in Shanghai, P.R. China, during December 7–10, 2003. GCC is designed to serve as a forum to present current and future work as well as to exchange research ideas among researchers, developers, practitioners, and users in Grid computing, Web services and cooperative computing, including theory and applications. For this workshop, we received over 550 paper submissions from 22 countries and regions. All the papers were peer-reviewed in depth and qualitatively graded on their relevance, originality, significance, presentation, and the overall appropriateness of their acceptance. Any concerns raised were discussed by the program committee. The organizing committee selected 176 papers for conference presentation (full papers) and 173 submissions for poster presentation (short papers). The papers included herein represent the forefront of research from China, USA, UK, Canada, Switzerland, Japan, Australia, India, Korea, Singapore, Brazil, Norway, Greece, Iran, Turkey, Oman, Pakistan and other countries. More than 600 attendees participated in the technical section and the exhibition of the workshop. The success of GCC 2003 was made possible by the collective efforts of many people and organizations. We would like to express our special thanks to the Ministry of Education of P.R. China and the municipal government of Shanghai. We also thank IBM, Intel, Platform, HP, Dawning and Lenovo for their generous support. Without the extensive support from many communities, we would not have been able to hold this successful workshop. Moreover, our thanks go to Springer-Verlag for its assistance in putting the proceedings together. We would like to take this opportunity to thank all the authors, many of whom traveled great distances to participate in this workshop and make their valuable contributions. We would also like to express our gratitude to the program committee members and all the other reviewers for the time and work they put into the thorough review of the large number of papers submitted. Last, but not least, our thanks also go to all the workshop staff for the great job they did in making the local arrangements and organizing an attractive social program. December 2003
Minglu Li, Xian-He Sun Qianni Deng, Jun Ni
This page intentionally left blank
Conference Committees
Honorary Chair Qinping Zhao (MOE, China)
Steering Committee Guojie Li (CCF, China) Weiping Shen (Shanghai Jiao Tong University, China) Huanye Sheng (Shanghai Jiao Tong University, China) Zhiwei Xu (IEEE Beijing Section, China) Liang-Jie Zhang (IEEE Computer Soceity, USA) Xiaodong Zhang (NSF, USA)
General Co-chairs Minglu Li (Shanghai Jiao Tong University, China) Xian-He Sun (Illinois Institute of Technology, USA)
Program Co-chairs Qianni Deng (Shanghai Jiao Tong University, China) Jun Ni (University of Iowa, USA)
Panel Chair Hai Jin (Huazhong University of Science and Technology, China)
VIII
Conference Committees
Program Committee Members Yaodong Bi (University of Scranton, USA) Wentong Cai (Nanyang Technological University, Singapore) Jian Cao (Shanghai Jiao Tong University, China) Jiannong Cao (Hong Kong Polytechnic University, China) Guo-Liang Chen (University of Science and Technology of China, China) Jian Chen (South Australia University, Australia) Xuebin Chi (Computer Network Information Center, CAS, China) Qianni Deng (Shanghai Jiao Tong University, China) Xiaoshe Dong (Xi’an Jiao Tong University, China) Joseph Fong (City University of Hong Kong) Yuxi Fu (Shanghai Jiao Tong University, China) Guangrong Gao (University of Delaware, Newark, USA) Yadong Gui (Shanghai Supercomputing Center, China) Minyi Guo (University of Aizu, Japan) Jun Han (Swinburne University of Technology, Australia) Yanbo Han (Institute of Computing Technology, CAS, China) Jinpeng Huai (Beihang University, China) Weijia Jia (City University of Hong Kong) ChangJun Jiang (Tongji University, China) Hai Jin (Huazhong University of Science and Technology, China) Francis Lau (University of Hong Kong) Keqin Li (State University of New York, USA) Minglu Li (Shanghai Jiao Tong University, China) Qing Li (City University of Hong Kong) Xiaoming Li (Peking University, China) Xinda Lu (Shanghai Jiao Tong University, China) Junzhou Luo (Southeast University, China) Fanyuan Ma (Shanghai Jiao Tong University, China) Dan Meng (Institute of Computing Technology, CAS, China) Xiangxu Meng (Shandong University, China) Jun Ni (University of Iowa, USA) Lionel M. Ni (Hong Kong University of Science & Technology) Yi Pan (Georgia State University, USA) Depei Qian (Xi’an Jiao Tong University, China) Yuzhong Qu (Southeast University, China) Hong Shen (Advanced Institute of Science & Technology, Japan) Xian-He Sun (Illinois Institute of Technology, USA) Huaglory Tianfield (Glasgow Caledonian University, UK) Weiqin Tong (Shanghai University, China) Cho-Li Wang (University of Hong Kong) Frank Wang (London Metropolitan University, UK) Jie Wang (Stanford University, USA) Shaowen Wang (University of Iowa, USA) Xingwei Wang (Northeastern University, China)
Conference Committees
Jie Wu (Florida Atlantic University, USA) Zhaohui Wu (Zhejiang University, China) Nong Xiao (National University of Defense Technology, China) Xianghui Xie (Jiangnan Institute of Computing Technology, China) Chengzhong Xu (Wayne State University, USA) Zhiwei Xu (Institute of Computing Technology, CAS, China) Guangwen Yang (Tsinghua University, China) Laurence Tianruo Yang (St. Francis Xavier University, Canada) Qiang Yang (Hong Kong University of Science & Technology) Jinyuan You (Shanghai Jiao Tong University, China) Haibiao Zeng (Sun Yat-Sen University, China) Ling Zhang (South China University of Technology, China) Xiaodong Zhang (NSF, USA and College of William and Mary, USA) Wu Zhang (Shanghai University, China) Weimin Zheng (Tsinghua University, China) Aoying Zhou (Fudan University, China) Wanlei Zhou (Deakin University, Australia) Jianping Zhu (University of Akron, USA) Hai Zhuge (Institute of Computing Technology, CAS, China)
Organization Committee Xinda Lu (Chair) (Shanghai Jiao Tong University, China) Jian Cao (Shanghai Jiao Tong University, China) Ruonan Rao (Shanghai Jiao Tong University, China) Meiju Chen (Shanghai Jiao Tong University, China) An Yang (Shanghai Jiao Tong University, China) Zhihua Su (Shanghai Jiao Tong University, China) Feilong Tang (Shanghai Jiao Tong University, China) Jiadi Yu (Shanghai Jiao Tong University, China)
IX
X
Conference Committees
Will Globus dominate Grid computing as Windows dominated in PCs? If not, what will the next Grid toolkits looks like? Panel Chair Hai Jin, Huazhong University of Science and Technology, China
[email protected]
Panelists Wolfgang Gentzsch, Sun Microsystems, Inc., USA
[email protected] Satoshi Matsuoka, Tokyo Institute of Technology, Japan
[email protected] Carl Kesselman, University of Southern California, USA
[email protected] Andrew A. Chien, University of California at San Diego, USA achien @ ucsd.edu Xian-He Sun, Illinois Institute of Technology, USA
[email protected] Richard Wirt, Intel Corporation, USA
[email protected] Zhiwei Xu, Institute of Computing Technology, CAS, China
[email protected] Francis Lau, University of Hong Kong
[email protected] Huaglory Tianfield, Glasgow Caledonian University, UK
[email protected]
Table of Contents, Part II
Session 6: Advanced Resource Management, Scheduling, and Monitoring Synthetic Implementations of Performance Data Collection in Massively Parallel Systems Chu J. Jong, Arthur B. Maccabe
1
GMA+ – A GMA-Based Monitoring and Management Infrastructure for Grid Chuan He, Zhihui Du, San-li Li
10
A Parallel Branch–and–Bound Algorithm for Computing Optimal Task Graph Schedules Udo Hönig, Wolfram Schiffmann
18
Selection and Advanced Reservation of Backup Resources for High Availability Service in Computational Grid Chunjiang Li, Nong Xiao, Xuejun Yang
26
An Online Scheduling Algorithm for Grid Computing Systems Hak Du Kim, Jin Suk Kim
34
A Dynamic Job Scheduling Algorithm for Computational Grid Jian Zhang, Xinda Lu
40
An Integrated Management and Scheduling Scheme for Computational Grid Ran Zheng, Hai Jin Multisite Task Scheduling on Distributed Computing Grid Weizhe Zhang, Hongli Zhang, Hui He, Mingzeng Hu Adaptive Job Scheduling for a Service Grid Using a Genetic Algorithm Yang Gao, Hongqiang Rang, Frank Tong, Zongwei Luo, Joshua Huang
48
57
65
Resource Scheduling Algorithms for Grid Computing and Its Modeling and Analysis Using Petri Net Yaojun Han, Changjun Jiang, You Fu, Xuemei Luo
73
Architecture of Grid Resource Allocation Management Based on QoS Xiaozhi Wang, Junzhou Luo
81
XII
Table of Contents, Part II
An Improved Ganglia-Like Clusters Monitoring System Wenguo Wei, Shoubin Dong, Ling Zhang, Zhengyou Liang Effective OpenMP Extensions for Irregular Applications on Cluster Environments Minyi Guo, Jiannong Cao, Weng-Long Chang, Li Li, Chengfei Liu
89
97
A Scheduling Approach with Respect to Overlap of Computing and Data Transferring in Grid Computing Changqin Huang, Yao Zheng, Deren Chen
105
A Deadline and Budget Constrained Cost-Time Optimization Algorithm for Scheduling Dependent Tasks in Grid Computing Haolin Feng, Guanghua Song, Yao Zheng, Jun Xia
113
A Load Balancing Algorithm for Web Based Server Grids Shui Yu, John Casey, Wanlei Zhou Flexible Intermediate Library for MPI-2 Support on an SCore Cluster System Yuichi Tsujita Resource Management and Scheduling in Manufacturing Grid Lilan Liu, Tao Yu, Zhanbei Shi, Minglun Fang A New Task Scheduling Algorithm in Distributed Computing Environments Jian-Jun Han, Qing-Hua Li
121
129 137
141
GridFerret: Grid Monitoring System Based on Mobile Agent Juan Fang, Shu-Jie Zhang, Rui-Hua Di, He Huang
145
Grid-Based Resource Management of Naval Weapon Systems Bin Zeng, Tao Hu, ZiTang Li
149
A Static Task Scheduling Algorithm in Grid Computing Dan Ma, Wei Zhang
153
A New Agent-Based Distributed Model of Grid Service Advertisement and Discovery Dan Ma, Wei Zhang, Hong-jun Zhang
157
IMCAG: Infrastructure for Managing and Controlling Agent Grid Jun Hu, Ji Gao
161
A Resource Allocation Method in the Neural Computation Platform Zhuo Lai, Jiangang Yang, Hongwei Shan
166
Table of Contents, Part II
An Efficient Clustering Method for Retrieval of Large Image Databases Yu-Xiang Xie, Xi-Dao Luan, Ling-Da Wu, Song-Yang Lao, Lun-Guo Xie
XIII
170
Research on Adaptable Replication Protocol Dong Zhao, Ya-wei Li, Ming-Tian Zhou
174
Co-operative Monitor Web Page Based on MD5 Guohun Zhu, YuQing Miao
179
Collaboration-Based Architecture of Flexible Software Configuration Management System Ying Ding, Weishi Zhang, Lei Xu The Research of Mobile Agent Security Xiaobin Li, Aijuan Zhang, Jinfei Sun, Zhaolin Yin
183 187
Research of Information Resources Integration and Shared in Digital Basin Xiaofeng Zhou, Zhijian Wang, Ping Ai
191
Scheduling Model in Global Real-Time High Performance Computing with Network Calculus Yafei Hou, Shi Yong Zhang, YiPing Zhong
195
CPU Schedule in Programmable Routers: Virtual Service Queuing with Feedback Algorithm Tieying Zhu
199
Research on Information Platform of Virtual Enterprise Based on Web Services Technology Chao Young, Jiajin Le
203
A Reliable Grid Messaging Service Based on JMS Ruonan Rao, Xu Cai, Ping Hao, Jinyuan You A Feedback and Investigation Based Resources Discovery and Management Model on Computational Grid Peng Ji, Junzhou Luo
207
211
Moment Based Transfer Function Design for Volume Rendering Huawei Hou, Jizhou Sun, Jiawan Zhang
215
Grid Monitoring and Data Visualization Yi Chi, Shoubao Yang, Zheng Feng
219
An Economy Driven Resource Management Architecture Based on Mobile Agent Peng Wan, Wei-Yong Zhang, Tian Chen
223
XIV
Table of Contents, Part II
Decentralized Computational Market Model for Grid Resource Management Qianfei Fu, Shoubao Yang, Maosheng Li, Junmao Zhun A Formal Data Model and Algebra for Resource Sharing in Grid Qiujian Sheng, Zhongzhi Shi An Efficient Load Balance Algorithm in Cluster-Based Peer-to-Peer System Ming-Hong Shi, Yong-Jun Luo, Ying-Cai Bai
227 231
236
Resource Information Management of Spatial Information Grid Deke Guo, Honghui Chen, Xueshan Luo
240
An Overview of CORBA-Based Load Balancing Jian Shu, Linlan Liu, Shaowen Song
244
Intelligence Balancing for Communication Data Management in Grid Computing Jong Sik Lee
250
On Mapping and Scheduling Tasks with Synchronization on Clusters of Machines Bassel R. Arafeh
254
An Efficient Load Balancing Algorithm on Distributed Networks Okbin Lee, Sangho Lee, Ilyong Chung
259
Session 7: Network Communication and Information Retrieval Optimal Methods for Object Placement in En-Route Web Caching for Tree Networks and Autonomous Systems Keqiu Li, Hong Shen
263
A Framework of Tool Integration for Internet-Based E-commerce Jianming Yong, Yun Yang
271
Scalable Filtering of Well-Structured XML Message Stream Weixiong Rao, Yingjian Chen, Xinquan Zhang, Fanyuan Ma
279
Break a New Ground on Programming in Web Client Side Jianjun Zhang, Mingquan Zhou
287
An Adaptive Mixing Audio Gateway in Heterogeneous Networks for ADMIRE System Tao Huang, Xiangning Yu Kernel Content-Aware QoS for Web Clusters Zeng-Kai Du, Jiu-bin Ju
294 303
Table of Contents, Part II
A Collaborative Multimedia Authoring System Mee Young Sung, Do Hyung Lee
XV
311
Research of Satisfying Atomic and Anonymous Electronic Commerce Protocol Jie Tang, Juan-Zi Li, Ke-Hong Wang, Yue-Ru Cai
319
Network Self-Organizing Information Exploitation Model Based on GCA Yujun Liu, Dianxun Shuai, Weili Han
327
Admire – A Prototype of Large Scale E-collaboration Platform Tian Jin, Jian Lu, XiangZhi Sheng
335
A Most Popular Approach of Predictive Prefetching on a WAN to Efficiently Improve WWW Response Times Christos Bouras, Agisilaos Konidaris, Dionysios Kostoulas
344
Applications of Server Performance Control with Simple Network Management Protocol Yijiao Yu, Qin Liu, Liansheng Tan
352
Appcast – A Low Stress and High Stretch Overlay Protocol V. Radha, Ved P Gulati, Arun K Pujari
360
Communication Networks: States of the Arts Xiaolu Zuo
372
DHCS: A Case of Knowledge Share in Cooperative Computing Environment Shui Yu, Le Yun Pan, Futai Zou, Fan Yuan Ma
380
Improving the Performance of Equalization in Communication Systems Wanlei Zhou, Hua Ye, Lin Ye
388
Moving Communicational Supervisor Control System Based on Component Technology Song Yu, Yan-Rong Jie
396
A Procedure Search Mechanism in OGSA-Based GridRPC Systems Yue-zhuo Zhang, Yong-zhong Huang, Xin Chen
400
An Improved Network Broadcasting Method Based on Gnutella Network Zupeng Li, Xiubin Zhao, Daoyin Huang, Jianhua Huang
404
Some Conclusions on Cayley Digraphs and Their Applications to Interconnection Networks Wenjun Xiao, Behrooz Parhami
408
XVI
Table of Contents, Part II
Multifractal Characteristic Quantities of Network Traffic Models Donglin Liu, Dianxun Shuai
413
Network Behavior Analysis Based on a Computer Network Model Weili Han, Dianxun Shuai, Yujun Liu
418
Cutting Down Routing Overhead in Mobile Ad Hoc Networks Jidong Zhong, Shangteng Huang
422
Improving Topology-Aware Routing Efficiency in Chord Dongfeng Chen, Shoubao Yang
426
Two Extensions to NetSolve System Jianhua Chen, Wu Zhang, Weimin Shao
430
A Route-Based Composition Language for Service Cooperation Jianguo Xing
434
To Manage Grid Using Dynamically Constructed Network Management Concept: An Early Thought Zhongzhi Luan, Depei Qian, Weiguo Wu, Tao Liu
438
Design of VDSL Networks for the High Speed Internet Services Hyun Yoe, Jaejin Lee
442
The Closest Vector Problem on Some Lattices Haibin Kan, Hong Shen, Hong Zhu
446
Proposing a New Architecture for Adaptive Active Network Control and Management System Mahdi Jalili-Kharaajoo, Alireza Dehestani, Hassan Motallebpour A Path Based Internet Cache Design for GRID Application Hyuk Soo Jang, Kyong Hoon Min, Won Seok Jou, Yeonseung Ryu, Chung Ki Lee, Seok Won Hong On the Application of Computational Intelligence Methods on Active Networking Technology Mahdi Jalili-Kharaajoo
450 455
459
Session 8: Grid QoS Grid Computing for the Masses: An Overview Kaizar Amin, Gregor von Laszewski, Armin R. Mikler A Multiple-Neighborhoods-Based Simulated Annealing Algorithm for Timetable Problem He Yan, Song-Nian Yu
464
474
Table of Contents, Part II
Lattice Framework to Implement OGSA: Its Constructs and Composition Scenario Hui Liu, Minglu Li, Jiadi Yu, Lei Cao, Ying Li, Wei Jin, Qi Qian
XVII
482
Moving Grid Systems into the IPv6 Era Sheng Jiang, Piers O’Hanlon, Peter Kirstein
490
MG-QoS: QoS-Based Resource Discovery in Manufacturing Grid Zhanbei Shi, Tao Yu, Lilan Liu
500
An Extension of Grid Service: Grid Mobile Service Wei Zhang, Jun Zhang, Dan Ma, Benli Wang, Yun Tao Chen
507
Supplying Instantaneous Video-on-Demand Services Based on Grid Computing Xiao-jian He, Xin-huai Tang, Jinyuan You
513
A Grid Service Lifecycle Management Scheme Jie Qiu, Haiyan Yu, Shuoying Chen, Li Cha, Wei Li, Zhiwei Xu
521
An OGSA-Based Quality of Service Framework Rashid Al-Ali, Kaizar Amin, Gregor von Laszewski, Omer Rana, David Walker
529
A Service Management Scheme for Grid Systems Wei Li, Zhiwei Xu, Li Cha, Haiyan Yu, Jie Qiu, Yanzhe Zhang
541
A QoS Model for Grid Computing Based on DiffServ Protocol Wandan Zeng, Guiran Chang, Xingwei Wang, Shoubin Wang, Guangjie Han, Xubo Zhou
549
Design and Implementaion of a Single Sign-On Library Supporting SAML (Security Assertion Markup Language) for Grid and Web Services Security Dongkyoo Shin, Jongil Jeong, Dongil Shin Performance Improvement of Information Service Using Priority Driven Method Minji Lee, Wonil Kim, Jai-Hoon Kim
557
565
HH-MDS: A QoS-Aware Domain Divided Information Service Deqing Zou, Hai Jin, Xingchang Dong, Weizhong Qiang, Xuanhua Shi
573
Grid Service Semigroup and Its Workflow Model Yu Tang, Haifang Zhou, Kaitao He, Luo Chen, Ning Jing
581
A Design of Distributed Simulation Based on GT3 Core Tong Zhang, Chuanfu Zhang, Yunsheng Liu, Yabing Zha
590
XVIII
Table of Contents, Part II
A Policy-Based Service-Oriented Grid Architecture Xiangli Qu, Xuejun Yang, Chunmei Gui, Weiwei Fan
597
Adaptable QOS Management in OSGi-Based Cooperative Gateway Middleware Wei Liu, Zhang-long Chen, Shi-liang Tu, Wei Du
604
Design of an Artificial-Neural-Network-Based Extended Metacomputing Directory Service Haopeng Chen, Baowen Zhang
608
Session 9: Algorithm, Economic Model, Theoretical Model of the Grid Gridmarket: A Practical, Efficient Market Balancing Resource for Grid and P2P Computing Ming Chen, Guangwen Yang, Xuezheng Liu
612
A Distributed Approach for Resource Pricing in Grid Environments Chuliang Weng, Xinda Lu, Qianni Deng
620
Application Modelling Based on Typed Resources Cheng Fu, Jinyuan You
628
A General Merging Algorithm Based on Object Marking Jinlei Jiang, Meilin Shi
636
Charging and Accounting for Grid Computing System Zhengyou Liang, Ling Zhang, Shoubin Dong, Wenguo Wei
644
Integrating New Cost Model into HMA-Based Grid Resource Scheduling Jun-yan Zhang, Fan Min, Guo-wei Yang
652
CoAuto: A Formal Model for Cooperative Processes Jinlei Jiang, Meilin Shi
660
A Resource Model for Large-Scale Non-hierarchy Grid System Qianni Deng, Xinda Lu, Li Chen, Minglu Li
669
A Virtual Organization Based Mobile Agent Computation Model Yong Liu, Cong-fu Xu, Zhaohui Wu, Wei-dong Chen, Yun-he Pan
677
Modeling Distributed Algorithm Using B Shengrong Zou
683
Multiple Viewpoints Based Ontology Integration Kai Zhang, Yunfa Hu, Yu Wang
690
Table of Contents, Part II
XIX
Automated Detection of Design Patterns Zhixiang Zhang, Qing-Hua Li
694
Research on the Financial Information Grid Jiyue Wen, Guiran Chang
698
RCACM: Role-Based Context-Awareness Coordination Model for Mobile Agent Applications Xin-huai Tang, Yaying Zhang, Jinyuan You
702
A Model for Locating Services in Grid Environment Erfan Shang, Zhihui Du, Mei Chen
706
A Grid Service Based Model of Virtual Experiment Liping Shen, Yonggang Fu, Ruimin Shen, Minglu Li
710
Accounting in the Environment of Grid Society Jiulong Shan, Huaping Chen, GuoLiang Chen, Haitao Tian, Xin Chen
715
A Heuristic Algorithm for Minimum Connected Dominating Set with Maximal Weight in Ad Hoc Networks Xinfang Yan, Yugeng Sun, Yanlin Wang Slice-Based Information Flow Graph Wan-Kyoo Choi, Il-Yong Chung
719 723
Session 10: Semantic Grid and Knowledge Grid Semantic Rule Service Model: Enabling Intelligence on Grid Architecture Qi Gao, HuaJun Chen, Zhaohui Wu, WeiMing Lin CSCW in Design on the Semantic Web Dazhou Kang, Baowen Xu, Jianjiang Lu, Yingzhou Zhang SIMON: A Multi-strategy Classification Approach Resolving Ontology Heterogeneity – The P2P Meets the Semantic Web Le Yun Pan, Liang Zhang, Fanyuan Ma
727 736
744
SkyEyes: A Semantic Browser for the KB-Grid Yuxin Mao, Zhaohui Wu, HuaJun Chen
752
Toward the Composition of Semantic Web Services Jinghai Rao, Xiaomeng Su
760
A Viewpoint of Semantic Description Framework for Service Yuzhong Qu
768
XX
Table of Contents, Part II
A Novel Approach to Semantics-Based Exception Handling for Service Grid Applications Donglai Li, Yanbo Han, Haitao Hu, Jun Fang, Xue Wang
778
A Semantic-Based Web Service Integration Approach and Tool Hai Zhuge, Jie Liu, Lianhong Ding, Xue Chen
787
A Computing Model for Semantic Link Network Hai Zhuge, Yunchuan Sun, Jie Liu, Xiang Li
795
A Semantic Web Enabled Mediator for Web Service Invocation Lejun Zhu, Peng Ding, Huanye Sheno
803
A Data Mining Algorithm Based on Grid Xue-bai Zang, Xiong-fei Li, Kun Zhao, Xin Guan
807
Prototype a Knowledge Discovery Infrastructure by Implementing Relational Grid Monitoring Architecture (R-GMA) on European Data Grid (EDG) Frank Wang, Na Helian, Yike Guo, Steve Thompson, John Gordon
811
Session 11: Data Remote Access, Storage, and Sharing The Consistency Mechanism of Meta-data Management in Distributed Storage System Zhaofu Wang, Wensong Zhang, Kun Deng
815
Link-Contention-Aware Genetic Scheduling Using Task Duplication in Grid Environments Wensheng Yao, Xiao Xie, Jinyuan You
822
An Adaptive Meta-scheduler for Data-Intensive Applications Xuanhua Shi, Hai Jin, Weizhong Qiang, Deqing Zou
830
Dynamic Data Grid Replication Strategy Based on Internet Hierarchy Sang-Min Park, Jai-Hoon Kim, Young-Bae Ko, Won-Sik Yoon
838
Preserving Data Consistency in Grid Databases with Multiple Transactions Sushant Goel, Hema Sharda, David Taniar
847
Dart: A Framework for Grid-Based Database Resource Access and Discovery Chang Huang, Zhaohui Wu, Guozhou Zheng, Xiaojun Wu
855
An Optimal Task Scheduling for Cluster Systems Using Task Duplication Xiao Xie, Wensheng Yao, Jinyuan You
863
Table of Contents, Part II
XXI
Towards an Interactive Architecture for Web-Based Databases Changgui Chen, Wanlei Zhou
871
Network Storage Management in Data Grid Environment Shaofeng Yang, Zeyad Ali, Houssain Kettani, Vinti Verma, Qutaibah Malluhi
879
Study on Data Access Technology in Information Grid YouQun Shi, ChunGang Yan, Feng Yue, Changjun Jiang
887
GridTP Services for Grid Transaction Processing Zhengwei Qi, Jinyuan You, Ying Jin, Feilong Tang
891
FTPGrid: A New Paradigm for Distributed FTP System Liutong Xu, Bo Ai
895
Using Data Cube for Mining of Hybrid-Dimensional Association Rules Zhi-jie Li, Fei-xue Huang, Dong-qing Zhou, Peng Zhang Knowledge Sharing by Grid Technology Bangyong Liang, Juan-Zi Li, Ke-Hong Wang A Security Access Control Mechanism for a Multi-layer Heterogeneous Storage Structure Shiguang Ju, Héctor J. Hernández, Lan Zhang Investigating the Role of Handheld Devices in the Accomplishment of Grid-Enabled Analysis Environment Ashiq Anjum, Arshad Ali, Tahir Azim, Ahsan Ikram, Julian J. Bunn, Harvey B. Newman, Conrad Steenberg, Michael Thomas
899 903
907
913
Session 12: Computer-Supported Cooperative Work and Cooperative Middleware A TMO-Based Object Group Model to Structuring Replicated Real-Time Objects for Distributed Real-Time Applications Chang-Sun Shin, Su-Chong Joo, Young-Sik Jeong Fuzzy Synthesis Evaluation Improved Task Distribution in WfMS Xiao-Guang Zhang, Jian Cao, Shensheng Zhang
918 927
A Simulation Study of Job Workflow Execution Models over the Grid Yuhong Feng, Wentong Cai, Jiannong Cao
935
An Approach to Distributed Collaboration Problem with Conflictive Tasks Jingping Bi, Qi Wu, Zhongcheng Li
944
XXII
Table of Contents, Part II
Temporal Problems in Service-Based Workflows Zhen Yu, Zhaohui Wu, ShuiGuang Deng, Qi Gao
954
iCell: Integration Unit in Enterprise Cooperative Environment Ruey-Shyang Wu, Shyan-Ming Yuan, Anderson Liang, Daphne Chyan
962
The Availability Semantics of Predicate Data Flow Diagram Xiaolei Gao, Huaikou Miao, Shaoying Liu, Ling Liu
970
Virtual Workflow Management System in Grid Environment ShuiGuang Deng, Zhaohui Wu, Qi Gao, Zhen Yu
978
Research of Online Expandability of Service Grid Yuan Wang, Zhiwei Xu, Yuzhong Sun
986
Modelling Cooperative Multi-agent Systems Lijun Shan, Hong Zhu
994
GHIRS: Integration of Hotel Management Systems by Web Services Yang Xiang, Wanlei Zhou, Morshed Chowdhury
1002
Cooperative Ants Approach for a 2D Navigational Map of 3D Virtual Scene Jiangchun Wang, Shensheng Zhang
1010
Workflow Interoperability – Enabling Online Approval in E-government Hua Xin, Fu-ren Xue
1018
A Multicast Routing Algorithm for CSCW Xiong-fei Li, Dandan Huan, Yuanfang Dong, Xin Zhou
1022
A Multi-agent System Based on ECA Rule Xiaojun Zhou, Jian Cao, Shensheng Zhang
1026
A Hybrid Algorithm of n-OPT and GA to Solve Dynamic TSP Zhao Liu, Lishan Kang
1030
The Application Research of Role-Based Access Control Model in Workflow Management System Baoyi Wang, Shaomin Zhang, Xiaodong Xia
1034
Research and Design of Remote Education System Based on CSCW Chunzhi Wang, Miao Shao, Jing Xia, Huachao Chen
1038
Data and Interaction Oriented Workflow Execution Wan-Chun Dou, Juan Sun, Da-Gang Yang, Shi-Jie Cai
1042
Table of Contents, Part II
XXIII
XCS System: A New Architecture for Web-Based Applications Yijian Wu, Wenyun Zhao
1046
A PKI-Based Scalable Security Infrastructure for Scalable Grid Lican Huang, Zhaohui Wu
1051
A Layered Grid User Expression Model in Grid User Management Limin Liu, Zhiwei Xu, Wei Li
1055
A QoS-Based Multicast Algorithm for CSCW in IP/DWDM Optical Internet Xingwei Wang, Hui Cheng, Jia Li, Min Huang, Ludi Zheng
1059
An Evolutionary Constraint Satisfaction Solution for over the Cell Channel Routing Ahmet Ünveren, Adnan Acan
1063
Author Index
1067
This page intentionally left blank
Table of Contents, Part I
Vega Grid: A Computer Systems Approach to Grid Research Zhiwei Xu
1
Problems of and Mechanisms for Instantiating Virtual Organizations Carl Kesselman
2
Grid Computing: The Next Stage of the Internet Irving Wladawsky-Berger
3
Making Grid Computing Real for High Performance and Enterprise Computing Richard Wirt
4
Grid Computing for Enterprise and Beyond Songnian Zhou
5
Semantic Grid: Scientific Issues, Methodology, and Practice in China Hai Zhuge
6
Grid Computing, Vision, Strategy, and Technology Wolfgang Gentzsch
7
Towards a Petascale Research Grid Infrastructure Satoshi Matsuoka
8
The Microgrid: Enabling Scientific Study of Dynamic Grid Behavior Andrew A. Chien
9
On-Demand Business Collaboration Enablement with Services Computing Liang- Jie Zhang
10
Session 1: Grid Application Multidisciplinary Design Optimization of Aero-craft Shapes by Using Grid Based High Performance Computational Framework Hong Liu, Xi-li Sun, Qianni Deng, Xinda Lu A Research on the Framework of Grid Manufacturing Li Chen, Hong Deng, Qianni Deng, Zhenyu Wu Large-Scale Biological Sequence Assembly and Alignment by Using Computing Grid Wei Shi, Wanlei Zhou
11 19
26
XXVI
Table of Contents, Part I
Implementation of Grid-Enabled Medical Simulation Applications Using Workflow Techniques Junwei Cao, Jochen Fingberg, Guntram Berti, Jens Georg Schmidt A New Overlay Network Based on CAN and Chord Wenyuan Cai, Shuigeng Zhou, Linhao Xu, Weining Qian, Aoying Zhou An Engineering Computation Oriented Visual Grid Framework Guiyi Wei, Yao Zheng, Jifa Zhang, Guanghua Song
34 42 51
Interaction Compatibility: An Essential Ingredient for Service Composition Jun Han
59
A Distributed Media Service System Based on Globus Data-Management Technologies Xiang Yu, Shoubao Yang, Yu Hong
67
Load Balancing between Heterogeneous Computing Clusters Siu-Cheung Chau, Ada Wai-Chee Fu
75
“Gridifying” Aerodynamic Design Problem Using GridRPC Quoc-Thuan Ho, Yew-Soon Ong, Wentong Cai
83
A WEB-GIS Based Urgent Medical Rescue CSCW System for SARS Disease Prevention Xiaolin Lu MASON: A Model for Adapting Service-Oriented Grid Applications Gang Li, Jianwu Wang, Jing Wang, Yanbo Han, Zhuofeng Zhao, Roland M. Wagner, Haitao Hu Coordinating Business Transaction for Grid Service Feilong Tang, Minglu Li, Jian Cao, Qianni Deng Conceptual Framework for Recommendation System Based on Distributed User Ratings Hyun-Jun Kim, Jason J. Jung, Geun-Sik Jo
91 99
108
115
Grid Service-Based Parallel Finite Element Analysis Guiyi Wei, Yao Zheng, Jifa Zhang
123
The Design and Implementation of the GridLab Information Service Giovanni Aloisio, Massimo Cafaro, Italo Epicoco, Daniele Lezzi, Maria Mirto, Silvia Mocavero
131
Comparison Shopping Systems Based on Semantic Web – A Case Study of Purchasing Cameras Ho-Kyoung Lee, Young-Hoon Yu, Supratip Ghose, Geun-Sik Jo
139
Table of Contents, Part I
XXVII
A New Navigation Method for Web Users Jie Yang, Guoqing Wu, Luis Zhu
147
Application Availability Measurement in Computational Grid Chunjiang Li, Nong Xiao, Xuejun Yang
151
Research and Application of Distributed Fusion System Based on Grid Computing Yu Su, Hai Zhao, Wei-ji Su, Gang Wang, Xiao-dan Zhang An Efficient and Self-Configurable Publish-Subscribe System Tao Xue, Boqin Feng The Implementation of the Genetic Optimized Algorithm of Air Craft Geometry Designing Based on Grid Computing Xi-li Sun, Xinda Lu, Qianni Deng Distributed Information Management System for Grid Computing Liping Niu, Xiaojie Yuan, Wentong Cai The Design of Adaptive Platform for Visual-Intensive Applications over the Grid Hui Xiang, Bin Gong, Xiangxu Meng, Xianglong Kong
155 159
164 168
172
Maintaining Packet Order for the Parallel Switch Yuguo Dong, Binqiang Wang, Yunfei Guo, Jiangxing Wu
176
Grid-Based Process Simulation Technique and Support System Hui Gao, Li Zhang
180
Some Grid Automata for Grid Computing Hao Shen, Yongqiang Sun
184
The Cooperation of Virtual Enterprise Supported by the Open Agent System Zhaolin Yin, Aijuan Zhang, Xiaobin Li, Jinfei Sun The Granularity Analysis of MPI Parallel Programs Wei-guang Qiao, Guosun Zeng NGG: A Service-Oriented Application Grid Architecture for National Geological Survey Yu Tang, Kaitao He, Zhen Xiang, Yongbo Zhang, Ning Jing
188 192
196
Integration of the Distributed Simulation into the OGSA Model Chuanfu Zhang, Yunsheng Liu, Tong Zhang, Yabing Zha
200
An Extendable Grid Simulation Environment Based on GridSim Efeng Lu, Zhihong Xu, Jizhou Sun
205
XXVIII
Table of Contents, Part I
The Architecture of Traffic Information Grid Zhaohui Zhang, Qing Zhi, Guosun Zeng, Changjun Jiang
209
Construction Scheme of Meteorological Application Grid (MAG) Xuesheng Yang, Weiming Zhang, Dehui Chen
213
OGSA Based E-learning System: An Approach to Build Next Generation of Online Education Hui Wang, Xueli Yu, Li Wang, Xu Liu Multimedia Delivery Grid: A Novel Multimedia Delivery Scheme ZhiHui Lv, Jian Yang, ShiYong Zhang, YiPing Zhong The System for Computing of Molecule Structure on the Computational Grid Environment Yongmei Lei, Weimin Xu, Bingqiang Wang An Efficient Parallel Crawler in Grid Environment Shoubin Dong, Xiaofeng Lu, Ling Zhang, Kejing He The Development and Application of Numerical Packages Based on NetSolve Haiying Cheng, Wu Zhang, Yunfu Shen, Anping Song
217 221
225 229
233
Grid-Based Biological Computation Service Environment Jing Zhu, Guangwen Yang, Weimin Zheng, Tao Zhu, Meiming Shen, Li’an Qiao, Xiangjun Liu
237
CIMES: A Collaborative Image Editing System for Pattern Design Xianghua Xu, Jiajun Bu, Chun Chen, Yong Li
242
Campus Grid and Its Application Zhiqun Deng, Guanzhong Dai
247
The Realization Methods of PC Cluster Experimental Platform in Linux Jiang-ling Zhang, Shi-jue Zheng, Yang Qing
251
Coarse-Grained Distributed Parallel Programming Interface for Grid Computing Yongwei Wu, Qing Wang, Guangwen Yang, Weiming Zheng
255
User Guided Parallel Programming Platform Yong Liu, Xinda Lu, Qianni Deng A High-Performance Intelligent Integrated Data Services System in Data Grid Bin Huang, Xiaoning Peng, Nong Xiao, Bo Liu
259
262
Table of Contents, Part I
Architecting CORBA-Based Distributed Applications Min Cao, Jiannong Cao, Geng-Feng Wu, Yan-Yan Wang
XXIX
266
Design of NGIS: The Next Generation Internet Server for Future E-society Chong-Won Park, Myung-Joon Kim, Jin-Won Park
269
Video-on-Demand System Using Multicast and Web-Caching Techniques SeokHoon Kang
273
Session 2: Peer to Peer Computing PeerBus: A Middleware Framework towards Interoperability among 277 P2P Data Sharing Systems Linhao Xu, Shuigeng Zhou, Keping Zhao, Weining Qian, Aoying Zhou Ptops Index Server for Advanced Search Performance of P2P System with a Simple Discovery Server Boon-Hee Kim, Young-Chan Kim
285
Improvement of Routing Structure in P2P Overlay Networks Jinfeng Hu, Yinghui Wu, Ming Li, Weimin Zheng
292
Overlay Topology Matching in P2P Systems Yunhao Liu, Xiao Li, Lionel M. Ni, Yunhuai Liu
300
Effect of Links on DHT Routing Algorithms Futai Zou, Liang Zhang, Yin Li, Fanyuan Ma
308
A Peer-to-Peer Approach to Task Scheduling in Computation Grid Jiannong Cao, Oscar M.K. Kwong, Xianbing Wang, Wentong Cai
316
Efficient Search in Gnutella-Like “Small-World” Peer-to-Peer Systems Dongsheng Li, Xicheng Lu, Yijie Wang, Nong Xiao
324
Dominating-Set-Based Searching in Peer-to-Peer Networks Chunlin Yang, Jie Wu
332
GFS-Btree: A Scalable Peer-to-Peer Overlay Network for Lookup Service Qinghu Li, Jianmin Wang, Jiaguang Sun
340
An Approach to Content-Based Approximate Query Processing in Peer-to-Peer Data Systems Chaokun Wang, Jianzhong Li, Shengfei Shi
348
A Hint-Based Locating and Routing Mechanism in Peer-to-Peer File Sharing Systems Hairong Jin, Shanping Li, Tianchi Ma, Liang Qian
356
XXX
Table of Contents, Part I
Content Location Using Interest-Based Subnet in Peer-to-Peer System Guangtao Xue, Jinyuan You, Xiaojian He
363
Trust and Cooperation in Peer-to-Peer Systems Junjie Jiang, Haihuan Bai, Weinong Wang
371
A Scalable Peer-to-Peer Lookup Model Haitao Chen, Chuanfu Xu, Zunguo Huang, Huaping Hu, Zhenghu Gong
379
Characterizing Peer-to-Peer Traffic across Internet Yunfei Zhang, Lianhong Lei, Changjia Chen
388
Improving the Objects Set Availability in the P2P Environment by Multiple Groups Kang Chen, Shuming Shi, Guangwen Yang, Meiming Shen, Weimin Zheng
396
PBiz: An E-business Model Based on Peer-to-Peer Network Shudong Chen, Zengde Wu, Wei Zhang, Fanyuan Ma
404
P2P Overlay Networks of Constant Degree Guihai Chen, Chengzhong Xu, Haiying Shen, Daoxu Chen
412
An Efficient Contents Discovery Mechanism in Pure P2P Environments In-suk Kim, Yong-hyeog Kang, Young Ik Eom Distributed Computation for Diffusion Problem in a P2P-Enhanced Computing System Jun Ni, Lili Huang, Tao He, Yongxiang Zhang, Shaowen Wang, Boyd M. Knosp, Chinglong Lin Applications of Peer to Peer Technology in CERNET Chang-ji Wang, Jian-Ping Wu
420
428
436
PSMI: A JXTA 2.0-Based Infrastructure for P2P Service Management Using Web Service Registries Feng Yang, Shouyi Zhan, Fuxiang Shen
440
CIPS-P2P: A Stable Coordinates-Based Integrated-Paid-Service Peer-to-Peer Infrastructure Yunfei Zhang, Shaolong Li, Changjia Chen, Shu Zhang
446
A Multicast Routing Algorithm for P2P Networks Tingyao Jiang, Aling Zhong Leveraging Duplicates to Improve File Availability of P2P Storage Systems Min Qu, Yafei Dai, Mingzhong Xiao
452
456
Table of Contents, Part I
XXXI
Distributing the Keys into P2P Network Shijie Zhou, Zhiguang Qin, Jinde Liu
460
SemanticPeer: An Ontology-Based P2P Lookup Service Jing Tian, Yafei Dai, Xiaoming Li
464
Authentication and Access Control in P2P Network Yuqing Zhang, Dehua Zhang
468
Methodology Discussion of Grid Peer-Peer Computing Weifen Qu, Qingchun Meng, Chengbing Wei
471
PipeSeeU: A Scalable Peer-to-Peer Multipoint Video Conference System Bo Xie, Yin Liu, Ruimin Shen, Wenyin Liu, Changjun Jiang
475
Session 3: Grid Architectures Vega Grid: A Computer Systems Approach to Grid Research Zhiwei Xu, Wei Li RB-GACA: A RBAC Based Grid Access Control Architecture Weizhong Qiang, Hai Jin, Xuanhua Shi, Deqing Zou, Hao Zhang
480
487
GriDE: A Grid-Enabled Development Environment 495 Simon See, Jie Song, Liang Peng, Appie Stoelwinder, Hoon Kang Neo Information Grid Toolkit: Infrastructure of Shanghai Information Grid Xinhua Lin, Qianni Deng, Xinda Lu
503
On-Demand Services Composition and Infrastructure Management Jun Peng, Jie Wang
511
GridDaen: A Data Grid Engine Nong Xiao, Dongsheng Li, Wei Fu, Bin Huang, Xicheng Lu
519
Research on Security Architecture and Protocols of Grid Computing System Xiangming Fang, Shoubao Yang, Leitao Guo, Lei Zhang
529
A Multi-agent System Architecture for End-User Level Grid Monitoring Using Geographic Information Systems (MAGGIS): Architecture and Implementation Shaowen Wang, Anand Padmanabhan, Yan Liu, Ransom Briggs, Jun Ni, Tao He, Boyd M. Knosp, Yasar Onel
536
An Architecture of Game Grid Based on Resource Router Yu Wang, Enhua Tan, Wei Li, Zhiwei Xu
544
XXXII
Table of Contents, Part I
Scalable Resource Management and Load Assignment for Grid and Peer-to-Peer Services Xuezheng Liu, Ming Chen, Guangwen Yang, Dingxing Wang
552
Research on the Application of Multi-agent Technology to Spatial Information Grid Yan Ren, Cheng Fang, Honghui Chen, Xueshan Luo
560
An Optimal Method of Diffusion Algorithm for Computational Grid Rong Chen, Yadong Gui, Ji Gao
568
A Reconfigurable High Availability Infrastructure in Cluster for Grid Wen Gao, Xinyu Liu, Lei Wang, Takashi Nanya
576
An Adaptive Information Grid Architecture for Recommendation System M. Lan, W. Zhou
584
Research on Construction of EAI-Oriented Web Service Architecture Xin Peng, Wenyun Zhao, En Ye
592
GridBR: The Challenge of Grid Computing S.R.R. Costa, L.G. Neves, F. Ayres, C.E. Mendonça, R.S.N. de Bragança, F. Gandour, L.V. Ferreira, M.C.A. Costa, N.F.F. Ebecken
601
Autonomous Distributed Service System: Basic Concepts and Evaluation H. Farooq Ahmad, Kashif Iqbal, Hiroki Suguri, Arshad Ali ShanghaiGrid in Action: The First Stage Projects towards Digital City and City Grid Minglu Li, Hui Liu, Changjun Jiang, Weiqin Tong, Aoying Zhou, Yadong Gui, Hao Zhu, Shui Jiang, Ruonan Rao, Jian Cao, Qianni Deng, Qi Qian, Wei Jin
608
616
Spatial Information Grid – An Agent Framework Yingwei Luo, Xiaolin Wang, Zhuoqun Xu
624
Agent-Based Framework for Grid Computing Zhihuan Zhang, Shuqing Wang
629
A Hierarchical Grid Architecture Based on Computation/Application Metadata Wan-Chun Dou, Juan Sun, Da-Gang Yang, Shi-Jie Cai
633
A Transparent-to-Outside Resource Management Framework for Computational Grid Ye Zhu, Junzhou Luo
637
Table of Contents, Part I
XXXIII
A Service-Based Hierarchical Architecture for Parallel Computing in Grid Environment Weiqin Tong, Jingbo Ding, Jianquan Tang, Bo Wang, Lizhi Cai
641
A Grid Computing Framework for Large Scale Molecular Dynamics Simulations WenRui Wang, GuoLiang Chen, HuaPing Chen, Shoubao Yang
645
Principle and Framework of Information Grid Evaluation Hui Li, Xiaolin Li, Zhiwei Xu, Ning Yang
649
Manufacturing Grid: Needs, Concept, and Architecture Yushun Fan, Dazhe Zhao, Liqin Zhang, Shuangxi Huang, Bo Liu
653
Developing a Framework to Implement Security in Web Services Fawaz Amin Alvi, Shakeel A. Khoja, Zohra Jabeen
657
Session 4: Grid Middleware and Toolkits Computing Pool: A Simplified and Practical Computational Grid Model Peng Liu, Yao Shi, San-li Li
661
Formalizing Service Publication and Discovery in Grid Computing Systems Chuliang Weng, Xinda Lu, Qianni Deng
669
An Improved Solution to I/O Support Problems in Wide Area Grid Computing Environments Bin Wang, Ping Chen, Zhuoqun Xu
677
Agora: Grid Community in Vega Grid Hao Wang, Zhiwei Xu, Yili Gong, Wei Li
685
Sophisticated Interaction – A Paradigm on the Grid Xingwu Liu, Zhiwei Xu
692
A Composite-Event-Based Message-Oriented Middleware Pingpeng Yuan, Hai Jin
700
An Integration Architecture for Grid Resources Minglu Li, Feilong Tang, Jian Cao
708
Component-Based Middleware Platform for Grid Computing Jianmin Zhu, Rong Chen, Guangnan Ni, Yuan Liu
716
Grid Gateway: Message-Passing between Separated Cluster Interconnects Wei Cui, Jie Ma, Zhigang Huo
724
XXXIV
Table of Contents, Part I
A Model for User Management in Grid Computing Environments Bo Chen, Xuebin Chi, Hong Wu GSPD: A Middleware That Supports Publication and Discovery of Grid Services Feilong Tang, Minglu Li, Jian Cao, Qianni Deng, Jiadi Yu, Zhengwei Qi Partially Evaluating Grid Services by DJmix Hongyan Mao, Linpeng Huang, Yongqiang Sun Integrated Binding Service Model for Supporting Both Naming/Trading and Location Services in Inter/Intra-net Environments Chang-Won Jeong, Su-Chong Joo, Sung-Kook Han
732
738
746
754
Personal Grid Running at the Edge of Internet Bingchen Li, Wei Li, Zhiwei Xu
762
Grid Workflow Based on Performance Evaluation Shao-hua Zhang, Yu-jin Wu, Ning Gu, Wei Wang
770
Research on User Programming Environment in Grid Ge He, Donghua Liu, Zhiwei Xu, Lin Li, Shengliang Xu
778
The Delivery and Accounting Middleware in the ShanghaiGrid Ruonan Rao, Baiyan Li, Minglu Li, Jinyuan You Applying Agent into Web Testing and Evolution Baowen Xu, Lei Xu, Jixiang Jiang
786 794
Experiences on Computational Program Reuse with Service Mechanism Ping Chen, Bin Wang, Guoshi Xu, Zhuoqun Xu
799
Research and Implementation of the Real-Time Middleware in Open System Jian Peng, Jinde Liu, Tao Yang
803
An Object-Oriented Petri Nets Based Integrated Development Environment for Grid-Based Applications Hongyi Shi, Aihua Ren
809
Some Views on Building Computational Grids Infrastructure Bo Dai, Guiran Chang, Wandan Zeng, Jiyue Wen, Qiang Guo
813
Research on Computing Grid Software Architecture Changyun Li, Gansheng Li, Yin Li
817
Table of Contents, Part I
XXXV
Research on Integrating Service in Grid Portal Zheng Feng, Shoubao Yang, Shanjiu Long, Dongfeng Chen, Leitao Guo
821
GSRP: An Application-Level Protocol for Grid Environments Zhiqiang Hou, Donghua Liu, Zhiwei Xu, Wei Li
825
Towards a Mobile Service Mechanism in a Grid Environment Weiqin Tong, Jianquan Tang, Liang Jin, Bo Wang, Yuwei Zong
829
Mobile Middleware Based on Distributed Object Song Chen, Shan Wang, Ming-Tian Zhou
833
Session 5: Web Security and Web Services On the Malicious Participants Problem in Computational Grid Wenguang Chen, Weimin Zheng, Guangwen Yang
839
Certificate Validation Scheme of Open Grid Service Usage XKMS Namje Park, Kiyoung Moon, Sungwon Sohn, Cheehang Park
849
Distributed IDS Tracing Back to Attacking Sources Wu Liu, Hai-Xin Duan, Jian-Ping Wu, Ping Ren, Li-Hua Lu
859
The Study on Mobile Phone-Oriented Application Integration Technology of Web Services Luqun Li, Minglu Li, Xianguo Cui
867
Group Rekeying Algorithm Using Pseudo-random Functions and Modular Reduction Josep Pegueroles, Wang Bin, Miguel Soriano, Francisco Rico-Novella
875
Semantics and Formalizations of Mission-Aware Behavior Trust Model for Grids Minglu Li, Hui Liu, Lei Cao, Jiadi Yu, Ying Li, Qi Qian, Wei Jin
883
Study on a Secure Access Model for the Grid Catalogue Bing Xie, Xiao-Lin Gui, Qing-Jiang Wang
891
Modeling Trust Management System for Grids Baiyan Li, Wensheng Yao, Jinyuan You
899
Avoid Powerful Tampering by Malicious Host Fangyong Hou, Zhiying Wang, Zhen Liu, Yun Liu
907
Secure Grid-Based Mobile Agent Platform by Instance-Oriented Delegation Tianchi Ma, Shanping Li
916
XXXVI
Table of Contents, Part I
Authenticated Key Exchange Protocol Secure against Offline Dictionary Attack and Server Compromise Seung Bae Park, Moon Seol Kang, Sang Jun Lee
924
StarOTS: An Efficient Distributed Transaction Recovery Mechanism in the CORBA Component Runtime Environment Yi Ren, Jianbo Guan, Yan Jia, Weihong Han, Quanyuan Wu
932
Web Services Testing, the Methodology, and the Implementation of the Automation-Testing Tool Ying Li, Minglu Li, Jiadi Yu
940
Composing Web Services Based on Agent and Workflow Jian Cao, Minglu Li, Shensheng Zhang, Qianni Den
948
Structured Object-Z Software Specification Language Xiaolei Gao, Huaikou Miao, Yihai Chen
956
Ontology-Based Intelligent Sensing Action in Golog for Web Service Composition Zheng Dong, Cong Qi, Xiao-fei Xu
964
The Design of an Efficient Kerberos Authentication Mechanism Associated with Directory Systems Cheolhyun Kim, Yeijin Lee, Ilyong Chung
972
A Multi-agent Based Architecture for Network Attack Resistant System Jian Li, Guo-yin Zhang, Guo-chang Gu
980
Design and Implementation of Data Mapping Engine Based on Multi-XML Documents Yu Wang, Liping Yu, Feng Jin, Yunfa Hu
984
Research on the Methods of Search and Elimination in Covert Channels Chang-da Wang, Shiguang Ju, Dianchun Guo, Zhen Yang, Wen-yi Zheng Design and Performance of Firewall System Based on Embedded Computing Yuan-ni Guo, Ren-fa Li OGSA Security Authentication Services Hongxia Xie, Fanrong Meng Detecting Identification of a Remote Web Server via Its Behavioral Characteristics Ke-xin Yang, Jiu-bin Ju
988
992 996
1000
Table of Contents, Part I
Access Control Architecture for Web Services Shijin Yuan, Yunfa Hu Formalizing Web Service and Modeling Web Service-Based System Based on Object Oriented Petri Net Xiaofeng Tao, Changjun Jiang
XXXVII
1004
1008
Report about Middleware Beibei Fan, Shisheng Zhu, Peijun Lin
1012
Grid Security Gateway on RADIUS and Packet Filter Jing Cao, BingLiang Lou
1017
A Security Policy Implementation Model in Computational GRID Feng Li, Junzhou Luo
1021
An Approach of Building LinuxCluster-Based Grid Services Yu Ce, Xiao Jian, Sun Jizhou
1026
Dynamic E-commerce Security Based on the Web Services Gongxuan Zhang, Guowei Zuo
1030
Standardization of Page Service Using XSLT Based on Grid System Wanjun Zhang, Yi Zeng, Wei Dong, Guoqing Li, Dingsheng Liu
1034
Secure Super-distribution Protocol for Digital Rights Management in Unauthentic Network Environment Zhaofeng Ma, Boqin Feng
1039
X-NIndex: A High Performance Stable and Large XML Document Query Approach and Experience in TOP500 List Data Shaomei Wu, Xuan Li, Zhihui Du
1043
The Analysis of Authorization Mechanisms in the Grid Shiguang Ju, Zhen Yang, Chang-da Wang, Dianchun Guo
1047
Constructing Secure Web Service Based on XML Shaomin Zhang, Baoyi Wang, Lihua Zhou
1051
ECC Based Intrusion Tolerance for Web Security Xianfeng Zhang, Feng Zhang, Zhiguang Qin, Jinde Liu
1055
Design for Reliable Service Aggregation in an Architectural Environment Xiaoli Zhi, Weiqin Tong The Anatomy of Web Services Hongbing Wang, Yuzhong Qu, Junyuan Xie
1059 1063
XXXVIII
Table of Contents, Part I
Automated Vulnerability Management through Web Services H. T. Tian, L.S. Huang, J.L. Shan, G.L. Chen
1067
Optimizing Java Based Web Services by Partial Evaluation Lin Lin, Linpeng Huang, Yongqiang Sun
1071
An XML Based General Configuration Language: XGCL Huaifeng Qin, Xingshe Zhou
1075
Modification on Kerberos Authentication Protocol in Grid Computing Environment Rong Chen, Yadong Gui, Ji Gao
1079
A Distributed Honeypot System for Grid Security Geng Yang, Chunming Rong, Yunping Dai
1083
Web Security Using Distributed Role Hierarchy Gunhee Lee, Hongjin Yeh, Wonil Kim, Dong-Kyoo Kim
1087
User Authentication Protocol Based on Human Memorable Password and Using ECC Seung Bae Park, Moon Seol Kang, Sang Jun Lee New Authentication Systems Seung Bae Park, Moon Seol Kang, Sang Jun Lee
1091 1095
Web Proxy Caching Mechanism to Evenly Distribute Transmission Channel in VOD System Backhyun Kim, Iksoo Kim, SeokHoon Kang
1099
Author Index
1103
Synthetic Implementations of Performance Data Collection in Massively Parallel Systems Chu J. Jong1 and Arthur B. Maccabe2 1
School of Information Technology, Illinois State University, IL, USA
[email protected]
2
Department of Computer Science, University of New Mexico, NM USA
[email protected]
Abstract. Most performance tools that run on Massively Parallel (MP) systems do not scale up as the number of nodes increases. We studied the scalability problem of MP system performance tools and proposed a solution, replacing the two-level data collection structure by hierarchal one. To demonstrate that hierarchical data collection structure solves the scalability problem, we synthesized an implementation model to implement the performance data collection in MP systems. This paper presents our synthetic implementation results. Keywords: Data collection, response time, split node, performance knee.
1
Introduction
Complex applications, such as genetic analysis, material simulation, and climate modeling[8], require high performance and high computation resources to generate results. MP systems, built with thousands processors and huge amount of memory, meet these applications’ needs1. The effectiveness of using the MP system computation power mainly depends on the user’s knowledge and sometimes on the compilers or system performance tools. In the past years, developers have made significant efforts to parallel performance tools. Recent work showed that many areas, such as reducing overheads[3], improving accuracies[10], minimizing perturbations[9], and increasing convenience[5], have been improved except the tool’s scalability. We use the response time, time between issuing a user command and a reply, to measure the performance of a tool. The results of performance tools are based on the performance data collection and processing. Two main factors contribute to the response time and they are: effective processor utilization and balanced point [6]. In MP systems, when the workload incurred by workers exceeds the 1
ASCI project: The Red had 9,298 Pentium Xeon processors; the Blue-Pacific composed 1464 RS/6000 nodes with 4 CPUs; the Blue-Mountain had 256 MIPS R10000 processors; and the BlueGene/L will have 130,000 advanced microprocessors to achieve 367 teraflops.
M. Li et al. (Eds.): GCC 2003, LNCS 3033, pp. 1–9, 2004. © Springer-Verlag Berlin Heidelberg 2004
2
C.J. Jong and A.B. Maccabe
server’s balanced point, the server starts thrashing and that causes exponential processor utilization drop and response time increase. Since most performance tools use two-level structure (one server and workers) to collect data, the workload of the server is proportional to the number of workers. When the number of workers reaches the server’s limit, thrashing occurs. A level hierarchical data collection structure (one server, workers, and two or more worker-servers) allows worker-servers share the workload to prevent server thrashing. Thus increases the total number of workers significantly. In theory, the maximum numbers of workers can be handled by a single server without thrashing are: in a two-level data collection structure and similar to in a level hierarchical data collection structure. and are ratios of network throughput, memory size, and processing power between server and workers respectively. Although some systems provide large ratios [4] to accommodate more workers, and are bounded by the system capacities.
2
Previous Work – Response Time Simulation
We built a time driven event simulator to simulate the response time behaviors for both data collection structures. From our simulation results, we concluded that a hierarchical data collection structure eliminates the response time knee (exponential increasing) that two-level data collection structures cannot avoid [7].
3
Response Time Implementation
We used a small cluster of 8 Pentium III 500 MHz PCs to construct our implementation model. We wrote MPI implementation programs in C run on Linux with customized kernel modules. We used a node splitting mechanism, to produce a larger virtual node cluster. The is a virtualization mechanism that splits a physical node into a number of virtual nodes. The basic principle of is to divide resources of a physical node into equivalent slices and group one slice from each divided resource to form a virtual node (processor). Theoretically the value of can be arbitrary chosen, the reality is that the more virtual processors, the higher the system overheads and the heavier the channel workload. We applied to seven PCs. Virtual processors are workers or workerservers, the un-split PC is the server. Applying to seven PCs, we built a virtual processor cluster that is equivalent to an one-order magnitude scale down cluster of a 56 500-MHz single CPU workers and a one-GHz quad CPU server connected by a one-Gigabit network cluster.
3.1
System Modules
Our customized kernel modules allows us to have better control on the system resources. Our pseudo application, pseudo data generating/collection, and pseudo
Synthetic Implementations of Performance Data Collection
3
data processing allows us to emulate a system without side effects. Following are descriptions of our modules. System Structure. All PCs are connected by a 100-megabit Ethernet. The server processor is the un-split PC, the worker and worker-server processors are virtual processors. Both workers and worker-servers are evenly distributed among seven PCs, no two worker-servers reside in the same PC, and no two children from the same parent reside in the same PC too. System Control Units. Memory Management Unit (MMU) - Locks a block of memory for processors. It uses paging to handle memory page faults and all memory requests have to go through it. Processor Management Unit (PMU) Controls CPU cycles consumed by processors. It suspends a process when that process reaches its CPU cycle limit. Perturbation Control Unit (PCU) - Controls application perturbation rate. Implementation Software. Processors - One server processor and many worker and/or worker-server processors. A 8:1 computation ratio between server and worker (worker-server) processor and a 8:4:1 memory ratio among server, worker-servers, and workers. Server. Runs on the server processor. Major functions are: to interact with the user, set system topology, monitor process behaviors, and fulfill the user’s request. Server collects the response time and calculates global statistics, such as data gathering time, data processing time, data processing rate, and channel time. Worker. Runs on worker processor. Worker calculates local statistics, such as response time, data collection time, data processing time, data processing rate, and channel time. Worker-Server. Runs on worker-server processor. Worker-server calculates non-local statistics, such as worker-server response time, data gathering time, data processing time, data processing rate, and channel time. Application Process - Runs on all processors, it emulates the computation and I/O behavior of different applications. Data Processing Process - Invoked by data generating/collection process after data gathering completed. It processes data by reading and writing every byte at least once. It provides a hook to allow different data access methods to be used, such as sequential, offset, indexed, link list, scattered among pages or segments. The size of data access range from a single byte to several hundred bytes. Data Generating/Collection Process Invoked by performance tool process. It performs three different tasks, data generating, data gathering, and data forwarding. It generates performance data and puts them in the data buffer with other data gathered from its children. After data processing is completed, it sends the result to its parent.
4
3.2
C.J. Jong and A.B. Maccabe
The Implementations
The two-level structure has two kinds of processes: server and worker, the server can have up to 56 child workers. The hierarchical structure has three kinds of processes: server, worker-server, and worker, the server has seven child workerservers, and each worker-server can have up to seven child workers. Communications are restricted to the processes having direct parent and child relations. Following are logical actions of each of them: Processor has no parent - server. To get a user request, parse the request, send data collection command, allocate data processing buffers, wait for all data and then process data, and present results to the user. Processor has no children - worker. To wait for data collection command, allocate data buffers, store data in the buffer, and send data to its parent. Processor has both parent and children - worker-server. To wait for data collection command, allocate data buffer, send data collection command, allocate data processing buffers, store data in the buffer, wait for all data and then process data, and sends results to its parent.
4
Implementation Results
Implementations start from one server and 7 workers (worker-servers) and increment one worker per physical node at a time (to eliminate impacts from unbalanced communication delay) until the total worker number reaches to 56.
Fig. 1. Server Response Time of Two-Level Structure
Synthetic Implementations of Performance Data Collection
5
Fig. 2. Server Data Processing Rate of Two-Level Structure
4.1
Server of Two-Level Structure
Figure 1 shows the response time of the two-level data collection structure. Horizontal scale is the number of workers and vertical scale is the response time in milliseconds. Labels indicate data sizes in kilobytes collected by each worker. The total amount of data gathered by the server equals the data size multiplied by the number of workers. Figure 2 shows the data processing rates. The 256K rate drops from 2183 bytes/ms at 48 workers to 355 bytes/ms at 50 workers and the 384K rate drops from 2187 bytes/ms at 32 workers to 406 bytes/ms at 33 workers. The rate drops indicate thrashings.
6
C.J. Jong and A.B. Maccabe
Fig. 3. Average Worker Server Response Time
4.2
Worker-Server of Hierarchical Structure
Figure 3 shows the average worker-server response times, the sums of the workerserver data gathering times and the worker-server data processing times, of the hierarchical data collection structure. The worker-server data gathering time is the longest time between when a worker-server issues a data collection command and receives all data packets. The average worker-server data processing times are shown in table 1. Except one value, 0.76 ms from 8K data size, most of them are in the range between 0.30 ms/KByte and 0.42 ms/Kbyte. Either of gathering time or processing time that start non-linear incrementation will make the response time non-linear. Table 1 indicated that none of the worker-servers were thrashing. Larger values were caused by the delay from the Linux process management. Actually, thrashing occurred in the virtual node subsystem due to the TCP/IP stack and buffer contention.
4.3
Server of Hierarchical Structure
Figure 4 shows the normalized (filtering outliers and replacing subsystem by values generated from algorithms based on the data sizes) response times of the hierarchical data collection structure. Graphs are data sizes of 4, 8, 16, 32, 64, 128, 256, 384, and 512 kilobytes. The overall data collected by all processors equals the data size multiplied by the total number of processors. Figure 5 shows the corresponding data processing rates. All rates are in the range between 2700 bytes/ms and 3300 bytes/ms. They showed no evidence of the server being saturated, and thrashing did not occur.
Synthetic Implementations of Performance Data Collection
7
Fig. 4. Normalized Server Response Time
Fig. 5. Server Data Processing Rate
5
Discussion
In figure 1, 256K and 384K graphs start non-linear incrementation when the total data collected by the server reaches 12 megabytes. The same graphs in figure 2 also showed a non-linear decrementing at a total data size of 12 megabytes. From the theory of thrashing [2] [1], when all main memory are used, swapping and waiting occurs. The 12 megabyte main memory was the upper limit we set up for the server.
C.J. Jong and A.B. Maccabe
8
In figure 3, some response time start non-linear incrementation after 50 processors regardless of the data size. However, from table 1, we know that all data processing times (except the 8K) are in the range between 0.30 ms/Kbyte to 0.42 ms/Kbyte. That means that none of the worker-servers reach their thrashing point. The large response time delays must caused by their data gathering times. Although applying to creates enough virtual nodes, it causes the sub-node system thrashing since the increasing workload reaches the system’s balanced point. The only way to prevent the sub-node system thrashing is not to increase the number of but to add physical nodes (PCs) to the system. The normalized hierarchical structure graphs in figure 4 shows that the response times are increased linearly in terms of the total processors. The overall data size does not affect the response time even after it reaches the memory limit. Figure 5 shows flat server data processing rates across all data sizes. That means that the server never reaches its balance point and thrashing has been totally eliminated. We also noticed that larger data size has slightly higher data processing rate. The constant data packet overhead in favors larger data collection size
6
Conclusion and Future Work
The results of our implementations shows that the hierarchical data collection structure eliminates the response time knee that a two-level data collection structure cannot avoid. The scalability has been improved in orders of magnitude with a minor network delay penalty per level. Both structures collectes the same overall amount of data, however, the amont of data gathered by two servers are not the same. In fact, the server in the hierarchical data collection structure receives quality data instead of quantity data. We are currently porting our implementation model to a larger cluster. We are also working on instrumentation and performance data presentation. We plan to enhance our virtualization mechanisms to provide a better development environment. Our long term goal is to produce a system that helps developers develop better MP system performance tools.
References 1. W. C. L. A. Alderson and B. Randell. Thrashing in a multiprogrammed paging system. Operating Systems Techniques by Hoare and Perrott, pages 152–167, 1972. 2. P. J. Denning. The working set model for program behavior. Communication of the ACM, (5):323–333, May 1968. 3. G. Eisenhauer, B. Schroeder, K. Schwan, V. Martin, and J. Vetter. DataExchange: High Performance Communication in Distributed Laboratories. Ninth International Conference on Parallel and Distributed Computing and Systems, October 1997. 4. D. A. R. et al. Scalable Performance Analysis: The Pablo Performance Analysis Environment. IEEE Scalable Performance Libraries Conference, IEEE Service Center, Piscaataway, N.J., 1993.
Synthetic Implementations of Performance Data Collection
9
5. W. Gu, G. Eisenhauer, and K. Schwan. Falcon: On-line Monitoring and Steering of Parallel Programs. Concurrency: Practice and Experience, 1995. 6. P. B. Hansen. Operating System Principles. Prentice-Hall, Inc., Prentice-Hall, Inc., Englewood Cliffs, New Jersey, 1973. 7. C. J. Jong and A. B. Maccabe. A simulator for performance tools in massively parallel system. In Postceedings of The International Conference on Parallel and Distributed Processing Techniques and Applications, June 2003. 8. T. Kindler, K. Schwan, D. Silva, M. Trauner, and F. Alyea. A Paraller Spectral Model for Atmospheric Transport Processes. Concurrency: Practice and Experience, 8:639–666, November 1996. 9. C. Liao, M. Martonosi, and D. W. Clark. Performance Monitoring in a MyrinetConnected Shrimp Cluster. In Symposium on Parallel and Distributed Tools, pages 21–29, P.O. Box 12114 Church Street Station, New York, N.Y. 10257, August 1998. The Association for Computing Machinery. 10. R. L. Ribler, J. S. Vetter, H. Simitci, and D. A. Reed. Autopilot: Adaptive Control of Distributed Applications. Proceedings of the 7th IEEE Symposium on HighPerformance Distributed Computing, Chicago, IL, July 1998.
GMA+ – A GMA-Based Monitoring and Management Infrastructure for Grid Chuan He, Zhihui Du, and Sanli Li Grid Research Group, Department of Computer Science and Technology, Tsinghua University, Beijing, China
[email protected]
Abstract. In this paper, we investigate many monitoring and management tools in Grid and other distributed systems. After focusing on the advantage and disadvantage of GMA (Grid Monitoring Architecture), we propose a new monitoring and management schema for Grid --GMA+. In GMA+, we add a close loop feedback structure to GMA and provides interfaces which match Grid Service standards for all its components and defines metadata for monitoring events. It is a novel infrastructure for Grid monitoring and management with highly modularity, usability and scalability.
1 Introduction Nowadays, single PC and even HPCs can not satisfy the explosive need of high performance computing. It needs to connect various heterogeneous resources which are distributed in physical location with high speed network to solve some huge problems. Grid [1] is the extension of traditional distributed computing technology, it waves resources in LAN or WAN and constructs dynamic VO(Virtual Organization) to implement secure and coordinated sharing of resources between persons, organizations and resources. The target of Grid monitoring and management is monitoring resources in Grid for fault detection, performance analysis, performance tuning, load balancing and scheduling. Compared with traditional distributed systems, Grid is more complicated in architecture, larger in scale and more distributed in physical location. So it is more urgent to construct a monitoring and management system with high performance, high scalability and high stabilization to do automatic management in Grid environment.
2 Related Works There have already been many monitoring tools in traditional distributed systems. However, those existing tools can not completely meet the needs of Grid monitoring and management.
M. Li et al. (Eds.): GCC 2003, LNCS 3033, pp. 10–17, 2004. © Springer-Verlag Berlin Heidelberg 2004
GMA+ – A GMA-Based Monitoring and Management Infrastructure for Grid
11
NetLogger [2], Paradyn [3], AIMS [4], Gloperf [5] and SPI [6] collect data from distributed systems and then analyze the data using special tools. Those tools generate monitoring data with unique format, which constrains their cooperation with other systems. Globus HBM [7] periodically sends “Heart Beat” to a centralized collection system in order to do fault detection in a distributed environment. The centrality of HBM make it difficult for extending, what’s more, HBM relies on local information so that it can not make forecast and management from the whole point of view. NWS [8] and DSRT [9] only monitor some specific resources (network bandwidth, CPU) but are not adaptive for new resources. RMON [10] and Autopilot [11] implement intelligent and dynamic control by using technology like reactive circuits. JAMM [12] is another similar system, but it only can be used in Java program. The shortcoming of those systems is that they are bound to given programming languages. So they can’t cooperate with other systems. SNMP-based tools are not suitable for Grid monitoring and management which runs on WAN and requires high performance. In addition, those toolkits do not provide application level monitoring.
3 GMA GMA [13] is an architecture presented and supported by GGF. It aims to constitute standards for grid monitoring and make existing systems interoperate.
3.1 Architecture GMA first adopts a producer-consumer model in Grid monitoring. All monitoring information are events which are base on timestamp for storing and transferring.
Fig. 1. Grid Monitoring Architecture
12
C. He, Z. Du, and S. Li
Fig. 1. shows the architecture of GMA. GMA is consisted of four key components: 1. Sensors. A sensor is any program which can generate time-stamped monitoring events. For example, we have sensors that monitor CPU usage, memory usage, and network usage. 2. Producers. Producers is the source of performance events. Producers send events to consumers through their interfaces and one producer can provide several independent interfaces for sending different events. 3. Consumers. Applications who receive and consume monitoring events. Consumers can not only run at the same computer with the producer, but can run at remote computers also. 4. Directory Service. The directory service in Grid likes a registry. Producers and consumers publish their location information in the directory service. When a producer and a consumer find each other through directory services, the monitoring procedure runs only between the producer and the consumer, but has no relationship with the directory service at all. All monitoring information in GMA are events. Another important contribution of GMA is that it abstracts three event passing patterns between producers and consumers. They are: Publishing/subscribing pattern, Query/response pattern and Notification pattern. The protocol between producers and consumers are not defined in GMA, it can be implemented in many ways. For example: using SOAP/HTTP, LDAP or XML/BXXP. What’s more, we also can use one protocol in controlling but another distinct protocol in transmission under different situations.
3.2 Current Status of GMA and Its Limitations R-GMA [14] makes use of relation database to offer directory service instead of LDAP. But it can not be suitable for huge data transaction, especially when facing outburst of information. GridMon [15] is the first prototype of Grid monitoring in China. Although it applies GMA thoughts partially, it is not entirely base on GMA model. In fact, GridMon uses LDAP as directory service and only realizes the query/ response model. It defines a scalable format for monitoring events, yet it is too simple to serve a complex system like Grid. GMA presents a highly scalable and flexible architecture for grid monitoring. However, there are still some limitations in GMA that should be improved in the following ways: 1. In GMA, the directory service should be universal enough to support LDAP, relation database and P2P distributed directory storage rather than restricted to LDAP. 2. There is no definition of the metadata model of monitoring information in GMA system. Using XML schema is a good way to define it and make the system more suitable for monitoring various kinds of new resources. 3. Producers and consumers in GMA system need to provide standard external interfaces. Moreover, considering that Grid is a wide area system, we should encapsulate those interfaces as Web Service or Grid Service proposed in OGSA [16].
GMA+ – A GMA-Based Monitoring and Management Infrastructure for Grid
13
4. GMA only offers monitoring functions but does not integrate monitoring with management. In a practical system, GMA ought to be joined into the structure like close loop feedback in order to combine monitoring and management together.
4 GMA+ 4.1 Architecture According to the shortages of GMA mentioned above, we give an improved Grid Monitoring system—GMA+ based on GMA. The architecture of GMA+ is showed in Fig. 2. We classify all events in GMA+ into 2 types: M-Event for monitoring events and C-Event for controlling events. We also add controller and actuator as 2 new parts.
Fig. 2. The architecture of GMA+
Actually, the controller consists of a consumer, a producer and its controlling logic. The controller can analyze various events, then it will generate new M-Events and CEvents, in the end, it will send corresponding C-Events to the actuator. The actuator receives the evens and adjusts the status of Grid resources dynamically. Typically, the functions of the controller can be: validating the monitoring events, classifying the events, decision-making system and etc. In GMA+, many controllers can be connected as a chain, so sensor->producer-> controller...->controller->actuator forms a local closed loop structure. Fig. 3. shows three different types of controller: controller1 filters M-Event; controller2 analyzes the receiving C-Events and M-Events and generates C-Events for controlling; controller3 is a more complicated one for decision-making.
4.2 Components in GMA+ The interfaces of all GMA+ components follow Grid Service Specification in OGSA. Grid Services are more suitable for use in a Grid environment than Web Services,
14
C. He, Z. Du, and S. Li
Fig. 3. Different Controllers in GMA+
because Web Services are mostly persistent, while services in Grid are mainly volatile. Another important reason is that Grid Service has a soft lifetime management to release useless resources automatically, but Web Service can not solve that problem easily. In a word, adopting Grid Service in Grid monitoring and management has many benefits such as standardization, easy to distribute, easy for cooperating, independent for platforms and programming languages.
4.2.1 Sensors We implement four different types of sensors in GMA+. They are host sensors, network sensors, process sensors and application sensors. In a real Grid, there may be more kinds of sensors than what we have defined. For extension, we have given the metadata model for all events in GMA+, encapsulated sensors with Grid Service interface and defined the programming model for how to develop a new sensor. Those all guarantee that new sensors could be added into GMA+ easily. 4.2.2 Consumers GMA+ offers many kinds of querying and analyzing tools as consumers. They mainly contains: 1. Storing archives. Although the monitoring events in Grid is mainly useful in short period of time, it still needs a storing archive to keep those events for later use. We implement a distributed storage system to archive the monitoring events in GMA+ using LDAP and RDBMS. 2. Real-time monitoring tools. The tools are used to monitor real-time data. 3. Analyzing tools. These tools are used to analyze the data which is kept in the storing archives. 4. Query and analysis portal. GMA+ also provides a web portal to do query and analysis. In GMA+, we define several types of users with different privileges to do monitoring and management.
GMA+ – A GMA-Based Monitoring and Management Infrastructure for Grid
15
4.2.3 Controller and Actuator In GMA+, we just implement two simple controllers: C-Controller and A-Controller to demonstrate the usage of controllers and actuators. C-Controller is used to classify monitoring events. A-Controller is used to analyze the monitoring events of computers (the computing resources in Grid). If the load or temperature of CPU exceeds the threshold, A-Controller will notify the corresponding actuator to report an alarm. Fig. 4. shows the collaboration sequence of sensors, controllers and actuators.
Fig. 4. Sequence diagram of sensors, controllers and actuators
4.3 Directory Service There are some traditional directory systems such as LDAP, DNS, DEC’s GNS [17], Intentional Naming Systems [18] and Active Names [19]. Nevertheless, they may meet similar problems when used directly in the Grid. 1. These directory services can not serve for the storage of a great number of data; as a result they can not satisfy the extension of Grid. 2. These services are not suitable for Grid monitoring data which needs to be updated frequently. They are only fit for the frequently-asked queries. 3. These services are not able to support queries related with multi-objects, for example, function “Join” in SQL. Recently, more methods were put forward to solve the directory service problems, such as using RDBMS [20]. But we have to see that there are not any mature solutions. As all components in GMA+ are Grid Services, the directory service in GMA+ is used to index Grid Services. We use WSIL to implement the directory. WSIL has a lightweight, distributed model: the XML documents which describe Web Services can be stored at any location; independent documents can connect with others through URL. Every component in GMA+ (producer, consumer, controller, sensor, and actuator) contains three parts: Grid Service interfaces, service entity and service description in WSIL. The distributed WSIL documents in the network construct a logical directory service. Fig. 5. shows the architecture of directory service in GMA+.
16
C. He, Z. Du, and S. Li
Fig. 5. Directory Service using WSIL
4.4 Metadata and Protocol Monitoring and management events are widely used in GMA+. So it is important to define the metadata of events with high scalability. We use XML Schema to define the metadata for various events. The metadata of events do not rely on transferring protocol. In GMA+, we use SOAP as the transfer protocol. SOAP is a lightweight protocol base on HTTP and XML. It is a protocol supporting RPC through HTTP and has many benefits such as: high scalability, easy to understand and easy to deploy.
5 Next Step Work In the future, we prepare to add more adapters and sensors in GMA+ in order to monitor and manage more Grid resources. And we also plan to implement more complicated controllers and actuators with powerful algorithm in order to do intelligent control and management in Grid.
References 1. 2.
3.
Foster and C. Kesselman, “The Grid: Blueprint for a New Computing Infrastructure”, Morgan Kaufmann Publishers, San Francisco, CA, 1999. Brian Tierney, William Jonston, Brian Crowley, Gary Hoo, Chris Brooks, and Dan Gunter, “The NetLogger Methodology for High Performance Distributed Systems Performance Analysis”, Proc. of IEEE High Performance Distributed Computing Conference (HPDC7), July 1998. Barton P. Miller, Jonathan M. Cargille, R. Bruce Irvin, Krishna Kunchithapadam, Mark D. Callaghan, Jeffrey K. Hollingsworth, Karen L. Karavanic, and Tia Newhall, “The Paradyn Parallel Performance Measurement Tool”, IEEE Computer, 28(11), November 1995, pp. 37–46.
GMA+ – A GMA-Based Monitoring and Management Infrastructure for Grid 4.
5.
6.
7. 8. 9. 10.
11.
12. 13.
14. 15.
16.
17. 18.
19.
20.
17
Jerry C. Yan, “Performance Tuning with AIMS—An Automated Instrumentation and Monitoring System for Multicomputers”, Proc. of the Twenty-Seventh Hawaii Int. Conf. on System Sciences, Hawaii, January 1994. Craig A. Lee, Rich Wolski, Ian Foster, Carl Kesselman, and James Stepanek, “A Network Performance Tool for Grid Environments”, Proc. of SC’99, Portlan, Oregon, Nov. 13–19, 1999. Devesh Bhatt, Rakesh Jha, Todd Steeves, Rashmi Bhatt, and David Wills, “SPI: An Instrumentation Development Environment for Parallel/Distributed Systems”, Proc. of Int. Parallel Processing Symposium, April 1995. http://www.globus.org/hbm/heartbeat_spec.html R. Wolski et al., “The Network Weather Service: A Distributed Resource Performance Forecasting Service for Metacomputing”, Journal of Future Generation Systems, 1998. H. Chu and K. Nahrstedt, “CPU Service Classes for Multimedia Applications,” Proc. of IEEE Multimedia Computing and Applications, Florence, Italy, June 1999. Clifford W. Mercer and Ragunathan Rajkumar, “Interactive Interface and RTMach Support for Monitoring and Controlling Resource Management”, Proceedings of Real-Time Technology and Applications Symposium, Chicago, Illinois, May 15-17, 1995, pp. 134– 139. J.S. Vetter and D.A. Reed, “Real-time Monitoring Adaptive Control and Interactive Steering of Computational Grids”, The International Journal of High Performance Computing Applications (2000) Chris Brooks, Brian Tierney, and William Johnston, “Java Agents for Distributed System Management”, LBNL Technical Report, Dec. 1997. B. Tierney, R. Aydt, D. Gunter et al. “A Grid Monitoring Architecture (2002)”, GGF Performance Working Group, http://www-didc.lbl.gov/GGF-PERF/GMA-WG/ papers/GWD-GP-16-1.pdf Fisher.S. “Relational Grid Monitoring Architecture Package”, http://hepunx.rl.ac.uk/grid/wp3/releases.html Li Cha, Zhiwei Xu, Guozhang Lin, “A Grid monitoring system using LDAP”, Computer science and technology department, Beijing Institute of Technology. Journal of Computer Research and Development. August, 2002. Foster, C. Kesselman, J. Nick, S. Tuecke, “The Physiology of the Grid: An Open Grid Services Architecture for Distributed Systems Integration”, Open Grid Service Infrastructure WG, Global Grid Forum, June 22, 2002. Lampson, B. W., “Designing a global name service”, In 4th ACM Symposium on Principles of Distributed Computing (August 1986). Adjie-Winoto, W., Schwartz, E., Balakrishnan, H., and Lilley, J. “The design and implementation of an intentional naming system”, In Proceedings of the 17th ACM Symposium on Operating System Principles (December 199). Vahdat A., Dahlin M., Anderson T. and Aggarwal A. “Active names: flexible location and transport of wide-area resources”, In USENIX Symposium on Internet Technology and Systems (Oct 1999). E.F.Codd, “A relational model of data for large shared data banks”, CACM, 13(6), Jun 1970.
A Parallel Branch–and–Bound Algorithm for Computing Optimal Task Graph Schedules Udo Hönig and Wolfram Schiffmann FernUniversität Hagen, Lehrgebiet Technische Informatik I, 58084 Hagen, Germany {Udo.Hoenig|Wolfram.Schiffmann}@FernUni-Hagen.de http://www.informatik.ti1.fernuni-hagen.de/
Abstract. In order to harness the power of parallel computing we must firstly find appropriate algorithms that consist of a collection of (sub)tasks and secondly schedule these tasks to processing elements that communicate data between each other by means of a network. In this paper, we consider task graphs that take into account both, computation and communication costs. For a homogeneous computing system with a fixed number of processing elements we compute all the schedules with minimum schedule length. Our main contribution consist of parallelizing an informed search algorithm for calculating optimal schedules based on a Branch–and–Bound approach. While most recently proposed heuristics use task duplication, our parallel algorithm finds all optimal solutions under the assumption that each task is only assigned to one processing element. Compared to exhaustive search algorithms this parallel informed search can compute optimal schedules for more complex task graphs. In the paper, the influence of parameters on the efficiency of the parallel implementation will be discussed and optimal schedule lengths for 1700 randomly generated task graphs are compared to the solutions of a widely used heuristic.
1
Introduction
A task graph is a directed acyclic graph (DAG), that describes the dependencies between the parts of a parallel program [8]. In order to execute it on a cluster or grid computer, it’s tasks must be assigned to the available processing elements. Most often, the objective of solving this task graph scheduling problem is to minimize the overall computing time. The time that a task needs to compute an output by using the results from preceding tasks corresponds to the working load for the processing element to which that task is assigned. It is denoted by a node weight of the task node. The cost of communication between two tasks and is specified as an edge weight If both tasks are assigned to the same processor, the communication cost is zero. Task graph scheduling comprises two subproblems. One problem is to assign the tasks to the processors, the other problem consists of the optimal sequencing of the tasks. In this paper, we suppose a homogeneous computing environment, e.g. a cluster computer. But, even if we assume identical processing elements, the M. Li et al. (Eds.): GCC 2003, LNCS 3033, pp. 18–25, 2004. © Springer-Verlag Berlin Heidelberg 2004
A Parallel Branch–and–Bound Algorithm
19
problem to determine an optimal schedule has been proven to be NP–complete, apart from some restrained cases [8]. Thus, most researchers use heuristic approaches to solve the problem for reasonable sizes of the task graph. Three categories can be distinguished: list–based, clustering–based and duplication–based heuristics. List–based heuristics assign priority levels to the tasks and map the highest priority task to the best fitting processing element [10]. Clustering-based heuristics embrace heavily communicating tasks and assign them on the same processing element, in order to reduce the overall communication overhead[1]. Duplication-based heuristics also decrease the amount of communication while simultaneously the amount of (redundant) computation will be increased. It has been combined with both list-based [2] and cluster-based approaches [9]. In order to evaluate the quality of all those heuristics in a unified manner it would be desirable to compare the resulting schedules lengths of those heuristics to the optimal values. The parallel Branch–and–Bound algorithm proposed in this paper can be used to create a benchmark suite for this purpose. Of course, this is only feasible for task graphs of moderate size (e.g. with lower than 30 tasks). Usually, there are multiple optimal schedules that provide a solution set of the task graph scheduling problem. All these schedules are characterized by the same minimal schedule length. To compute these optimal schedules we have to search for all the possible assignments and sequences of the tasks. The simplest algorithm to compute the set of optimal schedules enumerates all possible solutions and stores only the best ones. But, even for a small number of tasks the number of solutions will be enormous. If we want to get the set of optimal schedules in an acceptable period of time and with maintainable memory requirements we have to devise a more skillful algorithm. The basic idea to shorten the effort of an exhaustive search is to perform a structured or informed search that reduces the state space. Thus, the number of schedules that have to be investigated is much smaller than the number of possible processor assignments multiplied by the number of possible sequences. In this way, an informed search can manage more complex task graphs than exhaustive search strategies. The informed search is often based on a A* algorithm ([3], [5]). In this paper, we will present a Branch–and–Bound approach and its implementation on a parallel virtual machine [4]. The paper is organized as follows. In the next section, the concepts of the Branch–and–Bound algorithm will be explained. The third section is concerned with the parallelization of that algorithm. It describes how the workload is partitioned and how load balancing will be achieved. In the fourth section, we present results and discuss the influence of various parameters on the efficiency of the parallel implementation.
2
Branch–and–Bound Algorithm
If we want to shorten the time to compute the set of optimal solutions, we are not allowed to consider every valid schedule (assignment of the tasks to the processing elements plus determination of the tasks’ starting times). Instead,
20
U. Hönig and W. Schiffmann
we have to divide the space of possible schedules into subspaces that contain partially similar solutions. These solutions should have in common that a certain number of tasks is already scheduled in the same way. The corresponding subspace contains all the schedules that are descended from the partial schedule but differ in the scheduling of the remaining tasks. Each partial schedule can be represented by a node in a decision-tree. Starting from the root, which represents the empty schedule, all possible schedules will be constructed. At any point of this construction process, we can identify a set of tasks that are ready to run and a set of idle processing elements to which those tasks can be assigned. In this way, each conceivable combination will produce a new node in the decision tree (Branch). Supposed we have an estimate for the total schedule length, we can exclude most of the nodes that are created in the Branch part of the algorithm. This estimate can be initialized by any heuristic. Here, we used the heuristic from Kasahara and Narita [6]. After the creation of a new partial schedule (node of the decision tree), we can estimate a lower bound of it’s runtime by means of it’s current schedule length and the static b-level values of the remaining (yet unscheduled) tasks. The lower bound is computed by the sum of the partial schedule length plus the maximum of the static b-level values. If is greater than we can exclude the newly created node from further investigation. By this deletion of a node (Bound) we avoid the evaluation of all the schedules that depend on the corresponding partial schedule (subspace of the search space). In this way, we accelerate the computation of the solution set for the task graph problem. As long as a node’s is lower or equal to the current we continue to expand this node in a depth-first manner. When all the tasks of the graph are scheduled, a leaf of the decision tree is reached. If we add the corresponding schedule to the set of best schedules. we clear the set of best schedules, store the new (complete) schedule into the set of best schedules and set Then we continue with the next partial schedule. The pruning scheme above is further enhanced by a selection heuristic that controls the order of the creation of new nodes. By means of this priority controlled breadth-first search we improve the threshold for pruning the decision tree as early as possible. Likewise to the Bound phase, this procedure reduces further the total number of evaluations. By proceeding as described above, all possible schedules are checked. At the end of the search procedure, the current set of best schedules represents the optimal schedules for the task graph problem.
3
The Parallel Algorithm
The parallelisation of the sequential Branch–and–Bound algorithm requires a further subdivision of the search-space into disjunct subspaces, which can be assigned to the processing units.
A Parallel Branch–and–Bound Algorithm
21
As already described in Section 2, every inner node of the decision-tree represents a partial schedule and every leaf node corresponds to a complete schedule. The branching rule used by the algorithm, guarantees that the sons of a node will represent different partial schedules. Since the schedules are generated along the timeline, a later reunification of the subtrees, rooting in these sons, is impossible. Therefore two subtrees of the decision-tree always represent disjunct subspaces of the search-space, if none of their roots is an ancestor of the other one. Another result of these thoughts is that every part of the search-space can unambiguously be identified by it’s root-node. In order to achieve a balanced assignment of the computation to the available processing units, the algorithm generates a workpool, containing a certain number of subtree-roots. This workpool is managed by a master-process, which controls the distribution of the tasks to the slave-processes. The workpool is created by means of a breadth-first-search which terminates, when a user defined number of elements is collected in the workpool. The nodes are numbered by the ordinal numbers of the nodes’ permutations. These ordinal numbers allow an unambiguous identification of the nodes. By means of the root’s ordinal number, it is possible to build the corresponding subtree. For that reason, the only information, that need to be stored in the workpool, are the ordinal numbers of the subtrees’ roots. This helps to keep the required memory small. The parallel algorithm can be partitioned into three parts, called Initialisation, Computation and Finalisation. During the Initialisation-Phase, the master launches the slave-processes and splits the whole task into a number of smaller subtasks. The number of subtasks depends on the size of the workpool, which is specified by the user. The Computation-Phase begins as soon as the master assigns a subtask to every slave1. Then, the master has to wait until it receives a message from one of the slaves which indicates that the slave has completely analysed a given subtree or that it has found an improved schedule. In the last case, the master only stores the broadcasted schedule length and the process-id of the sending slave. In the other case, it sends a new subtask to the slave if the workpool is not empty, otherwise the slave will stay idle. As soon as all subtasks are processed and all slaves are idle, FinalisationPhase will take place. The master informs all slaves about the end of the computation-process. This request is necessary, because the sending of messages appears asynchronously and it is not guaranteed, that every message that indicates a new best solution was already sent and received. Every slave receiving the finalisation message, compares the global best solution to it’s own recent results and possibly deletes it’s own suboptimal results. If the slave recognizes, that it’s own recent temporal solution is better than the global best solution, it sends an appropriate broadcast to the master and to all other slaves. Then, the slave sends the master an acknowledgement to indicate, that it finished the adjustment successfully. The master waits, until it receives an acknowledgement 1
It is required that the workpool contains more tasks than slaves.
22
U. Hönig and W. Schiffmann
from every slave. Then it requests the complete schedule from the last slave that reported to have found the best solution so far. Additionally it requests some bookkeeping information of all slaves. The slaves terminate after sending their replies. Finally, the master creates the output-file and terminates as well.
4
Results
To achieve an efficient informed search algorithm, there are some constraints that should be analysed before starting the computation of larger problems. It was found, that some of the most important constraints that influence the search-speed are independent of the given task graph. These aspects belong to the algorithm’s properties such as the size of the workpool and the number of processing elements that are involved in the search-process. Additionally, we demonstrate the suitability of our approach for the evaluation of scheduling heuristics. For this purpose, we analyse the heuristic of Kasahara and Narita [6] using a test bench of approximately 1700 task graphs.
4.1
Size of the Workpool
After it’s creation, the workpool includes the complete search space, subdivided into a user-defined number of subspaces. Apparently, the size of a subspace is determined by the number of schedules that it contains. If the number of subspaces will be increased, the size of every subspace will be reduced. In this way the workpool’s size determines the granularity of the search space and the number of schedules one slave has to analyse. Figure 1 shows how the runtime for different task graph problems depends on the size of the workpool. On the left side, we see how an increase of the workpool size can reduce the runtime on a parallel computing system with 30 processing elements. It is clearly visible that a workpool size between approx. 300 to 1200 elements (partial schedules) will be useful in this case. In contrast, we see on the right side of figure 1, that the situation for light-weight scheduling problems changes to get worse when using a parallel implementation. In this case, the minimal runtime is reached with the sequential implementation and no subtasks at all. The relative slowdown increases with the workpool’s size and might become clearly more than 100 %. Since it is difficult or even impossible to estimate the computational complexity of a schedule, the workpool size has to be chosen carefully in order to minimize the overall runtime.
4.2
Number of Processing Elements
Usually, the maximum speedup of a parallel program will be equal to the number of the available processing elements. In order to evaluate the scaling of the parallel implementation we used three task graphs that had sequential runtimes of approximately one minute each. The workpool size was set to 6000.
A Parallel Branch–and–Bound Algorithm
23
Fig. 1. Influence of the workpool’s size on the runtime. Sequential runtime on the left side diagram: 50..250s; on the right side diagram: 0,01..1,2s
Figure 2 shows the relation between the speedup-factor and the number of used processing elements. For smaller numbers of processing elements, the speedup-factor increases almost linear (for one example even a slight superlinear speedup can be recognized). If the number of processing elements gets larger than 8 the speedup differs from being linear and it begins to move to a saturation limit of approximately 16.
Fig. 2. Influence of the number of processing elements on the speedup-factor
4.3
Analysing Scheduling Heuristics
The computation of optimal schedules is a rather time-consuming process which is only possible for small to medium-size task graphs. Although most of the
24
U. Hönig and W. Schiffmann
proposed scheduling heuristics aim at large task graphs, this subsection should show, that the efficiency of those heuristics can also be analysed by considering smaller graphs for which the optimal schedule lenghts can be computed by the proposed algorithm. A test with approximately 1700 computed optimal schedules was carried out to evaluate the heuristic’s efficiency. The used graphs were generated randomly in terms of multiple possible settings of the DAGs’ properties, e.g. the connection density between the nodes. Using such a wide spread variation of task graph properties, we can be sure that the results are independent of the chosen task graph set. This way, our approach enables scientists to evaluate and compare their heuristics’ results more objectively. To demonstrate this new opportunity, we use the well-known heuristic of Kasahara and Narita, described in [6].
Table 1 shows the deviation of this heuristic’s results from the optimal schedule lengths. The heuristic finds a solution with the optimal schedule length for 57.67% of the investigated task graphs. Regarding to the other task graphs, the observed deviation from the optimal schedule length is rather low (< 10%) in 83.41% of the cases. Only 2.86% of all solutions are worse than 25%. The performance of heuristics is usually evaluated by comparing their solutions with the ones of another (well known) heuristic. We argue that it would be more meaningful to use the deviations from the optimal solutions introduced above. For this purpose we will soon release a benchmark suite that provides the optimal solutions for 36.000 randomly created task graph problems which cover a wide range of different graph properties.
5
Conclusion
In this paper we presented a parallel implementation of a Branch–and–Bound algorithm for computing optimal task graph schedules. By means of parallelization the optimization process is accelerated and thus a huge number of test cases can be investigated within a reasonable period of time. The runtime needed for the computation of an optimal schedule is highly dependent of the workpool’s size and the number of processing elements that are available for computation. In order to reduce the runtime, the size of the workpool has to be chosen carefully. A nearly linear speedup can be achieve, provided that an appropriate workpool size is used.
A Parallel Branch–and–Bound Algorithm
25
By means of the parallel Branch–and–Bound algorithm, the optimal schedules for a benchmark suite that comprises 1700 task graphs were computed. This allows for a more objective evaluation of scheduling-heuristics than comparisons between heuristics. We evaluated the solutions of the heuristic of Kasahara and Narita [6] by comparing the corresponding schedule lengths towards the optimal schedule lengths of all the 1700 test cases. The authors’ future work will include the release of a test bench, which will provide a collection of 36000 task graph problems together with their optimal schedule lengths. This benchmark suite will enable researchers to compare the performance of their heuristics with the actually best solutions. Acknowledgement. The authors would like to thank Mrs. Sigrid Preuss who contributed some of the presented results from her diploma thesis.
References 1. Aguilar, J., Gelenbe E.: Task Assignment and Transaction Clustering Heuristics for Distributed Systems, Information Sciences, Vol. 97, No. 1& 2, pp. 199–219, 1997 2. Bansal S., Kumar P., Singh K.: An improved duplication strategy for scheduling precedence constrained graphs in multiprocessor systems, IEEE Transactions on Parallel and Distributed Systems, Vol. 14, No. 6, June 2003 3. Dogan A., Özgüner F.: Optimal and Suboptimal reliable scheduling of precedenceconstrained tasks in heterogeneous distributed computing, International Workshop on Parallel Processing, p. 429, Toronto, August 21-24, 2000 4. Geist A., Beguelin A., Dongarra J., Jiang W., Mancheck R., Sunderam V.: PVM 3 Users Guide and Reference Manual, Oak Ridge National Laboratory, Tennessee 1993 5. Kafil M., Ahmad I.: Optimal Task assignment in heterogeneous distributed computing systems, IEEE Concurrency: Parallel, Distributed and Mobile Computing, pp. 42-51, July 1998 6. Kasahara, H., Narita, S.: Practical Multiprocessor Scheduling Algorithms for Efficient Parallel Processing. IEEE Transactions on Computers, Vol. C-33, No. 11, pp. 1023-1029, Nov. 1984 7. Kohler, W.H., Steiglitz, K.: Enumerative and Iterative Computational Approaches. in: Coffman, E.G. (ed.): Computer and Job-Shop Scheduling Theory. John Wiley & Sons, New York, 1976 8. Kwok, Y.-K., Ahmad, I.: Static scheduling algorithms for allocating directed task graphs to multiprocessors. ACM Computing Surveys, Vol. 31, No. 4, 1999, pp. 406–471 9. Park C.-I., Choe T.Y.: An optimal scheduling algorithm based on task duplication, IEEE Transactions on Computerss, Vol. 51, No. 4, April 2002 10. Radulescu A., van Gemund A. J.C.: Low-Cost Task Scheduling for DistributedMemory Machines, IEEE Transactions on Parallel and Distributed Systems, Vol. 13, No. 6, June 2002
Selection and Advanced Reservation of Backup Resources for High Availability Service in Computational Grid* Chunjiang Li, Nong Xiao, and Xuejun Yang School of Computer, National University of Defense Technology, Changsha, 410073 China, +86 731 4575984
[email protected]
Abstract. Resource redundancy is a primary way to improve availability for applications in computational grid. How to select backup resources for an application during the resource allocation phase and how to make advanced reservation for backup resources are challenging issues for grid environment to provide high availability service. In this paper, we proposed a backup resources selection algorithm base on resources clustering, then devised several policies for advanced reservation of backup resources. With this algorithm and these policies, the backup resource management module in grid middleware can provide resource backup service more efficiently and cost-effectively. These algorithm and policies can be implemented on the GARA system, make the QoS architecture more powerful and practical for computational grid.
1
Introduction
Grid computing [1] is a kind of distributed supercomputing, in which geographically distributed computational and data resources are coordinated for solving large-scale problems. The resources in the grid environment are wide-area distributed, heterogeneous in nature, owned by different individuals or organizations; which makes the grid a more variable and unreliable computing environment. The most common failure include machine faults in which hosts go down, and network faults where links go down. When some resources fail, the applications using such resources have to stall, waiting for the recovery of the failed resources or migration to other resources. Ways to reduce the stall-time for applications are critical for grid middleware to provide high availability service. Resource backup is such a kind of methods, that is, at the resource allocation phase, allocates redundant resources as the backup resources for the application, when some resources fail, the application’s tasks running on the failed resources can migrate to the backup resources, * This work is supported by the National Science Foundation of China under Grant No.60203016 and No.69933030; the National High Technology Development 863 Program of China under Grant No.2002AA131010. M. Li et al. (Eds.): GCC 2003, LNCS 3033, pp. 26–33, 2004. © Springer-Verlag Berlin Heidelberg 2004
Selection and Advanced Reservation of Backup Resources
27
without asking the global resources manager to reallocate resources which is time-consuming in the grid. The application in computational grid usually uses a large amount of resources, and the resources usually differ from each other on type, hardware/software architecture, and performance. So, how to select backup resources for this application is more complex than ever. The backup resources allocated for the application may not be used at all during the application running process. If making advanced reservation for all those backup resources during this phase, it is more feasible to get the resource wasted, which makes the application less cost-effective. So, it is necessary to design multiple policies for advanced reservation of backup resources. In this paper, firstly, we proposed a backup resources selection algorithm based on resources clustering. This algorithm simplified the selection process by dividing the resources used by the application into subsets, the resources in each subset share somewhat similarity and can share backup resources. Then we devised several policies for advanced reservation of backup resources. These policies can be implemented with the GARA system [2]. This paper is organized as follows. The resource backup process is described in section 2. In section 3, the selection algorithm of backup resources based on resources clustering is introduced. In section 4, the policies for advanced reservation of backup resources are presented, and briefly discussed the architecture of the policy engine for resource backup. Conclusion is drawn in section 5.
2
Resource Backup
Resource backup [3] in a single computer system, like a cluster or a server, is often done by hardware component redundancy. In computational grid, however, as the resources belong to different administrative domains, the grid middleware cannot rearrange the hardware components for redundancy. The only way for resource backup is to allocate redundant resources for the application that need high availability. Here, we call the resources allocated to the application on which the application is running as primary resources, and call the resources for redundancy as backup resources. As we know, the resource allocation process in the grid includes two phases [4]: resource discovery and reservation, for example, when a user submits an application with resources requirement described with RSL [5] to the computational grid, the global scheduler first analyzes the resource requirement, performs resource discovery using the grid information system, then computes a primary resource list; secondly, it try to obtain reservations for these resource. If the application needs high availability service, the scheduler can allocate redundant resources at these phases, keeping advanced reservation of some resources as backup. So, in the running process, when the resources on which some application’s task running are failed, these tasks can migrate to the backup resources and continue to run without reallocation process. This can reduce the stall time of the application, increasing its availability. Usually, the application in the grid does not explicitly declare which resources should be allocated as backup resources when it is submitted. The backup resources management module should select backup resource according to the resources requirement and
28
C. Li, N. Xiao, and X. Yang
availability requirement of the application. So, backup resources selection algorithm is absolute necessary. Furthermore, the backup resources may not be used during the running process, in order to avoid the waste of resources, flexible advanced reservation policies is also necessary. In this paper, we first present a backup resource selection algorithm based on resource clustering, then designed some policies for the advanced reservation of backup resources. They are very valuable for providing high availability services in computational grid.
3 3.1
Selection Algorithm Definitions
Before process resource clustering, we give the following definitions for the relations between resources. Definition 1, Substitution Relation, if the task running on resource can also run on and can satisfy the performance requirement of the tasks, then we call that resource is substitutable by denoted as Sub Definition 2, Similarity relation, if two resources and can substitute each other, i.e. Sub and Sub then we call and as similar resources, denoted as Sim Definition 3, Complete resource set, a resource set if Sim then we call as complete resource set. Definition 4, Similarity relation of resource set, complete resource set and for if Sub and Sub then we call and as similar resource set, denoted as Sim
3.2
Resource Clustering
It is obvious that the resources in a complete resource set can share backup resources. The primary resources allocated to an application can cluster into several complete resource set based on similarity relation, then we can choose backup resources for each set. The clustering includes two steps: inner domain clustering and inter domain clustering. First we will examine the determination of similarity relation between two resources. Determination of Similarity Relation. The similarity relation can be determined at two levels: physical level and logical level. At the physical level, it is obvious that homogeneous resources allocated to an application are similar. At the logical level, for two resources allocated to an application, and if the tasks running on can also run on and vice versa, and the application performance can still be satisfied, then and are similar resources. For example, a grid application GA, the tasks of it are programmed with Java, and there are two workstations can run these two tasks , one is a Linux workstation, and the other is a Windows workstation. If the tasks running on these two resources can be exchanged without degradation of the performance, then these two workstations are similar computing resources for the application, although they are heterogeneous computing resources.
Selection and Advanced Reservation of Backup Resources
29
Inner Domain Clustering. It is common that quite a few resources in the primary set are belonging to one administrative domain, for example a cluster or a mainframe. Usually, the resources in a domain are homogeneous, we suppose this is true for all administrative domains. So, the inner domain clustering is easy to perform. The primary resource set can be denoted as these resources are from domains, and the resources in each domain is a complete resource set. is the resources set from the domain. If the resources coming from a domain are heterogeneous, we can divide the domain into sub-domains, and keep the resources in each sub-domain are homogeneous. Inter Domain Clustering. In order to have the primary resources of the application cluster into complete resource sets, the application level clustering must be performed. Inter domain clustering is based on the similarity between domains, which can be determined with following rule: for and if Sim then Sim We use a matrix to describe the similarity relation between domains. If Sim then otherwise The algorithm for inter domain clustering is given in 1.
Fig. 1. Inter Domain Resources Clustering
3.3
Backup Resource Selection for a Resource Set
Availability Measurement. For selecting backup resources, it is necessary to devise a measurement method for the availability of a resource set. In this paper, for simplicity, we use an availability measurement model based on probabilistic model [6]. Suppose a primary resource set of an application is only when all the resources in it are available, the application can run smoothly; otherwise, the application will stall. Suppose A(R)is the availability of this resource set, and the failure rate of is then,
30
C. Li, N. Xiao, and X. Yang
Suppose the availability demand of this application is if then need to allocate backup resources for it. Suppose we have selected backup resources for this resource set, and the expanded resource set is the availability of it can be defined as: {at least resources in is available } If add a backup resource to R, denoted as then
If add more than one backup resources, the computation of is very difficult, for simplicity, we use an approximate method. In this approximate method, we suppose the failure rate of each resources in R is equal to the highest one, denoted as Then the availability of resource set R is In selecting backup resource for this resource set, the failure rate of the backup resource should not over suppose we chosen backup resources, then
Backup Resource Selection algorithm. Based on the upper discussions, we proposed the algorithm for selecting backup resources for a resource set R, shown in 2 In this algorithm, each iteration only choose one backup resource for
Fig. 2. Backup Resources Selection Algorithm for a Complete Resource Set
Selection and Advanced Reservation of Backup Resources
31
the complete resource set. This can determine the minimum number of backup resources for it. In practice, we can choose more than one resource at each time, improve the efficiency of this algorithm.
3.4
Backup Resource Selection Algorithm Based on Resource Clustering
Now we can describe the whole backup resource selection algorithm based on resource clustering as shown in 3:
Fig. 3. Backup Resource Selection Algorithm based on Resource Clustering
4
Policies for Advanced Reservation of Backup Resources
The allocation of backup resources is fulfilled by advanced reservation, in which the reservation is requested before it is needed. The GARA system based on the famous grid middleware Globus Toolkit [7,8], can process advanced reservation for multiple resources such as CPU slot, network bandwidth and storage capacity. But the GARA system lacks flexible policies for advanced reservation. In order to reduce the waste of resources, we designed several policies for advanced reservation of backup resources, these policies can be implemented on the GARA system, providing flexible resource backup mechanism. Flowing, we will introduce the idea of each policy briefly. Here, we use to denote the list of backup resource for application GA, the resources in which is selected by the selection algorithm proposed above.
4.1
Policies
Totally Advanced Reserved, TAR. When allocating backup resources, make advanced reservation for all of the resources in of application GA; that is
32
C. Li, N. Xiao, and X. Yang
only when all the backup resources have been advanced reserved, the application can begin to run. Partially Advanced Reserved, PAR. In the advanced reservation stage, only make advanced reservation for some of the resources in form the backup resource set During the running process, if the advanced reserved resources are not enough for failure recovery, then make advanced reservation for other backup resources in Compensate for Risk, CR. For reducing the number of backup resources in the whole grid environment, different applications can share their backup resources. In this policy, the backup resources which are advanced reserved can assemble into a resource pool, like the insurance mechanism in the society. But for this policy, the time management for advanced reservation is critical, because it is very often that backup resources for different application have different time period for reservation. Delayed Advanced reservation, DAR. In this policy, before the application start, none of the resources in is advanced reserved. Only when resource failure occurs, the resource reservation agent begins to reserve the backup resources in the backup resource list of this application. The number of resources reserved can be determined according to the failure condition and the availability demand of the application.
Fig. 4. The Architecture of Policy Engine
No-backup, NB. For completeness, we also call the method that does not prepare any backup resources for the application as a backup policy. That is, never make advanced reservation of resources used for backup. When failure
Selection and Advanced Reservation of Backup Resources
33
occurs, the job management module in the grid reallocates resources for the failed tasks.
4.2
Policy Engine
It is obvious that each policy has benefits and drawbacks. The backup resource management module in the computational grid will never use only one policy to serve all the applications. It is undoubtedly that a policy engine should be implemented for resource backup service. In 4 we described the architecture of the policy engine for resource backup service of computational grid. There are three critical modules in the policy engine: MLBR is the module that Manage the List of Backup Resources for applications, MARR is the module that Manage the Advanced Reserved Resources in the whole environment, and TMARR is Time Management module for Advanced Reserved Resources. All these modules can call the GARA API to control the advanced reservation of resources. The policy engine can provide flexible resource backup service for the applications.
5
Conclusion
Backup resource management for providing high availability service in computational grid faces two critical issues: backup resource discovery and advanced reservation. In this paper we proposed a backup resource selection algorithm and devised several policies for advanced reservation. These algorithm and policies can provide flexible resource backup service for the applications in computational grid.
References 1. Foster, I., Kesselman, C.: The Grid: Blueprint for a New Computing Infrastructure. Morgan Kaufmann Publishers (1999) 2. Simoni, A.: End-to-End Quality of Service for High-End Applications. PhD thesis, the University of Chicago (2001) 3. Hwang, K., Xu, Z.: Scalable Parallel Computing. Mc-Graw-Hill Companies Inc. (1998) 4. K. Czajkowski, I. Foster, N.K.C.S.M.W.S., Tuecke, S.: A resource management architecture for metacomputing systems. In Proceedings of the IPPS/SPDP’s 98 Workshop on Job Scheduling Strategies for Parallel Processing (1998) 5. WWW: The globus resource specification language rsl v1.0. (http://www.globus.org/gram/rsl_spec1.htm) 6. Archana Sathaye, S.R., Trivedi, K.: Availability models in practice. In Proceedings of Int. Workshop on Fault-Tolerant Control and Computing (FTCC-1) (2000) 7. Foster, I., Kesselman, C.: Globus: A metacomputing infrastructure toolkit. International Journal of Supercomputing Applications 11 (1997) 115–128 8. WWW: (http://www.globus.org)
An Online Scheduling Algorithm for Grid Computing Systems Hak Du Kim1 and Jin Suk Kim2* 1
Electronics and Telecomunications Research Institute, Taejon, Korea 2 School of Computer Science, University of Seoul, Seoul, Korea
[email protected]
Abstract. Since the problem of scheduling independent jobs in heterogeneous computational resources is known as NP-complete [4], an approximation or heuristic algorithm is highly desirable. Grid is an example of the heterogeneous parallel computer system. Many researchers propose heuristic scheduling algorithm for Grid [1], [8], [9], [10]. In this paper, we propose a new on-line heuristic scheduling algorithm. We show that our scheduling algorithm has better performance than previous scheduling algorithms by extensive simulation.
1 Introduction A Grid computing system is a system which has various machines to execute a set of tasks. We need high performance Grid computing systems in the field of natural science and engineering for large scale simulation. In this paper, we propose a scheduling algorithm which assigns tasks to machines in a heterogeneous Grid computing system. The scheduling algorithm determines the execution order of the tasks which will be assigned to machines. Since the problem of allocating independent jobs in heterogeneous computational resources is known as NP-complete [4], an approximation or heuristic algorithm is highly desirable. In the scheduling algorithms, we consider that the tasks randomly arrive the system. We assume that the scheduling algorithms are nonpreemptive, i.e., tasks must run to completion once they start, and the tasks have no deadlines. All the tasks are independent, i.e., there is no synchronization or communication among the tasks. In the on-line mode, a task is assigned to a machine as soon as it arrives at the scheduling system
2 Related Works The scheduling problem has already been investigated by several researchers [1]. In MET(Minimum Execution Time), the scheduling algorithm is developed to minimize execution time, i.e., the algorithm assigns a task to the machine which has the least * Corresponding author: Jin Suk Kim M. Li et al. (Eds.): GCC 2003, LNCS 3033, pp. 34–39, 2004. © Springer-Verlag Berlin Heidelberg 2004
An Online Scheduling Algorithm for Grid Computing Systems
35
amount of execution time. Since this algorithm does not see the ready times of the machines, it has imbalance of load among machines. This algorithm calculates only the minimum one among m machine execution times, and then the algorithm assigns the task to the selected machine. The time to find the machine which has minimum execution time is O(m). The MCT(Minimum Completion Time) assigns a task to the machine which has minimum completion time, i.e., the algorithm gets the completion time for each task by adding begin time and execution time, and calculates the minimum one among m machine completion times. The algorithm assigns the task to the selected machine. Therefore, the time to get the machine which has minimum completion time is O(m). The KPB(K-Percent Best) first finds (k/100)*m best machines based on the execution time for the task, and the algorithm calculates the minimum one among selected machine completion times, and then the algorithm assigns the task to the machine which has the minimum. The time to get the subset of machines is O(mlogm) because the time for sorting m execution times is needed. The time to determine the machine which has minimum completion time is O(m). Overall time complexity of KPB is O(mlogm).
3 A Scheduling Algorithm The execution time denotes the amount of time which is taken to execute task on machine [1]. The completion time denotes the time at which machine completes task Let the begin time of on be We can see that from the above definition. is defined as the set of tasks. n is the number of tasks and m is the number of machines. In this paper, we use a makespan as a performance metric for scheduling algorithms. The makespan is the maximum completion time when all tasks are scheduled. Figure 1 shows a proposed scheduling algorithm MECT(Minimum Execution Completion Time). The inputs of the scheduling algorithm are a task and a set of execution times which is taken to execute on machines In the step I, MECT finds maximum begin time among the begin times of all machines. In the step II, find a subset of machines M’ such that for in M’. In the step III, if M’ is not empty, MECT determines the machine in M’ which has minimum execution time to execute the task Otherwise, MECT determines the machine in M which has minimum completion time to execute the task Finally, MECT returns the index of machine k. Here, we compute the time complexity of MECT. The time that is taken to get a maximum begin time is O(m). The time to find a subset of machines M’ is also O(m). In the step III, we can get k in O(m). Therefore, overall time complexity of MECT is O(m).
36
H.D. Kim and J.S. Kim
Fig. 1. A Scheduling Algorithm MECT
4 Simulation Results In this section, we made a simulation program with SimJava which is used in discrete model simulations [6]. In this simulation, we assume that the execution time for each task on each machine is known prior to execution. This assumption is used when studying scheduling algorithm for heterogeneous computing systems [11]. We use task-machine matrix which has the execution times. Figure 2 shows an example of task-machine matrix. For example, the 3rd row represents execution times for on each machines, i.e., To simulate the scheduling algorithms on various scheduling situations, many studies use task-machine matrix consistency model [11]. We say a task-machine matrix is consistent if machine executes task faster than machine then machine executes all tasks faster than machine We say a task-machine matrix is inconsistent where machine executes some tasks faster than machine and machine executes other tasks faster than machine A task-machine matrix is said to be semi-consistent if some columns are consistent and other columns are inconsistent. Figure 2 represents inconsistent task-machine matrix which has 10 tasks and 5 machines. In this matrix, we can see that executes faster than but executes slower than In this simulation, we made task-machine matrices which have 1,000 tasks and 20 machines. We use the arrival rate of tasks 100. Figure 3 shows the average makespans for scheduling algorithms in inconsistent model. The machine heterogeneity is varied 10 to 120 and the task heterogeneity is 3000. We have 50 tests for each cases. It can be noted that MECT outperforms previous scheduling algorithms.
An Online Scheduling Algorithm for Grid Computing Systems
Fig. 2. A 10×5 Task-Machine Matrix
Fig. 3. The makespans for scheduling algorithms in the inconsistent model
Fig. 4. The makespans for scheduling algorithms in semi-consistent model
37
38
H.D. Kim and J.S. Kim
Fig. 5. The makespans for scheduling algorithms in consistent model
Figure 4 and 5 show the simulation results in the semi-consistent model and the consistent model, respectively. In these figures, we can see that MECT competes with MCT. Note that the performance of MET is lower than that of other three algorithms. In the last simulation, the machine heterogeneity is 20 and the task heterogeneity is varied from 500 to 3000. Figure 6 compares the scheduling algorithms based on makespan. We can see that MECT outperforms previous scheduling algorithms when the task heterogeneity is high.
Fig. 6. The makespans for scheduling algorithms in consistent model
An Online Scheduling Algorithm for Grid Computing Systems
39
5 Conclusion In this paper, we propose a new scheduling algorithm MECT for heterogeneous Grid computing systems. The proposed scheduling algorithm is a kind of on-line scheduling algorithm. We show that MECT has better performance than the traditional scheduling algorithms especially when the heterogeneity is high.
References [1]
M. Maheswaran, S. Ali, H. J. Siegel, D. Hensgen, and R. F. Freund, “Dynamic Matching and Scheduling of a Class of Indenpendent Tasks onto Heterogeneous Computing Systems,” Proc. of the 8th Heterogeneous Computing Workshop, pp. 30-44, April, 1999. [2] I. Foster, C. Kesselman, and S. Tuecke, “The Anatomy of the Grid: Enabling Scalable Virtual Organizations,” Journal of High-Performance Computing Applications, vol. 15, no. 3, pp. 200-222,2001. [3] T. D. Braun, H. J. Siegel, and Noah Beck, “A Comparison of Eleven Static Heuristics for Mapping a Class of Independent Tasks onto Heterogeneous Distributed Computing Systems,” Journal of Parallel and Distributed Computing, vol. 61, pp. 810-837, 2001. [4] O. H. Ibarra and C. E. Kim, “Heuristic Algorithm for Scheduling Independent Tasks on Nonidentical Processors,” Journal of the ACM, vol. 24, no. 2, pp. 280-289, April, 1977. [5] M. Pinedo, Scheduling: Theory, Algorithms, and Systems, Prentice Hall, NJ, 1995. [6] F. Howell and R. McNab, “SimJava: A Discrete Event Simulation Package For Java With Applications In Computer Systems Modelling,” Proc. of the 1st International Conference on Web-based Modelling and Simulation, January, 1998. [7] A. A. Khokhar, V. K. Prasanna, M. E. Shaaban, and C. L. Wang, “Heterogeneous Computing: Challenges and Opportunities,” IEEE Computer, vol. 26, pp. 18-27, June, 1993. [8] R. Buyya, J. Giddy, and D. Abramson, “An Evaluation of Economy-based Resource Trading and Scheduling on Computational Power Grids for Parameter Sweep Applications,” Proc. of the 2nd International Workshop on Active Middleware Services, August, 2000. [9] H. Barada, S. M. Sait, and N. Baig,“Task Matching and Scheduling in Heterogeneous Systems using Simulated Evolution,” Proc. of the 15th Parallel and Distributed Processing Symposium, pp. 875-882, 2001. [10] B. Hamidzadeh, Lau Ying Kit, and D.J. Lilja, “Dynamic Task Scheduling using Online Optimization,” Journal of Parallel and Distributed Systems, vol. 11, pp. 1151-1163, 2000. [11] T. D. Braun, H. J. Siegel, N. Beck, L. L. Boloni, M. Maheswaran, A. I. Reuther, J. P. Robertson, M. D. Theys, B. Yao, D. Hensgen, and R. F. Freund, “A Comparison Study Mapping Heuristics for a Class of Meta-tasks on Heterogeneous Computing Systems,” 8th IEEE Heterogeneous Computing Workshop, pp. 15-29,1999.
A Dynamic Job Scheduling Algorithm for Computational Grid* Jian Zhang and Xinda Lu Department of Computer Science and Eng., Shanghai Jiaotong Univ., Shanghai 200030, China {zhangjian,
lu-xd}@cs.sjtu.edu.cn
Abstract. In this paper, a dynamic job-scheduling algorithm is proposed for a computational grid of autonomous nodes. This algorithm tries to utilize the information of a practical system to allocate the jobs more evenly. In this algorithm, the communication time between nodes and the scheduler is overlapped with the computation time of the nodes. So the communication overhead can be little. The principle of scheduling the job is based on the desirability of each node. The scheduler would not allocate a new job to a node that is already fully utilized. The execution efficiency of system will be increased. An implementation framework of the algorithm is also introduced.
1 Introduction The Grid concept has recently emerged as a vision for future network based computing. A computational grid is a large scale, heterogeneous collection of autonomous systems, geographically distributed and interconnected by low latency and high bandwidth networks. Networks of workstations, NOWs, represent particular forms of grids. Like an electrical power grid, the Grid will aim to provide a steady, reliable source of computing power. The most difficult problems in a computational grid are the management and control of resources, dependability and security. Obviously, until now, researchers have proposed many techniques to allocate jobs dynamically in a parallel system to improve its performance. But most of these algorithms ignore practical issues such as the speed of nodes, the process ability of the node, and the different size of the jobs. These schedulers might not perform satisfactorily in practical. In this paper, a dynamic job-scheduling algorithm is proposed. In this algorithm, the scheduler tries to allocate a job according to the knowledge of the nodes. This algorithm is very general and it can adapt to more situations to improve the job fairness. This algorithm is also a valid method to prevent the saturation of the nodes. This paper is organized as follows. In the second section, an analysis of the general job scheduling policies is presented. Then in the third section, the job-scheduling algorithm is introduced and explained in detail. The mobile agent based implementation framework is giving in the fourth section, followed by a summary of this paper in the fifth section. *
This work was supported by the National Science Foundation of China (No. 60173031)
M. Li et al. (Eds.): GCC 2003, LNCS 3033, pp. 40–47, 2004. © Springer-Verlag Berlin Heidelberg 2004
A Dynamic Job Scheduling Algorithm for Computational Grid
41
2 Analysis of the General Job Scheduling Policies There are three general job-scheduling policies [1]: Static scheduling: In this policy, the job is assigned to the nodes at compile time and will never be reassigned again. Dynamic scheduling: System makes all scheduling decisions at run time. They use a central work-queue where all idle nodes go to find work to execute. Affinity scheduling: In this policy, schedulers create one local work queue for each node. Each node is statically assigned some work, as if static scheduling were used. If load imbalance actually occurs, idle nodes search the work queues of other nodes to find work to do. In the static scheduling policy, because the scheduler need not communicate with the node before the assigning the job, and the job will never be reassigned, the synchronization and communication overhead will be very little. But the drawback is that it may lead to underutilization of nodes. In the dynamic scheduling policy, the right to take initiative is controlled by the node. When a node is in the idle state, it will send message to the scheduler to ask for the job. The job in the head of job queue will be assigned to this node. In this policy, the load imbalance will be reduced to the minimum. However, this policy may also result in an increase of communication overhead. Before the idle node can get the job, it has to spend time in making communication with scheduler. The affinity scheduling policy attempts to strike a balance among the static and dynamic schedulers. On one hand, it can reduce the load imbalance. There will be no idle node if there is a job waiting for executing. On the other hand, the communication overhead between nodes and scheduler is little. Each node has its own job queue. But in this policy, migration may be taken among nodes. The overhead between nodes is increasing. In some condition, the overhead related to migration is higher than the overhead related to load imbalance. Thus the performance of affinity scheduling policy may be worse than static scheduling policy. If no migration in the affinity scheduling policy, the performance of system would be improved notably. With the utilization of some other practical information, we can do this. The size of jobs is useful practical information, but it is hard to get in advance. We still can get some other information from the system. We can estimate the speed of each node. We can know the maximum number of jobs that can be executed concurrently on each node. And we can also know that there are three jobs running in each node right now. Such information is also useful. The algorithm we proposed in this paper is based on the utilization of these information.
3 The Dynamic Job Scheduling Algorithm 3.1 The Architecture of the Algorithm Intuitively, the best load-balancing status occurs when all nodes are at the point of full utilization and each node’s workload is proportional to its capacity. We try to increase the throughput of the system. We may not allocate more jobs to a fully utilized node, because this will cause imbalance without improving the overall throughput [2]. We
42
J. Zhang and X. Lu
should know whether we could allocate a new job to a particular node or not. An important characteristic of the algorithm is to estimate the desirability of executing a new job in each node. We use a scheduling function to reflect this desirability. When the node is saturated, scheduler will not allocate new job to it. The architecture of this algorithm is shown in Fig.1.
Fig. 1. Architecture of the algorithm
The characteristic of this architecture is that there is no job queue for each node. Additionally, there is a message queue for the scheduler. All the messages sent to the scheduler will be appended to this queue. The scheduler will extract the message from the message queue to process. Taking Fig.1 as an example. Assuming a node will be fully utilized when three jobs are running in it, then the scheduler will not dispatch the next job until a running job is completed. Because all short jobs are in a job in will more likely be completed first. Therefore, the next long job has a higher chance of being allocated to Then we can reduce the chances of overloading the nodes and tend to distribute long jobs to the nodes more evenly.
3.2 The Algorithm In order to explain this algorithm in detail, here some notions are explained at first. P The set of all nodes A node in the set P, The initial speed of a node The bounding factor of a node The run queue length of a node The effective speed of a node The scheduling function Central job queue Message queue
A Dynamic Job Scheduling Algorithm for Computational Grid
43
In a computational grid, all the nodes consist the set of nodes P. denotes each node in the node set, is a bounding factor. It limits the number of schedulable jobs in that node. The bounding factor is generally set such that when jobs are scheduled to the node is fully utilized. The value of the bounding factor will affect the response time of system. If we set a high for a node the number of jobs that can be executed concurrently on this node will be high, then the response time will be long. So if in a system where response time is important, the bounding factor should be set to a low value. is the run queue length of a node, reflecting the number of active jobs which are being executed on this node. Moreover, should not larger than
Each node has its speed. When it is in idle state, its speed will be its initial speed. We use to denote this speed. This speed should be the highest speed for this node. When some jobs are being executed in this node, the speed of this node will decrease. The current speed will be its effective speed. We use to denote the effective speed of node. The effective speed of a node has an inverse proportion with the number of jobs in this node. The more the number of jobs is, the lower the effective speed is. When the node is in idle state, its effective speed should be its initial speed. We may use the formula below to calculate the effective speed of a node:
is the scheduling function reflecting the desirability of executing a new job on this node The larger is, the more desirable sending a job to is. If equals zero, this means the number of jobs in this node has reached this node has already been fully utilized. The scheduler tries to find the node with the highest from the nodes whose is larger than zero.
If of all the nodes are equal to zero,
this means all the nodes in the parallel system are all saturated. The scheduler will not dispatch additional jobs to overload an already saturated system but to wait for some running jobs to complete. The scheduling function may be expressed like this:
From this formula, we see that the larger is, the smaller is. When is less than will be larger than zero. When equals will be zero. If is less than zero, it means the node is overloaded with local jobs.
44
J. Zhang and X. Lu
There are three kinds of messages that the scheduler will receive. Job_done: It is sent from the node to the scheduler when a job in this node is completed. New_job: This message is sent to the scheduler when a new job is coining. The scheduler will append this job at the end of the central job queue. Current_load: The current run queue length of a node. The algorithm is shown below:
In the initial phase, it will get the bounding factor and the initial speed of each node The for each node will be set zero. Then calculates the effective speed and the value of scheduling function for each node. The algorithm then processes the incoming message in the main loop. If the message is “New_job”, it will append the new job at the end of central job queue If the message is “Job_done”, the of that node will be minus 1. The and will be recalculated. In the next step, the algorithm will find the with the highest from the set P. If the highest is zero, it will not extract the job from the to execute but to process the next message from the If the highest is larger than zero, it will extract the job from the and execute it on The of that node will be added 1. The and will also be recalculated. Compared with the dynamic scheduling policy, in our algorithm, the node does not need to use a special time to make communication with the scheduler. The time for communication and the time for computation are overlapped. When it completed a job, it will send a “Job_done” message to the scheduler, and it will continue to execute other jobs assigned on it but to wait for new job. This could reduce the overhead between the node and the scheduler. It alleviates the drawback of the dynamic scheduling policy. Compared with the affinity scheduling policy, when the scheduler want to allocated a job, the algorithm does not select the node blindly. It will select among nodes whose scheduling functions are large than zero, which is calculated with the process ability and the effective speed of that node. Therefore, it can evenly distribute the workload among the nodes, and no migration is needed. Another important characteristic of this algorithm is that it would not allocate more jobs to a node when the desirability of that node is zero. This means it would not allocate more jobs to the node that is already fully utilized. Most other scheduling algorithms submit the jobs to the selected node without checking if the node has become
A Dynamic Job Scheduling Algorithm for Computational Grid
45
saturated after selection and before sending out the job. These algorithms want to increase the throughput of system, but on contrary, it will decrease the execution efficiency of system.
4 Mobile Agent Based Implementation of the Algorithm 4.1 Mobile Agent Mobile agent is an emerging paradigm that is now gaining momentum in several fields of applications [3]. A mobile agent corresponds to a small program that is able to migrate to some remote machines, where it is able to execute some function or collect some relevant data then migrate to other machines in order to accomplish another task. The basic idea of this paradigm is to distribute the processing through the network: that is, sent the code to the data instead of bringing the data to the code. The type of applications that are most appropriate for mobile agent technology would include at least one of the following features: data collection, searching and filtering, distributed monitoring, information dissemination, negotiating and parallel processing [4]. When the application is computationally intensive or requires the access to distributed sources of data then the parallel execution of mobile agents in different machines of the network seems to be an effective solution. At the same time, the dynamic and asynchronous execution of mobile agents fits very well in changing environments where it is necessary to exploit some notion of adaptive parallelism.
4.2 Implementation Framework The implementation of the algorithm is based on Aglet (IBM). Aglet is probably the most famous mobile agent system. It models the mobile agent to closely follow the applet model of Java, with the following characteristics: object-passing, autonomous execution, local interaction, asynchronous, disconnected operation, parallel execution, etc. Aglets are Java objects that can move from one host to another, their fundamental operations including: creation, cloning, dispatching, retraction, deactivation, activation, disposal, and messaging [6]. It is possible for them to halt execution, dispatch to a remote host, and restart executing again by presenting their credentials and obtaining access to local services and data. Aglet provides a uniform paradigm for distributed object computing [7]. Using Aglet can ease the development of distributed computing system. We are doing research on mobile agent based parallel computing. On the basis of that, an implementation framework of the algorithm is proposed. It is composed of two parts: Console and Monitor. They are both aglets with ability of communication through messaging. Console is responsible for the initialization, decision-making and job dispatching. Monitor is responsible for the load monitoring. Console resides on the central node, waiting for the coming of new jobs and messages from monitor in each node. When a new job comes it will find an appropriate node to execute it according to the algorithm. Meantime it will handle messages from
46
J. Zhang and X. Lu
monitors: update run queue length and scheduling function. Monitors check the run queue length of each node, and send this information to console if these values change
4.3 Experimental Results The experiments were conducted on a network, consisting of a Sun server and five Sun workstations. The tasks are generated on the server and then scheduled to other machines. Two conditions were considered in the tests: without and with background loads. The background loads are computing agents, which are long time consuming. The tasks are generated with interval of 4 and 6 second respectively, until 100 tasks are generated. For comparing with the dynamic scheduling algorithm (DS), the round robin (RR) scheduling algorithm was used to do the same tests. The experimental results are shown in table 1.
From table 1, it is observed that the performance of DS is better than that of RR. The average speedups for the two conditions are 1.24 and 1.27 respectively. As the tasks are generated and scheduled, the run queue length of some machines may be greater than the bounding factor, their scheduling function is less than zero. DS algorithm will not assign new tasks to these nodes until the scheduling function is positive. While RR algorithm continues scheduling new tasks to them and finally get a bad result.
5 Conclusion In this paper, we introduce a dynamic job scheduling algorithm. The basic principle of this algorithm is trying to utilize the information of each node in a computational grid to allocate the jobs among them. A scheduling function is used to determine the desirability of each node to accept a new job. If a node were already fully utilized, the new job would not be allocated to it again. This algorithm tries to improve the throughput, response time, and fairness of the system. Moreover, a mobile agent based implementation framework is proposed.
A Dynamic Job Scheduling Algorithm for Computational Grid
47
References 1. Markatos E P.: How architecture evolution influences the scheduling discipline used in shared-memory multinodes. Joubert G R. Proceedings of Parco 93. Amsterdam: Elsevier, (1993) 524-528 2. Hui C C, Chanson S T.: Improved strategies for dynamic load balancing. IEEE Concurrency, 3 (1999) 58-67 3. V. Pham, A. Karmouch.: Mobile Software Agents: An Overview. IEEE Communications Magazine, 7 (1998) 26-37 4. B. Venners.: Solve Real Problems with Aglets, a Type of Mobile Agent, JavaWorld Magazine, 5 (1997) 5. Perdikeas M.K., Chatzipapadopoulos F.G., Venieris I.S. An Evaluation Study of Mobile Agent Technology: Standardization, Implementation and Evolution. IEEE International Conference on Multimedia Computing and Systems, 2 (1999) 287 -291 6. Lange Danny B., Oshima Mitsuru.: Mobile Agents with Java: The Aglet API. World Wide Web Journal, 3 (1998) 111-121 7. Lange Danny B., Oshima Mitsuru.: Programming and Deploying Mobile Agents with Java, Addison-Wesley, MA, (1998)
An Integrated Management and Scheduling Scheme for Computational Grid* Ran Zheng and Hai Jin Cluster and Grid Computing Lab Huazhong University of Science and Technology, Wuhan, 430074, China {zhraner, hjin}@hust.edu.cn
Abstract. Computational grids have become attractive and promising platforms for solving large-scale high-performance applications of multi-institutional interest. However, the management of resources and computational tasks is a critical and complex undertaking as they are geographically distributed, heterogeneous in nature, owned by different individuals or organizations with their own policies, different access, and dynamically varying loads and availability. In this paper, we propose an integrated management and scheduling scheme for computational grid. It solves some pivotal and important questions such as resources heterogeneous and information dynamic. It affords transparent support for high-level software and grid applications, enhancing the performance, expansibility and usability of computers, and providing incorporate environment and information service. This scheme has universality for computational grid and makes every grid resource work efficiently.
1 Introduction Computational grids [1][2] are becoming more attractive and promising platform for solving large-scale computing intensive problems. In this environment, various geographically distributed resources are logically coupled together and presented as a single integrated resource. The resource management and scheduling is the key technology of a grid. How to manage the resources efficiently is the pivotal issue, which decides whether grid is available or not. At the same time it is a complex undertaking as the resources are distributed geographically, heterogeneous in nature, owned by different individuals or organizations, and they have dynamically varying loads and availability. Some existing resource managing technologies of the parallel and distributed system cannot fit well for the characteristics of the computational grids mentioned above. This paper presents an integrated resource management and scheduling scheme for computational grid. In section 2, we analyze three resource management models and point out the hierarchical structure is suitable for grid. We put forward an integrated * This paper is supported by National Science Foundation under grant 60125208 and 60273076. M. Li et al. (Eds.): GCC 2003, LNCS 3033, pp. 48–56, 2004. © Springer-Verlag Berlin Heidelberg 2004
An Integrated Management and Scheduling Scheme for Computational Grid
49
management and scheduling scheme in section 3, and the prototype is also explained. In section 4, task dispatching and selection algorithms for this architecture are introduced. Section 5 focuses on the performance evaluation of this scheme. Finally, we draw the conclusion and give out future work in section 6.
2 Anatomy of Resource Management Architectures Primarily, there are three different scheduling models: Centralized management model This can be used for managing single or multiple resources, which suits well for cluster (or batch queuing) systems such as Condor [3], [4], LSF [5], and Codine [6]. There are many advantages: simple structure, convenient maintenance, certifiable consistency or integrality. However, it is hard to achieve in distributed system for the scheduling bottleneck. Therefore it is not suitable for capacious grid. Decentralized management model In this model resources are partitioned into different virtual domains. In each domain here is a domain scheduler. The model appears high scalable, but remote status is not available so the optimal scheduling is questionable! What’s more, the traffic is heavy and the data are located decentralized, which make against data consistency and scheduling in multi-domains. Hierarchical management model This model looks like a hybrid (central and decentralized) model, which not only avoids the shortcoming of the two models, but also settles some challenging problems: site autonomy, heterogeneous environment and policy extensibility. It has been adopted in Globus [7][8], Legion [9][10], Ninf [11], and NetSolve [12][13].
Fig. 1. Hierarchical Architecture Model
Our grid resource management architecture follows this hierarchical model, shown in Figure 1. It is constructed with a super-scheduler, several local schedulers and published resources, just like a tree. Super-scheduler is root, and local schedulers are non-leaves. All leaves are resources, which are divided into several virtual domains.
50
R. Zheng and H. Jin
3 Integrated Management and Scheduling Scheme 3.1 Integrated Resource Management and Scheduling Scheme Resource management is highly important in grid, which is similar but more complex than distributed system. It should not only support multi-scheduling, but also suit for the complex surrounding and provide necessary QoS. The integrated management and scheduling scheme is shown in Figure 2. The key components are Grid Resource Scheduler, Grid Information Server and Grid Nodes.
Fig. 2. Integrated Resource Management and Scheduling Structure
Grid Resource Scheduler is a decision-making unit, which incepts user requests, adopts optimal scheduling algorithms and handles seamless managing issues. Furthermore, the scheduler must be able to deal exceptional case. For example, after the fail of one resource, the scheduler can reschedule tasks to other idle resources. Grid nodes include devices and software. The node managers handle all issues from upper scheduler and harmonize the actions of devices and active processes. The dispatcher determines inner scheduling based on upper info or resource statuses that are collected by monitor. Examples of local manager include cluster systems such as MOSIX and queuing systems such as Condor, Codine and LSF. Grid Information Server acts as databases for describing items of interest to the resource management systems, such as resources, jobs, schedulers.
3.2 Grid Scheduler Infrastructure Grid scheduler acts as a mediator between users (application) and grid resources. It is responsible for grid management. The representation of grid scheduler is shown in Figure 3, where there are two hierarchies: decomposing level and scheduling level.
An Integrated Management and Scheduling Scheme for Computational Grid
51
Job receiver module incepts user requests and returns results. Task decomposing module decomposes job into several parallel, mutually exclusive or synchronous atomic tasks. The rules are saved in database, which are the foundation of rule-based illation. Resource-task matching module finishes the matching between atomic tasks and resources, identifying the exchangeable and compensatory ability of resources. Scheduling module searches information from information server, and saves or modifies some context. Task scheduling module analyses scheduling strategies with different principles. Rule-based illation module arranges resources for atomic tasks. Scheduler optimizing module can optimize scheduling on-line. Job receiver module takes charge of scheduling generation, creation of atomic tasks, and maintenance of job status. Resource matching module decomposes jobs, searches grid information server, and generates allocating schemes. Scheduling illation module analyses generated reasonable schemes and determines the best. Scheduling module allocates tasks to selected resources according with the result.
Fig. 3. Grid Scheduling Structure
Re-scheduler happens with interruption of outer or inner abnormity. Outer abnormity is caused with the arrival of urgent jobs or cancellation. Inner abnormity is caused by factors such as resource failure. When interruption happens, job scheduler sends signal to task scheduling module, then re-dispatches and reschedules.
4 Grid Scheduling Algorithm 4.1 Dynamic Scheduling Mechanism There are two commonly dynamic methods, named event-based and timed-based. In timed-based method the interval of scheduling is periodical. After a fixed time a new period is coming: eliminate all finished tasks and insert new tasks to reschedule.
52
R. Zheng and H. Jin
Event-based method is different, which inspects the rescheduling status constantly and decides the possibility whether to issue a rescheduling event. The structure of dynamic scheduling is shown in Figure 4. Job has its own priority to be scheduled. A new submitted job springs the scheduling of the selected local scheduler at the same time if its emergency is high enough to exceed the threshold value. Otherwise it is scheduled with other tasks when the scheduling slot comes. The failure of resource or the cancellation of tasks will all lead to reschedule.
Fig. 4. The Structure for Dynamic Scheduling
4.2 Integrated Scheduling Algorithms All tasks in grid can be classified as real-time or best-effort class. All tasks will be space-based dispatched widely and time-based selected in virtual domain. The basic rule is real-time tasks are processed earlier than best-effort tasks. 4.2.1 Grid Task Dispatch Algorithm of Grid Scheduler We propose a mixed scheduling algorithm with the goal of the least number of missed real-time deadlines and load balance of grid resources, called LMLB. The algorithm is invoked at every real-time task or best-effort task arrival. For every real-time task, resource-task matching is done first. If no satisfied resource, add 1 to the scheduling counter whose initial value is 0. If the value is out of the scheduling threshold, it is regarded the task is disable, else put it to renewed window to reschedule next time, then repeat the operation in any case. If some resources are suitable for the request, select one from the matching unit with the goal of the least number of missed deadlines. Compute as
where is the deadline specification, is the scheduling time. Estimate the processing time on each available resource
where
denotes the round-trip time of network,
between resource and user,
is the bandwidth,
is transmitted data is the waiting time on
is a
An Integrated Management and Scheduling Scheme for Computational Grid
parameter of waiting probability, arbitrary units) for the task, and Select a suitable resource
where
53
is the logical computational “cost” (in some is resource performance (in units per second).
whose
is not over and nearest to
denotes the logical computation of resource
mation of all tasks’ logical computation “costs” in resource
the real-time sumis
,
is the boundary whether resource overloads or not. However, if there is no resource satisfying which is shown no suitable resource for the task at this moment, add 1 to its scheduling counter for rescheduling. For every best-effort task, the initial operation is similar with real-time task. Select one with the goal of load balance of grid resources from the matching unit. Estimate current load of resource on each available resource
where in resource
is the real-time summation of all tasks’ logical computation “costs” and
Select a suitable resource
denotes the logical computation of resource whose
is the smallest.
4.2.2 Tasks Selection Algorithm in Virtual Organization A mixed algorithm is proposed, in which best-effort tasks are solved after real-time tasks, so that most deadlines can be satisfied and resource can be utilized efficiently. Grid scheduler should ensure the maximal benefits of users, namely the minimal number of missed tasks. Therefore, real-time tasks are prior to best-effort tasks to schedule. But best-effort tasks should also be processed as soon as possible. The real-time task selection algorithm should consider QoS of all tasks. Weighted Priority Schedule Algorithm (WPSA) is adopted in real-time scheduling. In WPSA, the priorities of tasks in virtual organization are varied dynamically with their importance. Tasks with different priority get different QoS in this algorithm. Highest Responsibility First Algorithm (HRFA) is used for best-effort tasks. Response Rate is the ratio of response time of the task, defined as:
54
R. Zheng and H. Jin
Here Response Time is the summation of waiting time that the task joins the system and the execute time estimated. Therefore, the Eq.6 can be written as:
5 Performance Evaluation of the Scheduling Scheme In this section, we will evaluate the grid schedule scheme from the viewpoints of QoS of grid applications. The process of matching, scheduling, and executing is performed so that some metric of aggregate QoS delivered to the requestor is maximized [14]. LMLB algorithm is based on the greedy scheduling algorithm described in [15] as MCT (Minimum Completion Time). MCT is an aggressive approach that does not consider the possible deadlines. It can lead to an increasing load of resource, even overloaded. LMLB can overcome this shortcoming efficiently. The scheduler uses load measurements and searches all resources and finds an optimal one. Figure 5 shows a comparison of the failure rate between MCT and LMLB algorithm. The failure rate is defined as the percentage of requests that missed their deadlines. Results are shown for the different thresholds of workload conditions. Although LMLB decreases the overloads of grid resources, it is inevitable that the loads of them are not in balance. In order to utilize idle resources sufficiently, the resources with the least loads are distributed to best-effort tasks with no limitation of deadlines. It not only gets load balance, but also ensures earlier finishing time.
Fig. 5. Failure Rate for Greedy and the LMLB Algorithm
Fig. 6. Waiting Time of Tasks with Different Priorities
WPSA is adopted for real-time scheduling. The different deadlines or degrees of importance are distinguished with different weights. WPSA ensures higher priority for more emergent tasks, which can be ahead processed. Suppose tasks are divided
An Integrated Management and Scheduling Scheme for Computational Grid
55
into two classes with higher or lower priorities. Figure 6 shows the comparison among WT1, WT2 and WT, which denote the higher, the lower and all tasks respectively. The conclusion is that tasks with higher priorities get better QoS. HRFA is used for best-effort tasks. Compare it with First Come First Server algorithm (FCFS) and Shortest Executing Time First algorithm (SETF). FCFS only considers Waiting Time and ignores Executing Time, while SETF just on the opposition emphasizing Executing Time. HRFA is the compromise between them, which not only cares for short tasks, but also do not let long tasks wait for too long. From Eq.7, we can know tasks with shorter executing time can get higher response rate, saying HRFA gives special treatment to short tasks. But if waiting time of one task is so long that its response time increases with the extending of waiting time, the task will be possible to have the highest response rate to schedule immediately.
6 Conclusions and Future Work In this paper, we proposed an integrated resource management and scheduling scheme for computational gird. The integrated algorithms for high QoS of grid applications are used and correlative evaluations are investigated. The results suggest that future applications on grid will compete for resources. Based on this architecture, there are many factors and aspects need to be studied carefully, such as fault tolerance, high utilities of grid resources, trade-off between failure-rate and cost.
References 1. 2.
3. 4. 5. 6. 7. 8.
9.
I. Foster and C. Kesselman (ed.), The Grid: Blueprint for a New Computing Infrastructure, Morgan Kaufmann Publishers, 1998. M. Baker, R. Buyya, and D. Laforenza, “The Grid: International Efforts in Global Computing”, Proc. of International Conference on Advances in Infrastructure for Electronic Business, Science, and Education on the Internet, Rome, Italy, 2000. M. Litzkow, M. Livny, and M. W. Mutka, “Condor – A Hunter of Idle Workstations”, Proc. of the 8th International Conference of Distributed Computing Systems, June 1988. J. Basney and M. Livny, “Deploying a High Throughput Computing Cluster”, High Performance Cluster Computing, Vol. 1, Chapter 5, 1999. Q. Zhao and J. Suzuki, “Efficient quantization of LSF by utilizing dynamic interpolation”, Proc. of 1997 IEEE International Symposium on Circuits and Systems, Hong Kong, 1997. F. Ferstl, Job and resource management systems: Architectures and Systems, Vol.1, pp.499~518, 1999. I. Foster and C. Kesselman, “Globus: A Metacomputing Infrastructure Toolkit”, International Journal of Supercomputer Applications, Vol.11, No.2, pp.115-128, 1997. K. Czajkowski, I. Forster, N. Karonis, C. Kesselman, S. Martin, W. Smith, and S. Tuecke, “A Resource Management Architecture for Metacomputing Systems”, Proc of the 4th Workshop on Job Scheduling Strategies for Parallel Processing, 1998. A. Grimshaw and W. Wulf, “The Legion Vision of a Worldwide Virtual Computer”, Communications of the ACM, Vol.40, No.1, 1997.
56
R. Zheng and H. Jin
10. S. Chapin, J. Karpovich, and A. Grimshaw, “The Legion Resource Management System”, Proc. of the 5th Workshop on Job Scheduling Strategies for Parallel Processing, 1999. 11. H. Nakada, M. Sato, and S. Sekiguchi, “Design and Implementations of Ninf: towards a Global Computing Infrastructure”, Future Generation Computing Systems, Metacomputing Special Issue, 1999. 12. H. Casanova and J. Dongarra, “NetSolve: A Network Server for Solving Computational Science Problems”, International Journal of Supercomputing Applications and High Performance Computing, Vol. 11, No. 3, 1997. 13. H. Casanova, M. Kim, J. Plank, and J. Dongarra, “Adaptive Scheduling for Task Farming with Grid Middleware”, International Journal of Supercomputer Applications and HighPerformance Computing, 1999. 14. M. Maheswaran, “Quality of Service Driven Resource Management Algorithms for Network Computing”, Proc. of International Conference on Parallel and Distributed Processing Technologies and Applications, 1999. 15. M. Maheswaran, S. Ali, H. Siegel, D. Hensgen, and R. Freund, “Dynamic Mapping of a Class of Independent Tasks onto Heterogeneous Computing Systems”, Journal of Parallel and Distributed Computing, Vol.59, pp.107-131, 1999.
Multisite Task Scheduling on Distributed Computing Grid Weizhe Zhang1, Hongli Zhang1, Hui He2, and Mingzeng Hu1 1
School of Computer Science and Technology, Harbin Institute of Technology, P.R.China {zwz, zhl, mzh}@pact518.hit.edu.cn 2
http://pact518.hit.edu.cn/index.html Network Information Center, Harbin Institute of Technology, P.R.China
[email protected]
Abstract. Multisite task scheduling plays more and more important role in the grid computing as the WAN becomes faster and faster. Through the development of a three-level architecture of the distributed computing grid model and a grid schedule model, a scalable environment for multisite task scheduling is put forward. Then, a multisite Distributed Scheduling Server is designed and its prototype is implemented. A heuristic strategy, Clustering-based Grid Resource Selection algorithm, is described. Experiment indicates the scheduler and the algorithm are effective.
1 Introduction Grid computing refers to the coordinated and secured sharing of computing resources across different administrative domains, aiming to solve the large-scale embarrassing problems such as fluid dynamics, weather modeling, nuclear simulation and molecular modeling....etc. Currently, computational grid can be classified into distributed computing grid and high-throughput computing grid [1]. A distributed supercomputing grid executes the application in parallel on multiple machines to reduce the completion time of a job. A high-throughput grid increases the completion rate of a stream of jobs. Task scheduling is necessary and important to achieve less running time and higher throughput. Traditionally, the definition of task scheduling is the assignment of start and end times to a set of tasks to some certain resources, subject to certain constraints. However, computing grid involves so many resources over multiple administrative domains that resources should be selected carefully in order to provide the best Qos. Thus, the traditional scheduling model based on static resources can not satisfy the large-scale dynamic resources requirement of the grid computing. In this paper, a new scheduling model oriented to the distributed computing grid is put forward. In the new scheduling model, the resource selection phrase plays an important role. Normally, resource selection algorithms can be classified into single-site and multisite resource selection algorithms. Currently, most of the scheduler systems adopt the M. Li et al. (Eds.): GCC 2003, LNCS 3033, pp. 57–64, 2004. © Springer-Verlag Berlin Heidelberg 2004
58
W. Zhang et al.
single-site resource selection algorithm such as Matchmaker/Class Ad system of University of Wisconsin-Madison [2], Nimrod/G Scheduler of Monash University[3], Silver Grid scheduler of Supercluster Organization[4] and the Metascheduler of the Poznan Supercomputing and Networking Center[5]. However, only the GrADS [6] project matches sets of resources to applications instead of just a single resource. The lack of the multi-site resource selection algorithms is the result that many users fear a significant adverse effect on the computation time due to the limitations in network bandwidth and latency over wide-area networks. As WAN networks become faster and faster, the overload caused by communication may decrease over time. In fact, [7] has proved the usage of multi-site application can significantly improve running time in terms of a smaller average response time and about 25% communication overload. In this paper, we propose our enhanced multi-site resource selection algorithm— CGRS algorithm based on the distributed computing grid model and the grid scheduling model. The CGRS algorithm integrates a new density-based internet clustering algorithm into the decoupled scheduling approach of the GrADS and decreases its time complexity. The rest of this paper is organized as follows. First, our scheduling model is discussed in the next section. In Section 3, we present the design of our scheduler. The resource selection algorithm and experiments are presented and discussed in Section 4 and 5 respectively. The paper ends with a brief conclusion.
2 Models 2.1 Distributed Computing Grid Model Distributed Computing Grid Model (DCGM) adopts three-level architecture as shown in Fig.1: the top level consists of Grid Information Servers (GIS) and Grid Meta Scheduling Server (GMSS); the second level has several domains and each domain consists of a Grid Distributed Scheduling Server (GDSS); all kinds of Grid Computing Resources (GCR) and Grid User Groups (GUG) are third level. Grid Information Servers (GIS) are the essential part of any Grid software infrastructure, providing fundamental mechanisms for discovery and monitoring [8]. Each domain is controlled by at least one GIS, which dynamically collects information about resources registered to it and spread information to other GISs. A GIS receives Grid information request sent by GMSS, GDSS and GUG and returns the satisfactory resource aggregate to the requester Grid Meta Scheduling Servers (GMSS) focus on harmonizing the scheduling of different GDSSs. The goal of the GDSS is to avoid the mistake that GDSS assumes the absence of the others when two or more applications are submitted simultaneously. Every GMSS accepts the meta scheduling request from the GDSSs and cooperates with other GMSSs to increase the system throughput. There is much work done for the GMSS policies, in the current stage we only focus on the GDSS scheduling policies. Grid Distributed Scheduling Servers (GDSS) are the key component in the arch-
Multisite Task Scheduling on Distributed Computing Grid
59
itecture, which administer the efficient use of registered resources and mapping the grand-challenging application on the selected resources aggregate. When the Grid User Group (GUG) submits the job to GDSS, GDSS contacts with GIS to gather the information of the Grid. Then, GDSSs use the decision module for scheduling and dispatches the meta scheduling request to GMSSs. Grid Computing Resources (GCR) are non-dedicated workstations or personal computers, which may be homogeneous or heterogeneous. Every GCR registered to GIS acts as the target of task mapping performed by GDSS or GMSS. Grid User Group (GUG) has the challenge problems such as fluid dynamics, weather modeling and nuclear simulation....etc. GUG interacts with Grid environment through the Grid Portal along with GDSS.
Fig. 1. Distributed computing grid model
2.2 Scheduling Model Distributed computing grid mainly focuses on some specific grand application which takes hours, days, weeks and months while high throughout grid targets stream of tasks. Thus the scheduling purpose of our DCGM is not to maximize system utilization but to reduce the turn around time. The GDSSs make best effort decisions of static scheduling using predicable performance model of specific applications and submit the job to the resources selected. The scheduling model is formally defined as a seven-tuple: where the meanings are as follows: 1. R is a finite and nonempty set of the non-dedicated and heterogeneous GCRs. 2. represents an application requirement model, satisfying is a finite and nonempty set of application information.
60
3. 4. 5. 6. 7.
W. Zhang et al.
and are a finite set of GUG network and host minimal application requirement respectively, which provide the basic Qos guarantee. T is a finite and nonempty set of arbitrarily divisible grand-challenge tasks P is a finite and nonempty set of performance models determined by types of T . , S denotes the set of the start time of tasks } is nonempty set of mapping strategies. is a function filtering out the resources that do not meet the GUG minimal job requirements and reduce the resources set for the GDSS. is a function determining the best fit resource (or set of best resources) to submit a job, which is the core process of the GDSS.
3 The GDSS Design Combing the scheduling model of DCG and the general architecture presented in [8], we begin with a framework of a single GDSS node. The framework as shown in Figure 2 will give a broad overview of the work required to build a generic unit.
Fig. 2. The framework of the Grid Distributed Scheduling Server
There are three main phases when scheduling on the GDSSs. Phase One is resource filtering, which consists of distributed computing grid portal, XML parser, job priority queue and resource filter. In order to proceed to resource filtering, the users must specify task description and some minimal set of job requirements through Web portal which creates the XML document parsed by our DOM parser. Then, job priority queue is with responsibility for determining the priority of the job. Subsequently, resource filter removes unsuitable resources utilizing the information from GIS. At the end of phase one, the list of potential resources is generated. Phase Two involves mapping tasks and selecting the best resource set. Predicable information collector gathers the detailed information from the GIS. Our system adopts information provider based on Globus and NWS to support dynamic information collection. Job scheduling decision module is the key component of GDSSs,
Multisite Task Scheduling on Distributed Computing Grid
61
which determines the best-fit resource (or the resource set) as a meta request. The efficiency of job scheduling decision module is directly determined by best-fit resource selection algorithm. Our resource selection algorithm based on grid clustering will be explained in the next section. Subsequently, the meta request is sent to the GMSSs and the cooperating resource set is feed back after the GMSSs negotiate a compromise about the contention of different GUGs request the same GCRs at the same time. At the end of phase two, a set of cooperating resource is generated. In Phase Three the job is executed, which includes a file dispatcher and a result retriever. We adopt gridftp, GRAM services based on Globus to implement remote job submission and remote compilation. At last, the result is retrieved and displayed on the Web portal using Virtual Reality Modeling Language (VRML).
4 A Resource Selection Algorithm The resource selection algorithm is at the core of the job scheduling decision module and must have the ability to integrate multi-site computation power. Our Clusteringbased Grid Resource Selection (CGRS) algorithm clusters the set of available resources, generates the candidate schedules for all the subsets in each cluster and evaluates the candidate schedules to select a final schedule. Pseudo-code for our multi-site search procedure is given in Figure 3. The first method called by the procedure is GCRClustering ( ); The method clusters the available GCR into disjoint subsets, such that the network delays within each subset are lower than the network delays between subsets. The clustering algorithm of available GCRs clustering is so important as the basis of CGRS algorithm that we design a sophisticated clustering algorithm based on data mining [10] method, which will be expounded in the following section. Another core method is the MapAndPredict ( ). The method adopts performance model and mapping strategy of some specific applications to predict execution time. Because the predicted execution time directly determines the correctness of the best schedule, performance model and mapping strategy plays an important role.
Fig. 3. Clustering-based Grid Resource Selection (CGRS) algorithm
62
W. Zhang et al.
Our methodology of CGRS algorithm is similar to the GrADS approach in that it decouples the performance model and adopts the multisite selection algorithm to promote application performance. However, the CGRS algorithm outperforms the schedule search procedure of GrADS in two aspects: Firstly, the CGRS algorithm introduces more sophisticated clustering algorithm than the method based on the Internet Domain Name Service adopted by the GrADS. . It is well-known that clustering algorithm based on DNS is unreasonable and imprecise. The CGRS algorithm adopts a new clustering method based on data mining [9] providing firmly theoretic ground for resource selection. Secondly, the CGRS algorithm is an O(n) algorithm, where n represents the available GCRs, if the GCRClustering method is decoupled and implemented by a separate module which runs periodically. The time complexity of GrADS is about where n and s represents the available GCRs and the number of clusters respectively.
4.1 Density-Based GCR Clustering (DGC) Algorithm The process of grouping a set of physical or abstract objects into classes of similar objects is called clustering .The purpose of GCR clustering, which serves as a pivotal preprocessing step for CGRS algorithm, is to identify the clusters of low intra-cluster network latencies to enable coarse-grain parallelism. We propose a density-based GCR clustering technique instead of the traditional DNS-based clustering method which leads to more static clusters. The basic ideas of DGC algorithm involve a number of new definitions: The neighborhood within a radius of a given edge is called the neighborhood of the edge, where radius represents network latency or bandwidth. If the of an edge contains at least a minimum number, MinPts, of edges, then the edge is called a core edge. Given a set of edges, D, we say that an edge p is directly density-reachable from edge q if p is within the of q. Now, the DGC algorithm is presented as follow: 1. All the directly density-reachable edges of every edge in the AvailableGCRPool are found and stored into the adjacency list. 2. Then, the DGC algorithm determines the core edges among the low latency edges or high bandwidth. 3. At last, it iteratively collects directly density-reachable edges from these core edges, which may involve the merge of a few density-reachable clusters. The process terminates when no new edge can be added to any cluster. The time complexity of DCG algorithm is where e is the edge number.
Multisite Task Scheduling on Distributed Computing Grid
63
5 Experiments The efficiency of the decoupled multi-site scheduling methodology itself has been demonstrated in [6].In this section, we present validation results for the density-based GCR Clustering (DGC) algorithm developed in Section 4.1. We have implemented DGC algorithm on the tree network topology, graph network topology and AS-level network topology shown in Figure 4. In each topology, according to a user-defined parameter D, the edges of graph can be classified into two categories: low-latency and high-latency. The low-latency edges are the edges between two black nodes while others are high-latency edges. In the experiment, we initialize MinPts and as 1, which means that the core edges itself are low-latency edges and at least directly connect with one low-latency edge. In the tree network topology, after clustering using DGC algorithm, three clusters {(1,2)(2,3)(2,9)(3,4)(4,5)},{(11,12)(11,13)(11,15)(13,14)},{(18,19)(19,20)(19,21)} are acquired and resource selection combinations of DGC algorithm are 9 less than that of the DNS-based method. In the graph network topology, only one cluster {(3,6)(3,7)(5,8)(6,8)(7,12)} is acquired and 7 resource selection combinations are erased. In AS-level network topology, the low-latency edges are {(1,2)(2,3)(3,4)(4,1)(5,6)(6,7)(7,8)(8,5)(9,10)(9,11)(9,12)}and the result of clustering is three clusters: {(1,2)(2,3)(3,4)(4,1)}{(5,6)(6,7)(7,8)(8,5)} and {(9,10)(9,11)(9,12)}.
Fig. 4. The tree, graph network and AS-level network topology
The above results indicate that our clustering strategy is correct and effective for clustering grid computing resources. It avoids the negative impact of high-latency edges, reduces the member number of the resource aggregate and the resource evaluation combination of CGRS algorithm.
6 Conclusion In this paper, a three-level architecture of the Distributed Computing Grid Model (DCGM) is brought forward and acts as the infrastructure of multisite scheduling environment. The design of the key component of multisite scheduling environment, Distributed Scheduling Server (GDSS), is discussed in detail.
64
W. Zhang et al.
Also, we focus on the multisite resource selection algorithm of GDSS. A heuristic strategy, Clustering-based Grid Resource Selection (CGRS) algorithm, was described. In the CGRS algorithm, we mainly introduce the Density-based GCR Clustering (DGC) algorithm to cluster the resources in the distributed computing grid and combine it with the decoupled scheduling approach. The next step in this research is to precisely quantify the benefit of the CGRS algorithm with actual internet application in real distributed computing grid environment. Moreover, we will involve more parallel applications such as loose synchronous applications and embarrassing applications into the schema of our scheduling.
References 1. Foster and C. Kesselman, The Grid: Blueprint for a New Computing Infrastructure, Morgan Kaufmann, San Fransisco, CA, 1999. 2. R. Raman, M. Livny and M.Solomon, Matchmaking: distributed resource management for high throughput computing, High Performance Distributed Computing, 1998. Proceedings. The Seventh International Symposium on 28-31 July 1998 Page(s): 140 -146 3. R.Buyya, D.Abramson and J Giddy, Nimrod/G: an architecture for a resource management and scheduling system in a global computational grid, High Performance Computing in the Asia-Pacific Region, 2000. Proceedings. The Fourth International Conference/Exhibition on May 2000, Volume: 1 , 14-17 Page(s): 283 -289 vol.1 4. Silver Design Overview, http://supercluster.org/projects/silver/designoverview.html 5. Krysztof Kurowski, Jarek Nabrzyski, and Juliusz Pulacki, User Preference Driven Multiobjective ResourceManagement in Grid Environments, Proceedings of CCGrid 2001, May 2001. 6. H. Dail, F. Berman and H. Casanova, A Decoupled Scheduling Approach for the Grads Program Development Environment, to appear in Journal of Parallel and Distributed Computing (JPDC), 2003 7. Carsten Ernemann, Volker Hamscher, Uwe Schwiegelshohn, Ramin Yahyapour and Achim Streit, On Advantages of Grid Computing for Parallel Job Scheduling, 2nd IEEE/ACM International Symposium on Cluster Computing and the Grid (CCGRID’02), May 21 - 24, 2002 , Berlin, Germany 8. J. Schopf, A General Architecture for Scheduling on the Grid. Submitted to special issue of JPDC on Grid Computing (2002) 9. Jiawei Han, Micheline Kamber, Data Mining: Concepts and Technology, Morgan Kaufmann, 2001
Adaptive Job Scheduling for a Service Grid Using a Genetic Algorithm Yang Gao1, Hongqiang Rong2, Frank Tong2, Zongwei Luo 2 , and Joshua Huang2 1
National Laboratory for Novel Software Technology, Nanjing University, Nanjing 210093, China
[email protected]
2
E-Business Technology Institute, The University of Hong Kong, Hong Kong, China {hrong,ftong,zwluo,jhuang}@eti.hku.hk
Abstract. This paper presents a new approach to scheduling jobs on a service Grid using a genetic algorithm (GA). A fitness function is defined to minimize the average execution time of scheduling N jobs to machines on the Grid. Two models are proposed to predict the execution time of a single job or multiple jobs on each machine with varied system load. The single service type model is used to schedule jobs of one single service to a machine while the multiple service types model schedules jobs of multiple services to a machine. The predicted execution times from these models are used as input to the genetic algorithm to schedule N jobs to M machines on the Grid. Experiments on a small Grid of four machines have shown a significant reduction of the average execution time by the new job scheduling approach.
1 Introduction One of the challenges for a service Grid is to efficiently process users’ requests to Grid services in large numbers. This is essentially a problem of optimal allocation of the Grid resources to complete the requested services within a given time slot through effective job scheduling. Given N jobs submitted at time to a service Grid that has machines to execute these jobs in parallel, the optimal job scheduling strategy is to minimize the execution time of these jobs subject to a given cost. Job scheduling problems on a service Grid can be divided into the three levels. System-level scheduling deals with the problem of assigning a single job to one of M machines on the Grid that can finish the job in the shortest time [1][6][4]. Application-level scheduling deals with the problem of scheduling N various jobs 1
The work was conducted when the author was visiting the E-Business Technology Institute of The University of Hong Kong, under the support of the IBM China Scholar Visitorship Program, Natural Science Foundation of P.R.China (No.60103012) and the National Grand Fundamental Research 973 Program of China (No.2002CB312002)
M. Li et al. (Eds.): GCC 2003, LNCS 3033, pp. 65–72, 2004. © Springer-Verlag Berlin Heidelberg 2004
66
Y. Gao et al.
that are submitted to the Grid at the same time slot to M machines of the Grid [3]. Grid-level scheduling deals with the problem that N jobs are submitted to the Grid at the same time slot but the Grid is lack of resources to complete these jobs in a given time slot. In such a situation, the Grid-level scheduling system needs to find other Grids to execute some of these jobs. Unlike job scheduling in parallel computing and cluster computing that usually use a static load model or performance model estimated from experience data [8], the Grid job scheduling uses a dynamic model to predict job execution time due to the heterogeneity of computing resources and dynamics of the machine load [7]. The traditional approach to job scheduling is to first model the available computing resources, then determine the system load and finally estimate the jobs’ execution time. Direct application of this approach to Grid job scheduling often results in poor performance due to the special characteristics of the Grid environment [2]. In addition, job scheduling in parallel computing and cluster computing emphasizes on the performance and load balance of the whole system while in Grid computing, different scheduling polices and algorithms are required to deal with different kinds of tasks [5]. In this paper, we present an approach to using a genetic algorithm (GA) to minimize the average execution time of scheduling N jobs on heterogenous machines on a service Grid. To solve this job scheduling problem, we first develop a model to predict the execution time of a single service (job) on different machines with varied system load. Then, we extend the single service model to the multiple service types model that deals with situations where different types of jobs arrive at each machine in sequence. With the multiple service types model, we define an objective function to evaluate the optimal scheduling of N services of different types to M machines of different load situations and use a genetic algorithm to find the solution by minimizing the objective function. We conducted simulated experiments on a small scale Grid composed of four machines with different capacities and operating systems. The experiment results have shown significant reduction of the average execution time by our approach in comparison with the random allocation and average allocation methods.
2 2.1
Adaptive Models for Predicting Job Execution Times Single Service Type Model
We first develop a model to predict the execution time of a single service or job on each machine on the Grid. The major factors that affect the execution time include the machine capacity, complexity of the algorithm for the service and the size of data involved. The machine’s capacity changes dynamically over system load. Because of the load dynamics and many other unknowns, it is impossible to predict the precise execution time of a job on a machine. We can only predict the possible execution time of a job from historical experiences and use this predicted execution time to schedule the execution of the job. In the service Grid,
Adaptive Job Scheduling for a Service Grid Using a Genetic Algorithm
67
the computational performance of each service is likely tested on each machine before it is published for use. Therefore, the computational performance and ability to process different sizes of data for each service can be known or learned incrementally from the historical data of using the service. The difficult part is to deal with the dynamic load of the system that affects the execution performance of the service to be submitted. To simplify this problem we first assume that only one service is submitted to the Grid at a time slot. Our objective is to optimize the performance of the whole system no matter whether the system has a light or heavy load. In order to increase system’s throughput, the scheduling system must maximize the numbers of completed jobs within a time slot. To solve this problem, we use the following model to predict the execution time of a single job on a machine.
Here, is the predicted execution time of a new job on machine is the number of times that the jobs of the same service have been executed on is the actual execution time of the same service on the same machine. is the learning rate. and as The historical values of and are stored on the machine, can be obtained by experiments. If there are jobs generated from the same service already running on machine the actual execution time of the job will be affected due to the system load. In this case we use the following model to predict the execution time of the job.
Here, is the predicted execution time of job on machine that has jobs of the same services still running. and on the right side are the last historical values of the expected execution time and actual execution time respectively. is the learning rate. Because of the dynamics of the system load, it is difficult to obtain However, the ratios of can be estimated. Using the ratios, the execution time of the job on machine can be predicted by
where
and as and approach constants if the Grid system is stable. Figure 1 explains the process of calculating the predicted execution time of job on machine When the first job is submitted to the Grid, its predicted
68
Y. Gao et al.
Fig. 1. Predict the execution time of the on a machine
job when there are
jobs still running
execution time on machine is calculated by (1). The second job arrives while the first job is still running on machine The predicted execution time of the second job on machine is calculated by (3). Similarly, we can calculate the predicted execution time of the job, on machine when the previous submitted jobs are still running on it.
2.2
Multiple Service Types Model
To predict the execution time of the jobs in multiple service types we use the following model.
where
The superscript indicates a type of service. The difference of (6) from equation (3) is that two subsequent jobs can be different services as shown in (7) and (8). Figure 2 shows how the predicted execution time of the job is calculated. Because the predicted execution times of all preceding jobs are known, the scheduling path is known for a particular sequence of jobs, e.g., shown as the light line in Figure 2. However, unlike the single service type model, depends on the scheduling path. In other words, different scheduling paths result in different execution times since services in each path are different. Therefore, in implementation, we do not save individual on machine but ratios instead. We can observe from Figure 2 that if there are S services of different types on machine and the maximal number of possible concurrent jobs is N, then the total stored weights of connection lines are It is feasible to store these weights in the scheduling system since the number of services on a machine is limited. To implement this scheduling algorithm, the Grid initializes all parameters and all based on experiments. When a new job arrives, the Grid predicts all execution times on each machine, sorts them and selects
Adaptive Job Scheduling for a Service Grid Using a Genetic Algorithm
69
a machine with the minimal execution time to execute this job. When the job ends, the scheduling system records the real execution time and adjusts the prediction value. When another new job arrives, the schedule system schedules the job based on these new prediction values. The computational complexity of this system-level scheduling algorithm is O(M), where M is the number of machines.
3
A GA Approach to Application-Level Scheduling
Application-level scheduling deals with the problem of scheduling N jobs of different service types to machines on the Grid. To solve this scheduling problem, we can use the execution time prediction models to calculate the predicted execution time of these jobs on each machine and find an optimal allocation of these jobs to the M machines by minimizing
subject to
where
is the average execution time of jobs on machine N is the total number of jobs submitted to the Grid at a given time slot and is the maximal number of jobs limited to machine is the current, private load on machine can be obtained from experiments or historical results of running different numbers of jobs on each machine. Figure 3 shows three examples. Essentially, each curve is the accumulative distribution function of (3). Interpolation and extrapolation can be used to obtain a particular value. is also determined by experiments. (9) can be optimized using a genetic algorithm. Table 1 shows the pseudo code of the algorithm. First, the Grid gatekeeper sends requests to all machines and inquires whether or not they can process the new jobs. Each machine checks its load according to the current system performance and returns the information to the gatekeeper. The machine which agrees to receive the new jobs returns its current load status, such as the current number of jobs and The Grid scheduling system produces initial population including certain jobs assignments, evaluates each individual’s fitness, chooses the individuals with higher fitness to make copies, performs crossover and mutation operations, obtains the new population, and evaluates each individual’s fitness in the new population. Finally,
70
Y. Gao et al.
Fig. 2. Predict the execution time of the job when the jobs of different service types are runing on the machine.
Fig. 3. The performance curves of these machines running different numbers of jobs.
the Grid obtains the nearly optimal jobs assignment strategy and assigns the jobs to each machine. At last, each machine receives the new jobs that will be scheduled by its OS. In this algorithm, indicates the population in the step.
4
Experimental Results and Analysis
We conducted two experiments to test our models on a small scale Grid consisting of 4 machines. In these experiments, only one service to calculate the Discrete Flourier Transform (DFT) was used. The scheduling time slot was set as one second. In the first experiment, a request of the DFT service to transform 100 points was sent to the Grid in each time slot. 1000 requests for the same service were sent consecutively. The Grid system-level scheduling model was used to schedule these 1000 jobs. Figure 4 shows the results of scheduling the jobs randomly and by using the multiple service types model. One can clearly see
Adaptive Job Scheduling for a Service Grid Using a Genetic Algorithm
71
the reduction of the average execution time by the prediction model. For example, in 1000 second time slots, the Grid finished more than 800 jobs scheduled by the prediction model while it could only complete 400 jobs by the random scheduling. Figure 5 shows the distribution of the difference between the predicted execution time and the actual execution time of 1000 jobs. Although a system error of -3.8s is present, the model is able to predict the execution time within a small variance (4.95s). Even for interactive analysis, this prediction error is acceptable in many applications .
Fig. 4. Comparison of random scheduling and model scheduling.
Fig. 5. Distribution of the difference between the predicted execution time and the actual execution time.
Fig. 6. Comparison of GA scheduling with Random scheduling and average scheduling.
Fig. 7. Performance of the GA scheduling algorithm.
In the second experiment, we conducted 20 tests. In each test, we changed the number of jobs submitted to the Grid in each time slot. The number of jobs increased from 20 to 100. Figure 6 shows the average execution time of jobs scheduled by the GA approach, the average scheduling and the random
72
Y. Gao et al.
scheduling. We can see that the GA approach performed best and the random scheduling performed worst. The performance of the average scheduling is close to the GA approach when the number of jobs is samll. When the number of jobs becomes large, the GA approach shows a clear advantage. For example, the average execution time of the average scheduling was 20 seconds longer than that of the GA approach when they scheduled 80 jobs. Figure 7 shows predicted execution time against the iterations of the genetic algorithm. Our experiments showed that a near-optimal scheduling can be found within 50 iterations.
5
Conclusions
In this paper, we have presented two prediction models that are used to predict the execution time of a job on a given machine with varied system load. Based on the prediction models, we have developed a genetic algorithm approach to scheduling N jobs of different services to M machines on a Grid. Our experiment results have shown that the GA approach can reduce the average execution time of N jobs run on the Grid in comparison with some naive scheduling methods. Our experiments also demonstrated that the prediction models can predict the execution time accurately.
References 1. The globus grid project. http://www.globus.org. 2. Miguel L. Bote-Lorenzo, Yannis A. Dimitriadis, and Eduardo Gomez-Sanchez. Grid characteristics and uses: a grid definition. In Proceeding of the First European Across Grids Conference, 2 2003. 3. Henri Casanova, MyungHo Kim, James S. Plank, and Jack J. Dongarra. Adaptive scheduling for task farming with grid middleware. The International Journal of High Performance Computing Applications, 13(3):231–240, Fall 1999. 4. Steve J. Chapin, D. Katramatos, J. Karpovich, and A. Grimshaw. Resource management in legion. Future Generation Computer Systems, 15(5–6):583–594, 1999. 5. Klaus Krauter, Rajkumar Buyya, and Muthucumaru Maheswaran. A taxonomy and survey of grid resource management systems for distributed computing. Software Practice and Experience, 2:135–164, 2002. 6. Rajesh Raman, Miron Livey, and Marvin Solomon. Matchmaking:distributed resource management for high throughput computing. In Proceedings of the seventh IEEE International Symposium on High Performance Distributed Computing, Chicago, IL, July 1998. 7. D. Thain, T. Tannenbaum, and Miron Livny. Condor and the grid. In Anthony J.G. Hey, Fran Berman, Geoffrey C. Fox, editor, Grid Computering: Making the Global Infrastructure a Reality, chapter 11, pages 299–335. Wiley, West Sussex, England, 2003. 8. Y. Zhang, H. Franke, J. E. Moreira, and A. Sivasubramaniam. An integrated approach to parallel scheduling using gang-scheduling, backfilling, and migration. In D.G. Feitlson and L. Rudolph, editors, JSSPP 2001, Lecture Notes in Computer Science, pages 133–158, Berlin Heidelberg, Springer-Verlag.
Resource Scheduling Algorithms for Grid Computing and Its Modeling and Analysis Using Petri Net* Yaojun Han1,2,3, Changjun Jiang1 ,You Fu1,2, and Xuemei Luo2,3 1
Department of Computer Science & Engineering, Tongji University, Shanghai, 200092, China 2 Department of Computer Science, Shandong University of Science & Technology, Qingdao, 266510, China 3 Lab. Computer Science, ISCAS, Beijing, 100080, China
[email protected]
Abstract. A resource scheduling algorithm called XMin-min is proposed in this paper. In the XMin-min algorithm, we consider not only the expected execution time of tasks, but also expected communication time when calculating expected completion time. In the paper, the execution cost of tasks and budget of application are selected as QoS and an algorithm XMin-min with QoS is also proposed. An extended high-level timed Petri net (EHLTPN) model suiting scheduling of resource in grid computing is presented in the paper. In the EHLTPN, the firing times assigned to transitions are functions of the tokens of input places. We construct a simple model for the resource scheduling in grid computing using EHLTPN. A definition of Reachable Scheduling Graph (RSG) of EHLTPN to analyze the timing property of the resource scheduling is given in this paper. Two algorithms can be use to settle the “state explosion” problem while constructing RSG of EHLTPN.
1 Introduction In grid computing environment, the scheduling problem becomes complex, as resources are geographically distributed, heterogeneous in nature, owned by different individuals or organizations [1]. It is well known that the choice of the best pairs of tasks and resources is a NP-complete problem. Some simple heuristics for dynamic scheduling of a class of independent tasks onto a heterogeneous computing system have been presented [2]. It is well known that the Min-min heuristics is now becoming the benchmark of such kinds of task/host scheduling problems. However, the Min-min algorithm is unable to balance the load well since it usually maps small tasks *
This work is support partially by projects of National Preeminent Youth Science Foundation (No. 60125205), National 863 Plan (2002AA4Z3430, 2002AA1Z2102A), Foundation for University Key Teacher by the Ministry of Education, Shanghai Science & Technology Research Plan (02DJ14064, 03JC14071), Open project of Laboratory of Computer Science, ISCAS (SYSKF0304).
M. Li et al. (Eds.): GCC 2003, LNCS 3033, pp. 73–80, 2004. © Springer-Verlag Berlin Heidelberg 2004
74
Y. Han et al.
first and did not deal with the Quality of Service (QoS). A novel QoS guided taskscheduling algorithm for grid computing was introduced in [3]. However, there are few algorithms consider the communication time of tasks while scheduling. An extension of Min-min algorithm called XMin-min is proposed in this paper. In the XMin-min algorithm, we consider not only the expected execution time of tasks, but also expected communication time of tasks when calculating expected completion time. In the paper, the execution cost of tasks and budget of application are selected as QoS. We give another scheduling algorithm XMin-min with QoS by embedding the QoS information into the XMin-min algorithm to improve the efficiency and the utilization of a grid system. In grid computing environment, the need arises in resource scheduling for powerful graphical and analytical tools such as Petri nets. Petri nets have gained more and more applications because of their ability to model asynchronous events, parallelism, connection, and synchronization [4]. In order to describe real processes well, many extensions of Petri nets such as colored Petri nets [5] and timed Petri nets [6] have been proposed. Some Petri nets models for scheduling were given in [7,8]. But, these models and their analysis technologies are not suitable to the resource scheduling in grid computing environment. Up to now, there are few Petri nets models for grid computing. We gave an extended colored time Petri net (ECTPN) model for describing and analyzing resource scheduling in grid computing environment in [9]. We modify the ECTPN and give an extended high-level timed Petri net (EHLTPN) model in order to well suit scheduling of resource in grid computing environment. In the EHLTPN, the firing times assigned to transitions are functions of the tokens of input places. A definition of reachable scheduling graph (RSG) to analyze the timing property of the resource scheduling in grid computing environmenis is given in this paper. Meantime, the XMin-min and XMin-min with QoS algorithms can be also use to settle the “state explosion” problem while constructing RSG of EHLTPN. The rest of this paper is organized as follows. Two algorithms are proposed in section 2. An EHLTPN model for the resource scheduling in grid computing environment is constructed in section 3. The definition of RSG is given in section4. Section 5 gives an example and experimental results. Section 6 concludes the paper.
2 Algorithms for Resource Scheduling We assume that there are m computing resources that are accessible to the user via m distinct network links, n tasks that are mapped onto m heterogeneous machines. The tasks are assumed to be independent. The expected execution time of task on machine is defined as the amount of time taken by to execute given has no load when is assigned. The expected transmit time is defined as the amount of time taken by transmitting task to machine from user site. Let denote the expected time machine will become ready to execute a task after finishing the execution of all tasks assigned to it at that point in time. The expected completion time of task on machine is defined as the wall-clock time at which completes In our paper,
Resource Scheduling Algorithms for Grid Computing and Its Modeling
75
Let denote the expected execution cost of task on machine denote the budget of task and B denote the total budget of all tasks Algorithm 1. XMin-min algorithm (1) For all tasks (2) For all machines (3) (4) Do until all tasks in are mapped (5) For each find the earliest completion time and that obtains it (6) Find with the minimum earliest completion time within budget B (7) Assign to that gives the earliest completion time within budget B (8) Delete task Update Update for all i (9) Enddo Algorithm 2. XMin-min Algorithm with QoS (1) For all tasks (2) For all machines (3) (4) Do until all tasks in are mapped (5) For each find the earliest completion time within budget ( i.e. and the machine that obtains it (6) Find with the minimum earliest completion time within budget B (7) Assign to that gives the earliest completion time within budget B (8) Delete task Update Update for all i (9) Enddo Obviously, above algorithms have the same complexity as the Min-min algorithm.
3 Petri Net Model for Resource Scheduling The basic concepts and properties of Petri nets have been introduced in [4,5,6], we do not intend to review them here. Definition 1. An extended high-level timed Petri net a eight-tuple where, is a finite nonempty set of places, is a finite nonempty set of transitions, is a finite set of directed arcs from P to T and T to P. C is a function: where is a power set of color set and are the negative function and positive function of P×T. is an initial marking that satisfies D is a set of firing durations, where firing duration is a function of the tokens of input places. Definition 2. An EHLTPN model for the resource scheduling in grid computing environment RSPN is a eight-tuple where, is a finite set of places, where, represents all unmapped tasks, represents the task selected to schedule using some algorithm,
76
Y. Han et al.
and represent the data of tasks used to reschedule, represent the tasks mapped to machine is a finite set of transitions, where, is used to select a task to schedule from unmapped tasks, represent the execution of any task on machine are used to modify the data of all unmapped tasks, is a finite set of arcs, is a set of colors, where u is the number of tasks in and M is the current marking, where and are selected from all unmapped tasks according to some algorithm, where u is the number of tasks in where is the running time of the task on the machine The graphical representation of RSPN is shown as figure 1.
Fig. 1. RSPN model
4 Reachable Scheduling Graph Definition 3. Let RSPN is an EHLTPN model for the resource scheduling. The reachable scheduling graph (RSG) of RSPN is defined as a directed graph with labeled directed edges and labeled nodes RSG(RSPN)=(V,E1,E2) and divided into m vertical sections corresponding to m machines and some levels. Proposition 1. The RSG(RSPN) =(V,E1,E2) is constructed by the following algorithm. (1) Let For j=1 to m do lv[j]=0. (2) Place in level 0 and tag “new”.
Resource Scheduling Algorithms for Grid Computing and Its Modeling
77
(3) If there exists no “new” node in V, then the algorithm ends, otherwise go to (4) (4) Select a “new” marking M and do the following: (4.1) While there exist at M, do the following for each enabled transitions at M:
(4.11) Obtain M’ that results from firing at M by calculating arc functions. (4.12) If (4.121) (4.122) If then lv[j]=lv[j]+1, M’ is placed in level lv[j] and section j and tag M’ “new”, where j is the index of and (4.123) If then is placed in level lv[j] and section j and tag M’ “new” and where i and j are the indexes of and respectively and (4.124) If then M’ is placed in level lv[j] and section j and tag "new", where j is the index of and (4.13) with (4.14)If then tag where (4.2) If there exists no transition t such that M[t>, then tag M “dead node”. (4.3) Remove “new” from M and go to (3). The correctness of the algorithm can be easily proven according to the definitions of RSPN and RSG and the firing rule of Petri net. In order to reduce the scale of RSG, we can use above two algorithms to generate successive nodes while calculating arc functions. Proposition 2. Let RSG(RSPN)=(V,E1,E2) is the reachable scheduling graph of RSPN. The sequence composed of “from beginning of level 1 along the edge E2 in section j represents the scheduling sequence of tasks on machine Proposition 3. Let RSG(RSPN)=(V,E1,E2) is the reachable scheduling graph of is in last level of section j. is the tag attached to Then the makespan for the complete schedule is equal to Example: Suppose that there are 4 independent tasks and there are two machines at time t. Table 1 gives the expected execution time, transmitting time, execution cost and budget data. The total budget required to run all tasks is 60.
The graphical representation of the RSPN for the example is similar to figure 1. We construct RSGs (shown in figure 2, 3 and 4) using the Min-min, XMin-min and XMin-min with QoS algorithms when calculating the arc functions of RSPN according to proposition 1 respectively.
78
Y. Han et al.
Fig. 2. The RSG constructed using Min-min
Fig. 3. The RSG constructed using XMin-min
Fig. 4. The RSG constructed using XMin-min with QoS.
From figure 2,3 and 4, we know that the Min-min algorithm gives a schedule sequence on machine and a makespan of 18, the XMin-min algorithm gives a schedule sequence on machine on machine and a makespan of 19, where execution time is 11, and the XMin-min with QoS
Resource Scheduling Algorithms for Grid Computing and Its Modeling
79
algorithm gives schedule sequence on machine and on machine and a makespan of 16, where execution time is 11. It shows that the XMinmin with QoS algorithm outperforms the XMin-min without QoS and the XMin-min algorithm outperforms the Min-min algorithm in this example.
5 Experimental Results and Discussion In our experimental testing, the system consists of a cluster named DAWNING 3000 including 4 nodes and 12 PCs. We design a program running the system evaluate the newly proposed scheduling algorithm. The expected execution time, expected transmit time and expected execution cost of tasks on machines were produced randomly by the program. The budget of each task is equal to the maximum of costs of 85%. The experimental evaluation of the algorithms is performed for n={50, 100,150,200} tasks. We get the average makespan and the cost of the 100 times. Table 2 and figure 5 shows the comparison of makespans and costs.
Fig. 5. (a) Makespans for three algorithms
(b) Costs for three algorithms
In order to compare three algorithms, we subtract the transmit time from makespan for Xmin-min and Xmin-min with QoS in figure 5. The difference of makespan among three algorithms is little in figure 5(a). But, from figure 5(b), we know that the difference of cost among three algorithms is big. The cost of Xmin-min with QoS is minimum. The bigger the number of tasks is, the bigger the difference of cost is.
80
Y. Han et al.
6 Conclusions In this paper, two resource scheduling algorithms dealing with execution time and transmitting time were presented. The example and experimental results show that the XMin-min with QoS algorithm outperforms the XMin-min without QoS. As a powerful graphical and analytical tool, an EHLTPN model was presented and a simple model for the resource scheduling in grid computing environment was constructed using EHLTPN. The reachable scheduling graph was given and used to analyze the timing property and the sequence of the resource scheduling efficiently and intuitively. Because the transmitting time values of tasks vary with time, we will consider the dynamic transmitting time when calculating the completion time in every iteration of the XMin-min and XMin-min with QoS algorithms in our future work.
References 1. Buyya, R., Giddy, J., Abramson, D.: An Evaluation of Economy-based Resource Trading and Scheduling on Computational Power Grids for parameter Sweep Applications. Proceedings of the Int. Workshop on Active Middleware Services (AMS 2000), Kluwer Academic Press, USA(2000). 2. Maheswaran, M., Ali, S., et al.: Dynamic Mapping of a Class of Independent Task onto Heterogeneous Computing Systems. IEEE Heterogeneous Computing Workshop (HCW’99),San Juan, Puerto Rico (1999). 3. He, X.-S., Sun, X.-H., Laszewski G. V..: A QoS Guided Scheduling Algorithm for Grid Computing. Proc. of the Int. Workshop on Grid and Cooperative Computing (GCC2002), Sanya,, China(2002)745-758. 4. Murata, T.: Petri Nets: Properties, Analysis And Applications. Proceeding of IEEE. Vol. 77, 4 (1989)541-580. 5. Jensen, K.: Coloured Petri nets: Basic Concepts, Analysis Methods and Practical Use, Vol. 1, Basic Concepts. Mono-graphs in Theoretical Computer Science. Berlin, Heideberg, New York: Springer-Verlag, 2nd corrected printing (1997). 6. Zuberek, W.M.: Timed Petri Nets: Definitions, Properties and Applications. Microelectron. Reliab., Vol. 31, 4(1991)627-644 7. Prashant Reddy, J., Kumanan, S., Krishnaiah Chetty, O.V..: Application of Petri Nets and a Genetic algorithm to Multi-Mode Multi-Resource Constrained Project Scheduling,” AMT 17 (2001)305-314. 8. Huang, B., Zhang, B.: A New Scheduling Model Based on Extended Petri Net - TREM Net. Proc. of the Int. Conference on Robotics and Automation, Vol. 1 (ICRA94-1). San Diego, CA , USA(1994)495-500. 9. Han Y.-J., Jiang C.-J.: Extended Colored Time Petri Net -Based Resource Scheduling in Grid Computing. Proc. of the Int. Workshop on Grid and Cooperative Computing (GCC2002), Sanya,, China(2002)7345-353.
Architecture of Grid Resource Allocation Management Based on QoS* Xiaozhi Wang and Junzhou Luo Department of Computer Science and Engineering, Southeast University Nanjing, 210096, P. R. China
[email protected],
[email protected]
Abstract. Qualities of service (QoS) and resource management are key technologies in grid. Through analyzing the characteristics of Grid QoS, this paper sets up the layered structure of Grid QoS. Based on the analysis of the content of grid resource allocation management (GRAM) based on QoS, this paper puts forward the architecture of GRAM based on QoS. Through mapping, converting and negotiating the QoS parameters, it can implant the user’s requirement about QoS in the process of resource allocation management, and connect Grid QoS with GRAM very well. All these provide a reasonable consulting model for QoS and resource allocation management in grid.
1 Introduction The total target of grid is to provide users the ability to harness the power of large numbers of heterogeneous resources: computational resources, storage resources, devices and useful information etc, which are distributed in the wide area and belong to different organizations. In Open Grid Services Architecture (OGSA [1]), all resources are organized in a rational way and formed virtual organizations, which are dynamic and expansive. Virtual organization makes it possible for the mapping of many logical resources cases to the same physical resource. Resource management can be conducted in virtual organization based on basic resource formation. So resource management encounters new challenges. On one hand, in OGSA, grid resources are transparent to grid users, in the form of logical resource. But they are distributed in physical and have their own management strategies. How to allocate and schedule these resources in virtual organization, and enhance their utilization are important problems for resource management to be solved in grid. On the other hand, different grid services have different QoS requests to resources participating in the service, and in the case of considering the service cost, different users can have different QoS needs. In OGSA, the QoS characteristics of physical resource cannot *
This work is supported by National 973 Fundamental Research Program of China (G1998030402) and National Natural Science Foundation of China (90204009)
M. Li et al. (Eds.): GCC 2003, LNCS 3033, pp. 81–88,2004. © Springer-Verlag Berlin Heidelberg 2004
82
X. Wang and J. Luo
represent that of logical resource. How to convert the user’s QoS request to particular QoS parameters that are in grid becomes a problem to be solved urgently. Moreover, the resource allocation under grid environment is closely related to Grid QoS, while carrying on resource management, one should consider the two synthetically. Based on above issues, through analyzing the characteristics of Grid QoS, we propose and set up the layered structure of Grid QoS. On the basis of analyzing the content of GRAM based on QoS, further, we propose the architecture of grid resource allocation management based on QoS (GRAM-QoS). Through the mapping among different layers of Grid QoS, it converts the user’s QoS demand to particular QoS parameters of resources, and implants the mapping conversion of QoS into the resource selection processes. Considering the characteristics of Grid QoS roundly, GRAM-QoS provides a reasonable consulting model for resource allocation management based on QoS. The rest of the paper is as follows. Section 2 reviews related work in GRA and Grid QoS. In Section 3, we analyze the characteristics of Grid QoS and set up the layered structure of Grid QoS. In Section 4, we propose the content of GRAM based on QoS, and introduce the architecture and working flow of GRAM-QoS. Finally, we conclude and point to future directions in Section 5.
2 Related Work and Limitations In [2], the author indexed the resource allocation in grid has two phases: the external and the internal. It points out the characteristics of resource allocation under the grid environment. In [3], the author introduced the economics method, which the service price of resources is determined by the market supply and demand state. It puts forward one new method about resource allocation in terms of service price. But they don’t consider the user’s QoS request synthetically. In [4][5][6][7], the author mainly researched the architecture, reservation strategy and scheduling technology based on resource co-reservation in grid computing systems. Other scholars studied grid resource allocation technology from different angles, e.g. [8][9][10], these research works raised the performance of GRA from different aspects. Though above works can offer QoS guarantee in some extent, they didn’t analyze the characteristics of Grid QoS roundly. So there isn’t a systemic solution based on Grid QoS in grid resource allocation up to now.
3 The Characteristics and Layered Structure of Grid QoS 3.1 The Characteristics of Grid QoS Quality of Service (QoS) is a synthetically guideline, which is used for measuring the satisfaction of a service. It describes some characteristics of a certain service. It’s expressed as a group of parameters using an understandable language to users. In
Architecture of Grid Resource Allocation Management Based on QoS
83
[11], the author divides the QoS of multimedia network system into network QoS and devices QoS. But it can’t summarize QoS issues in grid circumstance. In grid, QoS issues not only include network QoS issue and devices QoS issue, it should also include resource QoS issue. Resources in grid circumstance not only contain hard resource but also soft resource in the form of information, data and software, etc. They should respond to the resource demand of grid job as well as that of local job. Generally, the priority of local job is higher than that of grid job. So the status of the resource, such as load-factor, arrival rate of local job etc, will have important effect on the quality of resource to grid users. On the other hand, the performance of the device, which the resource lied on, also has important effect on the QoS to grid users. In order to evaluate the quality of grid resource accurately, we separate the devices QoS and resources QoS. Among them the devices QoS parameters express the QoS parameters of the specific devices such as response time, throughput capacity, etc, resources QoS parameters express the performance of resources in grid circumstance, such as load ability, interrupt rate, etc. The devices QoS parameters and resources QoS parameters are totally different. In addition, for all components in OGSA are virtual objects, grid users are only interest in logical resource, which is in virtual organization. The characteristic of physical resource should transparent to grid user. Based on the analyzing of last paragraph, the QoS characteristics of physical resource cannot represent that of logical resource. So in grid, we should also differentiate logical resource and physical resource. The Grid QoS system should provide strategy and function that can convert and map the QoS parameters of logical resources to that of the physical resources.
3.2 The Layered Structure of Grid QoS Because QoS have different descriptions to different objects, for example, QoS demands put forward by the end user maybe only some simple descriptions, such as bad, generally, better, best. The QoS demands of resource in that of grid service QoS is the QoS demands to logical resource and system, for instance, resources are excellent, system response time 180ms, system transmission speeds 2 Mb/s, etc. The final QoS parameters are a group of particular numerical value. Further extended in [11], grid QoS can be divided into four layers, as fig. 1 shows. The top of it is user layer, representing the QoS demand, brought forth by the users when they apply for the grid service. The second is the grid service layer. It describes the QoS demand of grid service, for instance, the responding time of service, the transmission rate of the system, and quality of resource that takes part in the service etc. The third is a layer of system and logical resource, which satisfies the QoS parameters in layer of grid service. In system QoS, it mainly refers to network QoS demands and device QoS demands. In logical resource QoS, it mainly refers to the QoS demands on resources in virtual organizations. The bottom is a layer of network, devices and physical resource. The layer of network QoS describes the performance of network, such as ability of loading, internal time, delay, bandwidth etc. The layer of devices QoS describes the demands on devices such as the responding time of
84
X. Wang and J. Luo
Fig. 1. Layered structure of Grid QoS
devices, throughput, etc. The layer of physical resource QoS describes the demands on physical resource that takes part in the service actually, such as loadable ability of physical resource, useable time, interruption rate of grid job etc. Through the analysis above, we can divide Grid QoS into three parts: network, devices and physical resource. QoS parameters of each layer are coincidentally converted from top to bottom or from bottom to top by specific grid system.
4 GRAM-QoS: GRAM Based on QoS 4.1 The Content of GRAM Based on QoS The activity of GRAM based on QoS exists in the process of service application, service execution and service close. At the stage of service application, the resource allocation management system will define user’s resource demands according to specific grid service, and convert user’s QoS demands to particular grid QoS parameters, then it will take these QoS parameters as constrained factors to search for available resources that satisfy the requirement in grid. In the process of searching, system maybe negotiate with the user, then get final result: not being able to supply, being able to supply or reducing QoS demands to supply. If the negotiation is successful finally, it means that service provider can provide resource with final QoS demands, and then system can carry out the admission control according to specific strategy. After that, it reserves the resource and sent the grid job to resource waiting pool, waiting to be scheduled and executed. If not successful, system should inform the user and terminate the application. At the executive stage of service, the resource allocation management system will monitor the resource which at the reserved state, and renew the relevant QoS information of them. If the information of reserved resource cannot satisfy the user’s demand, it should make new QoS negotiation or choose commutability resource in order to ensure that the user’s QoS demand can be satisfied. As for the resource at reserved state, it will be scheduled according to the strategies offered by the provider. Because in general situation, the priority of local job is higher than that of the grid job, the arrival of local job will lead to the interruption of grid job. In order to ensure that grid job can be done before deadline, it’s necessary to dynamic adjust the priority
Architecture of Grid Resource Allocation Management Based on QoS
85
of grid job, in another word, with closer to deadline, the priority of grid job should becomes higher. Adopting this scheme also can enhance the resource utilization. At the stage of close, system should release the resource and renew the statistical information of the resource. For the use of resource in grid need tolls, system should also record the information such as the cost of the used resource and the user’s account information etc.
4.2 Logical Structure of GRAM Based on QoS (GRAM-QoS) According to the analysis above about the content of GRM based on QoS, in addition to the analysis of the layered structure of Grid QoS, we propose the logical structure of GRAM based on QoS (GRAM-QoS), just as fig. 2 shows. The main modules are explained as follows. 1. Grid Services Market On one hand, Grid Service Market provides the function of inquire about grid service for the grid user; on the other hand, it provides a function of register and publish grid service for the service provider. When the provider register and publish, they should provide identity proves and relevant description of service, such as resource demand and QoS demand which with particular QoS parameters in different layers. 2. Grid Middleware Services This module is mainly responsible for sign-on, safety control, managing user’s information and accounting the information about the used resource. 3. Grid Resource Broker The Resource Information Service Center module is the information center of available resource in grid circumstance. It provides information about the quality and QoS parameters of the logical resource. The Resource Information Provider Service module in Grid resource node offers this information. The QoS Mapping & Converting module implements the mapping conversion from user’s QoS demand to particular QoS parameters in different layers. The QoS Negotiation module in Grid Resource Broker used for judging whether system QoS and logical resource QoS can satisfy user’s demands. The QoS Negotiation module in Grid Resource Node judges whether physical resource QoS, network QoS and devices QoS can satisfy the user’s demands. When presenting resources cannot satisfy the user’s demand, two QoS Negotiation modules should interact with relevant modules and inquire whether the user can reduce QoS demand. The Resource Monitor module is responsible for monitoring the reserved resources. If the QoS parameters of reserved resources cannot satisfy user’s demands, the module would get touch with the QoS Negotiation module to make new QoS negotiation or choose commutability resource. The Resource Information Provider Service module offers the information needed by this module. The Error Process module processes errors that come from the QoS Negotiation module with the resource, which cannot satisfy user’s QoS demands. It finishes the execution of grid service and reminds the user.
86
X. Wang and J. Luo
Fig. 2. Logical structure of GRAM based on QoS
4. Grid Resource Node The Resource Information Provider Service module locates in Grid Resource Node, which is used for monitoring the QoS information of physical resources in grid. It obtains the newest information of resources through the QoS Control module, and provides the Resource Information Service Center module and the Resource Monitor module with renewed information. If the result of the QoS negotiation is that it is able to provide resource that can satisfy user’s demand, the QoS Admission Control module would complete tasks such as resources co-allocation, conflict detect, deadlock detect and load balance, etc. Then, finally the module will finish the affirmation work requested by the user. The Trade Server module is responsible for determine the using price and record the information such as the total cost of the used resource and the user’s account information etc. The Resource Reservation module is responsible for setting resources reservation flag and sending grid job to the Waiting-job Pool, waiting to be scheduled. Otherwise, Waiting-job Pool should responsible for adjusting the priority of gird jobs dynamically. The Scheduler takes charge of the scheduling of jobs in Waiting-job Pool according to particular strategy. In general, the priority of local job is higher than that of the grid job. It is permitted that the grid job has higher priority when grid job is very close to its deadline. The QoS Control module takes charge of the control of all dynamic QoS parameters. It adjusts QoS parameters according to the result of QoS negotiation, such as bandwidth, buffer size, etc. It should also response the inquiry from the Resource Information Provider Service module and renew its state information.
Architecture of Grid Resource Allocation Management Based on QoS
87
4.3 Working Flow Without considering the service register and publication, starting with the grid service application, we give the working flow of GRAM-QoS as follows: 1) Through the Grid Middleware Services module, grid user sign-on the grid system; 2) Grid user inquire and apply for grid service through Grid Services Market; 3) System confirms user’s resource demands according to the specific grid service; 4) The user puts forward QoS demand; 5) The QoS Mapping & Converting module implements the mapping conversion from user’s QoS demand to particular QoS parameters in different layers; 6) System chooses logical resources according to that needed by grid service in Resource Information Service Center. Through QoS negotiating, mapping and converting, system assures that selected logical resources can satisfy user’s QoS demands. If not finding resource that can satisfy the demands, the Error Process module would inform the user and terminate the applying; 7) According to the result from step 6), system inquire about the information of physical resources according the mapping relation between logical resource and physical resource; 8) Through the QoS Negotiation module in Grid Resource Node, system judges whether physical resource QoS, network QoS and devices QoS can satisfy the user’s demands. When presenting resources cannot fully satisfy the user’s demand, two QoS Negotiation modules should interact with relevant modules and inquire whether the user can reduce QoS demand, working flow go back to step 6); 9) Then the QoS Admission Control module implements affirmation work requested by grid job; 10) The Trade Server module determines the using price of resource and records the information about the used resource; 11) The Resource Reservation module sets up resource reservation flag and record QoS demands; 12) Grid job enters Waiting-job Pool. The Waiting-job Pool module takes charge of dynamic adjust the priority of grid jobs in Waiting-job Pool; 13) The Resource Monitor module monitors the state of reserved resources; 14) The Scheduler schedules local jobs and grid jobs in Waiting-job Pool according to particular strategy; 15) The QoS Control module adjusts QoS parameters according to the result of QoS negotiation and reacts the requirement from the Resource Information Provider Service module and renews its information about resource state.
5 Conclusions and Future Work Grid QoS and resource management are key technologies in grid. The relationship between them is much closer in OGSA. Through analyzing the QoS characteristic in grid, we propose and set up the layered structure of QoS in grid, which provides a reasonable gist for mapping and converting QoS parameters in grid. On the basis of
88
X. Wang and J. Luo
analyzing the content of GRAM based on QoS, we put forward the architecture of GRAM based on QoS (GRAM-QoS). The GRAM-QoS provides a reasonable consulting model for the QoS and resource allocation management in grid. In future work, we plan to design a simulation platform based on Grid QoS to experiment the usability of GRAM-QoS and enhance its performance. We also aim to implement GRAMA-QoS on Globus toolkit. Another interesting aspect is to study the technology of dynamic adjust the priority of grid job. In this aspect, we maybe consult relevant solution of CORBA [12]. Furthermore, we plan to formalize the description language about the parameters of Grid QoS, which is based on XML.
References I. Foster, C. Kesselman, Jeffrey M. Nick, S. Tuecke. The Physiology of the Grid: An Open Grid Services architecture for Distributed Systems Integration. http://www.gridforum.org/ogsi-wg/drafts/ogsa_draft2.9_2002-06-22.pdf 2. Chen Hongtu, M. Maheswaran. Distributed dynamic scheduling of composite tasks on grid computing systems. Parallel and Distributed Processing Symposium., Proceedings International, IPDPS 2002, on page(s): 88-97 3. R. Buyya, D. Abramson, J. Giddy. A case for economy grid architecture for service oriented grid computing. Parallel and Distributed Processing Symposium., Proceedings 15th International, Apr 2001, on page(s): 776-790 4. L. Foster, C. Kesselman, C. Lee, R. Lindell, K. Nahrstedt, A. Roy. A Distributed Resource Management Architecture that Supports Advance Reservations and Co-Allocation. Intl Workshop on Quality of Service, 1999 5. K. Czajkowski, I. Foster, and C. Kesselman. Resource Co-Allocation in Computational Grids. Proceedings of the Eighth IEEE International Symposium on High Performance Distributed Computing (HPDC-8), 1999 on page(s). 219-228 6. W. Smith, I. Foster, V. Taylor. Scheduling with advanced reservations. Parallel and Distributed Processing Symposium, 2000. IPDPS 2000. Proceedings. 14th International, 1-5 May 2000, on page(s): 127 –132 7. Lizhe Wang, Wentong Cai, Bu-Sung Lee, Simon See, Wei Jie. Resource co-allocation for parallel tasks in computational grids. Challenges of Large Applications in Distributed Environments, 2003. Proceedings of the International Workshop on , 21 June 2003, on page(s): 88 –95 8. Omer F. Rana, Michael Winikoff, Lin Padgham, James Harland. Applying conflict management strategies in BDI agents for resource management in computational grids Author. IEEE Computer Society Press. 2002, on page(s): 205-214 9. Jonghun Park. A scalable protocol for deadlock and livelock free co-allocation of resources in Internet computing. Applications and the Internet, 2003. Proceedings. 2003 Symposium on , 27-31 Jan. 2003, on page(s): 66 –73 10. Grosu Daniel, Anthony T. Chronopoulos. Algorithmic Mechanism Design for Load Balancing in Distributed Systems. Transactions on Systems, Man, and Cybernetics - Part B: Cybernetics: Accepted for future publication, 2003,on page(s): 1-8 11. K. Nahrstedt, R. Steinmete. Resource Management in Networked Multimedia Systems. Computer, May 1995, Volume: 28 Issue: 5, on page(s): 52 –63 12. Y. Wang, F. Brasileiro, E. Anceaume, F. Greve, and M. Hurfin. Avoiding Priority Inversion on the Processing of Requests by Active Replicated Servers. Proc. Int’l Conf. Dependable Systems and Networks (DSN 2001), on page(s): 97-106, 2001 1.
An Improved Ganglia-Like Clusters Monitoring System* Wenguo Wei1,2 , Shoubin Dong 1 , Ling Zhang1, and Zhengyou Liang1 1
Guangdong Key Laboratory of Computer Network, South China University of Technology, Guangzhou, 510641, P.R.China {wgwei, 2
sbdong,
ling,
zhyliang}@scut.edu.cn
Department of Computer Science, Guangdong Polytechnic Normal University, Guangzhou, 510665, P.R.China
Abstract. Ganglia [1] is a scalable distributed monitoring system for high performance computing systems such as clusters and Grids. We propose an improved Ganglia-like clusters monitoring system, which has more reliability with federation node and associated link failures; some monitoring data is accessed by permission; adding control functions such as restart or shutdown confusion processes; send email or pager to cluster administrator when important event occurs; and optionally select some data to federation node based on user policy in order to speedup the WAN access. We have implemented a prototype system.
1 Introduction Currently there has been an enormous shift in high performance computing from systems composed of small numbers of computationally massive devices to systems composed of large numbers of commodity components. This architectural shift from the few to the many is causing designers of high performance systems to revisit numerous design issues such as scale, reliability, heterogeneity, manageability, and system evolution over time. With clusters now the de facto building block for high performance systems, scale and reliability have become key issues, as many independently failing and unreliable components need to be continuously accounted for and managed over time. Heterogeneity, previously a non-issue when running a single vector supercomputer or an MPP, must now be designed for from the beginning, since systems that grow over time are unlikely to scale with the same hardware and software base. Manageability also becomes of paramount importance, since clusters today commonly consist of hundreds or even thousands of nodes. Finally, as systems evolve to accommodate growth, system configurations inevitably need to adapt. In summary, high performance systems today have sharply diverged from the monolithic machines of the past and now face the same set of challenges as that of largescale distributed systems. * This research was supported by Guangdong Key Laboratory of Computer Network under grant 2002B60113. M. Li et al. (Eds.): GCC 2003, LNCS 3033, pp. 89–96, 2004. © Springer-Verlag Berlin Heidelberg 2004
90
W. Wei et al.
This paper presents the design and implementation of the improved Ganglia-like distributed monitoring system. It is organized as follows. In Section 2, we describe the key challenges in building a distributed monitoring system and why we select Ganglia to improve, then we analyze the architecture of Ganglia, finally we point out Ganglia’s main issues. In Section 3, we describe our current design and implementation of Ganglia-like system that is improved at several fields. In Section 4, we present a performance analysis of our system theoretically. And in Section 5, we conclude the paper.
2 The Presupposition and Foundation of Our Work 2.1 Monitoring System Design Challenges The key design challenges for distributed monitoring systems thus include: Scalability: The system should scale gracefully with the number of nodes in the system. Clusters commonly consist of hundreds nodes. Grid computing efforts, such as TeraGrid [2], will eventually push these numbers out even further. Robustness: The system should be robust to node and network failures of various types. As systems scale in the number of nodes, failures become inevitable. The system should localize such failures so that the system continues to operate and delivers useful service in the presence of failures. Extensibility: The system should be extensible in the types of data that are monitored. It is impossible to know a priori everything that ever might want to be monitored. The system should allow new data to be collected and monitored. Manageability: The system should incur management overheads that scale slowly with the number of nodes. For example, managing the system should not require a linear increase in system administrator time as the number of nodes increases. Manual configuration should also be avoided as much as possible. Portability: The system should be portable to a variety of operating systems and CPU architectures. Despite the recent trend towards Linux on x86, there is still wide variation in hardware and software used for HPC. Systems such as Globus [3] further facilitate use of such heterogeneous systems.
2.2 Why Ganglia? There are a number of research efforts centered on monitoring of clusters, but only a handful that have a focus on scale. Supermon [4] is a hierarchical cluster monitoring system that uses a statically configured hierarchy of point-to-point connections to gather and aggregate cluster data collected by custom kernel modules running on each cluster node. CARD [5] is a hierarchical cluster monitoring system that uses a statically configured hierarchy of relational databases to gather, aggregate, and index cluster data. Compared to these systems, Ganglia differs in four key respects. First, Ganglia uses a hybrid approach to monitoring which inherits the desirable properties
An Improved Ganglia-Like Clusters Monitoring System
91
of listen/announce protocols including automatic discovery of cluster membership, no manual configuration, at the same time still permitting federation in a hierarchical manner. Second, Ganglia makes extensive use of widely-used, self-contained technologies such as XML and XDR which facilitate reuse and have rich sets of tools that build on these technologies. Third, Ganglia makes use of simple design principles and sound engineering to achieve high levels of robustness, ease of management, and portability. Finally, Ganglia has demonstrated operation at scale.
2.3 Ganglia Architecture Ganglia is based on a hierarchical design targeted at federations of clusters (Figure 1). It relies on a multicast-based listen/announce protocol [6,7] to monitor state within clusters and uses a tree of point-to-point connections amongst representative cluster nodes to federate clusters and aggregate their state. Within each cluster, Ganglia uses heartbeat messages on a well-known multicast address as the basis for a membership protocol. Membership is maintained by using the reception of a heartbeat as a sign that a node is available and the non-reception of a heartbeat over a small multiple of a periodic announcement interval as a sign that a node is unavailable.
Fig. 1. Ganglia architecture
Each node (daemon “gmond”) monitors its local resources and sends multicast packets containing monitoring data on a well-known multicast address whenever significant updates occur. All nodes in same cluster always have an approximate view of the entire cluster’s state and this state is easily reconstructed after a crash. Ganglia (daemon “gmetad”) federates multiple clusters together using a tree of point-to-point connections. Each leaf node specifies a node in a specific cluster being federated, while nodes higher up in the tree specify aggregation points. Each leaf node logically
92
W. Wei et al.
represents a distinct cluster while each non-leaf node logically represents a set of clusters. (You can specify multiple cluster nodes for each leaf to handle failures.) Aggregation at each point in the tree is done by polling child nodes at periodic intervals. Monitoring data from both leaf nodes and aggregation points is then exported.
2.4 Ganglia’s Main Issues There are several issues in Ganglia (2.x version): If any aggregation nodes and associated links are failure, then all the data of its leaf nodes (a set of clusters) cannot be collected, i.e. it provides no redundancy of non-leaf nodes and associated links. Ganglia is a distributed monitoring system that may span multiple clusters, if those clusters belong to different organization, some clusters owner may not want anyone to know all information Ganglia reported. So a mechanism must be proposed to access monitoring data by permission. There is little or no control mechanism. Sometimes people not only monitor passively, but also want to restart or kill some processes, or want Ganglia send email or pager to cluster administrator if any important event occurs. Ganglia aggregates all data that gmond reported to client, even if there is many clusters, each cluster is composed of many nodes, and the network is slowly. To speedup network access, only part of monitoring data (e.g. dynamic information) is sent when network is busy, however user have choice to see all data if they want. Infrastructure limitation. Ganglia has a flat namespace, i.e. it assumes that all measurements on hosts can be easily represented by a simple key/value pair. This may hold for some metrics such as the number of CPUs but fails miserably when you want something like the %CPU user for process 1289.
3 Improvements and Implementation 3.1 Improved Reliability of Whole System As systems scale in the number of nodes, failures become both inevitable. If any aggregation nodes and associated links are failure, then all the data of its leaf nodes (a set of clusters) cannot be collected, i.e. it provides no redundancy of non-leaf nodes and associated links. So we assume any of two aggregation nodes have at least two different paths linked (may not directly linked) in the monitored system, i.e. the structure of monitored system isn’t a tree but contain rings. We propose a mechanism to deal with failure of aggregation nodes. Data collection in gmetad is done by periodically polling a collection of child data sources, which are specified in a configuration file. Each data source is identified using a unique tag and has multiple IP address/TCP port pairs associated with it, each of which is equally capable of providing data for the given data source. It use configuration files for specifying the structure of the federation tree for simplicity and
An Improved Ganglia-Like Clusters Monitoring System
93
since computational Grids, while consisting of many nodes, typically consist of only a small number of distinct sites.
Fig. 2. Example of monitored system logic connection relationship
Configuration File’s Structure. If a case of monitored system is as figure 2. Our aggregation node’s configuration file extends Ganglia function. We explain as following (figure 3): There are two types data source, one is gmond (a cluster state), and another is gmetad (a set of clusters state). For gmond type data source, spokesman is any node of the cluster, IP address and TCP port pairs can identify it, and generally we can specify multiple nodes for redundancy. The parent field is up level or same level aggregation node to collect its monitoring data, two types parent nodes, i.e. primary parent is the main aggregation node, secondary parent is backup node, it begins to work when primary is unavailable. For another data source gmetad, there is only parent field, which is also used for data collecting. Example of lowest aggregation node configuration file is as figure 3.
Fig. 3. Example of lowest aggregation node’s configuration file
Procedure of Monitoring Data Collecting. If all aggregation nodes work normally, collecting data is done just as Ganglia by polling child nodes at periodic intervals.
94
W. Wei et al.
When any aggregation node is failure (for example, in figure 2, Agg1 is failure), its upper aggregation node (the primary parent node: Agg11) triggers a message to the failed aggregation node’s lower nodes (Data Source1 and Data Source2) to send monitoring data to its secondary parent node (Agg2). Reliability Analysis. This solution has better reliability then Ganglia. If the failure node is a cluster spokesman, the engine (Listening thread) could collect data from any other spokesman (at least 2 spokesman, however you can specify many spokesman if you like), if the failure node is an aggregation node, which is parent node of a data source, then the data source monitoring data can be collected by another parent node. According to graph connectivity theory [8], the connectivity of monitored system topological graph is at least 2, because any of two aggregation nodes have at least two different links in the monitored system. When both parent nodes fail synchronously, then some data may not be collected because of disconnection of the graph. So our solution can work with many numbers of spokesman failures (at least a spokesman is running) and one of parent node failure, its reliability significantly improved. Anyway, if the connectivity of graph is bigger, the reliability is higher.
3.2 Accessing Monitoring Data by Permission Ganglia is a distributed monitoring system that may span multiple clusters, if those clusters belong to different organization, some clusters owners may not want anyone to know all information (for example the running processes) Ganglia reported. So we propose a mechanism to access monitoring data by permission. We add a one-byte field-- “security” to some metrics by default, anyone whose permission is bigger then the field could see this metric data, and the granularity of permission is metric. Further, we can extend it to more levels security control. However, cluster administrator can customize it by adding more metrics to security control, or reducing some metrics from security control.
3.3 More Control Functions and Aggressive Behaviors Ganglia has little or no control mechanism. Sometimes people not only monitor passively, but also want to clear some died processes, or restart some confusion processes, of course only anyone has permission could do it, or expect Ganglia to send email or pager to cluster administrator if any important event occurs. We implement the process control by root authorization. The cluster administrator will be notified when any important events occur such as disk is over 95% full, CPU load average is unacceptably high, some important processes have died, can’t connect to special IP address and some service is down etc. We modify Ganglia engine to implement this function.
An Improved Ganglia-Like Clusters Monitoring System
95
3.4 Aggregation Monitoring Data by User Policy Ganglia aggregates all data that gmond (Ganglia monitoring daemon) reported to client, even if the number and size of cluster is big, and the network is slowly. To speedup network access, it’s necessary to have part of monitoring data sent, for example, dynamic information is sent when network is busy. We implement a policy to send data selectively by 4 approaches. The first is by basic static data such as the number of CPUs, operating system (name, version, architecture); the second is by dynamic data such as %CPU (user, nice, system, idle), load (1, 5, and 15-minute averages), memory (free, shared), processes (running, total), free swap etc; the third is by granularity of data, I.e. we limit how deeply the xml data is recursively displayed, there are 3 granularity: cluster, node and metric; the fourth is customized by the above 3 approaches. However, user have choice to see all data if they want and have permission to see it.
3.5 Hierarchical Namespace for Monitoring Data Ganglia has a flat namespace, i.e. it assumes that all measurements on hosts can be easily represented by a simple key/value pair. This may hold for some metrics such as the number of CPUs but fails miserably when you want something like the %CPU user for process 1289, which needs at least 3 fields to represent it. We implement a hierarchical namespace that can have any arbitrary depth (limited only by maximum stack size), this hierarchical namespace can copy with vary data structure.
4 Performance Analysis We improve data storage structure by adding a field to some metrics to deal with permission and change flat namespace to hierarchical namespace; repair Ganglia engine (for example, Listening thread) for aggregation node’s failure and send notify when important event occurs etc. These improvements only add little operational overhead, Theoretical analysis shows sacrificing little performance to get more reliability and flexibility. A quantitative comparison analysis of Ganglia and our system gained through real world deployments on distributed-systems is under taking.
5 Summary Our system improves Ganglia from 5 aspects as following: Enhance the whole reliability from aggregation node’s failure; increase permission assignment and control function; more flexible monitoring data collecting and hierarchical namespace for data storage. This system has good performance and reliability to manage middle and large multiple-clusters environment. Further enhancements and optimizations of this
96
W. Wei et al.
model are currently under investigation. Now Ganglia can monitor PlanetLab [9], which currently consists of 102 nodes distributed across 42 sites spanning three continents: North America, Europe, and Australia. We believe our system will do better on CERNET or ChinaGrid in future.
References 1. 2. 3. 4. 5. 6.
7.
8. 9.
Massie, M. L., Chun, B. N., and Culler, D. E. The Ganglia Distributed Monitoring System: Design, Implementation, and Experience, submitted for publication, February 2003. The TeraGrid Project. Teragrid project web page (http://www.teragrid.org), 2001. I. Foster and C. Kesselman. Globus: A meta computing infrastructure toolkit. International Journal of Supercomputer Applications, 11(2): 115–128, 1997. Matt Sottile and Ron Minnich. Supermon: A high speed cluster monitoring system. In Proceedings of Cluster 2002, September 2002. Eric Anderson and Dave Patterson. Extensible, scalable monitoring for clusters of computers. In Proceedings of the 11th Systems Administration Conference, October 1997. Elan Amir, Steven McCanne, and Randy H. Katz. An active service framework and its application to realtime multimedia transcoding. In Proceedings of the ACM SIGCOMM ’98 Conference on Communications Architectures and Protocols, pages 178–189, 1998. Brent N. Chun and David E. Culler. Rexec: A decentralized, secure remote execution environment for clusters. In Proceedings of the 4th Workshop on Communication, Architecture and Applications for Network based Parallel Computing, January 2000. F. Hyarary, Graph Theory, Addison-Wesley, Reading, Mass, 1969. Larry Peterson, David Culler, Tom Anderson, and Timothy Roscoe. A blueprint for introducing disruptive technology into the internet. In Proceedings of the 1st Workshop on Hot Topics in Networks (HotNets-I), October 2002.
Effective OpenMP Extensions for Irregular Applications on Cluster Environments Minyi Guo1, Jiannong Cao2, Weng-Long Chang3, Li Li1, and Chengfei Liu4 1
Department of Computer Software, The University of Aizu, Aizu-Wakamatsu City, Fukushima 965-8580, Japan minyi@u–aizu.ac.jp 2
4
Department of Computing, The Hong Kong Polytechnic University, Kowloon, Hong Kong 3 Department of Information Management, Southern Taiwan University of Technology, Tainan County, Taiwan School of Computer and Information Science, University of South Australia, Mawson Lakes, South Australia 5095, Australia
Abstract. Sparse and unstructured computations are widely used in Scientific and Engineering Applications. Such problem inherent in sparse and unstructured computations is called irregular problem. In this paper, we propose some extensions to OpenMP directives, aiming at efficient irregular OpenMP codes to be executed in parallel. These OpenMP directives include scheduling for irregular loops, inspector/executor for parallelizing irregular reduction, and eliminating ordered loops. We also introduce implementation strategies with respect to these extensions.
1
Introduction
Many codes in scientific and engineering computing involve sparse and unstructured problems in which array accesses are made through a level of indirection or nonlinear array subscript expressions. This means that the data arrays are indexed either through the values in other arrays, which are called indirection arrays/index arrays, or through non-affine subscripts. The use of indirect/nonlinear indexing causes the data access patterns, i.e. the indices of the data arrays being accessed, to be highly irregular. Such a problem is called irregular problem. Exploiting parallelism for irregular problems becomes very difficult due to their irregular data access pattern. A typical example is shown in Fig. 1. In the loop, elements are moved across the columns of a 2D array based on the information provided in the indirection arrays prev_elem and next_elem. The elements of array cell are shuffled and stored in array new_cell. If this loop is split across OpenMP threads with different threads taking care of different values of the prev_elam and next_elem may have the same values in different threads at the same time. This may result in a potential problem when updating the value of new_cell. There are some simple solutions to this problem, which include making all the updates atomic, or having each thread compute temporary results which are M. Li et al. (Eds.): GCC 2003, LNCS 3033, pp. 97–104, 2004. © Springer-Verlag Berlin Heidelberg 2004
98
M. Guo et al.
then combined across threads. However, for the extremely common situation of sparse array access neither of these approaches is efficient.
Fig. 1. A typical irregular loop
2
Requirements of Irregular Loop Scheduling
When parallelizing a loop in OpenMP, we may use the schedule clause to perform different scheduling policies which affect how loop iterations are mapped onto threads. There are four scheduling policies available in OpenMP: static Scheduling, dynamic scheduling, guided scheduling, and runtime scheduling. In order to achieve load balance for irregular loops, it is better to select dynamic or guided scheduling. In dynamic and guided scheduling schemes, the chunk parcel follows the owner computers rule. This rule specifies that, on a single-statement loop, each iteration will be executed by the processor which owns the left hand side array reference of the assignment for that iteration. However, if irregular loops are parceled in terms of dynamic scheduling, the performance of total execution may not be improved even if the load balance is achieved. The reason is that the communication overhead among threads may be considerable, especially for cluster environments or software distributed-shared memory (DSM) systems. Consider the following irregular loop.
Without
loss
of generality, and
for iteration assuming are distributed onto threads
that
Effective OpenMP Extensions for Irregular Applications
99
and respectively. Then the iteration of executing S1, S2, and S3 would be partitioned to threads and respectively. The following table shows the owner of executing assignments and the required communications and synchronizations for the example loop.
We can conclude that owner computes rule is often not best suited for irregular codes. Another situation is shown in Fig. 1. The index may have the same values on different threads. When parallelized in the cluster environment, there are often inter-thread dependencies in which two different iterations of the loop modify the same data. This situation prevents the loop from being processed in parallel, and thus serializes its execution. Though OpenMP provides two mechanisms that help in the parallelization of such loops: atomic and critical directives. These mechanisms, however, are excessively expensive in codes where not all the accesses need to be done in mutual exclusion and in other two situations, irregular reduction and loops in which only some iterations need to be executed in sequential order. As such, we propose a new OpenMP directive irregular, for loops that have irregular data access patterns. The directive will provide an efficient alternative to load balance, iteration partitioning and irregular data access.
3
OpenMP Directive Extensions for Irregular Loops
This section introduces our extensions to OpenMP, the irregular directive. The irregular directive can be applied to the parallel do directive in one of the following situations: When the parallel region is recognized as an irregular loop: in this case the compiler will invoke a runtime library which partitions irregular loop according to a special computes rule. When an ordered clause is recognized in the parallel region where the loop is irregular: in this case the compiler will treat this loop as partially ordered; that is, some iterations are executed sequentially while others may be executed in parallel. When an reduction clause is recognized in the parallel region where the loop is irregular: in this case the compiler will invoke an inspector/executor routines to perform irregular reduction in parallel.
100
M. Guo et al.
The irregular directives in extended OpenMP version may have the following patterns: This designates that the compiler will encounter an irregular loop, where irarrayl,. . .,irarrayN are possible indirection arrays, or This designates that the compiler will encounter a special irregular reduction or irregular ordered loop where expr1, .... exprN are expressions such as loop index variables.
3.1
Irregular Loop Scheduling
Irregular loop are frequently found in the core of scientific and engineering applications. The following loop is a more complicated irregular loop, which is a simplified version extracted from ZEUS-2D code:
For the above loop, the compiler will consider communication overhead when the iteration is partitioned to Although the number of elements to be communicated is 6, same as the former, but the communication steps are reduced (three times). This improvement is important when the outer sequential time step-loop is large. This illustrates that the owner computes rule is not always an optimal scheme for guiding partition of loop iterations.
3.2
Partially Ordered Loops
A special case for the example in Fig. 1 occurs when a shared update needs to be performed not only in a mutual exclusive manner but also in an ordered way. The use of the irregular clause in this case tells the compiler that for those iterations which may update the same data in the different threads, they need to be executed in an ordered way. There is no change to other iterations. An example of code using the indirect clause in this manner is shown as follows:
Effective OpenMP Extensions for Irregular Applications
3.3
101
Irregular Reduction
Some scientific applications need to perform reduction operations which are not directly parallelizable, where the update index for the element is not the induction variable of the loop, but a function of it, or another array. The following code shows an example of such a case.
The example shows that the computation is irregular because accesses to array y are determined by the index arrays idx1 and idx2, preventing the compiler from analyzing accesses exactly at compile time. The only way to parallelize the code using OpenMP is to protect the update of the y array either with atomic or with critical directives. These solutions, however, are excessively expensive in codes where not all the accesses need to be done in mutual exclusion. The inclusion of the irregular clause in the parallel do directive in the presence of a reduction clause tells the compiler that the reduction being performed in the parallel loop has an irregular data access pattern, but some parts of it can be executed in parallel, thus enabling the compiler to generate code to deal with this situation. The implementation of this clause will be introduced in the next section.
102
4
M. Guo et al.
Implementation
Our extended irregular directives for OpenMP can be implemented by adding several library routines in the compiler. The implementation strategies and algorithms are outlined in this section.
4.1
Implementation of Irregular Scheduling
We adopt the strategy of loop iteration partitioning for irregular codes by following the least communication computes rule [4]. Different from the owner computes rule, the whole loop body of a loop to be parallelized is processed. Suppose that all arrays including data arrays and index arrays are initially distributed as BLOCK. The communication pattern of a partitioned loop iteration on a processor can be represented as a directed graph G = (V, E), called communication pattern graph (CPG). The following algorithm describes how iterations of a loop to be partitioned to threads, where is defined as a set of threads which have to send (receive) data to (from) thread before (after) the iteration is executed. and are the number of processors in and respectively. and are defined as the degrees of the set and respectively.
4.2
Implementation of Partial Ordered Loops
To parallelize partial ordered loops, the key technique is to detect data dependence. However, it is very expensive to test most of the data dependencies for irregular codes at runtime. We proposed a symbolic analysis method [3] similar to Range Test [2], which can detect irregular data dependence as much as at compile-time. In our symbolic analysis, symbolic solutions of a set of symbolic expressions are obtained by using certain restrictions. We introduced symbolic analysis algorithms to obtain the solutions in terms of a set of equalities and inequalities.
Effective OpenMP Extensions for Irregular Applications
103
Fig. 2. Performance of X2INTZC program Fig. 3. Performance of IRRCFD program on 8 processors SUN Cluster with three dif- on 8 processors SUN Cluster with the optiference scheduling strategies of OpenMP. mization of irregular reduction and partial ordered loop of OpenMP.
4.3
Implementation of Irregular Reduction
We use GatherScatter approach for the implementation of irregular reduction in our compiler. GatherSatter can generate explicit messages between threads for distributed memory systems. Reductions with regular accesses can be converted directly to collective communication. Irregular reductions may be parallelized by generating an inspector to identify nonlocal data needed by each processor. The inspector also generates a communication schedule and performs address translation, modifying indices of nonlocal data to use local buffers. Inspectors are expensive, but their code can be amortized over many time steps. on each time step an executor gathers nonlocal data using the communication schedule, performs the computation using local buffers, and scatters nonlocal results to the appropriate processors.
5
Experiments, Simulations, and Performance Results
We are constructing the library routines with the OpenMP implementation. We evaluated our extensions on two platforms, SGI Origin2000 with 16 nodes and SUN workstation cluster with 8 × 400MHz CPUs, connected by 100Mbps Ethernet cable. Since irregular scheduling and reduction are not part of the current OpenMP implementation, we implemented them by hand so that this part of the OpenMP program was generated to pthread routines in SGI Origin2000 and MPI routines in the cluster. The OpenMP versions are MIPSpro Fortran 77 Compiler for SGI Origin2000 and SUN Forte Developer 6 Update 2 compiler for SUN Cluster, both provide OpenMP support. Due to the limited space of this paper, we only show the results on the cluster. We select an irregular kernel X2INTZC of the fluid dynamics code, ZEUS-2D for our irregular scheduling study. X2INTZC includes some loops with similar appearance as Example 2. Another application IRRCFD is used to evaluate the irregular reduction and partial ordered loop optimizations. Figure 2 shows 8 CPUs speedup on the cluster for those three scheduling strategies. Here we observed that irregular scheduling improves the performance
104
M. Guo et al.
since it reduces communication cost. This phenomenon is more significant when the time steps are large. Figure 3 presents the optimized results of IRRCFD on the cluster. We see that in both cases the performance after optimization of irregular reduction and partial ordered loops has been improved. In comparison, speedup on the cluster is less than one on SGI Origin2000 because it costs more for inspector/executor manner.
6
Conclusion
The performance issue of irregular scientific computing codes in current OpenMP implementation has not well investigated. At its current version, OpenMP can only sequentially execute loops by using atomic, order loops directives for irregular codes. In this paper, we proposed the new directives to improve the sequentially decomposition of irregular loops, to parallelize irregular reductions, and to reduce atomic and ordered loops. These directives are specially useful for distributed memory multicomputers such as cluster platforms, though the implementation of them in OpenMP compilers may cost extra computation at runtime. The experiments and simulations validated our effort for these proposals. Our proposed method would enable straightforward and efficient automatic parallelization of a wide range of scientific applications.
References 1. R. Asenjo, E. Gutierrez, Y. Lin, D. Padua, B. Pottengerg, E. L. Zapata. On the Automatic Parallelization of Sparse and irregular Fortran codes. Technical Report 1512, University of Illinois at Urbana-Champaign, CSRD, December 1996. 2. W. Blume and R. Eigenmann. Nonlinear and symbolic data dependence testing. IEEE Transactions on Parallel and Distributed Systems, Vol. 9, No. 12, pp. 11801194, Dec. 1998. 3. M. Guo, Y. Pan, and C. Liu. Symbolic Communication Set generation for irregular parallel applications. The Journal of Supercomputing, Vol. 25, No. 3, pp. 197–214, 2003. 4. M. Guo. Efficient Loop Partitioning for parallel codes of irregular Scientific Computations. IEICE Transactions on Information and Systems, Vol. E86-D, No. 9, pp. 442–451, 2003. 5. E. Gutierrez, R. Asenjo, O. Plata, and E.L. Zapata. Automatic parallelization of irregular applications. Parallel Computing, 26(2000), pp. 1709-1738, 2000. 6. Y. Hu, A. Cox, and W. Zwaenepoel. Improving fine-grained irregular sharedmemory benchmarks by data reordering. In Proceedings of SC’00, Dallas, TX, November 2000. 7. D. S. Nikolopoulos, T. S. Papatheodorou, C. D. Polychronopoulos, J. Labarta, and E. Ayguade. Is Data Distribution Necessary in OpenMP? in proceedings of SC 2000, 2000. 8. R. Ponnusamy, J. Saltz, A. Choudhary, S. Hwang, and G. Fox. Runtime support and compilation methods for user-specified data distributions. IEEE Transactions on Parallel and Distributed Systems, 6(8), pp. 815-831, 1995.
A Scheduling Approach with Respect to Overlap of Computing and Data Transferring in Grid Computing Changqin Huang1,2, Yao Zheng1,2, and Deren Chen1 1
College of Computer Science, Zhejiang University, Hangzhou, 310027, P. R. China 2 Center for Engineering and Scientific Computation, Zhejiang University, Hangzhou, 310027, P. R. China
Abstract. In this paper, we present a two-level distributed schedule model, and propose a scheduling approach with respect to overlap of computing and data transferring. On the basis of network status, node load, and the relation between task execution and task data access, data transferring and computing can occur concurrently in the following three cases: a) A task is being executed on a part of its dataset when the other of its dataset is being replicated; b) A dataset of a scheduled task is being replicated to a node, at which another task is running; c) Data exchange happens when dependant subtasks are running at different nodes. Corresponding theoretical analysis and experimental results demonstrate that the scheduling approach improves execution performance and resource utilization.
1 Introduction A computational grid is an emerging computing infrastructure that enables effective access to distributed and heterogeneous computing resources in order to serve the needs of a Virtual Organization (VO) [1]. The performance that can be delivered varies dynamically for resources competing, network status, task type, and so on. Therefore, resource management and scheduling is a key and hard issue. In data management, replication from primary repositories to other locations at an apt moment can be an important optimization step [2,3]. In the present paper, we focus on scheduling approaches suitable for large-scale data-intensive applications or those of dataintensive and computing-intensive nature, which exist widely in the area of engineering and scientific computation. In the present work, we adopt a distributed schedule model, in which there exist two level schedulers. The scheduler schedules task execution on the basis of a variety of metrics and constraints, meanwhile it tries its best to reduce task expending time to improve performance by overlap of computing and data transferring. This paper is organized as follows: Section 2 reviews related work in the arena of grid scheduling. In Section 3, details of our approach and proposed scheduling model are described. An algorithm and apt analysis are included in Section 4. Case studies with experimental results are included in Section 5, and conclusions in Section 6. M. Li et al. (Eds.): GCC 2003, LNCS 3033, pp. 105–112, 2004. © Springer-Verlag Berlin Heidelberg 2004
106
C. Huang, Y. Zheng, and D. Chen
2 Related Work For the development and deployment of applications on computational grids, there are a number of approaches to scheduling. Vadhiyar et al. [4] present Metascheduler with a 2D chart and Metascheduler types. Berman et al. [5] adopt performance evaluation techniques [6], and they utilize the NWS [7] resource monitoring service at application-level scheduling. Abraham et al. [8] use a parametric engine and heuristic algorithms. Zomaya et al. [9] apply a genetic algorithm. Beaumont et al. [10] aim at independent and equal-sized tasks. Dogan et al. [11] consider the problem of scheduling independent tasks with multiple QoS requirements. The above schedules [4,5,8-11] are related to independent tasks or ignore issues of efficient replication. An adaptive scheduling algorithm for parameter sweep applications is used by Casanova et al. [12], and they take data storage into account. The essential difference between their work and ours is that our heuristic actively replicates datasets. Thain et al. [13] describe a system that links jobs and data by binding execution and storage sites into I/O communities, but do not address policy issues. Ranganathan et al. [14] focus on data-intensive applications, where data movement can be either tightly bound to job scheduling decisions or not by a decoupled way. They don’t consider the cases that task computing and data transferring proceed in a parallel fashion on a node.
3 Scheduling Strategy and Scheduling Model To provide the context for this scheduling strategy and system model, we first address the scheduling scenario in detail. Each site (LAN) comprises a number of nodes (such as PCs, clusters, and supercomputers), and each node has a limited amount of storage. A set of data is initially put onto a node, where user’s task is submitted, or it is mapped to nodes at this site according to a certain distribution. The target computational grid consists of heterogeneous nodes connected by LANs and/or WANs. The whole computational grid is hierarchical: node, LAN, and WAN. Scheduling at a single node is ignored here. The scheduling is divided into two levels: Global Scheduler (GS), corresponding to a WAN; and Local Scheduler (LS), corresponding to a LAN. Firstly, tasks are submitted to a site/node, at which the associated LS is activated to schedule the tasks, and when this scheduler fails in scheduling, these requests are passed to the associated GSs, A GS is responsible for determining which site(s) in its domain these tasks are sent to. Finally, the corresponding LS gives a complete schedule by the local scheduling algorithm. It kills these requests at the other schedulers, then lets tasks be executed and results be returned. As far as algorithms are concerned, the “Best” schedule considers information such as CPU speed, network status between hosts, and task properties. This information is retrieved from resource information providers, such as the Network Weather System (NWS) and the Metacomputing Directory Service (MDS). Our approach requires an application-specific performance model and a scheduler. The scheduler schedules
A Scheduling Approach with Respect to Overlap of Computing
107
tasks and make a decision of transferring data. The goal of the scheduler is to develop a schedule that minimizes makespan and maximizes utilization rate. Each scheduler has two components and two queues as shown in Fig. 1, and their functionalities and relations are described as follows.
Fig. 1. Scheduling model and interaction in a scheduler or among schedulers
Task Scheduling Component (TSC): TSC makes a scheduling decision on the basis of information about resources and tasks, and passes some messages of data transferring to Data Transferring Component (DTC), if overlap of computing and data transferring occurs (we will discuss the details in Section 4). When there exist tasks in Arrived Task Queue (ATQ), TSC keeps activated and gives a schedule of all tasks in the associated ATQ, puts the scheduled tasks into the associated Scheduled Task Queue (STQ), and directs the tasks to be executed on selected resources. Within a limited period of time, if the TSC is not able to give a schedule to a certain task, it will deliver the task request to associated GS’s ATQ to schedule the task with the similar method, otherwise, it returns “failure”. Data Transferring Component (DTC): DTC keeps track of the popularity of each dataset locally available. It works in the following two ways: a) Only if DTC receives associated messages from TSC, it can make a decision on “how” to replicate datasets necessary for tasks in STQ or tasks being executed, under conditions that CPU is busy but connected network is idle. b) It makes a decision on “how” to exchange data necessary for dependant subtasks being executed. Finally, it directs nodes to transfer datasets, so computing and data transferring are performed concurrently. Arrived Task Queue (ATQ) and Scheduled Task Queue (STQ): An ATQ stores all tasks to be delivered to its scheduler. Tasks are put into an ATQ when task requests arrive, and a task is taken out when it has been scheduled. The STQ store
108
C. Huang, Y. Zheng, and D. Chen
those tasks scheduled by the local TSC, and its task is taken out when the task comes into execution.
4 Scheduling Algorithm and Theoretical Analysis 4.1 Assumptions Based on the above-mentioned scheduling model, with a concern for network traffic, we limit a task’s execution in a LAN. To simplify the scheduling, we make the following assumptions: a) Each task/subtask (a subtask exists when a task is divided into parallel subtasks) is assigned to a specific node that it can meet its deadline. b) The time spent on it can be predicted by related techniques (e.g., the PACE [15]). c) Before execution, each task/subtask can get the information about the relation of its computing and its dataset (e.g., the computing may proceed on a part of dataset). d) Tasks/subtasks can be pre-scheduled on the basis of task status and grid information. The core algorithm, by which the scheduler schedules task execution, is not uncertain and can be selected by users (e.g., the FCFS algorithm, and the GA algorithm).
4.2 Scheduling Algorithm Both GS and LS adopt the same approach described below except the core algorithms may not be the same. Only if a distributed task gets its dataset/subset, it starts to run.
A Scheduling Approach with Respect to Overlap of Computing
109
4.3 Theoretical Analysis The metric in our analysis used is makespan and average resource utilization rate here. We only analyze efficiency to be brought by our data transferring strategy. The generic algorithm without our approach is assumed: A scheduled task/subtask needs to hit all of its dataset by replication before it starts execution. It is opposite to our approach. To simplify analysis, both computing and data exchanging in the concurrent way, between the dependant subtasks being executed, are not considered here. Under the conditions that the dataset of one task/subtask is divisible, the above algorithm is considered. Let p denote this task or subtask, and m data size. Dataset is divided into n blocks equally. Let x denote the percentage of CPU performance decrease when transferring data on network concurrently, the speed of transferring data on network, the speed of processing data by a CPU, the makespan for generic scheduling algorithm, and the makespan for a our algorithm It happens that both computing and transferring data are performed concurrently except the first block of data is transferred, so we have the following equation:
If
then
reversely, Obviously, under the first condi-
tion, there exists In general, when there exists multi-storage system, and m is very large, so there exists under the second one. Totally, the makespan adopting our algorithm decreases considerably in general. Let denote the average resource (CPU) utilization rate for generic scheduling algorithm, and the average resource utilization rate for our algorithm. We give a period of time
110
C. Huang, Y. Zheng, and D. Chen
Because If x is little and m is large, will increase considerably. If the dataset of one task/subtask cannot be divided, overlapping computing with data transferring can take place between the task/subtask to being executed and the scheduled task/subtask in a STQ. By analyzing, there exists a similar conclusion: Only if x is little and m is large, the makespan will be reduced and the average resource utilization rate will be increased considerably.
5 Experiments We have developed an engineering computation oriented visual grid prototype system, named VGRID, in which tasks are auto-scheduled in a visual fashion, and it permits a selection of task scheduling core algorithms. In this environment, three pairs of experiments have been designed by using the above scheduling approach. The tasks consist of the iterations of two application examples: Monte Carlo integration in high dimensions, including a small dataset transferring; video conversion application, including a large dataset replication and compression. All nodes are PCs with Intel Pentium 4 processors of 2.0G Hz, memory of 512M, Ethernet 100M, and hard disk 80G/7200rpm. The experiments are described as follows, where two approaches are used. Approach A adopts the FCFS algorithm, whereas Approach B adopts the FCFS algorithm with our scheduling approach. Case 1: One task: video conversion. One node. Case 2: Four tasks: Monte Carlo simulation, video conversion, Monte Carlo simulation, and video conversion in sequence. One node. Case 3: Four tasks: Monte Carlo simulation, video conversion, Monte Carlo simulation, and video conversion in sequence. Three nodes. Experimental results are illustrated in Fig.2 and 3. As shown in these figures, different types of tasks, scheduled task sequences and grid resources have different performance scenarios. In all experiments, all average resource utilization rates increase over 15% by adopting our algorithm. But in Case 1, the new makespan decreases very little and the associated average resource utilization rate increases 18%. This means that overlap of computing and transferring data can-
A Scheduling Approach with Respect to Overlap of Computing
111
not bring benefits, but adds a little workload. Therefore our algorithm isn’t very fit for the tasks of this type as performance decrease percentage x is large to these tasks, it occurs under the conditions of competing grid resources.
Fig. 2. Variation of the makespan
Fig. 3. Variation of the average resource utilization rate
6 Conclusions A scheduling model and an associated algorithm were proposed in the present work. This approach tries its best to reduce task expending time to improve performance by overlapping computing with data transferring. We have theoretically analyzed and instantiated this algorithm with three tests based on a FCFS core algorithm in the VGRID under different conditions. Our results show: Firstly, it is obvious to improve system performance. Secondly, the relation of task execution and its dataset, and the size of data have a significant impact on system performance. Though these results are promising, in interpreting their significance we have to bear in mind that they are based on the simplified grid scenarios. The case, that these dependant subtasks move data for exchange, has not yet been studied in detail. Acknowledgements. The authors wish to thank the National Natural Science Foundation of China for the National Science Fund for Distinguished Young Scholars under grant Number 60225009. We would like to thank the Center for Engineering
112
C. Huang, Y. Zheng, and D. Chen
and Scientific Compu-tation, Zhejiang University, for its computational resource with which the research project has been carried out.
References 1.
2. 3.
4. 5. 6.
7.
8.
9. 10.
11.
12. 13. 14.
15.
I. Foster, C. Kesselman et al.: The Anatomy of the Grid: Enabling Scalable Virtual Organizations. International Journal of High Performance Computing Applications, 2001, 15 (3): 200-222 J. Subhlok and G. Vondran: Optimal Use of Mixed Task and Data Parallelism for Pipelined Computations. Journal of Parallel and Distributed Computing, 2000, 60: 297-319 O. Beaumont, A. Legrand et al.: Scheduling Strategies for Mixed Data and Task Parallelism on Heterogeneous Clusters and Grids. Proc. of the 11th Euromicro Conference on Parallel, Distributed and Network-Based Processing, 2003 S. S. Vadhiyar and J. J. Dongarra: A Metascheduler for the Grid. Proc. of the 11th IEEE International Symposium on High Performance Distributed Computing, 2002 F. Berman et al.: Adaptive Computing on the Grid Using AppLeS. IEEE Transactions on Parallel and Distribted Systems, 2003, 14(4): 369-382 W. Smith, I. Foster, and V. Taylor: Predicting Application Run Times Using Historical Information. Proc. of the IPPS/SPDP Workshop on Job Scheduling Strategies for Parallel Processing, 1998 R. Wolski et al.: The Network Weather Service: A Distributed Resource Performance Forecasting Service for Metacomputing. Future Generation Computing Systems, 1999, (56): 757-768 A. Abraham, R. Buyya et al.: Nature’s Heuristics for Scheduling Jobs on Computational Grids. Proc. of 8th International Conference on Advanced Computing and Communications, Cochin, India, 2000 A. Y. Zomaya et al.: Observations on Using Genetic Algorithms for Dynamic LoadBalancing. IEEE Transactions on Parallel and Distributed Systems, 2001, 9: 899-911. O. Beaumont and L. Carter: Bandwidth-Centric Allocation of Independent Tasks on Heterogeneous Platforms. Proc. of the International Parallel and Distributed Processing Symposium, 2002 A. Dogan and F. Özgüner: Scheduling Independent Tasks with QoS Requirements in Grid Computing with Time-Varying Resource Prices. Proc. of Grid Computing-GRID 2002, 2002, 58-69 H. Casanova, G. Obertelli et al.: The AppLeS Parameter Sweep Template: User-Level Middleware for the Grid. Proc. of Supercomputing 2000, Denver, 2000 D. Thain, J. Bent et al.: Gathering at the Well: Creating Communities for Grid I/O. Proc. of Supercomputing 2000, Denver, 2000 K. Ranganathan and I. Foster: Decoupling Computation and Data Scheduling in Distributed Data-Intensive Applications. Proc. of the 11th International Symposium on High Performance Distributed Computing, 2002 G. R. Nudd et al.: PACE – A Toolset for the Performance Prediction of Parallel and Distributed Systems. Journal of High Performance Computing Applications, 2000, 3: 228251
A Deadline and Budget Constrained Cost-Time Optimization Algorithm for Scheduling Dependent Tasks in Grid Computing Haolin Feng1,3, Guanghua Song2,3, Yao Zheng2,3, and Jun Xia2,3 1 2
Chu Kechen Honors College, Zhejiang University, Hangzhou, 310027, P. R. China College of Computer Science, Zhejiang University, Hangzhou, 310027, P.R. China 3 Center for Engineering and Scientific Computation, Zhejiang University, Hangzhou, 310027, P. R. China
Abstract. Computational grid has a promising future in large-scale computing, because it enables the sharing of widely distributed computing resources. Good managements with excellent scheduling algorithms are in great demand to take full advantage of it. Many scheduling algorithms in grid computing are for independent tasks. However, communications are very common in scientific computing programs. In this paper, we will propose an easy-implemented algorithm to schedule the tasks with some communications. Our algorithm is suitable for a large proportion of scientific computing programs, and is based on Binary Integer Programming. It is able to meet the users’ quality of service (QoS) requirements, and to minimize the combination of costs and time consumed by the users’ programs. We will give an example of scheduling a typical scientific computing task to show the power of our algorithm. In our experiment, the grid resource consists of an SGI Onyx 3900 supercomputer, four SGI Octane workstations, four Intel P4-2.0GHz PCs and four Intel P4-1.8GHz PCs.
1 Introduction Computational grids [1] become more and more popular in large-scale computing, because they enable the sharing of computing resources that are distributed all over the world. Those computing resources are distributed widely and owned by many different organizations, and thus, good systems for resource management are essential to take full advantage of grids. Published literature provides us with various management systems with different policies and principles ([2, 3, 4]). The most important part of a good management system is an excellent algorithm for scheduling tasks. It is the management systems that do the jobs of resource discovery[8], selecting machines and scheduling the tasks for the users. Nowadays, numerous scheduling algorithms are available [5, 6, 7]. Most of the scheduling algorithms assume the tasks to be independent. Under this assumption, the existing algorithms can still work with many scientific and engineering computing problems. However, the majority of scientific computing problems and computing in engineering require communications among tasks, e.g. computation in areas of solid meM. Li et al. (Eds.): GCC 2003, LNCS 3033, pp. 113–120, 2004. © Springer-Verlag Berlin Heidelberg 2004
114
H. Feng et al.
chanics and fluid dynamics. Without considering the communications among tasks, algorithms are of obvious limitation, and cannot take full advantage of the powerful computational grids. However, it is very challenging to schedule general dependent tasks, and so far, there is no existing satisfying solution, due to causes such as the heterogeneous architectures of different machines in the same grid and the limited bandwidths of network transmission. Thus, for the first step, we try to add some constraints on communications in order to achieve an improved scheduling algorithm. In this paper, we present a model that can schedule both independent tasks and dependent tasks with special communications. In this model, we can reach a balance between the cost and the job completion time for different clients. That means, we provide an optimal solution for an objective function, which consists of the cost and the job completion time. Moreover, both the deadline and the budget set by the clients will be met in the algorithm. We select an array of machines for a batch of tasks, either independent or dependent under a constraint condition, and we show that our solution can be achieved by solving a classical problem -- Binary Integer Programming [11].
2 Problem Modeling Suppose a user has submitted a program consisting of N dependent tasks (denoted as and in the grid there are M machines (denoted as available at the moment (M >= N). The machines are different in terms of architectures, computing power, prices of CPU time, as well as the distances from the management system, which will result in different speeds of data transfer. Our goal is to assign each task to a specific machine (processor) in order to minimize the total “cost” -- the money and the time for completing all these N tasks. Note that the tasks would sometimes communicate with each other, which will make our problem even more complicated.
2.1 Assumptions 1) For each single task, while it is assigned to a specific processor in the grid, the time spent on it can be known. Many techniques are available to achieve this [9, 10]. 2) Tasks are dependent, and communicate with each other. The communication happens whenever a certain percentage amount of work of every task has been completed for all the tasks. For example, the communication happens when 10% of work of every task has been done, and then, communication happens again when another 6% work of every task has been done, and so on. We need not know the value of percentage before its execution, but we should know how many times of communication are to happen as well as the scale of communications. Remark. Although that is a constraint, most problems in scientific computing satisfy this assumption. For example, computations in computational structural analysis, in computational fluid dynamics, and in DNA sequencing, all satisfy this assumption. Also, a program with independent tasks can be considered as the program with tasks
A Deadline and Budget Constrained Cost-Time Optimization Algorithm
115
that communicate after 100% of work has been completed. Therefore, our algorithm works with both independent and dependent tasks. 3) According to most accounting systems, the charge for a unit of time is proportional to the resource used by the user at that moment. Provided that, for a specific processor, if its resource used is very close to zero in a period of time, the cost it charges is very close to zero. Thus, it is reasonable to assume that when waiting for communication, we do not have any monetary consumption.
2.2 Algorithm Description 2.2.1 Definition of the Object Function Now we have to define a proper function to measure the “cost”. Defining the function as a weighed sum of the money and the job completion time is a good idea [5]. People have different views of value towards money and time; thus, it is necessary to give our clients the right to specify the weights for the money and the time, respectively. For example, a certain user considers one unit of time as valuable as one hundred units of money, then we set and Here and stand for the weights of money and time, respectively. The users can also set the deadline (denoted as and the maximal cost that can be afforded (denoted as That is why we called it “a deadline and budget constrained cost-time optimization algorithm”. Based on this logic, we define the object function in this way: Here, is the time spent on task given that is assigned to prcessor For each pair of i and j, as we have assumed, is known. is the cost of processor per unit CPU time. If we really assign task to then the value of will be 1, otherwise 0. T stands for the duration from the beginning of the first task to the end of the last task. 2.2.2 Constrained Condition of the Problem
Here q stands for the times of communications happened during the process.
116
H. Feng et al.
The meaning of is the same with that of equation (1). Inequations (3) and (4) mean “deadline and budget constrained”. Equation (5) means that each single task should be assigned to one and only one processor. Inequation (6) means that each single processor should process at most one of those tasks. That is because communications cannot happen until every one of those tasks has finished by the same percentage, which has been assumed in Subsection 2.1. Equation (7) gives the value of the duration from the end of the (k-1)th communication to the end of the kth communication, and is the percentage amount of work completed during these two communications. For each k, stands for the time for the kth communication for task assigned to machine (The value of determines whether or not is assigned to Equation (7) means that, another (percentage amount) of every task has been finished, and then the kth communication will happen. The reason why we use the first “max” is that the communication will not happen until all the tasks are ready for communication. stands for the time spent on the kth communication. Here, we use “max” because of the following reason: the quality of network varies from place to place, and it is the slowest network that determines the time for communications. Equation (8) has given the value of the job completion time of N tasks. We use the term because after the last communication, of each task is left.
3 Model Modifications and Simplification Combining Equations (7) and (8), we have the following equation: From now on, we can use Equation (9) instead of Equations (7) and (8). A large proportion of scientific computing problems spend most of the time on computing, and the time for communications is relatively ignorable. (That does not mean we can ignore communications, because usually much time is spent on waiting before communications.) When the time transferring data is very little, we can just ignore the difference among the networks, and replace the term with Then, Equation (9) is replaced with the following equation: Now, we claim that we can replace Equation (10) with the following inequation: We state that the replacement will not change the solution. The proof is omitted here, due to the space limitation. In this special case our model can be presented in the following way:
A Deadline and Budget Constrained Cost-Time Optimization Algorithm
117
Except that should be binary integers, all the constrained conditions in our model are linear. Thus, the model is straightforward, and is reduced to a classical Binary Integer Programming problem, for which a lot of methods are available. In reality, the user may have some other requirement for some tasks, for example, reliability. In such cases, not all the processors in a grid are suitable for the tasks. If a certain machine is not suitable for a certain task, we set the corresponding term to be greater than In this way, our algorithm can avoid assigning that task to that machine. Therefore, our algorithm can schedule tasks with QoS requirement.
4 Experiments and Evaluation In this section, we will use a numerical program of Computational Fluid Dynamics (CFD) as an example to test our scheduling algorithm. This CFD program simulates the vortex streets downstream near the nozzle in a plane jet. The whole computational domain is divided into two types of sections, the physical domain, and one PML buffer zone at each end of the physical domain. Four processors have been used to get the final results in their respective subsections of the same height (Fig. 1).
Fig. 1. The steady vortex streets downstream near the jet nozzle
Because of its typicality in scientific computation, it is a satisfying example to show the value of our scheduling algorithm. The program consists of four tasks, which are to be scheduled by our algorithm. There are several different types of machines available for these tasks: an SGI Onyx 3900 supercomputer with 64 processors, four SGI Octane workstations and eight personal computers (four of which are better than the rest). According to the costs of these machines, we have assumed the
118
H. Feng et al.
price for each processor (Table 1). We will discuss two different cases. The first case is that the workload of each task is nearly the same; while the second is that the workloads are different. We will see how this difference will affect the outcome of the schedule. As we have four tasks, we need no more than four processors of the supercomputer. We denote these processors as SC1, SC2, SC3 and SC4. Similarly, WS1, WS2, WS3, and WS4 stand for the processors of four SGI workstations, respectively; P4-2-1, P4-2-2, P4-2-3 and P4-2-4 stand for the four P4 2.0G Hz processors; P4-1.8-1, P4-1.8-2, P4-1.8-3 and P4-1.8-4 stand for the four P4 1.8G Hz processors.
To estimate the time for computing and communications, we can run the program and record the real time. In this experiment, through the recorded data, we know that although the communications are frequent, the data transferred during communications are of very small size. Thus, compared with the time for computing and waiting, the total time for transferring data is of very small amount. As is claimed in Section 3, we can simplify our model in this case.
Case 1: The workload of each task is nearly the same, so, for each type of processors, we only have to list the estimation of CPU time needed to complete one task (Table
A Deadline and Budget Constrained Cost-Time Optimization Algorithm
119
2). Let be 10,000 (units of time), and the budget is 400,000 (units of money). And we will set different value of ratio so that we can see how the weights of time and money can affect the scheduling (Table 3). Remark: The data in Table 3 is given by our algorithm. Because the situation for each of those four tasks is the same, for each scheme, we only listed the CPU time for one task. But the monetary consumption and the value of Z are for those four tasks in each scheme. When really running that program on the super computer, the time for waiting and communications is too short to be measured accurately, so the walltime above should be 1984 minutes. However, the difference is small enough to be ignored. Analysis: When the term is less than 0.0655, all the tasks will be processed by the supercomputer, because it can save a lot of time, which the user values highly. If the term is between 0.0655 and 0.3122, all the tasks will be processed by those four P4 2.0G processors. While the term is larger than 0.3122, the four P4 1.8G processors are preferable, because of the low charge. The result shows that the workstations are not used in this case. However, if the user has some other requirements, for example, the requirement for reliability, then, both the workstations and the super computer may be preferable. The details for adding quality of service requirements have been discussed in Section 3. (Fig. 2).
Fig. 2. Changes of the ratio
result in the changes of the scheme
Case 2: The workload of each task is different. We will give a brief discussion on this case. Suppose there are two tasks with larger workload, each of which is twice as much as each of the smaller ones. Let be 0.01:0.99, then, according to our algorithm, we should assigned the larger tasks to the supercomputer, and leave the smaller tasks to the P4-2.0G Hz processors. This will help to minimize the waiting time before communications. But when the value of changes, the scheme will change greatly in order to meet the requirements of difference clients and to minimize the “cost” they defined. Of course, the budget of the program should also be taken into our consideration, so that to meet our goal – “budget and time” constrained algorithm.
5 Conclusions We have presented an algorithm to schedule programs with dependent tasks. Unlike other algorithms, this one takes the communications among tasks into consideration. Although we impose a constraint on the communications, the algorithm is suitable to
120
H. Feng et al.
scheduling a large proportion of programs on scientific computing. Moreover, we reduce the problem to a classical programming problem -- Binary Integer Programming, which can be solved by some existing methods. Our algorithm can meet the users’ quality of service requirements such as the deadline, budget, security and reliability. By scheduling such a typical scientific computing application, our experiment shows how the algorithm meets the requirements of different users, and how the communications will affect the scheme, and thus demonstrate the validity of the algorithm. Acknowledgements. The authors wish to thank the National Natural Science Foundation of China for the National Science Fund for Distinguished Young Scholars under grant Number 60225009. We would like to thank the Center for Engineering and Scientific Computation, Zhejiang University, for its computational resources, with which the numerical experiments have been carried out.
References I. Foster and C. Kesselman (eds.): The Grid: Blueprint for a Future Computing Infrastructure, Morgan Kaufmann Publishers, USA, 1999. 2. GRAM: Grid Resource Allocation & Management, Argonne National Laboratory, and USC Information Sciences Institute. 3. C. Youn: Resource Management and Scheduling in Grid (Concepts and Trends), 2002. 4. R. Buyya, D. Abramson, J. Giddy, and H. Stockinger: Economic Models for Resource Management and Scheduling in Grid Computing, Special Issue on Grid Computing Environments, the Journal of Concurrency and Computation: Practice and Experience (CCPE), 14(13-15), 2002 5. A. Dogan and F. Özgüner: Scheduling Independent Tasks with QoS Requirements in Grid Computing with Time-Varying Resource Prices, Proceeding of Grid Computing-GRID 2002, 58-69, 2002. 6. A. K. Amoura, E. Bampis, C. Kenyon, and Y. Manoussakis: Scheduling Independent Multiprocessor Tasks, Algorithmica, 32: 247–261, 2002 7. R. Buyya, M. Murshed, and D. Abramson: A Deadline and Budget Constrained Cost-Time Optimization Algorithm for Scheduling Task Farming Applications on Global Grids. (www.cs.mu.oz.au/~raj/, current September 14, 2003) 8. J. Yu, S. Venugopal, and R. Buyya: A Market-Oriented Grid Directory Service for Publication and Discovery of Grid Service Providers and their Service. (www.cs.mu.oz.au/~raj/, current September 14, 2003) 9. M. A. Iverson, F. Özgüner, and C. Lee: Potter: Statistical Prediction of Task Execution Times through Analytic Benchmarking for Scheduling in a Heterogeneous Environment, IEEE Trans. Computers, 48(12): 1374-1379, 1999 10. B. Reistad and D. K. Gifford: Static Dependent Costs for Estimating Execution Time, Proc. of the 1994 ACM Conference on LISP and functional programming, 65–78, 1994. 11. F. S. Hillier, G. J. Lieberman: Introduction to Operations Research, 7th ed., McGraw-Hill Higher Education, 2001. 1.
A Load Balancing Algorithm for Web Based Server Grids Shui Yu, John Casey, and Wanlei Zhou School of Information Technology, Deakin University 221 Burwood HWY, Burwood, VIC 3125, Australia {syu, jacasey, wanlei}@deakin.edu.au
Abstract. Load balance is a critical issue in distributed systems, such as server grids. In this paper, we propose a Balanced Load Queue (BLQ) model, which combines the queuing theory and hydro-dynamic theory, to model load balance in server grids. Base on the BLQ model, we claim that if the system is in the state of global fairness, then the performance of the whole system is the best. We propose a load balanced algorithm based on the model: the algorithm tries its best to keep the system in the global fairness status using job deviation. We present three strategies: best node, best neighbour, and random selection, for job deviation. A number of experiments are conducted for the comparison of the three strategies, and the results show that the best neighbour strategy is the best among the proposed strategies. Furthermore, the proposed algorithm with best neighbour strategy is better than the traditional round robin algorithm in term of processing delay, and the proposed algorithm needs very limited system information and is robust.
1 Introduction Server grids are an important and efficient architecture for Internet based applications. Server grids based on distributed architecture can improve the performance, which is a critical issue of Internet based applications. Nowadays, server grids in the Internet environment are very popular, such as, distributed web based databases, clustering web servers, mirrored servers, anycast servers, peer-to-peer computers, and so on. One issue of Internet based server grids is the load balance among the distributed servers. Most of the existing load balance algorithms [2], [3], [10] are based on the background of a static environment, but in the situation of Internet based server grids, the environment is no longer static because of the unstable Internet traffic, congestions, user requests, and so on. Graph theory is one of the methods of analyzing the load balance issue [3], and Statistics is a useful tool for the load balance problem as well [1], [2], [10]. [5], [6] applied a hydro-dynamic approach to model network traffic. The main advantage of this method is its power in describing dynamic load balancing activities. However, the hydro system describes a continuous world, while computer network systems belong to a discrete environment; therefore certain transformation methods have to be employed. On the other hand, because of its discrete nature, queuing theory has been used for modeling computer networks for decades. However, modeling dynamic load balancing activities using queuing theory is difficult. In this paper, we try to combine M. Li et al. (Eds.): GCC 2003, LNCS 3033, pp. 121–128, 2004. © Springer-Verlag Berlin Heidelberg 2004
122
S. Yu, J. Casey, and W. Zhou
balancing activities using queuing theory is difficult. In this paper, we try to combine the discrete nature of queuing theory and the power in describing dynamic activities of the hydro-dynamic approach to model load balance activities of Internet based server grids. The rest of this paper is organized as follows. Section 2 refers to the related work. In section 3 we propose the Balanced Load Queue model. A novel algorithm is proposed in section 4 based on the Balanced Load Queue model. The performance evaluation is discussed in section 5. Finally section 6 summaries the paper and presents the future work.
2 Related Work [9] presented the supermarket model to describe load balancing for a group of servers: customers arrive as a Poisson stream of rate at a collection of n servers. Each customer chooses some constant d servers independently and uniformly at random from the n servers, and waits for service at the one with the fewest customers. The service time for a customer is exponentially distributed with mean 1, and the service protocol is first-in first-out. Furthermore, the paper pointed out that the supermarket model is difficult to analyze because of dependencies: knowing the length of one queue affects the distribution of the other queues. Then the author first developed a limiting, deterministic model representing the behavior as and then translated the results from that model to results for large, but finite, values of n. Balls and bins model is used for load balancing research in [2], [10]. The problem is described as follow: suppose that n balls are thrown into n bins, with each ball choosing a bin independently and uniformly at random, then the largest number of balls in any bin is approximately log n /log log n with high probability. [1] proposed a approach of online load balance based on the balls and bins model, and obtained that if each user samples the load of two resources and sends his request to the least loaded one, the total overhead is small, and the load on the n resources varies by only a O(log log n) factor. [5], [6] introduced a hydro-dynamic approach to solve the dynamic load balancing issue on a network of heterogeneous computers. The authors modeled a computer as a cylinder, the diameter represents the computing capability of the computer and liquid in the cylinder denotes the work load on the computer. Their conclusion is when the system achieves the global fairness, namely the heights of all the cylinders are the same, the system is load balanced, at the same time, the potential energy of the system is minimized. Anycast is a new type of network service which always tries to find the “best” server among the anycast group [7], [11], [13]. Anycast mechanism provides an automatic load balance capability among an anycast group. Our previous research [14] provides a practical and efficient method for anycast routing, which integrates the network delay and the server performance as a criterion for finding the “best” server.
A Load Balancing Algorithm for Web Based Server Grids
123
3 Balanced Load Queue (BLQ) Model The hydro-dynamic approach is very effective for analyzing dynamic load balancing activities of distributed systems. However, the liquid system used in the hydrodynamic approach is a continuous system, while the situation in our computer systems is discrete. On the other hand, the queuing theory is a powerful tool for modeling computer systems, but it is less effective in modeling dynamic systems. In this section we combine the two distinct theories together to model Internet based server grids.
Fig. 1. Server Grid using the Queuing Model
Fig. 2. A queue and the related concepts
Here we model each server in a server grid as a queue, and the queues are connected by networks. Figure 1 shows an example of a server grid with four servers and five connections. In Figure 1, the queues, and represent servers, and there exists a network connecting them together to form a server grid. For each queue the width of a queue denotes its computing capability: the wider, the more powerful. In order to simplify the explanation, we describe some concepts here, which will be used in the rest of this paper. In Figure 2, parameter indicates the moving speed of the requests in the queue m, actually, is the service rate of the related computer. is a request in the queue, and is the service time for in the queue. Based on the definitions in Figure 2, we can find that during the processing of request i, at any time point t, When the processing finished, then Definition 1. Global Fairness (GF). In a server grid ers, if the sums of service time (where
n is the number of the servis the number denoting a
server, and is the sequence number for requests in a queue) in each queue are equivalent, then we call the system is in a state of global fairness. The definition can be expressed in the follow equation.
If a server grid is in the state of global fairness, then the current requests in all the queues will be finished at the same time, and further, that each server is equal for a new incoming request. Assertion 1. If the work load of a server grid with n servers is balanced, then in a given period [0, T] (T is sufficiently big), the system must be in the state of global fairness, namely, the equation (1) is correct.
124
S. Yu, J. Casey, and W. Zhou
Proof: There are three cases for the issue as listed below; any other situations are the combination of them. Case 1. There are no requests in the queues and is the arrival rate of requests for queue i) for the period [0, T]. It is obvious that the equations are correct. Case 2. i =1,2,...,n for the period [0, T]. This means all the arrival rates are bigger than the service rates respectively, namely, the all the servers are busy for the whole period, The assertion is correct. Case 3. Without loss generality, suppose there is no request in and there is/are one or more request(s) in at a given time point For the reason of load balance, if there comes a new request, the request will be dispatched to by the overloaded queue(s), this situation may happen from time to time. Therefore, if T is sufficiently big, the assertion is correct. In all of the three cases the assertion are correct, therefore the assertion is correct for any combination of them, as a result, the assertion is correct for any situation. Assertion 2. When a server grid is in the state of global fairness, then the performance of the whole system is the best. Proof: assume that there are n servers, and the service rates are if the system is not idle, in the state of global fairness, the total service rate is
if
the system is not in the state of global fairness, after a period of time, T, there will be at least one computer having no jobs to do, then the total service rate is/are the server/servers that has/have no jobs to do. It is obvious that therefore the assertion 2 is correct. Assertion 3. In a server grid with servers, if the system is in the state of balance, work load of n servers are balanced, then during a given period [0, T] (T is sufficiently big), the ratios of arrival rate to the service rate for each server are the same. Proof: If the system is in the state of balance, then equation (1) is correct. And we know that We ignore the switching time of processes, then for a long term view, we can obtain the following result.
Where k is a constant, which represents the ratio for convenience. This assertion implies that the relationship between the arrival rate and the service rate is fixed when the load of the system is balanced. Furthermore, parameter k implies the average waiting time for the users when the whole system is fully loaded. When k is bigger, the average waiting time is longer at that scenario.
A Load Balancing Algorithm for Web Based Server Grids
125
Assertion 4. If the work load of n servers are balanced, then during a given period [0, T] (T is sufficiently big), the relationship between mean time a request spends in the system, and the arrival rate is reciprocal. Proof: Assume that n=2, based on the equations of queuing theory, we can get the in terms of and shown as below,
From equation (1), we can obtain,
When
the proof is the same, then in general,
This assertion indicates that the relationship between the arrival rate and the mean time that a request spends in the system when the load of the system is balanced.
4 A Load Balanced Algorithm Based on the BLQ Model The balanced load queue model is good for describing load balance issues for server grids, but it is expensive because we need to know the states of all the queues. Based on assertion 3, we found that if the system is balanced, then the ratio of the arrival rate and the service rate for a given server is fixed. As we know, the service rate of a server is a constant value, for a given value k, if that means the server is approaching to the state of balance; On the other hand, if that means the server is overloaded, and the incoming requests should be dispatched to other servers in order to get the system back to the balanced state. The main advantage of this idea is that we just need to set a reasonable small k when the system is initiated, and then each server can judge weather it is necessary to deviate the incoming request or not without the information of network and any other information about the other servers. We assume that the whole performance of the system is satisfied by the users, which means the k in equation (2) is fixed, and then we get a boundary for arrival rate for each server, respectively. When there comes a new request to server i, the server will calculate its own if then it does nothing, otherwise, it deviates the incoming request to one of the other peer servers. How to decide the destination to process the deviated requests is an interesting issue, we design 3 strategies here for deviation: 1) Random Selection Strategy. Choose one server randomly from the other servers of the server grid; 2) Best Node Strategy. Choose the best one from all the servers of the grid using a global probing.
126
S. Yu, J. Casey, and W. Zhou
3) Best Neighbour Strategy. Choose the better one from the current server’s nearest two neighbors (neighboring servers). The details of the algorithm are shown as below.
We must point out that for the best neighbour strategy and the random selection strategy, there is a potential danger of a deviation loop. The probability of deviation loop is high when the number of servers is small.
5 Performance Analysis We have conducted some experiments on the Internet in order to demonstrate our proposed algorithm and compare the performance of the three strategies for job deviation. Moreover, we use a central controlled algorithm with round robin strategy [4] [8] [12] as a benchmark to evaluate our algorithm. The scenario for our algorithm is that requests are generated everywhere in the Internet and target to one of the servers of the server grid randomly. We know an estimated processing time for each job on a given server. Because of the delay of the deviation, there exists a delay of processing compared with the estimated processing time; we name it as Processing Delay. We use more than ten servers, which are distributed in two campuses, to act as the server grid. In the rest of this section, we will present and compare several factors, which have impact on the performance of the whole system. Figure 3 shows that when the number of nodes (servers) in a server grid increases, the processing delay of the best neighbour strategy keeps almost constant and less than the other two proposed strategies. Generally only the best neighbour strategy of the proposed algorithm is better than the central controller algorithm. The reason is that the best node strategy is expensive while the random selection strategy has no quality control. If the arrival rates are stable, then the number of requests can reflect the general performance in term of time. Based on Figure 4, we can observe that generally the average processing delays of the three strategies and central controller algorithm are close to a constant value respectively. In term of the general performance, best neighbour is better than best node, and much better than the random selection. Both of the
A Load Balancing Algorithm for Web Based Server Grids
127
strategies with quality control are better than the central controller algorithm in term of processing delay.
Fig. 3. No. of Nodes vs Processing Delay
Fig. 5. Network Delay vs Processing Delay
Fig. 4. No. of Requests vs Processing Delay
Fig. 6. Arrival Rate vs Processing Delay
Figure 5 compares the impact of network delay on the processing delay. It shows that the best neighbor strategy is the best in the three proposed strategies and the benchmark algorithm. Arrival rate is a parameter that reflects the concentration of the Internet traffic. The relationship of processing delay and the arrival rate is shown in Figure 6. Based on the result, we can conclude that the performance of the best neighbour strategy is the best in the four strategies.
6 Summary and Future Work In this paper, we proposed the balanced load queue model, which combines the advantages of the queuing theory and the hydro-dynamic approach to model the Internet based server grids. We proposed a load balancing algorithm based on our balanced load queue model, which tries its best to keep the system in the global fairness status using job deviation strategies. We presented three strategies: best node, best neighbour, and random selection for job deviation. We predefined a threshold in the algorithm for each server (queue) in the server grid, which depends on a reasonable delay for users. If one queue’s jobs exceed the predefined threshold, then a job deviation strategy will be employed.
128
S. Yu, J. Casey, and W. Zhou
Our experiments show that the best neighbour strategy is the best among the three strategies and the central controlled strategy at several aspects: number of servers (nodes), number of requests, network delay and arrival rate. The proposed algorithm can work with very limited system information, moreover, it can work independently from network traffic, link breaches, and so on. Some further researches need to be done, for example, the dynamic adjustment for the threshold for a server grid is an important issue for the whole system performance. Furthermore, the deviation loop is a critical and interesting topic for further research.
References 1. 2.
3.
4.
5.
6.
7. 8.
9. 10. 11. 12. 13.
14.
Yossi Azar, Andrei Z. Broder, Anna R. Karlin, and Eli, Upfal, “Balanced Allocations,” SIAM J. COMPUT. Vol. 29, No.1, pp180-200, 1999. Eleni Drinea, Alan Frieze, and Michael Mitzenmacher, “Balls and Bins Models with Feedback,” Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 308-315, 2002. Bharat S. Joshi, Seyed Hosseini, and K. Vairavan, “On a load balancing algorithm based on edge coloring,” Proceedings of the Southeastern Symposium on System Theory, pp174-178, 1997. Jing Liu, Hung Chun Kit, Mounir Hamdi, and Chi Ying Tsui, “Stable Round-Robin Scheduling Algorithms for High-Performance Input Queued Switches,” Proceedings of the Symposium on High Performance Interconnects Hot Interconnects, 2002. Chi-Chung Hui, and Samuel T. Chanson, “A hydro-dynamic approach to heterogeneous dynamic load balance in a network of computers,” Proceedings of the 1996 International Conference on Parallel Processing, pp. III-140-147, 1996. Chi-Chung Hui, and Samuel T. Chanson, “Efficient load balancing in interconnected LANs using group communication,” Proceedings of the International Conference on Distributed Computing Systems, pp.141-148, 1997. W. Jia, W. Zhou, and J. Kaiser, “Efficient Algorithm for Mobile Multicast Using Anycast Group,” IEE Proc.-Commun., Vol. 148, No. 1, February 2001. Tamas Marostis, Sandor Molnar, and Janos Sztrik, “CAC Algorithm Based on Advantage Round Robin Method for Qos Networks,” Proceedings of the Sixth IEEE Symposium on Computers and Communications, 2001. M. Mitzenmacher, “Load balancing and dependent jump markvo processes,” Proceedings of the Annual Symposium on Foundations of Computer Science, pp213-222, 1996. Michael Mitzenmacher, “The Power of Two Choices in Randomized Load Balancing,” Ph.D thesis, 1997. C. Partridge, T. Mendez, and W. Milliken, “Host Anycasting Service,” RFC 1546, November 1993. Jie Wang and Yonatan Levy, “Managing Performance Using Weighted Round-Robin,” Proceedings of the Fifth IEEE Symposium on Computers & Communications, 2000. Dong Xuan, Weijia Jia, Wei Zhao, and Hongwen Zhu, “A Routing Protocol for Anycast Message,” IEEE Transaction on Parallel and Distributed System, Vol. 11, No. 6, June 2000. Shui Yu, Wanlei Zhou, Fuchun Huang, and Mingjun Lan, “An Efficient Algorithm for Application-Layer Anycasting”, The Fourth International Conference on Distributed Communities on Web (DCW2002), Sydney, April 2002.
Flexible Intermediate Library for MPI-2 Support on an SCore Cluster System Yuichi Tsujita Department of Electronic Engineering and Computer Science, Faculty of Engineering, Kinki University 1 Umenobe, Takaya, Higashi-Hiroshima, Hiroshima 739-2116, Japan
[email protected]
Abstract. A flexible intermediate library named Stampi for MPI-2 support on a heterogeneous computing environment has been implemented on an SCore cluster system. With the help of a flexible communication mechanism of this library, users can execute MPI functions without awareness of underlying communication mechanism. In message transfer of Stampi, a vendor-supplied MPI library and TCP sockets are used selectively among MPI processes. Introducing its own router process mechanism hides a complex network configuration in inter-machine data transfer. In addition, the MPI-2 extensions, dynamic process creation and MPI-I/O, are also available. We have evaluated primitive functions of Stampi and sufficient performance has been achieved and effectiveness of our flexible implementation has been confirmed.
1
Introduction
The low cost and scalability of a PC cluster have made it the most popular platform today. But there is a difficulty that users need to pay attention to each PC node because each node is operated independently and users need to care heterogeneity in the PC cluster. To provide a seamless computing environment, an SCore cluster system (SCore system) [1] was developed. As MPI [2,3] is the de facto standard in parallel computation, almost all computer vendors have implemented their own MPI libraries. A built-in MPI library of the SCore system, MPICH-SCore [4], is one of the versions of an MPICH library [5]. Although this library is available inside a PC cluster (intramachine MPI communications), dynamic process creation and MPI communications among different platforms (inter-machine MPI communications) have not been supported. To realize such mechanisms, Stampi [6] has been implemented on an SCore system [7]. Recent applications in parallel computation handle huge amounts of data. Almost all data-intensive applications tend to have access to noncontiguous data rather than contiguous one. MPI-I/O was proposed as a parallel-I/O interface to support such I/O patterns in the MPI-2 standard [3]. But MPI-I/O operations among computers have not been supported in any vendor-supplied MPI library. To realize this mechanism, we have developed a flexible MPI-I/O library, named M. Li et al. (Eds.): GCC 2003, LNCS 3033, pp. 129–136, 2004. © Springer-Verlag Berlin Heidelberg 2004
130
Y. Tsujita
Stampi-I/O [8], as a part of a Stampi library. Users can call MPI-I/O functions in both local and remote I/O operations using a vendor-supplied MPI-I/O library. When the library is not available, UNIX I/O functions are used instead of the library (pseudo MPI-I/O method). An MPI-I/O function call is translated into the combination of the UNIX I/O operations and data manipulations inside a Stampi library. Primitive MPI functions of the Stampi library have been evaluated on interconnected Linux machines, a Linux cluster with an SCore system (SCore cluster) and a Linux workstation. Network connection between them was established on Gigabit Ethernet based LAN. In this paper, outline, architecture, and preliminary results of Stampi on an SCore system are described.
2
Implementation of Stampi on an SCore System
Stampi has been developed to hide complex network configuration and heterogeneity for flexible MPI communication on interconnected supercomputers. The features of Stampi are summarized as follows: 1. flexible communication mechanism among computers, 2. dynamic process creation and remote I/O operation mechanisms based on the MPI-2 standard, 3. flexible mechanism in both local and remote I/O operations, and 4. support of external32 data format among multiple platforms.
To use high availability and flexibility of an SCore system on a heterogeneous computing environment, Stampi has been implemented on the system. Rest of this section describes the details of Stampi on the SCore system.
2.1
Architecture of Stampi on an SCore System
Architectural view of Stampi on a heterogeneous computing environment including an SCore cluster is depicted in Fig. 1. When user processes execute MPI functions, the Stampi library is called at first. High performance intra-machine MPI communication is available using a well-tuned underlying communication library named PM2 [9] via an MPICH-SCore library. Although ROMIO [10] is available in MPICH-SCore, Stampi uses the pseudo MPI-I/O method in local MPI-I/O operations because ROMIO of MPICH-1.2.0 in SCore 5.0.1 does not support error handling. In inter-machine MPI communications, a communication path is switched to the TCP socket connections inside the Stampi library. When computation nodes can not communicate outside, a router process is invoked on the server node to relay messages from/to user processes on the computation nodes. The spawn functions based on the MPI-2 standard have been implemented in Stampi with the help of a remote shell command (rsh, ssh, etc.) to use computational resources effectively.
Flexible Intermediate Library for MPI-2 Support
131
Fig. 1. Architecture of Stampi on a heterogeneous computing environment.
Remote MPI-I/O operations are carried out with the help of an MPI-I/O process which is invoked on a remote computer. I/O interfaces for users are also based on the MPI-I/O APIs. I/O requests from user processes are translated into a message data, and it is transfered to the MPI-I/O process via a communication path switched to the TCP socket connections. The MPI-I/O process plays parallel-I/O operations according to the I/O requests. When a computer does not have own MPI-I/O library, the pseudo MPI-I/O library in Stampi is used. In the pseudo MPI-I/O method, each MPI-I/O function is translated into the combination of UNIX I/O functions such as write() and data manipulations.
2.2
Execution Mechanism of Stampi on an SCore System
Stampi supports interactive and batch mode both. Here, execution method to create child user processes and MPI-I/O processes from an SCore cluster to a remote computer with a batch system is explained using Fig. 2. Firstly, an SCore start-up process (scout) and a router process are initiated by a Stampi start-up command (starter). Then the scout process initiates user processes. When those user processes call MPI_Comm_spawn() or MPI_File_open(), a router process kicks off a starter process on a remote computer with the help of a remote shell command, and it generates a script file which is submitted to a batch queue system according to a specified queue class in an info object. Secondly, the starter written in the script file kicks off user processes or MPI-I/O processes in the case of MPI_Comm_spawn() or MPI_File_open(), respectively. Besides, a router process is invoked on an IP-reachable node if it is required. Finally, inter-machine MPI communication is available via a communication path established between both computers. Remote I/O operations are carried out by the MPI-I/O processes. When the user processes on the SCore cluster call MPI_File_close(), the MPII/O processes are terminated. Next, mechanism of remote I/O operations is explained. As an example, mechanism of MPI_File_write_at_all() in remote I/O operations is illustrated
132
Y. Tsujita
Fig. 2. Execution mechanism of dynamic process creation and remote I/O operation from an SCore cluster to a remote computer.
in Fig. 3. When user processes call this function, several parameters are packed in a user buffer using MPI–Pack(). Then the buffer is transfered to the MPI-I/O process using MPI_Send() and MPI_Recv() of the Stampi library. In these functions, Stampi-supplied underlying communication functions such as JMPI_Isend(), JMPI-Irecv(), and JMPI_Wait() are called for non-blocking TCP socket communications. After message data is transfered, I/O operation is carried out by the MPI-I/O process, and returned values are sent to the user processes. Other MPI-I/O functions of Stampi also use the similar mechanism.
3
Performance Measurement
Performance of MPI communications and MPI-I/O