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 24 Issue 3
May  2009
Turn off MathJax
Article Contents
Abstract
References
Related Articles
Xiao-Min Zhu, Pei-Zhong Lu. Multi-Dimensional Scheduling for Real-Time Tasks on Heterogeneous Clusters[J]. Journal of Computer Science and Technology, 2009, 24(3): 434-446.
Citation: Xiao-Min Zhu, Pei-Zhong Lu. Multi-Dimensional Scheduling for Real-Time Tasks on Heterogeneous Clusters[J]. Journal of Computer Science and Technology, 2009, 24(3): 434-446.
shu

Multi-Dimensional Scheduling for Real-Time Tasks on Heterogeneous Clusters

  • School of Computer Science, Fudan University, Shanghai 200433, China

Funds: This work is supported by the National Natural Science Foundation of China under Grant No. 60673082, and the Special Funds of Authors of Excellent Doctoral Dissertation in China under Grant No.200084.
More Information
  • Author Bio:

    Xiao-Min Zhu received the B.S. and M.S. degrees in computerscience from Liaoning Technical University in 2001 and 2004,respectively. He is currently working toward the Ph.D. degree with theSchool of Computer Science, Fudan University, China. Hisresearch interests are high performance computing, cluster computing,fault-tolerant computing, and information security.

    Pei-Zhong Lu received the B.S. and M.S. degrees in appliedmathematics from Institute of Information Engineering in 1982 and1987, respectively. He received the Ph.D. degree from Institute ofSystems Science, AMSS, China, in 1998. He is currently aprofessor in the School of Computer Science at Fudan University. Hisresearch interests are information security, algebra coding,parallel and distributed systems, real-time computing andperformance evaluation. He has published more than 50 technicalpapers in reputable journals and conference proceedings. He receivedthe Excellent Doctoral Dissertation Award of China in 2000. He is amember of IEEE.

  • Received Date: October 02, 2008
  • Revised Date: January 24, 2009
  • Published Date: May 04, 2009
    Abstract
  • Multiple performance requirements need to be guaranteed in some real-time applications such as multimedia data processing and real-time signal processing in addition to timing constraints. Unfortunately, most conventional scheduling algorithms only take one or two dimensions of them into account. Motivated by this fact, this paper investigates the problem of providing multiple performance guarantees including timeliness, QoS, throughput, QoS fairness and load balancing for a set of independent tasks by dynamic scheduling. We build a scheduler model that can be used for multi-dimensional scheduling. Based on the scheduler model, we propose a heuristic multi-dimensional scheduling strategy, MDSS, consisting of three steps. The first step can be of any existing real-time scheduling algorithm that determines to accept or reject a task. In step 2, we put forward a novel algorithm MQFQ to enhance the QoS levels of accepted tasks, and to make these tasks have fair QoS levels at the same time. Another new algorithm ITLB is proposed and used in step 3. The ITLB algorithm is capable of balancing load and improving throughput of the system. To evaluate the performance of MDSS, we perform extensive simulation experiments to compare MDSS strategy with MDSR strategy, DASAP and DALAP algorithms. Experimental results show that MDSS significantly outperforms MDSR, DASAP and DALAP.
    • FullText(HTML)
    • References (31)
  • [1]
    Hwang K, Xu Z. Scalable Parallel Computing: Technology,Architecture, Programming. USA: McGraw-Hill, 1998.
    [2]
    Qin X, Jiang H. A dynamic and reliability-driven schedulingalgorithm for parallel real-time jobs executing on heteroge-neous clusters. Journal of Parallel and Distributed Comput-ing, 2005, 65(8): 885-900.
    [3]
    Xie T, Qin X. Scheduling security-critical real-time applica-tions on clusters. IEEE Trans. Computers, 2006, 55(7): 864-879.
    [4]
    Krishna C M, Shin K G. Real-Time Systems. USA: McGraw-Hill, 2001.
    [5]
    Zhu X, Lu P. Study of scheduling for processing real-timecommunication signals on heterogeneous clusters. In Proc.9th Int. Symp. Parallel Architectures, Algorithms, and Net-works, Sydney, Australia, May 7-9, 2008, pp.121-126.
    [6]
    Zhu X, Lu P. Scheduling of real-time signal processing incluster-based software radio systems. Journal of Software,2009, 20(3): 766-778.
    [7]
    Zhu X, Lu P. Multi-dimensional scheduling scheme for QoSaware real-time applications on heterogeneous clusters. InProc. 10th IEEE Int. Conf. High Performance Comput-ing and Communications, Dalian, China, Sept. 25-27, 2008,pp.205-212.
    [8]
    Pyndiah R, Glavieux A, Picart A et al. Near optimal decodingof product codes. In Proc. IEEE Global TelecommunicationsConf., Dallas, Texas, USA, Nov. 29-Dec. 3, 2004, pp.339-343.
    [9]
    Chi Z, Song L, Parhi K K. A study on the performance,complexity tradeoffs of block turbo decoder design. In Proc.IEEE Int. Symp. Circuits and Systems, Sydney, Australia,May 6-9, 2001, pp.65-68.
    [10]
    Adde P, Pyndiah R. Recent simplifications and improvementsin block turbo codes. In Proc. 2nd Int. Symp. Trubo Codesand Related Topics, Brest, France, Sept. 4-7, 2000, pp.133-136.
    [11]
    Ullman J D. NP-complete scheduling problems. Journal ofComputer and System Sciences, 1975, 10(3): 384-393.
    [12]
    Braun T D, Siegal H J, Beck N et al. A comparison studyof static mapping heuristics for a class of meta-tasks on het-erogeneous computing systems. In Proc. 8th HeterogeneousComputing Workshop, San Juan, Puerto Rico, Apr. 12, 1999,pp.15-29.
    [13]
    Maheswaran M, Ali S, Siegel H J et al. Dynamic mappingof a class of independent tasks onto heterogeneous comput-ing systems. Journal of Parallel and Distributed Computing,1999, 59(2): 107-121.
    [14]
    Beccari G, Caselli S, Zanichelli F. A technique for adaptivescheduling of soft real-time tasks. Journal of Real-Time Sys-tems, 2005, 30(3): 187-215.
    [15]
    Manimaran G, Murthy C S R. A fault-tolerant dynamicscheduling algorithm for multiprocessor real-time systems andits analysis. IEEE Trans. Parallel and Distributed Systems,1998, 9(11): 1137-1152.
    [16]
    Topcuoglu H, Hariri S. Performance-effective and low-complexity task scheduling for heterogeneous computing.IEEE Trans. Parallel and Distributed Systems, 2002, 13(3):260-274.
    [17]
    Abdelzaher T F, Shin K G. Combined task and messagescheduling in distributed real-time systems. IEEE Trans.Parallel and Distributed Systems, 1999, 10(11): 1179-1191.
    [18]
    He L, Jarvis S A, Spooner D P et al. Dynamic schedulingof parallel real-time jobs by modeling spare capabilities inheterogeneous clusters. In Proc. IEEE Int. Conf. ClusterComputing, Hong Kong, China, Dec. 1-4, 2003, pp.2-10.
    [19]
    Cheng S, Huang Y. Dynamic real-time scheduling multi-processor tasks using genetic algorithm. In Proc. Int. Conf.Computer Software and Applications, Hong Kong, China,Sept. 28-30, 2004, pp.154-160.
    [20]
    Boyer W F, Hura G S. Non-evolutionary algorithm forscheduling dependent tasks in distributed heterogeneous com-puting environments. Journal of Parallel and DistributedComputing, 2005, 65(9): 1035-1046.
    [21]
    Ghosh S, Melhem R, Mosse D. Fault-tolerance throughscheduling of aperiodic tasks in hard real-time multiproces-sor systems. IEEE Trans. Parallel and Distributed Systems,1997, 8(3): 272-284.
    [22]
    Palis M A. Online real-time job scheduling with rate ofprogress guarantees. In Proc. Int. Symp. Parallel Archi-tectures, Algorithms and Networks, Manila, Philippines, May23-25, 2002, pp.57-62.
    [23]
    Xu J, Parnas L. Scheduling processes with release times, dead-lines, precedence, and exclusion relations. IEEE Trans. Soft-ware Engineering, 1990, 16(3): 360-369.
    [24]
    Yang C, Deconinck G, Gui W. Fault-tolerant scheduling forreal-time embedded control systems. Journal of ComputerScience and Technology, 2004, 19(2): 191-202.
    [25]
    Li W, Kavi K, Akl R. A non-preemptive scheduling algorithmfor soft real-time systems. Journal of Computers and Elec-trical Engineering, 2007, 33(1): 12-29.
    [26]
    Manimaran, C S R Murthy. An efficient dynamic schedulingalgorithm for multiprocessor real-time systems. IEEE Trans.Parallel and Distributed Systems, 1998, 9(3): 312-319.
    [27]
    Atdelzater T F, Atkins E M, Shin K G. QoS negotiation inreal-time systems and its application to automated flight con-trol. IEEE Trans. Computers, 2000, 49(11): 1170-1183.
    [28]
    Guo J, Bhuyan L N. Load balancing in a cluster-based webserver for multimedia applications. IEEE Trans. Parallel andDistributed Systems, 2006, 17(11): 1321-1334.
    [29]
    Harada F, Ushio T, Nakamoto Y. Adaptive resource alloca-tion control for fair QoS management. IEEE Trans. Com-puters, 2007, 56(3): 344-357.
    [30]
    He L, Jarvis S A, Spooner D P. Dynamic scheduling of par-allel jobs with QoS demands in multiclusters and grids. InProc. 5th IEEE/ACM Int. Workshop on Grid Computing,Pittsburgh, USA, Nov. 8, 2004, pp.402-409.
    [31]
    Do•gan A, ÄOzgÄuner F. On QoS-based scheduling of a meta-taskwith multiple QoS demands in heterogeneous computing. InProc. 16th IEEE Int. Symposium on Parallel and DistributedProcessing, Florida, USA. Apr. 15-19, 2002, pp.50-55.
    • Relative Articles

  • Related Articles

    [1]Zhang-Jin Huang, Xiang-Xiang He, Fang-Jun Wang, Qing Shen. A Real-Time Multi-Stage Architecture for Pose Estimation of Zebrafish Head with Convolutional Neural Networks[J]. Journal of Computer Science and Technology, 2021, 36(2): 434-444. DOI: 10.1007/s11390-021-9599-5
    [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]Jing Chen, Zi-Ning Cao. Model Checking Real-Time Value-Passing Systems[J]. Journal of Computer Science and Technology, 2004, 19(4).
    [4]ZHAN Naijun. An Intuitive Formal Proof for Deadline Driven Scheduler[J]. Journal of Computer Science and Technology, 2001, 16(2).
    [5]Luo Tiegeng, Chen Huowang, Wang Bingshan, Wang Ji, Gong Zhenghu, Qi Zhichang. Verifying Automata Specification of Distributed Probabilistic Real-Time Systems[J]. Journal of Computer Science and Technology, 1998, 13(6): 588-596.
    [6]Li Wei, Zhang Bo, Hilmar Jaschek. Real-Time Collision-Free Path Planning for Robots in Configuration Space[J]. Journal of Computer Science and Technology, 1994, 9(1): 37-52.
    [7]Zhou Di. Adapting Backward Error Recovery to Parallel Real Time Systems[J]. Journal of Computer Science and Technology, 1992, 7(3): 257-267.
    [8]Yan Yong, Jin Canming. A Theory for the Initial Allocating of Real Time Tasks in Distributed Systems[J]. Journal of Computer Science and Technology, 1992, 7(2): 185-188.
    [9]Li Weihua, Yuan Youguang. Error Recovery in a Real-Time Multiprocessor System[J]. Journal of Computer Science and Technology, 1992, 7(1): 83-87.
    [10]Duan Ping, Cai Xiyao. A Real-Time Interprocessor Synchronization Algorithm for Communication in Distributed Computer Systems[J]. Journal of Computer Science and Technology, 1987, 2(4): 292-302.
    • Supplements (0)

Catalog

    Get Citation
    XML
    Article views (38) PDF downloads (2506) 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