A GPU Based Approach for Solving the Workflow Scheduling Problem

A GPU Based Approach for Solving the Workflow Scheduling Problem

Mohammed Benhammouda (EEDIS Laboratory, Djillali Liabes University at Sidi Bel Abbes, Sidi Bel Abbès, Algeria) and Mimoun Malki (LabRI-SBA Laboratory, Ecole Supérieure en Informatique de Sidi Bel Abbes, Sidi Bel Abbès, Algeria)
Copyright: © 2019 |Pages: 12
DOI: 10.4018/IJIRR.2019100101

Abstract

Cloud computing is considered a new way to use on-demand computing resources. When executing a workflow process in such an environment, task scheduling, a well-known NP-hard problem is a very important step. Many heuristic algorithms have been proposed to solve this problem. In this article, the authors present a GPU-based approach for solving the workflow scheduling problem. The main idea of the approach is to implement a massively parallel version of the simulated annealing algorithm, in an asynchronous way where no information is exchanged among parallel runs. The proposed approach, called PSA algorithm, is against another well-established scheduling HEFT heuristic. Experiments with randomly generated graphs show a much better performance from the proposed approach.
Article Preview
Top

2. Scheduling Problem Modeling

Task scheduling problem is one of the most important steps when using cloud computing environment capabilities to execute a workflow. A workflow can be represented by a Directed Acyclic Graph (DAG), G = (V, E), as shown in Figure 1, where V is the set v nodes, vi in V represents a workflow task, which contains a known number of instructions that must be executed on the same processor. E represents the set of communication edges between tasks; each edge e(i, j) ∈ E represents the task-dependency constraint which means that task ni should be executed before task nj can be started. A computation cost matrix W matrix complements the DAG, this matrix is a v × p, where v is the number of tasks and p is the number of processors. wij gives the estimated time to execute task vi on machine pj. Each edge e(i, j) ∈ E is associated with a nonnegative weight cij representing the communication cost between the tasks vi and vj (Topcuoglu et al., 2002).

In a given task graph, a task without any parent is called an entry task and a task without any child is called an exit task. A task graph may have more than one entry task and more than one exit task.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 10: 4 Issues (2020): 1 Released, 3 Forthcoming
Volume 9: 4 Issues (2019)
Volume 8: 4 Issues (2018)
Volume 7: 4 Issues (2017)
Volume 6: 4 Issues (2016)
Volume 5: 4 Issues (2015)
Volume 4: 4 Issues (2014)
Volume 3: 4 Issues (2013)
Volume 2: 4 Issues (2012)
Volume 1: 4 Issues (2011)
View Complete Journal Contents Listing