Towards Efficient Bounds on Completion Time and Resource Provisioning for Scheduling Workflows on Heterogeneous Processing Systems

Towards Efficient Bounds on Completion Time and Resource Provisioning for Scheduling Workflows on Heterogeneous Processing Systems

D. Sirisha (Pragati Engineering College, Kakinada, India) and G. Vijayakumari (JNTU College of Engineering, JNTU, Hyderabad, India)
Copyright: © 2017 |Pages: 23
DOI: 10.4018/IJGHPC.2017070105


Compute intensive applications featured as workflows necessitate Heterogeneous Processing Systems (HPS) for attaining high performance to minimize the turnaround time. Efficient scheduling of the workflow tasks is paramount to attain higher potentials of HPS and is a challenging NP-Complete problem. In the present work, Branch and Bound (BnB) strategy is applied to optimally schedule the workflow tasks. The proposed bounds are tighter, simpler and less complex than the existing bounds and the upper bound is closer to the exact solution. Moreover, the bounds on the resource provisioning are devised to execute the workflows in the minimum possible time and optimally utilize the resources. The performance of the proposed BnB strategy is evaluated on a suite of benchmark workflows. The experimental results reveal that the proposed BnB strategy improved the optimal solutions compared to the existing heuristic scheduling algorithms for more than 20 percent of the cases and generated better schedules over 7 percent for 82.6 percent of the cases.
Article Preview

1. Introduction

Advanced compute-intensive applications such as genomics, oil and gas exploration, data analytics, modeling, simulations, and bioinformatics demand high performance for increasing the pace of computing. Such applications usually comprise of a set of tasks with precedence’s among them and are often featured as workflows. Heterogeneous Processing Systems (HPS) are gaining prominence as economically viable environments, rendering high performance to the computationally intensive applications. Such applications face challenges in dealing with highly heterogeneous platforms where the diversity extends to a broad range of resource configurations and their network connections. Efficient scheduling of the workflow tasks becomes imperative for harnessing high performance on HPS (Topcuoglu et al., 2002; Hamid Arabnejad et al., 2016; Xie et al., 2017). Scheduling defines the task execution order and maps each task to the best resource. Scheduling workflows on HPS is a great challenging NP-Complete problem and can only be solved when P = NP (Gary & Johnson, 1979). The holy grail of the researchers is to find a schedule that maximizes the concurrent executions of the tasks and reduces the overheads due to communication to maximize the potential speedup.

In the present work, Branch and Bound (BnB) strategy is employed for scheduling the workflows on HPS to attain globally optimal schedules. The BnB strategy examines all the potential cases of allocating each workflow task on all the resources of HPS; however, this leads to huge search space that can be minimized by effective bounds to arrive at an optimal solution in lesser time. The exponential complexity has confined the application of BnB strategy to small sized problems. However, the wide spread usage of HPS primarily for large scale problems incorporates BnB strategy to resolve its limitations (Kasahara & Narita, 1985).

The literature on BnB strategy reports that tighter bounds with effective pruning techniques aid in rapidly converging to the solutions. Motivated by this challenge, the proposed BnB strategy mainly focuses on these two aspects. The key contributions of the present work are:

  • The bounds on the completion time of the workflow are devised.

  • The proposed bounds are simple, tighter and less complex than the existing bounds.

  • The bounds on the minimal number of resources essential to execute the workflow.

The bounds provide an estimation of the best-case and worst-case completion time prior to the execution of the workflow. The estimation of the bounds must guarantee admissibility; such that the lower bound does not overestimate and the upper bound never underestimates the actual makespan of the workflow, i.e., the estimation of the bounds must be tight. Tighter bounds enable to identify inferior solutions so that they can be pruned subsequently. This alleviates the number of states in the search space to be examined and aids BnB strategy to converge to the solution quickly. Moreover, much gain in the performance can be realized if the intermediate states early in the search tree are pruned. The bounds on the resource provisioning are also proposed to determine the number of resources adequate to execute the workflow in the least possible time by exploring the inherent parallelism of the workflow such that the resources are optimally utilized.

The rest of the paper is configured as follows: in Section 2, the workflow scheduling problem on HPS is defined. In Sections 3 and 4, the generic BnB strategy and the related work are presented. The proposed BnB strategy is introduced in Section 5 while the experimental results are the discussed in Section 6. The outline of the proposed BnB strategy and future scope of the research are drawn in Section 7.

2. The Workflow Scheduling Problem

The scheduling of the workflows entails a workflow application, a HPS, and the criteria for scheduling.

Complete Article List

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