Performance‐based parallel loop self‐scheduling using hybrid OpenMP and MPI programming on multicore SMP clusters

Parallel loop self‐scheduling on parallel and distributed systems has been a critical problem and it is becoming more difficult to deal with in the emerging heterogeneous cluster computing environments. In the past, some self‐scheduling schemes have been proposed as applicable to heterogeneous cluster computing environments. In recent years, multicore computers have been widely included in cluster systems. However, previous researches into parallel loop self‐scheduling did not consider certain aspects of multicore computers; for example, it is more appropriate for shared‐memory multiprocessors to adopt Open Multi‐Processing (OpenMP) for parallel programming. In this paper, we propose a performance‐based approach using hybrid OpenMP and MPI parallel programming, which partition loop iterations according to the performance weighting of multicore nodes in a cluster. Because iterations assigned to one MPI process are processed in parallel by OpenMP threads run by the processor cores in the same computational node, the number of loop iterations allocated to one computational node at each scheduling step depends on the number of processor cores in that node. Experimental results show that the proposed approach performs better than previous schemes. Copyright © 2010 John Wiley & Sons, Ltd.     

网络集群计算系统中的并行任务调度

基于多处理机并行任务调度模型，探讨网络集群计算系统中的并行任务调度问题，首先证明了一般网络集群计算系统中调度算法的可近似性难度，然后提出了三种不同的启发式算法：最大长度优先调度算法、最大宽度优先调度算法和最大面积优先调度算法；然后根据大量的模拟实验对这些算法以及文献中已提出的调度算法进行了比较分析，结果表明该文的启发式算法比文献中的算法在性能上效果更好。     

异构系统功耗感知的并行循环调度方法

以类OpenMP的并行程序为研究对象,在满足性能约束的条件下,结合异构系统并行循环调度和处理器动态电压调节技术优化系统功耗.首先建立了异构系统功耗感知的并行循环调度问题基本模型;然后,通过分析方法给出异构系统并行循环调度的能耗下界,该下界可用于评估功耗优化方法的实际效率;进而将异构系统并行循环调度问题归纳为整数规划问题,在此基础上,提出了处理器内循环再调度方法进一步降低功耗.最后,以CPU-GPU异构系统为平台评测了10个典型kernel程序.实验结果表明,该方法可以有效降低系统功耗,提高系统效能.     

Distributed loop‐scheduling schemes for heterogeneous computer systems

Distributed computing systems are a viable and less expensive alternative to parallel computers. However, a serious difficulty in concurrent programming of a distributed system is how to deal with scheduling and load balancing of such a system which may consist of heterogeneous computers. Some distributed scheduling schemes suitable for parallel loops with independent iterations on heterogeneous computer clusters have been designed in the past. In this work we study self‐scheduling schemes for parallel loops with independent iterations which have been applied to multiprocessor systems in the past. We extend one important scheme of this type to a distributed version suitable for heterogeneous distributed systems. We implement our new scheme on a network of computers and make performance comparisons with other existing schemes. Copyright © 2005 John Wiley & Sons, Ltd.     

Loop Staggering,Loop Compacting:Restructuring Techniques for Thrashing Problem

Parallel loops account for the greatest amount of parallelism in numerical programs.Executing nested loops in parallel wit low run-time overhead is thus very important for achieving high performance in paralleo processing systems.However,in parallel processing systems with caches of local memories in memory hierarchies,“thrashing problemmay” may arise when data move back and forth frequently between the caches or local memories in different processors.The techniques associated with parallel compiler to solve the problem are not completely developed.In this paper,we present two restructuring techniques called loopg staggering,loop staggering and compacting,with which we can not only eliminate the cache or local memory thrashing phemomena significantly,but also exploit the potential parallelism existing in outer serial loop.Loop staggering benefits the dynamic loop scheduling strategies,whereas loop staggering and compacting is good for static loop scheduling strategies,Our method especially benefits parallel programs,in which a parallel loop is enclosed by a serial loop and array elements are repeatedly used in the different iterations of the parallel loop.     

网络并行计算系统中基于多处理机任务的资源调度模型

简要描述了网络并行计算系统中任务调度问题和经典的多处理机任务调度研究现状,并将两者结合到一起建立网络并行计算系统中的新型调度模型,较详细地论述了多处理机任务的定义,然后还讨论了该模型求解的近似调度策略及其近似优化问题,给出了其特例Pm｜fix｜Cmax问题的最优调度的时间跨度下界。     

