Linear Programming-Based Affinity Scheduling of Independent Tasks on Heterogeneous Computing Systems

Resource management systems (RMS) are an important component in heterogeneous computing (HC) systems. One of the jobs of an RMS is the mapping of arriving tasks onto the machines of the HC system. Many different mapping heuristics have been proposed in recent years. However, most of these heuristics suffer from several limitations. One of these limitations is the performance degradation that results from using outdated global information about the status of all machines in the HC system. This paper proposes several heuristics which address this limitation by only requiring partial information in making the mapping decisions. These heuristics utilize the solution to a linear programming (LP) problem which maximizes the system capacity. Simulation results show that our heuristics perform very competitively while requiring dramatically less information.     

Characterization of the iterative application of makespan heuristics on non-makespan machines in a heterogeneous parallel and distributed environment

Heterogeneous computing (HC) is the coordinated use of different types of machines, and networks to process a diverse workload in a manner that will maximize the combined performance and/or cost effectiveness of the system. Heuristics for allocating resources in an HC system are based on some optimization criterion. A common optimization criterion is to minimize the completion time of the machine that finishes last (makespan). In this study, we consider an iterative approach that repeatedly runs a mapping heuristic to minimize the makespan of the considered machines and tasks. For each successive iteration, the makespan machine of the previous iteration and the tasks assigned to it are removed from the set of considered machines and tasks. This study focuses on understanding the different mathematical characteristics of resource allocation heuristics that cause them to behave differently when combined with this iterative approach. This paper has three main contributions. The first contribution is the study of an iterative technique used in conjunction with resource allocation heuristics. The second contribution is the definition and mathematical characterization of “iteration invariant” heuristics. The third contribution is to determine the characteristics of a heuristic that will cause the mapping to change across iterations.     

Dynamic Mapping of a Class of Independent Tasks onto Heterogeneous Computing Systems

Dynamic mapping (matching and scheduling) heuristics for a class of independent tasks using heterogeneous distributed computing systems are studied. Two types of mapping heuristics are considered, immediate mode and batch mode heuristics. Three new heuristics, one for batch mode and two for immediate mode, are introduced as part of this research. Simulation studies are performed to compare these heuristics with some existing ones. In total five immediate mode heuristics and three batch mode heuristics are examined. The immediate mode dynamic heuristics consider, to varying degrees and in different ways, task affinity for different machines and machine ready times. The batch mode dynamic heuristics consider these factors, as well as aging of tasks waiting to execute. The simulation results reveal that the choice of which dynamic mapping heuristic to use in a given heterogeneous environment depends on parameters such as (a) the structure of the heterogeneity among tasks and machines and (b) the arrival rate of the tasks.     

Static resource allocation for heterogeneous computing environments with tasks having dependencies,priorities, deadlines,and multiple versions

Heterogeneous computing (HC) environments composed of interconnected machines with varied computational capabilities are well suited to meet the computational demands of large, diverse groups of tasks. One aspect of resource allocation in HC environments is matching tasks with machines and scheduling task execution on the assigned machines. We will refer to this matching and scheduling process as mapping. The problem of mapping these tasks onto the machines of a distributed HC environment has been shown, in general, to be NP-complete. Therefore, the development of heuristic techniques to find near-optimal solutions is required. In the HC environment investigated, tasks have deadlines, priorities, multiple versions, and may be composed of communicating subtasks. The best static (off-line) techniques from some previous studies are adapted and applied to this mapping problem: a genetic algorithm (GA), a GENITOR-style algorithm, and a two phase greedy technique based on the concept of Min–min heuristics. Simulation studies compare the performance of these heuristics in several overloaded scenarios, i.e., not all tasks can be executed by their deadlines. The performance measure used is the sum of weighted priorities of tasks that completed before their deadline, adjusted based on the version of the task used. It is shown that for the cases studied here, the GENITOR technique finds the best results, but the faster two phase greedy approach also performs very well.     

A Comparison of Eleven Static Heuristics for Mapping a Class of Independent Tasks onto Heterogeneous Distributed Computing Systems

Mixed-machine heterogeneous computing (HC) environments utilize a distributed suite of different high-performance machines, interconnected with high-speed links, to perform different computationally intensive applications that have diverse computational requirements. HC environments are well suited to meet the computational demands of large, diverse groups of tasks. The problem of optimally mapping (defined as matching and scheduling) these tasks onto the machines of a distributed HC environment has been shown, in general, to be NP-complete, requiring the development of heuristic techniques. Selecting the best heuristic to use in a given environment, however, remains a difficult problem, because comparisons are often clouded by different underlying assumptions in the original study of each heuristic. Therefore, a collection of 11 heuristics from the literature has been selected, adapted, implemented, and analyzed under one set of common assumptions. It is assumed that the heuristics derive a mapping statically (i.e., off-line). It is also assumed that a metatask (i.e., a set of independent, noncommunicating tasks) is being mapped and that the goal is to minimize the total execution time of the metatask. The 11 heuristics examined are Opportunistic Load Balancing, Minimum Execution Time, Minimum Completion Time, Min–min, Max–min, Duplex, Genetic Algorithm, Simulated Annealing, Genetic Simulated Annealing, Tabu, and A*. This study provides one even basis for comparison and insights into circumstances where one technique will out-perform another. The evaluation procedure is specified, the heuristics are defined, and then comparison results are discussed. It is shown that for the cases studied here, the relatively simple Min–min heuristic performs well in comparison to the other techniques.     

