Scheduling
Scheduling of jobs is the process of determining how the jobs should be executed in the environment, considering actual mapping
to the resources and time when the execution should take place. Scheduler is a service responsible for scheduling. There can be different
levels of schedulers in the system, depending on how far from the real environment the scheduling is performed. The most bottom-level scheduler (sometimes called
Local Resource Manager (LRM)) interacts directly with the operating system to submit and execute the jobs. Higher-level schedulers
(metaschedulers) consider more global view of the execution environment, and distribute the jobs between different LRMs which are responsible
for the mapping. The scheduling is usually based on some metrics to calculate goal function evaluating fitness value of the mapping. The schedule with the highest
fitness value is chosen for execution. Different criteria can be applied to calculate the metrics. The most widely used are: execution time, economic cost,
fault tolerance and quality of expected results. Scheduler can implement different fault-tolerance and fair-sharing policies to provide higher level of reliability of the environment and fair access to the resources in multi-application and multi-user environment. For instance, the jobs that failed can be restarted or submitted to other resources.
In the Askalon environment lower-level scheduling is done by existing LRMs (PBS, Condor, etc.) wrapped by the Globus middleware. The Askalon Scheduler is a metascheduler distributing the jobs between the Grid resources (e.g., clusters) managed by the middleware services.
Scheduler in ASKALON environment
Fig.1 Scheduler in ASKALON Grid environment. |
The Scheduler (see: Fig.1) is a service which prepares workflow application for execution on the Grid. It processes workflow specification described in AGWL language
converting a workflow to an executable form, and schedules it on available Grid resources. The Scheduler consists of two main
components: Workflow Converter and Scheduling Engine. Event Generator is meant as a future extension of the system to increase dynamicity
in workflow processing.
Workflow Converter resolves all ambiguities, transforming sophisticated workflow graphs to simple DAGs (Directed Acyclic Graphs).
The reason for doing such conversion is to make the workflows applicable for graph scheduling algorithms. All the
transformations are based on the most probable assumptions, and can be changed in
the later phase of workflow execution. The assumptions are applied for conditions and parameters of workflows,
that cannot be evaluated at the beginning of execution. The conditional constructs like while loop, if-then-else or switch are based on
the conditions which determine their execution (number of iterations or execution variant). parallel for may have different number of
parallel branches, depending on the input parameters. Correct prediction may benefit with significant scheduling profit, particulary if a strong imbalance
in the workflow is predicted. Incorrect prediction does not invoke any execution problem, but only brings about the necessity of rescheduling.
Scheduling Engine is responsible for actual scheduling of the evaluated workflows. It is based on a plug-in architecture, where different scheduling
algorithms fitting to the current workflow model can be used interchangeably. The algorithms may have different execution time and different accuracy of the results,
they may also regard different metrics as optimization goals. We applied the HEFT algorithm as the primary scheduling algorithm in
our system.
GridARM provides current status of the resources available on the Grid. It provides also information what Activity Deployments
available on the resources match to the Activity Types of the workflow nodes. Making query to the GridARM, Scheduler sends a set of constraints to be fulfilled
by the requested resources. Performance Predictor supplies predicted activity execution times and data transfer times for performance-driven scheduling algorithms.
Event Generator will coordinate workflow execution, generating events to the Enactment Engine every time when it is necessary.
For instance, rescheduling may be needed when some resources go down, become heavily loaded, or when another relevant event occurs in the system.
Scheduling process starts, when Enactment Engine sends a scheduling request with a workflow description. The workflow consists of nodes representing Activity Types,
control and data links between the nodes, and of specification of the inputs and the outputs (i.e., all the information available in AGWL input). The Workflow Converter
tries to predict all ambiguous control flows in the workflow, and simplifies the workflow to a DAG. The Scheduling Engine receives the DAG and tries to make the
optimal schedule for it. The Scheduling Engine queries the GridARM in order to receive information about different Activity Deployments (activities deployed on
individual resources) that can be mapped to the Activity Types specified in the workflow. From among all possible mapping the Scheduler
have to choose a set of mappings that produces a concrete workflow which is optimal in terms of assumed goal function. If the optimization goal is the execution
time, then the Scheduler queries the Performance Predictor for predicted execution times and data transfer times. One of available scheduling algorithms is applied to
map the workflow nodes to appropriate Activity Deployments. Once created, the mapped workflow is sent to the Enactment Engine for execution.
The execution goes on until it is finished or any interrupting event occurs in the system. If the latter is the case, then the Enactment Engine sends a rescheduling
event which forces the Scheduler to perform a new scheduling (and possibly a new prediction) of the workflow. For instance, a rescheduling event has to be invoked
if any of the assumptions made by the Workflow Converter fails. Another rescheduling strategy, based for instance on periodical rescheduling,
can also be assumed by the Scheduler.
Publications
- Marek Wieczorek, Andreas Hoheisel, Radu Prodan, Taxonomies of the Multi-criteria Grid Workflow Scheduling Problem, CoreGRID Workshop on Grid Middleware, June 25-26, 2007, Dresden, Germany, Springer-Verlag
- Jun Qin, Marek Wieczorek, Kassian Plankensteiner, Thomas Fahringer, Towards a Light-weight Workflow Engine in the ASKALON Grid Environment, First CoreGRID European Network of Excellence Symposium, August 27-28, 2007, IRISA, Rennes, France, Springer-Verlag
- Marek Wieczorek, Mumtaz Siddiqui, Alex Villazón, Radu Prodan, Thomas Fahringer, Applying Advance Reservation to Increase Predictability of Workflow Execution on the Grid, In Proceedings of 2nd IEEE International Conference on e-Science and Grid Computing, IEEE Computer Society Press, December 4-6, 2006, Amsterdam, Netherlands
- Marek Wieczorek, Radu Prodan and Thomas Fahringer, Scheduling of Scientific Workflows in the ASKALON Grid Environment, ACM SIGMOD Record journal, 2005, ACM Press
- Radu Prodan and Thomas Fahringer, Dynamic Scheduling of Scientific Workflow Applications on the Grid using a Modular Optimisation Tool: A Case Study, 20th Symposion of Applied Computing (SAC 2005), ACM Press
Related work
Projects
-
Pegasus
http://pegasus.isi.edu/
Project leaders: Ewa Deelman, Karl Kesselman -
Grid Application Deployment Software (GrADS)
http://icl.cs.utk.edu/grads/
Project leader: Jack Dongarra -
GridLab
http://www.gridlab.org/
Project leader: Jarek Nabrzyski
Articles
- Workflow scheduling
- Dong, F., and Akl, S. G. Scheduling Algorithms for Grid Computing: State of the Art and Open Problems, Technical Report, School of Computing, Queen's University, Kingston, Ontario, 2006
- Deelman, E., and Blythe, J., and Gil, Y., and Kesselman, C. Workflow Management in GriPhyN. Grid Resource Management, State of the Art and Future Trends, Kluwer Academic Publishers, 2004, pp. 99-116
- Deelman, E., and Singh, G., and Su, M., and Blythe, J., and Gil, Y., and Kesselman, C., and Mehta, G., and Vahi, K., and Berriman, G. B., and Good, J., and Laity, A., and Jacob, J. C., and Katz, D. Pegasus: a Framework for Mapping Complex Scientific Workflows onto Distributed Systems Scientific Programming Journal, 2005, 13
- N'Takpé, T., and Suter, F. Critical path and area based scheduling of parallel task graphs on heterogeneous platforms, Proceedings of the 12th International Conference onParallel and Distributed Systems, ICPADS 2006, IEEE Computer Society Press, 2006
- Sakellariou, R., and Zhao, H. A Hybrid Heuristic for DAG Scheduling on Heterogeneous Systems IPDPS, 2004
- Topcuouglu, H., and Hariri, S., and Wu, M. Performance-Effective and Low-Complexity Task Scheduling for Heterogeneous Computing, IEEE Trans. Parallel Distrib. Syst., IEEE Press, 2002, pp. 260-274
- Yu, Z., and Shi, W. An Adaptive Rescheduling Strategy for Grid Workflow Applications, Proceedings of the 21st IPDPS 2007, Wayne State University, IEEE Computer Society Press, 2007
- Sih, G. C., and Lee, E. A. A Compile-Time Scheduling Heuristic for Interconnection-Constrained Heterogeneous Processor Architectures, IEEE Trans. Parallel Distrib. Syst., IEEE Press, 1993, pp. 175-187
- Multi-objective scheduling
- Doğan, A., and Özgüner, F. Biobjective Scheduling Algorithms for Execution Time-Reliability Trade-off in Heterogeneous Computing Systems, Comput. J., Oxford University Press, 2005, 48, 300-314
- Qin, X., and Jiang, H. A novel fault-tolerant scheduling algorithm for precedence constrained tasks in real-time heterogeneous systems Parallel Comput., Elsevier Science Publishers B. V., 2006, 32, pp. 331-356
- Jia Yu, Rajkumar Buyya, and Chen Khong Tham, QoS-based Scheduling of Workflow Applications on Service Grids, Proceedings of the 1st IEEE International Conference on e-Science and Grid Computing (e-Science 2005, IEEE CS Press, Los Alamitos, CA, USA), Dec. 5-8, 2005, Melbourne, Australia.
- Jia Yu and Rajkumar Buyya, A Budget Constrained Scheduling of Workflow Applications on Utility Grids using Genetic Algorithms, Workshop on Workflows in Support of Large-Scale Science, Proceedings of the 15th IEEE International Symposium on High Performance Distributed Computing (HPDC 2006, IEEE CS Press, Los Alamitos, CA, USA), June 19-23, 2006, Paris, France.
- Jia Yu and Rajkumar Buyya, Scheduling Scientific Workflow Applications with Deadline and Budget Constraints using Genetic Algorithms, Scientific Programming Journal, ISSN: 1058-9244, IOS Press, Amsterdam, The Netherlands (in press, accepted in Sept. 2006).
- Jia Yu, Michael Kirley, and Rajkumar Buyya, Multi-objective Planning for Workflow Execution on Grids, Proceedings of the 8th IEEE/ACM International Conference on Grid Computing (Grid 2007, IEEE CS Press, Los Alamitos, CA, USA), Sept. 19-21, 2007, Austin, Texas, USA
- E. Tsiakkouri, R. Sakellariou, H. Zhao, and M. D. Dikaiakos, Scheduling Workflows with Budget Constraints, In Proceedings of the CoreGRID Workshop "Integrated research in Grid Computing", Nov. 2005, p.347-357
- Ivona Brandic, Siegfried Benkner, Gerhard Engelbrecht, Rainer Schmidt, QoS Support for Time-Critical Grid Workflow Applications, E-SCIENCE '05: Proceedings of the First International Conference on e-Science and Grid Computing
- Yaron Klein, Gideon Langholz, Multi-Criteria Scheduling Optimization Using Fuzzy Logic, IEEE Int Conference on Systems, Man and Cybernetics, 1998
- Service Level Agreements
- A. Andrieux, K. Czajkowski, A. Dan, K. Keahey, H. Ludwig, T. Kakata, J. Pruyne, J. Rofrano, S. Tuecke, M. Xu, Web Services Agreement Specification (WS-Agreement)
- Viktor Yarmolenko, and Rizos Sakellariou, An Evaluation of Heuristics for SLA Based Parallel Job Scheduling, 3rd High Performance Grid Computing Workshop/ (in conjunction with IPDPS'06), 2006, Rhodes, Greece.
- Antoine Pichot - Alcatel-Lucent, Philipp Wieder - Research Centre Jülich, Wolfgang Ziegler, Oliver Wäldrich, Dynamic SLA-negotiation based on WS-Agreement
- M. Aiello, G. Frankova, and D. Malfatti, What's in an Agreement? An Analysis and an Extension of WS-Agreement, (2005) LNCS 3826:424-436, Int. Conf. on Service-Oriented Computing (ICSOC) 2005 Springer.
- Philipp Wieder, Oliver Wäldrich, Wolfgang Ziegler, Ramin Yahyapour, Improving Workflow Execution through SLA-based Advance Reservation, Proceedings of the CoreGRID Integration Workshop 2006, Academic Computer Centre CYFRONET AGH, Kraków, Poland, October 19-20,2006, pp. 333-344
- Jarek Nabrzyski, Jennifer M. Schopf and Jan Weglarz, Grid Resource Management: State of the Art and Future Trends Kluwer Publishing, 2003
- Radu Prodan, Thomas Fahringer, Scheduling Workflow Applications on the Grid, ICS 2004
- Radu Prodan, Thomas Fahringer, ZENTURIO: AGrid Service-based Tool for Optimising Parallel and Grid Applications, Kluwer Academic Publishers, 2004
- T. C. Peachey and Monash University, Nimrod/O Users' Guide, 2003
- Some possible heuristics for scheduling beyond genetic algorithms
- Dror F. Feitelson, Larry Rudolph, Uwe Schwiegelshohn, Parallel Job Scheduling -- A Status Report, 10th Workshop on Job Scheduling Strategies for Parallel Processing, June 2004
- Description of backfilling and gang scheduling as two popular strategies for job scheduling
- Backfilling: study on the runtime prediction; is the exact runtime estimation really crucial?
- Gang scheduling: how many jobs may be allocated to the same resource at the same time?
- K. Cooper, F. Berman, L. Johnsson, D. Reed, Z. Shi, et. al., New Grid Scheduling and Rescheduling Methods in the GrADS Project
Books
- Optimization techniques
- Marco Dorigo and Thomas Stützle, Ant Colony Optimization
Theses
- Anirban Mandal, Toward a Tool for Scheduling Application Workflows onto Distributed Grid Systems, 2006
- Divya Prakash, Bi-criteria Scheduling Problems on Parallel Machines, 1997
- Graham Ritchie, Static Multi-processor Scheduling with Ant Colony Optimisation & Local Search, 2003
- Lu Tian, Resource allocation in streaming environments, 2006
Web pages
- University of Plymouth, Different scheduling related publications