A parallel bi-objective hybrid metaheuristic for energy-aware scheduling for cloud computing systems

In this paper, we investigate the problem of scheduling precedence-constrained parallel applications on heterogeneous computing systems (HCSs) like cloud computing infrastructures. This kind of application was studied and used in many research works. Most of these works propose algorithms to minimize the completion time (makespan) without paying much attention to energy consumption.We propose a new parallel bi-objective hybrid genetic algorithm that takes into account, not only makespan, but also energy consumption. We particularly focus on the island parallel model and the multi-start parallel model. Our new method is based on dynamic voltage scaling (DVS) to minimize energy consumption.In terms of energy consumption, the obtained results show that our approach outperforms previous scheduling methods by a significant margin. In terms of completion time, the obtained schedules are also shorter than those of other algorithms. Furthermore, our study demonstrates the potential of DVS.     

Static Scheduling of Conditional Branches in Parallel Programs

The problem of scheduling non-deterministic graphs arises in several situations in scheduling parallel programs, particularly in the cases of loops and conditional branching. When scheduling loops in a parallel program, non-determinism arises because the number of loop iterations may not be known before the execution of the program. However, since loops from a restricted class of conditional branching, there is a higher degree of non-determinism associated with scheduling conditional branching. In this case, the direction of every branch remains unknown before run time. It follows that entire subprograms of the parallel program may or may not get executed, which in turn increases the amount of non-determinism and complicates the scheduling process. Thus, the term non-determinism is frequently associated with conditional branching in the literature. In this paper, we study the problem of constructing a static schedule for task graphs that contain conditional branching on parallel computers. Generally, it is difficult to obtain optimal solutions for solving various scheduling problems, even in the deterministic case. When non-determinism is added to the scheduling problem through conditional branching, an optimal solution will be even harder to obtain. We start the paper with a brief discussion of the scheduling problem, then we introduce a model for representing parallel programs that contain branches. We present a two-step scheduling technique which employs two different approaches: a graph theoretic appraoch and a multi-phase approach. The first approach is based on exploring several graph theoretic properties of the model. This approach is used as a preprocessing step to decrease the amount of non-determinism before applying the multi-phase approach. In the second step, several execution instances of the program are generated, a schedule for every instance is obtained, and a unified schedule is constructed by merging the obtained schedules. Finally, we report the results of the experiments that we conducted to measure the performance of the techniques introduced in this paper.     

基于GSPN和人工免疫算法的并行测试任务调度研究

针对ATS中并行测试任务调度复杂、难以优化的问题,提出了一种广义随机Petri网和人工免疫算法相结合的任务调度优化算法.首先对并行测试系统建立广义随机Petri网(GSPN)模型,然后将激发的变迁序列集作为并行测试任务调度路径;将免疫克隆选择算法(ICSA)应用到并行测试系统任务调度问题中,并提出一种自适应克隆选择算子,搜索最优任务调度路径,得到以测试时间最短为目标的最优任务调度方案.用某型雷达接收机并行测试系统对该算法进行仿真验证,结果表明,与改进的混合遗传算法(IHGA)相比,该算法能够便捷地得到任务调度最优序列,且测试效率更高.     

Competitive online adaptive scheduling for sets of parallel jobs with fairness and efficiency

We study online adaptive scheduling for multiple sets of parallel jobs, where each set may contain one or more jobs with time-varying parallelism. This two-level scheduling scenario arises naturally when multiple parallel applications are submitted by different users or user groups in large parallel systems, where both user-level fairness and system-wide efficiency are of important concerns. To achieve fairness, we use the well-known equi-partitioning algorithm to distribute the available processors among the active job sets at any time. For efficiency, we apply a feedback-driven adaptive scheduler that periodically adjusts the processor allocations within each set by consciously exploiting the jobs’ execution history. We show that our algorithm achieves asymptotically competitive performance with respect to the set response time, which incorporates two widely used performance metrics, namely, total response time and makespan, as special cases. Both theoretical analysis and simulation results demonstrate that our algorithm improves upon an existing scheduler that provides only fairness but lacks efficiency. Furthermore, we provide a generalized framework for analyzing a family of scheduling algorithms based on feedback-driven policies with provable efficiency. Finally, we consider an extended multi-level hierarchical scheduling model and present a fair and efficient solution that effectively reduces the problem to the two-level model.     