A revisit of fast greedy heuristics for mapping a class of independent tasks onto heterogeneous computing systems

Mixed-machine heterogeneous computing (HC) environments utilize a distributed suite of different high-performance machines, interconnected with high-speed links, to perform groups of computing-intensive applications that have diverse computational requirements and constraints. The problem of optimally mapping a class of independent tasks onto the machines of an HC environment has been proved, in general, to be NP-complete, thus requiring the development of heuristic techniques for practical usage. If the mapping has real-time requirements such that the mapping process is performed during task execution, fast greedy heuristics must be adopted. This paper investigates fast greedy heuristics for this problem and identifies the importance of the concept of task consistency in designing this mapping heuristic. We further propose task priority graph based fast greedy heuristics, which consider the factors of both task consistency and machine consistency (the same concept of consistency as in previous studies). A collection of 20 greedy heuristics, including 17 newly proposed ones, are implemented, analyzed, and systematically compared within a uniform model of task execution time. This model is implemented by the coefficient-of-variation based method. The experimental results illuminate the circumstances when a specific greedy heuristic would outperform the other 19 greedy heuristics.     

Robust static allocation of resources for independent tasks under makespan and dollar cost constraints

Heterogeneous computing (HC) systems composed of interconnected machines with varied computational capabilities often operate in environments where there may be inaccuracies in the estimation of task execution times. Makespan (defined as the completion time for an entire set of tasks) is often the performance feature that needs to be optimized in such systems. Resource allocation is typically performed based on estimates of the computation time of each task on each class of machines. Hence, it is important that makespan be robust against errors in computation time estimates. In this research, the problem of finding a static mapping of tasks to maximize the robustness of makespan against the errors in task execution time estimates given an overall makespan constraint is studied. Two variations of this basic problem are considered: (1) where there is a given, fixed set of machines, (2) where an HC system is to be constructed from a set of machines within a dollar cost constraint. Six heuristic techniques for each of these variations of the problem are presented and evaluated.     

Scalable,low complexity,and fast greedy scheduling heuristics for highly heterogeneous distributed computing systems

For heterogeneous distributed computing systems, important design issues are scalability and system optimization. Given such systems, it is crucial to develop low computational complexity algorithms to schedule tasks in a manner that exploits the heterogeneity of the resources and applications. In this paper, we report and evaluate three scalable, and fast scheduling heuristics for highly heterogeneous distributed computing systems. We conduct a comprehensive performance evaluation study using simulation. The benchmarking outlines the performance of the schedulers, representing scalability, makespan, flowtime, computational complexity, and memory utilization. The set of experimental results shows that our heuristics perform as good as the traditional approaches, for makespan and flowtime, while featuring lower complexity, lower running time, and lower used memory. The experimental results also detail the various scenarios under which certain algorithms excel and fail.     

A static mapping heuristics to map parallel applications to heterogeneous computing systems

In order to minimize the execution time of a parallel application running on a heterogeneously distributed computing system, an appropriate mapping scheme is needed to allocate the application tasks to the processors. The general problem of mapping tasks to machines is a well‐known NP‐hard problem and several heuristics have been proposed to approximate its optimal solution. In this paper we propose a static graph‐based mapping algorithm, called Heterogeneous Multi‐phase Mapping (HMM), which permits suboptimal mapping of a parallel application onto a heterogeneous computing distributed system by using a local search technique together with a tabu search meta‐heuristic. HMM allocates parallel tasks by exploiting the information embedded in the parallelism forms used to implement an application, and considering an affinity parameter, that identifies which machine in the heterogeneous computing system is most suitable to execute a task. We compare HMM with some leading techniques and with an exhaustive mapping algorithm. We also give an example of mapping of two real applications using HMM. Experimental results show that HMM performs well demonstrating the applicability of our approach. Copyright © 2005 John Wiley & Sons, Ltd.     

Dynamically mapping tasks with priorities and multiple deadlines in a heterogeneous environment

