Scheduling with task replication on desktop grids: theoretical and experimental analysis
Pages 520 - 544
Abstract
Our main objective in this paper is to study the possible benefits of using task replication when generating a schedule in a desktop grid. We consider the problem of constructing a schedule in an environment where machines' speeds may be unpredictable and the objective is to minimize the makespan of the schedule. Another considered objective is to minimize the total processor cycle consumption. First we provide a theoretical study of a well known algorithm that makes use of replication: the WQRxx algorithm. We prove approximation ratios for this algorithm in different scenarios, and also show that such ratios are tight. We propose a simple interface and show how to add replication to any scheduling algorithm using this interface. We also prove approximation ratios for any algorithm that uses this interface. We then extend several well known algorithms to generate schedules with replication via the interface, and present computational simulations comparing the quality of the solutions of these algorithms with the addition of replication.
References
[1]
Anderson DP, Cobb J, Korpela E, Lebofsky M, Werthimer D (2002) Seti@home: an experiment in public-resource computing. Commun ACM 45(11):56-61.
[2]
Baratloo A, Karaul M, Kedem ZM, Wijckoff P (1999) Charlotte: metacomputing on the web. Future Gener Comput Syst 15(5-6):559-570.
[3]
Bougeret M, Dutot P, Jansen K, Otte C, Trystram D (2010) A fast 5/2-approximation algorithm for hierarchical scheduling. Euro-Par, pp. 157-167.
[4]
Casanova H, Legrand A, Zagorodnov D, Berman F (2000) Heuristics for scheduling parameter sweep applications in grid environments. In: Heterogeneous computing, workshop, pp. 349-363.
[5]
Cirne W, Brasileiro FV, da Silva DP, Góes LFW, Voorsluys W (2007) On the efficacy, efficiency and emergent behavior of task replication in large distributed systems. Parallel Comput 33(3):213-234.
[6]
Cirne W, da Silva DP, Costa L, Santos-Neto E, Brasileiro FV, Sauvé JP, Silva FAB, Barros CO, Silveira C (2003) Running bag-of-tasks applications on computational grids: the mygrid approach. In: 32nd international conference on parallel processing (ICPP), pp. 407-416.
[7]
da Silva DP, Cirne W, Brasileiro FV (2003) Trading cycles for information: Using replication to schedule bag-of-tasks applications on computational grids. In 9th International Euro-Par Conference on parallel processing (Euro-Par), pp. 169-180.
[8]
Dean J, Ghemawat S (2004) Mapreduce: simplified data processing on large clusters. In 6th symposium on operating system design and implementation (OSDI), pp. 137-150.
[9]
Dolan ED, Moré JJ (2002) Benchmarking optimization software with performance profiles. Math Program 91(2):201-213.
[10]
Dong F, Akl SG (2006) Scheduling algorithms for grid computing: state of the art and open problems. Technical Report No. 2006-504, School of Computing, Queen's University.
[11]
Fujimoto N (2008) On non-approximability of coarse-grained workflow grid scheduling. In 9th International symposium on parallel architectures, algorithms, and networks (ISPAN), pp. 127-132.
[12]
Fujimoto N, Hagihara K (2003) Near-optimal dynamic task scheduling of independent coarse-grained tasks onto a computational grid. In 32nd international conference on parallel processing (ICPP), pp. 391-398.
[13]
Fujimoto N, Hagihara K (2004) A comparison among grid scheduling algorithms for independent coarse-grained tasks. In SAINT workshops, pp. 674-680.
[14]
Fujimoto N, Hagihara K (2006) A 2-approximation algorithm for scheduling independent tasks onto a uniform parallel machine and its extension to a computational grid. In Proceedings of the 2006 IEEE international conference on cluster computing (CLUSTER).
[15]
Graham RL, Lawler EL, Lenstra JK, Kan AHGR (1979) Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann Discret Math 17:416-429.
[16]
Liu K, Chen J, Jin H, Yang Y (2009) A Min-Min average algorithm for scheduling transaction-intensive grid workflows. In: Proceedings of the 7th Australasian symposium on grid computing and e-research (AusGrid) Wellington. Australian Computer Society, New Zealand, pp. 41-48.
[17]
Menascé DA, Saha D, Porto SCS, Almeida V, Tripathi SK (1995) Static and dynamic processor scheduling disciplines in heterogeneous parallel architectures. J Parallel Distrib Comput 28(1):1-18.
[18]
Quezada-Pina A, Tchernykh A, González-García JL, Hirales-Carbajal A, Ramírez-Alcaraz JM, Schwiegelshohn U, Yahyapour R, Miranda-López V (2012) Adaptive parallel job scheduling with resource admissible allocation on two-level hierarchical grids. Future GenerComput Syst 28(7):965-976.
[19]
Schwiegelshohn U, Tchernykh A, Yahyapour R (2008) Online scheduling in grids. In 22nd IEEE international symposium on parallel and distributed processing (IPDPS) pp. 1-10.
[20]
Tchernykh A, Schwiegelshohn U, Yahyapour R, Kuzjurin N (2010) On-line hierarchical job scheduling on grids with admissible allocation. J Sched 13:545-552.
[21]
Xavier EC, Peixoto RRS (2010) On the Worst Case of Scheduling with Task Replication on Computational Grids. In 22nd international symposium on computer architecture and high performance computing (SBAC-PAD), pp. 135-142.
- Scheduling with task replication on desktop grids: theoretical and experimental analysis
Recommendations
On the efficacy, efficiency and emergent behavior of task replication in large distributed systems
Large distributed systems challenge traditional schedulers, as it is often hard to determine a priori how long each task will take to complete on each resource, information that is input for such schedulers. Task replication has been applied in a ...
Real-Time Task Replication for Fault Tolerance in Identical Multiprocessor Systems
RTAS '07: Proceedings of the 13th IEEE Real Time and Embedded Technology and Applications SymposiumMultiprocessor platforms have been widely adopted in both embedded and server systems. In addition to the performance improvement, multiprocessor systems could have the flexibility in tolerating processor failures via task replication. This paper ...
From preemptive to non-preemptive speed-scaling scheduling
We are given a set of jobs, each one specified by its release date, its deadline and its processing volume (work), and a single (or a set of) speed-scalable processor(s). We adopt the standard model in speed-scaling in which if a processor runs at speed ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © Copyright © 2015 Springer Science+Business Media New York.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 01 October 2015
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 06 Jan 2025