Quasi-static scheduling of communicating tasks

Good scheduling policies for distributed embedded applications are required for meeting hard real time constraints and for optimizing the use of computational resources. We study the quasi-static scheduling problem in which (uncontrollable) control flow branchings can influence scheduling decisions at run time. Our abstracted distributed task model consists of a network of sequential processes that communicate via point-to-point buffers. In each round, the task gets activated by a request from the environment. When the task has finished computing the required responses, it reaches a pre-determined configuration and is ready to receive a new request from the environment. For such systems, we prove that determining the existence of a scheduling policy that guarantees upper bounds on buffer capacities is undecidable. However, we show that the problem is decidable for the important subclass of “data-branching” systems in which control flow branchings are exclusively due to data-dependent internal choices made by the sequential components. This decidability result exploits ideas derived from the Karp and Miller coverability tree for Petri nets as well as the existential boundedness notion of languages of message sequence charts.     

Designing parallel loop self-scheduling schemes using the hybrid MPI and OpenMP programming model for?multi-core grid systems

Loop scheduling on parallel and distributed systems has been thoroughly investigated in the past. However, none of these studies considered the multi-core architecture feature for emerging grid systems. Although there have been many studies proposed to employ the hybrid MPI and OpenMP programming model to exploit different levels of parallelism for a distributed system with multi-core computers, none of them were aimed at parallel loop self-scheduling. Therefore, this paper investigates how to employ the hybrid MPI and OpenMP model to design a parallel loop self-scheduling scheme adapted to the multi-core architecture for emerging grid systems. Three different featured applications are implemented and evaluated to demonstrate the effectiveness of the proposed scheduling approach. The experimental results show that the proposed approach outperforms the previous work for the three applications and the speedups range from 1.13 to 1.75.     

Multi-objective energy-efficient workflow scheduling using list-based heuristics

Workflow applications are a popular paradigm used by scientists for modelling applications to be run on heterogeneous high-performance parallel and distributed computing systems. Today, the increase in the number and heterogeneity of multi-core parallel systems facilitates the access to high-performance computing to almost every scientist, yet entailing additional challenges to be addressed. One of the critical problems today is the power required for operating these systems for both environmental and financial reasons. To decrease the energy consumption in heterogeneous systems, different methods such as energy-efficient scheduling are receiving increasing attention. Current schedulers are, however, based on simplistic energy models not matching the reality, use techniques like DVFS not available on all types of systems, or do not approach the problem as a multi-objective optimisation considering both performance and energy as simultaneous objectives. In this paper, we present a new Pareto-based multi-objective workflow scheduling algorithm as an extension to an existing state-of-the-art heuristic capable of computing a set of tradeoff optimal solutions in terms of makespan and energy efficiency. Our approach is based on empirical models which capture the real behaviour of energy consumption in heterogeneous parallel systems. We compare our new approach with a classical mono-objective scheduling heuristic and state-of-the-art multi-objective optimisation algorithm and demonstrate that it computes better or similar results in different scenarios. We analyse the different tradeoff solutions computed by our algorithm under different experimental configurations and we observe that in some cases it finds solutions which reduce the energy consumption by up to 34.5% with a slight increase of 2% in the makespan.     

基于组合禁忌搜索的并行测试任务调度研究

任务调度是研究并行测试技术的核心问题。建立了该问题的数学模型,提出了一种基于组合禁忌搜索的并行测试任务调度方法,通过任务分组的规则构造较好的初始调度序列,利用禁忌搜索迭代寻找最好的调度序列,快速完成基于测试时间最短的任务调度规划。对实例进行了仿真实验,与基本禁忌搜索算法进行比较,仿真结果验证了该组合禁忌搜索算法的高效性和有效性。     

基于混合人工蜂群算法的并行测试任务优化研究

并行测试技术可以同时进行多个任务的测试,提高资源利用率,节约测试成本;并行测试调度问题是一种复杂的组合优化问题,是并行测试技术的核心要素;并行测试系统作为并行测试技术的载体,自身的性能和求解效率尤其重要;对并行测试完成时间极限定理进行了研究,建立了并行测试任务调度的数学模型,分析了传统元启发式算法求解并行测试问题的不足,提出了基于动态规划的递归搜索技术和人工蜂群算法相结合的混合人工蜂群算法,并采用整数规划精确算法和遗传算法对混合人工蜂群算法进行验证;得出结论采用混合人工蜂群算法进行并行测试任务的调度节约了接近50%的时间,降低了约20%的硬件资源占用,提高了测试效率,可以满足工程实际的应用。     