In a distributed heterogeneous computing system, the resources have different capabilities and tasks have different requirements. To maximize the performance of the system, it is essential to assign the resources to tasks (match) and order the execution of tasks on each resource (schedule) to exploit the heterogeneity of the resources and tasks. Dynamic mapping (defined as matching and scheduling) is performed when the arrival of tasks is not known a priori. In the heterogeneous environment considered in this study, tasks arrive randomly, tasks are independent (i.e., no inter-task communication), and tasks have priorities and multiple soft deadlines. The value of a task is calculated based on the priority of the task and the completion time of the task with respect to its deadlines. The goal of a dynamic mapping heuristic in this research is to maximize the value accrued of completed tasks in a given interval of time. This research proposes, evaluates, and compares eight dynamic mapping heuristics. Two static mapping schemes (all arrival information of tasks are known) are designed also for comparison. The performance of the best heuristics is 84% of a calculated upper bound for the scenarios considered.     

Dynamic Resource Management in Energy Constrained Heterogeneous Computing Systems Using Voltage Scaling

An ad hoc grid is a wireless heterogeneous computing environment without a fixed infrastructure. This study considers wireless devices that have different capabilities, have limited battery capacity, support dynamic voltage scaling, and are expected to be used for eight hours at a time and then recharged. To maximize the performance of the system, it is essential to assign resources to tasks (match) and order the execution of tasks on each resource (schedule) in a manner that exploits the heterogeneity of the resources and tasks while considering the energy constraints of the devices. In the single-hop ad hoc grid heterogeneous environment considered in this study, tasks arrive unpredictably, are independent (i.e., no precedent constraints for tasks), and have priorities and deadlines. The problem is to map (match and schedule) tasks onto devices such that the number of highest priority tasks completed by their deadlines during eight hours is maximized while efficiently utilizing the overall system energy. A model for dynamically mapping tasks onto wireless devices is introduced. Seven dynamic mapping heuristics for this environment are designed and compared to each other and to a mathematical bound.     

Heterogeneous Computing and Parallel Genetic Algorithms

This paper analyzes some technical and practical issues concerning the heterogeneous execution of parallel genetic algorithms (PGAs). In order to cope with a plethora of different operating systems, security restrictions, and other problems associated to multi-platform execution, we use Java to implement a distributed PGA model. The distributed PGA runs at the same time on different machines linked by different kinds of communication networks. This algorithm benefits from the computational resources offered by modern LANs and by Internet, therefore allowing researchers to solve more difficult problems by using a large set of available machines. We analyze the way in which such heterogeneous systems affect the genetic search for two problems. Our conclusion is that super-linear performance can be achieved not only in homogeneous but also in heterogeneous clusters of machines. In addition, we study some special features of the running platforms for PGAs, and basically find out that heterogeneous computing can be as efficient or even more efficient than homogeneous computing for parallel heuristics.     

元计算系统的批模式启发式任务调度算法研究

元计算系统是通过网络连接的地理上分散的主机、数据库和文件等资源。使用这些资源、可以运行用户的应用程序。研究元计算环境下的批模式启发式任务调度算法,论述Wade系统的应用任务的调度模型,比较4种调度算法的性能。     

A stochastic model for heterogeneous computing and its applicationin data relocation scheme development

In a dedicated, mixed-machine, heterogeneous computing (HC) system, an application program may be decomposed into subtasks, then each subtask assigned to the machine where it is best suited for execution. Data relocation is defined as selecting the sources for needed data items. It is assumed that multiple independent subtasks of an application program can be executed concurrently on different machines whenever possible. A theoretical stochastic model for HC Is proposed, in which the computation times of subtasks and communication times for intermachine data transfers can be random variables. The optimization problem for finding the optimal matching, scheduling, and data relocation schemes to minimize the total execution time of an application program is defined based on this stochastic HC model. The global optimization criterion and search space for the above optimization problem are described. It is validated that a greedy algorithm-based approach can establish a local optimization criterion for developing data relocation heuristics. The validation is provided by a theoretical proof based on a set of common assumptions about the underlying HC system and application program. The local optimization criterion established by the greedy approach, coupled with the search space defined for choosing valid data relocation schemes, can help developers of future practical data relocation heuristics     

Robust static resource allocation of DAGs in a heterogeneous multicore system

In this study, we consider an environment composed of a heterogeneous cluster of multicore-based machines used to analyze satellite data. The workload involves large data sets and is subject to a deadline constraint. Multiple applications, each represented by a directed acyclic graph (DAG), are allocated to a dedicated heterogeneous distributed computing system. Each vertex in the DAG represents a task that needs to be executed and task execution times vary substantially across machines. The goal of this research is to assign the tasks in applications to a heterogeneous multicore-based parallel system in such a way that all applications complete before a common deadline, and their completion times are robust against uncertainties in execution times. We define a measure that quantifies robustness in this environment. We design, compare, and evaluate five static resource allocation heuristics that attempt to maximize robustness. We consider six different scenarios with different ratios of computation versus communication, and loose and tight deadlines.     

