Implementation Of Grid Workflow Scheduling For Data Intensive Application

The Grid computing is a new technology. Grid implements distributed computing by assembling computational resources all over the world, to support scientific computing and provide other services. With the rapid development of the grid computing technology, the focus of research efforts has begun to transform from the implementation of infrastructure to the resolution of real scientific problems.Recently, high-performance data-intensive computing and networking technology has become a vital part of large-scale scientific research projects in areas such as high energy physics, astronomy, space exploration, human genome projects, and computational simulations in biomedical research. And users often need to connect the input and output of several applications into a workflow, so the grid workflow support and large-scale distributed data management are becoming two main requirements of scientists and researchers.In this paper, we integrate the workflow technology and the data grid technology and proposed a grid workflow scheduling for data intensive applications. This solution optimizes the time cost and space cost. We implement this solution using scheduling plug-ins in meta-scheduler CSF4 and ensure the two scheduling plug-ins work together smoothly.CSF4 is a meta-scheduler in the grid environment which implement a plug-in mechanism. The CSF4 plug-in mechanism consists of the scheduler framework and a number of scheduler plug-in modules. The scheduler framework works as a main-board with slots to hold scheduler plug-in modules. The framework maintains the elementary information for a scheduler, like pending jobs, available resources etc. Plug-in modules are able to access those data maintained by scheduler framework via CSF plug-in API. The particular scheduling policies are implemented inside plug-in modules.The plug-in modules are loaded dynamically by the framework at run time. The user can indicate which modules to be loaded via configuration. Using this mechanism, the users do not need to write a scheduler from scratch, but to provide just a plug-in module with the desired policy. Moreover, CSF4 plug-in mechanism supports the cooperation of multiple scheduling policies.Any grid workflow can be described as a directed acyclic graph (DAG).The nodes of the graph represent a sub job to be performed and the directed edges represent dependencies between jobs. We use a subset of XPDL(XML Process Definition Language)to describe grid workflow jobs.The following tags are used to describe a workflow task by our workflow engine. There is one tag for each workflow task. is the root tag for the task. There could be one or more tags inside tag to represent the sub workflows of the task. tag will indicate all the sub jobs that will be really executed in a grid for a sub-workflow. presents the dependencies among the sub jobs. In addition, we extended XPDL to support RSL by add a tag. RSL is the standard language to specify a grid job's resource requirements, to describe the sub tasks.The workflow plug-in is made up of two components: workflow engine and schedule algorithm.When you submit a workflow job, you need to submit a workflow description file. The workflow engine parse the description file, and transform the abstract jobs to the real jobs dynamically. We use dynamic parse, it will reduce the scheduler's memory cost and improve its scheduling performance at same time.The workflow plug-in implement the schedPlug class, which has four interface: schedInit, schedOrder, schedMatch, schedPost. schedOrder can order the sub-jobs by call the workflow engine's API. schedMatch can mapping the job to a resource, and make decision.The schedule algorithm as follows:At the very beginning, the algorithm will do the below operations:1. Insert all jobs whose predecessor job sets are NULL to New Ready Job List;2. Sort New Ready Job List in descending order based on N_DJS() value;3. Copy New Ready Job List to Ready Job List;4. Generate real jobs with RSL description for New Ready Job List;5. Insert new generated real jobs to the meta-scheduler's waiting job queue;6. Sort all the real jobs in the same order as Ready Job List; During the workflow running, the algorithm will do as below, While (not done) { Once a sub job finish {Set New Ready Job List to this job's successor job set; Remove non-ready jobs from New Ready Job List; If (New Ready Job List is not null) { Sort New Ready Job List in descending order based on N_DJS() value; Insert New Ready Job List to the head of Ready Job List; If(New Ready Job's value less than previous Job's value){ Adjust the location of the new Job; } Generate real jobs for New Ready Job List; Insert new generated real jobs to the meta-scheduler's waiting job queue; Sort all the real jobs in the same order as Ready Job List; } } Once a sub job start to run { Remove the sub job from Ready Job List; } }The algorithm has two main features. First, the sub jobs are dispatched in a combination of least makespan time and depth-first order. The sub jobs with higher N_DJS() value will have more chance to run earlier. And the new generated real jobs are inserted to head of the Read Job List. Second, the real jobs are generated for the ready jobs only. Hence, the real jobs are inserted to the scheduler job queue gradually instead of all at once. It will reduce the scheduler's memory cost and improve its scheduling performance at same time.We improve the data aware plug-in, so the data aware plug-in can work together smooth with the workflow plug-in. If a sub-job need to access a file in the GFarm file system, the data aware plug-in can identify it, and improve its schedule decision. So the job will be dispatched to the cluster own the file. It can reduce the waiting time and relax the network load.In this paper, we proposed a grid workflow schedule schema, which integrate the workflow technology and the data grid technology. This solution optimizes the schedule for data intensive workflow. This schema was implemented in multi-module. It is very easy to reuse those modules or compose with other module to implement a new schedule policy.In the future, we will research the resource advance reservation mechanism. By this mechanism, we can reduce the subjob's waiting time in the cluster's job queue, so it can reduce the makespan time of the whole workflow job.