Low-time complexity workflow application scheduling on heterogeneous systems

Jorge Barbosa, PhD | November 22, 2018 | 2 pm | E.2.69

A heterogeneous system can be defined as a range of different system resources, which can be local or geographically distributed, that are utilized to execute computationally intensive applications. The efficiency of executing parallel applications on heterogeneous systems critically depends on the methods used to define an assignment and mapping of the workflow tasks onto resources.

Scheduling in this context is mainly divided into two main approaches: single and multiple QoS parameters. On the single QoS parameter, the execution time of a workflow application, also called makespan, has been the major concern in most of the scheduling strategies. In this talk, it will be presented a novel algorithm for time optimization that implements a look-ahead feature while keeping a quadratic time complexity.

The problem becomes more challenging when two or more QoS parameters are considered in the scheduling problem. Time, cost, energy and reliability are common QoS parameters considered in recent research work in this area. Many algorithms consider time and cost in their formulation but most of them perform: (a) optimization of one parameter constrained to the other; (b) optimization of both parameters in a bi-objective formulation; and (c) a consideration of an unlimited number of resources, in particular for cloud platforms, where the strategy to accomplish time constraints is by allocating new computational instances.

In this talk two low-time complexity algorithms for QoS based scheduling, bounded to a set of resources, will be addressed. Namely, a time optimization and budget constrained scheduling and a budget-deadline constrained scheduling algorithm.

Research topics on resource management of heterogeneous systems will be discussed, namely, energy-aware scheduling, auto-tuning and concurrent scheduling.

Jorge Barbosa obtained his MSc degree from the University of Manchester Institute of Science and Technology, in 1993, and the PhD in Electrical and Computer Engineering from Faculdade de Engenharia da Universidade do Porto (FEUP), in 2001. He is Assistant Professor at the Department of Informatics Engineering at FEUP. He has (co-)authored over 60 scientific publications (including journal/conference papers and book chapters) on subjects related to parallel algorithms, resource management, energy-aware scheduling and performance modeling for heterogeneous systems. His current research interests are related to energy-aware scheduling, data locality, auto-parallelization tools and concurrent scheduling. He is member of the Editorial Board of Elsevier Journal „Simulation Modelling Practice and Theory“.

Posted in TEWI-Kolloquium | Leave a comment