Integrated well pad development scheduling with steam injection control in steam-assisted gravity drainage

In this paper, we study the problem of integrated well pad development scheduling with nonlinear model predictive control based steam injection in steam-assisted gravity drainage (SAGD). The scheduling problem has been modeled as a mixed-integer program to find optimal development sequence and timing of multiple well-pads. Model predictive control problems are solved to find optimal steam injection profile such that the reservoir is under control. The integrated problem is solved using open-loop and closed-loop methods: (1) scheduling problem is only solved at the beginning of project operation, (2) Scheduling problem is solved every year with shrinking horizon implementation, and (3) shrinking horizon implementation of scheduling with reservoir model update based on feedback from control level. Simulation results demonstrate the benefits of closed-loop integrated scheduling and control: the NPV increase is 19%.     

任务与资源双向匹配的动态任务调度策略研究

并行测试系统中的测试任务的执行时间是不确定的,测试任务过程具有随机性。为实现测试任务优化执行的目的,建立了并行自动测试系统的动态任务调动模型,并提出了基于测试任务剩余工作量和测试资源剩余负载的启发式调度规则,并在测试任务过程Petri网模型的运行演化算法中采用该规则,实现并行测试任务的动态调度。最后通过实例仿真,验证了该策略的可行性和优越性。     

An energy‐aware scheduling algorithm for divisible loads in a bus network

The schedule of divisible loads is one of the most typical problems in the research and application of parallel and distributed systems. For these large‐scale systems, the energy consumption problem has drawn great attention in recent years because of falling hardware costs and the growing concern of energy costs. In computing‐intensive systems, energy is primarily consumed by CPUs, and dynamic voltage‐frequency scaling technology is capable of adjusting CPUs' speed as well as saving energy. In this paper, we focus on computing‐intensive applications and study the energy‐aware scheduling problem for divisible loads in a bus network. The energy‐speed model is introduced to characterize the problem based on dynamic voltage scaling, and the energy‐aware scheduling problem is analyzed in the application layer above the operating system. The problem can be formulated mathematically as a nonlinear programming problem, and the solution is achieved using the Lagrange multiplier method under Kuhn–Tucker conditions. Based on the analytical results, an energy‐aware scheduling scheme called ENERG for divisible loads is presented. Finally, the energy‐aware scheme is compared with two other schemes to show the effectiveness and efficiency of the energy savings of our algorithm. Additionally, the experimental results illustrate the influence of network transmission delay on energy consumption. Copyright © 2015 John Wiley & Sons, Ltd.     

A strategy for scheduling tightly coupled parallel applications on clusters

Although various strategies have been developed for scheduling parallel applications with independent tasks, very little work exists for scheduling tightly coupled parallel applications on cluster environments. In this paper, we compare four different strategies based on performance models of tightly coupled parallel applications for scheduling the applications on clusters. In addition to algorithms based on existing popular optimization techniques, we also propose a new algorithm called Box Elimination that searches the space of performance model parameters to determine the best schedule of machines. By means of real and simulation experiments, we evaluated the algorithms on single cluster and multi‐cluster setups. We show that our Box Elimination algorithm generates up to 80% more efficient schedules than other algorithms. We also show that the execution times of the schedules produced by our algorithm are more robust against the performance modeling errors. Copyright © 2009 John Wiley & Sons, Ltd.     

An iterated greedy algorithm for the large-scale unrelated parallel machines scheduling problem

In this work, we tackle the problem of scheduling a set of jobs on a set of unrelated parallel machines with minimising the total weighted completion times as performance criteria. The iterated greedy metaheuristic generates a sequence of solutions by iterating over a constructive heuristic using destruction and construction phases. In the last few years, iterated greedy has been employed to solve a considerable number of problems. This is because it is based on a very simple principle, it is easy to implement, and it often exhibits an excellent performance. Moreover, scalability for high-dimensional problems becomes an essential requirement for modern optimisation algorithms. This paper proposes an iterated greedy model for the above-mentioned scheduling problem to tackle large-size instances. The benefits of our proposal in comparison to existing metaheuristics proposed in the literature are experimentally shown.