一种基于虚拟截止时间制导的改进的Min—Min元任务调度算法

在网格环境下，资源状况和用户行为相当复杂，是一个异构计算环境，元任务（meta—task）调度比传统并行调度更为复杂。如何映射一组任务到一组机器上被证明是NP问题，其目的一般是最小化任务完成时间（makespan）。为解决这一问题，已经提出一些启发式任务调度算法，例如具有代表性的MinMin元任务调度算法。本文在Min-Min元任务调度算法的基础上，通过虚拟截止时间制导的方法来改进Min-Min算法。实验结果表明，本文提出的算法具有更短的任务完成时间。     

Energy- and reliability-aware task scheduling onto heterogeneous MPSoC architectures

Scheduling periodic tasks onto a multiprocessor architecture under several constraints such as performance, cost, energy, and reliability is a major challenge in embedded systems. In this paper, we present an Integer Linear Programming (ILP) based framework that maps a given task set onto an Heterogeneous Multiprocessor System-on-Chip (HMPSoC) architecture. Our framework can be used with several objective functions; minimizing energy consumption, minimizing cost (i.e., the number of heterogeneous processors), and maximizing reliability of the system under performance constraints. We use Dynamic Voltage Scaling (DVS) for reducing energy consumption while we employ task duplication to maximize reliability. We illustrate the effectiveness of our approach through several experiments, each with a different number of tasks to be scheduled. We also propose two heuristics based on Earliest Deadline First (EDF) algorithm for minimizing energy under performance and cost constraints. Our experiments on generated task sets show that ILP-based method reduces the energy consumption up to 62% percent against a method that does not apply DVS. Heuristic methods obtain promising results when compared to optimal results generated by our ILP-based method.     

Analysis and Optimisation of Hierarchically Scheduled Multiprocessor Embedded Systems

We present an approach to the analysis and optimisation of heterogeneous multiprocessor embedded systems. The systems are heterogeneous not only in terms of hardware components, but also in terms of communication protocols and scheduling policies. When several scheduling policies share a resource, they are organised in a hierarchy. In this paper, we first develop a holistic scheduling and schedulability analysis that determines the timing properties of a hierarchically scheduled system. Second, we address design problems that are characteristic to such hierarchically scheduled systems: assignment of scheduling policies to tasks, mapping of tasks to hardware components, and the scheduling of the activities. We also present several algorithms for solving these problems. Our heuristics are able to find schedulable implementations under limited resources, achieving an efficient utilisation of the system. The developed algorithms are evaluated using extensive experiments and a real-life example.     

Dynamic task mapping for Network-on-Chip based systems

Efficiency of Network-on-Chip (NoC) based multi-processor systems largely depends on optimal placement of tasks onto processing elements (PEs). Although number of task mapping heuristics have been proposed in literature, selecting best technique for a given environment remains a challenging problem. Keeping in view the fact that comparisons in original study of each heuristic may have been conducted using different assumptions, environment, and models. In this study, we have conducted a detailed quantitative analysis of selected dynamic task mapping heuristics under same set of assumptions, similar environment, and system models. Comparisons are conducted with varying network load, number of tasks, and network size for constantly running applications. Moreover, we propose an extension to communication-aware packing based nearest neighbor (CPNN) algorithm that attempts to reduce communication overhead among the interdependent tasks. Furthermore, we have conducted formal verification and modeling of proposed technique using high level Petri nets. The experimental results indicate that proposed mapping algorithm reduces communication cost, average hop count, and end-to-end latency as compared to CPNN especially for large mesh NoCs. Moreover, proposed scheme achieves up to 6% energy savings for smaller mesh NoCs. Further, results of formal modeling indicate that proposed model is workable and operates according to specifications.     

Mapping workflow applications with types on heterogeneous specialized platforms

In this paper, we study the problem of optimizing the throughput of coarse-grain workflow applications, for which each task of the workflow is of a given type, and subject to failures. The goal is to map such an application onto a heterogeneous specialized platform, which consists of a set of processors that can be specialized to process one type of tasks. The objective function is to maximize the throughput of the workflow, i.e., the rate at which the data sets can enter the system. If there is exactly one task per processor in the mapping, then we prove that the optimal solution can be computed in polynomial time. However, the problem becomes NP-hard if several tasks can be assigned to the same processor. Several polynomial time heuristics are presented for the most realistic specialized setting, in which tasks of the same type can be mapped onto the same processor, but a processor cannot process two tasks of different types. Also, we give an integer linear program formulation of this problem, which allows us to find the optimal solution (in exponential time) for small problem instances. Experimental results show that the best heuristics obtain a good throughput, much better than the throughput obtained with a random mapping. Moreover, we obtain a throughput close to the optimal solution in the particular cases on which the optimal throughput can be computed (small problem instances or particular mappings).