We describe an approach that uses combinatorial optimization and machine learning to share the work between the host and device of heterogeneous computing systems such that the overall application execution time is minimized. We propose to use combinatorial optimization to search for the optimal system configuration in the given parameter space (such as, the number of threads, thread affinity, work distribution for the host and device). For each system configuration that is suggested by combinatorial optimization, we use machine learning for evaluation of the system performance. We evaluate our approach experimentally using a heterogeneous platform that comprises two 12-core Intel Xeon E5 CPUs and an Intel Xeon Phi 7120P co-processor with 61 cores. Using our approach we are able to find a near-optimal system configuration by performing only about 5 of all possible experiments.
A dynamic scheduling framework that divides tasks into smaller ones is proposed by Ravi and Agrawal @cite_19 . These task are distributed across different processing elements in a task-farm way. While making scheduling decisions, architectural trade-offs, computation and communication patterns are considered. Our approach considers only system runtime configuration and the input size that makes it a more general approach, which can be used with different applications and architecture.
@cite_19
2040466547 2401502609 2806513498 2162254032
Static scheduling of a program represented by a directed task graph on a multiprocessor system to minimize the program completion time is a well-known problem in parallel processing. Since finding an optimal schedule is an NP-complete problem in general, researchers have resorted to devising efficient heuristics. A plethora of heuristics have been proposed based on a wide spectrum of techniques, including branch-and-bound, integer-programming, searching, graph-theory, randomization, genetic algorithms, and evolutionary methods. The objective of this survey is to describe various scheduling algorithms and their functionalities in a contrasting fashion as well as examine their relative merits in terms of performance and time-complexity. Since these algorithms are based on diverse assumptions, they differ in their functionalities, and hence are difficult to describe in a unified context. We propose a taxonomy that classifies these algorithms into different categories. We consider 27 scheduling algorithms, with each algorithm explained through an easy-to-understand description followed by an illustrative example to demonstrate its operation. We also outline some of the novel and promising optimization approaches and current research trends in the area. Finally, we give an overview of the software tools that provide scheduling mapping functionalities. Scheduling is a crucial problem in parallel and distributed processing. It consists of determining where and when the tasks of parallel programs will be executed. The design of parallel algorithms has to be reconsidered by the influence of new execution supports (namely, clusters of workstations, grid computing and global computing) which are characterized by a larger number of heterogeneous processors, often organized by hierarchical sub-systems. Parallel Tasks model (tasks that require more than one processor for their execution) has been introduced about 15 years ago as a promising alternative for scheduling parallel applications, especially in the case of slow communication media. The basic idea is to consider the application at a rough level of granularity (larger tasks in order to decrease the relative weight of communications). As the main difficulty for scheduling in actual systems comes from handling efficiently the communications, this new view of the problem allows us to consider them implicitly, thus leading to more tractable problems. We kindly invite the reader to look at the chapter of Maciej Drozdowski (in this book) for a detailed presentation of various kinds of Parallel Tasks in a general context and the survey paper from Feitelsonsurvey for a discussion in the field of parallel processing. Even if the basic problem of scheduling Parallel Tasks remains NP-hard, some approximation algorithms can be designed. A lot of results have been derived recently for scheduling the different types of Parallel Tasks, namely, Rigid, Moldable or Malleable ones. We will distinguish Parallel Tasks inside the same application or between applications in a multi-user context. Various optimization criteria will be discussed. This chapter aims to present several approximation algorithms for scheduling moldable and malleable tasks with a special emphasis on new execution supports. In heterogeneous distributed environment, it is a great challenge to schedule multiple workflows submitted at different times. Particularly, scheduling of concurrent workflows with deadline and budget constraints makes the problem become more complex. Recent studies have proposed dynamic scheduling strategies for concurrent workflows which have limitations in inconsistent environments. Therefore, this paper presents a new dynamic scheduling algorithm for concurrent workflows. This algorithm proposes a uniform ranking that considers the time and costs for both workflows and workgroups to assign priorities for tasks. In the resource selection phase, it controls the resource selection range for each task based on an optimistic budget for the current task and selects resources for the current task according to a defined bi-factor. The experimental results show that our algorithm outperforms the existing algorithms in both consistent and inconsistent environments. Generally, a parallel application consists of precedence constrained stochastic tasks, where task processing times and intertask communication times are random variables following certain probability distributions. Scheduling such precedence constrained stochastic tasks with communication times on a heterogeneous cluster system with processors of different computing capabilities to minimize a parallel application’s expected completion time is an important but very difficult problem in parallel and distributed computing. In this paper, we present a model of scheduling stochastic parallel applications on heterogeneous cluster systems. We discuss stochastic scheduling attributes and methods to deal with various random variables in scheduling stochastic tasks. We prove that the expected makespan of scheduling stochastic tasks is greater than or equal to the makespan of scheduling deterministic tasks, where all processing times and communication times are replaced by their expected values. To solve the problem of scheduling precedence constrained stochastic tasks efficiently and effectively, we propose a stochastic dynamic level scheduling (SDLS) algorithm, which is based on stochastic bottom levels and stochastic dynamic levels. Our rigorous performance evaluation results clearly demonstrate that the proposed stochastic task scheduling algorithm significantly outperforms existing algorithms in terms of makespan, speedup, and makespan standard deviation.