3rd EGEE User Forum

Workflow meta-scheduler for Grid Environments

12 Feb 2008, 16:00

Exhibition Hall (<a href="http://www.polydome.org">Le Polydôme</a>, Clermont-Ferrand, FRANCE)

Poster Scientific Results Obtained Using Grid Technology Posters

Speakers

Mr Florin Pop (University "Politehnica" of Bucharest)Prof. Valentin Cristea (University "Politehnica" of Bucharest)

Description

Based on our contribution to the 2nd EGEE User Forum, we extend the DIOGENES (DIstributed Optimal GENEtic algorithm for grid application Scheduling) project that provides a solution to the Grid scheduling problem at application level. The extension consists of a new algorithm that aims to achieve a distributed, fault-tolerant, scalable and efficient method for dependable task (DAG) assignment in Grid environments. Several metrics including scheduling time, scheduling length and load balancing are used to highlight improved behavior of our proposal as compared with other existing scheduling strategies (HLFET – Highest Level First with Estimated Times, ETF – Earlier Time First, MCP – Modified Critical Path). The scheduling priority is represented by the ALAP (As Late As Possible) parameter. The improvements are made in the node sorting step: defining an additional criteria for nodes with the same ALAP and use of descendant prediction to improve the critical path.

URL for further information:

http://diogenes.grid.pub.ro

1. Short overview

Based on the analysis of DAG scheduling methods, we proposed an algorithm for workflow scheduling in Grid environments that respects the total scheduling time, the schedule length and load balancing. It provides efficient resource utilization by minimizing the idle time on the processing elements. Experimental results are provided to support the performance evaluation of the algorithm and compare them with other scheduling strategies. The algorithm have been integrated in the DIOGENES scheduler.

3. Impact

The proposed algorithm is useful in heterogeneous environments in which the optimization of task workflow scheduling leads to performance improvement. The algorithm has a quadratic polynomial time complexity. Example applications that generate workflows can be found in many application domains. In particular, for satellite image processing, some tasks that process an image segment (a region or a spectral band) could send their output (associated with attributes such as the resolution used in processing) to other tasks in a flow, or could create, configure and submit new tasks. For these applications, the integration of the proposed algorithm in DIOGENES meta-scheduler, which uses an agent framework for management and communication, offers access to different clusters in Grid and inter-communication between different VOs. The scheduler doesn't control the clusters/resources directly. We can consider it closer to Grid applications and consider user requirements as optimization criteria.

Provide a set of generic keywords that define your contribution (e.g. Data Management, Workflows, High Energy Physics)

Grid scheduling, DAG scheduling, Task Dependencies, Workflow Applications, Optimization, Heuristics.

4. Conclusions / Future plans

The proposed algorithm provides improvements of critical path based on using a heuristic prediction. The impact of the algorithm is directly visible in integration with an existing grid meta-scheduler, DIOGENES used in national and international projects (MedioGRID, SEE-GRID). The future plans for extensions refer to co-allocation of resources in scheduling process for a set of tasks with dependencies, and to the prediction the Grid status for building an advance reservation mechanism.