We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Advanced Search
Volume 25 Issue 4
July  2010
Turn off MathJax
Article Contents
Abstract
References
Related Articles
Zhi-Feng Yu, Wei-Song Shi. Queue Waiting Time Aware Dynamic Workflow Scheduling in Multicluster Environments[J]. Journal of Computer Science and Technology, 2010, 25(4): 864-873. DOI: 10.1007/s11390-010-1067-6
Citation: Zhi-Feng Yu, Wei-Song Shi. Queue Waiting Time Aware Dynamic Workflow Scheduling in Multicluster Environments[J]. Journal of Computer Science and Technology, 2010, 25(4): 864-873. DOI: 10.1007/s11390-010-1067-6
shu

Queue Waiting Time Aware Dynamic Workflow Scheduling in Multicluster Environments

  • Department of Computer Science, Wayne State University, Detroit, MI 48202, U.S.A.

Funds: This work is in part supported by the US National Science Foundation CAREER Grant No. CCF-0643521.
More Information
  • Author Bio:

    Zhi-Feng Yu received the B.S. degree in applied mathematics and M.S. degree in economics and management from Tongji University, Shanghai, China, in 1990 and 1993 respectively and the Ph.D. degree in computer science from Wayne State University, Detroit, USA in 2009. He is currently Manager of Application Development and Integration of TSystems North America, Rochester Hills, MI. His research interests include computer systems and enterprise computing.

    Wei-Song Shi is an associate professor of computer science at Wayne State University. He received his B.S. degree from Xidian University in 1995, and Ph.D. degree from the Chinese Academy of Sciences in 2000, both in computer engineering. His current research focuses on mobile computing, distributed systems and high performance computing. Dr. Shi has published more than 80 peer-reviewed journal and conference papers in these areas. He is the author of the book “Performance Optimization of Software Distributed Shared Memory Systems” (Higher Education Press, 2004). He has also served on technical program committees of several international conferences, including WWW, ICPP, MASS. He is a recipient of Microsoft Fellowship in 1999, the President Outstanding Award of the Chinese Academy of Sciences in 2000, one of 100 Outstanding Ph.D. Dissertations (China) in 2002, “Faculty Research Award” of Wayne State University in 2004 and 2005, the “Best Paper Award” of ICWE’04 and IPDPS’05. He is a recipient of the NSF CAREER award andWayne State University Career Development Chair award.

  • Received Date: July 31, 2009
  • Revised Date: March 16, 2010
  • Published Date: July 08, 2010
    Abstract
  • Workflows are prevailing in scientific computation. Multicluster environments emerge and provide more resources, benefiting workflows but also challenging the traditional workflow scheduling heuristics. In a multicluster environment, each cluster has its own independent workload management system. Jobs are queued up before getting executed, they experience different resource availability and wait time if dispatched to different clusters. However, existing scheduling heuristics neither consider the queue wait time nor balance the performance gain with data movement cost. The proposed algorithm leverages the advancement of queue wait time prediction techniques and empirically studies if the tunability of resource requirements helps scheduling. The extensive experiment with both real workload traces and test bench shows that the queue wait time aware algorithm improves workflow performance by 3 to 10 times in terms of average makespan with relatively very low cost of data movement.
    • FullText(HTML)
    • References (24)
  • [1]
    NSF teragrid. http://www.teragrid.org/.
    [2]
    Li H, Groep D, Wolters L. Workload characteristics of a multi-cluster supercomputer. In Proc. the 10th International Workshop on Job Scheduling Strategies for Parallel Processing (JSSPP,2004), New York, USA, June 13, 2004, pp.176-193.
    [3]
    Nurmi D, Brevik J, Wolski R. QBETS: Queue bounds estimation from time series. In Proc. the 2007 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS,2007), San Diego, USA, June 12-16, 2007, pp.379-380.
    [4]
    QBETS web service. http://spinner.cs.ucsb.edu/batchq/.
    [5]
    Aida K, Casanova H. Scheduling mixed-parallel applications with advance reservations. In Proc. the 17th International Symposium on High-Performance Distributed Computing (HPDC\,2008), Boston, USA, June 23-27, 2008, pp.65-74.
    [6]
    N'Takpe T, Suter F, Casanova H. A comparison of scheduling approaches for mixed-parallel applications on heterogeneous platforms. In Proc. the Sixth International Symposium on Parallel and Distributed Computing (ISPDC,2007), Hagenberg, Austria, July 5-8, 2007, p.35.
    [7]
    Rauber T, Runger G. M-task-programming for heterogeneous systems and grid environments. In Proc. 19th International Parallel and Distributed Processing Symposium (IPDPS,2005), Los Alamitos, USA, April 4-8, 2005, p.178b.
    [8]
    He L, Jarvis S, Spooner D, Nudd G. Performance evaluation of scheduling applications with DAG topologies on multiclusters with independent local schedulers. In Proc. the 20th International Parallel and Distributed Processing Symposium (IPDPS,2006), Rhodes Island, Greece, April 25-29, 2006, pp.8-15.
    [9]
    Yu Z, Shi W. An adaptive rescheduling strategy for grid workflow applications. In Proc. the 21st International Parallel and Distributed Processing Symposium (IPDPS,2007), Long Beach, USA, March 26-30, 2007, p.115.
    [10]
    Yu Z, Shi W. A planner-guided scheduling strategy for multiple workflow applications. In Proc. the Fourth International Workshop on Scheduling and Resource Management for Parallel and Distributed Systems, in conjunction with ICPP 2008, Portland, USA, Sept. 8-12, 2008, pp.1-8.
    [11]
    Topcuouglu H, Hariri S, Wu M. Performance-effective and low-complexity task scheduling for heterogeneous computing. IEEE Transactions on Parallel and Distribution Systems, 2002, 13(3): 260-274.
    [12]
    The Globus Alliance. http://www.globus.org/.
    [13]
    Huang R, Casanova H, Chien A. Automatic resource specification generation for resource selection. In Proc. the 2007 ACM/IEEE Conference on Supercomputing (SC\,2007), Reno, USA, Nov. 10-16, 2007, pp.1-11.
    [14]
    Hill M, Marty M. Amdahl's law in the multicore era. Computer, 2008, 41(7): 33-38.
    [15]
    Hõnig U, Schiffmann W. A comprehensive test bench for the evaluation of scheduling heuristics. In Proc. the 16th International Conference on Parallel and Distributed Computing and Systems (PDCS,2004), Cambridge, USA, Nov. 9-11, 2004, pp.437-442.
    [16]
    Sulistio A, Cibej U, Venugopal S, Robic B, Buyya R. A toolkit for modelling and simulating data grids: An extension to gridsim. Concurr. Comput.: Pract. Exper., 2008, 20(13): 1591-1609.
    [17]
    Portable Batch System. http://www.openpbs.org, Dec. 2008.
    [18]
    Sabin G, Kettimuthu R, Rajan A, Sadayappan P. Scheduling of parallel jobs in a heterogeneous multi-site environment. In the 9th International Workshop of Job Scheduling Strategies for Parallel Processing (JSSPP,2003), Seattle, USA, June 24, 2003, pp.87-104.
    [19]
    Yu Z. Toward practical multi-workflow scheduling in cluster and grid environments
    [Ph.D. Dissertation]. Wayne State University, 2008. %scheduling applications with dag topologies on multiclusters with%Symposium of Parallel and Distributed Processing Symposium (IPDPS,2006),
    [20]
    Shivaratri N, Krueger P, Singhal M. Load distributing for locally distributed systems. Computer, 1992, 25(12): 33-44.
    [21]
    Maheswaran M, Ali S, Siegel H, Hensgen D, Freund R. Dynamic mapping of a class of independent tasks onto heterogeneous computing systems. J. Parallel Distrib. Comput., 1999, 59(2): 107-131.
    [22]
    Hunold S, Rauber T, Runger G. Dynamic scheduling of multi-processor tasks on clusters of clusters. In Proc. 2007 IEEE International Conference on Cluster Computing, Austin, USA, Sept. 17-21, 2007, pp.507-514.
    [23]
    Hunold S, Rauber T, Suter F. Scheduling dynamic workflows onto clusters of clusters using postponing. In Proc. the 2008 Eighth IEEE International Symposium on Cluster Computing and the Grid (CCGRID,2008), Lyon, France, May 19-22, 2008, pp.669-674.
    [24]
    Nurmi D, Mandal A, Brevik J, Koelbel C, Wolski R, Kennedy K. Evaluation of a workflow scheduler using integrated performance modelling and batch queue wait time prediction. In Proc. the 2006 ACM/IEEE Conference on Supercomputing (SC,2006), Tampa, USA, Nov. 11-17, 2006, Article No.119.
    • Relative Articles

  • Related Articles

    [1]Bo Yu, Jian-Zhong Li. Minimum-Time Aggregation Scheduling in Duty-Cycled Wireless Sensor Networks[J]. Journal of Computer Science and Technology, 2011, 26(6): 962-970. DOI: 10.1007/s11390-011-1193-9
    [2]Lizhong Dai, Dongmei Zhao. Uplink Scheduling for Supporting Real Time Voice Traffic in IEEE 802.16 Backhaul Networks[J]. Journal of Computer Science and Technology, 2008, 23(5): 806-814.
    [3]Yong He, Yi-Wei Jiang. Preemptive Semi-Online Scheduling with Tightly-Grouped Processing Times[J]. Journal of Computer Science and Technology, 2004, 19(6).
    [4]Wen-Qi Huang, Zhi Huang. Algorithm Based on Taboo Search and Shifting Bottleneck for Job Shop Scheduling[J]. Journal of Computer Science and Technology, 2004, 19(6).
    [5]Kyung-Oh Lee, Jun-Ho Park, Yoon-Young Park. Striping and Scheduling for Large Scale Multimedia Servers[J]. Journal of Computer Science and Technology, 2004, 19(6).
    [6]HE Yong, CAI Shengyi. Semi-Online Scheduling with Machine Cost[J]. Journal of Computer Science and Technology, 2002, 17(6).
    [7]LI Guodong, ZHANG Defu. Distributing and Scheduling Divisible Task on Parallel Communicating Processors[J]. Journal of Computer Science and Technology, 2002, 17(6).
    [8]WANG wen jun, ZHONG Cuihao. The Distributed Workflow Management System - Flow Agent[J]. Journal of Computer Science and Technology, 2000, 15(4): 376-382.
    [9]Ju Jiubin, Wang Yong, Yin Yu. Scheduling PVM Tasks[J]. Journal of Computer Science and Technology, 1997, 12(2): 167-176.
    [10]Zhang Bo, Zhang Ling. A Relation Matrix Approach to Labelling Temporal Relations in Scheduling[J]. Journal of Computer Science and Technology, 1991, 6(4): 339-346.
    • Supplements (0)

Catalog

    Get Citation
    PDF
    XML
    Article views (33) PDF downloads (1783) Cited by()
    Related

    Copyright ©2025 JCST, All Rights Reserved     京ICP备05002829号-1

    Institute of Computing Technology, Chinese Academy of Sciences
    P.O. Box 2704, Beijing 100190, P.R. China

    Tel.: 86-10-62610746 E-mail: jcst@ict.ac.cn

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return