Multi-objective fuzzy multiprocessor flowshop scheduling

This paper considers a bi-objective hybrid flowshop scheduling problems with fuzzy tasks’ operation times, due dates and sequence-dependent setup times. To solve this problem, we propose a bi-level algorithm to minimize two criteria, namely makespan, and sum of the earliness and tardiness, simultaneously. In the first level, the population will be decomposed into several sub-populations in parallel and each sub-population is designed for a scalar bi-objective. In the second level, non-dominant solutions obtained from sub-population bi-objective random key genetic algorithm (SBG) in the first level will be unified as one big population. In the second level, for improving the Pareto-front obtained by SBG, based on the search in Pareto space concept, a particle swarm optimization (PSO) is proposed. We use a defuzzification function to rank the Bell-shaped fuzzy numbers. The non-dominated sets obtained from each of levels and an algorithm presented previously in literature are compared. The computational results showed that PSO performs better than others and obtained superior results.     

Data‐aware task scheduling on heterogeneous hybrid memory multiprocessor systems

In this paper, we propose a method about task scheduling and data assignment on heterogeneous hybrid memory multiprocessor systems for real‐time applications. In a heterogeneous hybrid memory multiprocessor system, an important problem is how to schedule real‐time application tasks to processors and assign data to hybrid memories. The hybrid memory consists of dynamic random access memory and solid state drives when considering the performance of solid state drives into the scheduling policy. To solve this problem, we propose two heuristic algorithms called improvement greedy algorithm and the data assignment according to the task scheduling algorithm, which generate a near‐optimal solution for real‐time applications in polynomial time. We evaluate the performance of our algorithms by comparing them with a greedy algorithm, which is commonly used to solve heterogeneous task scheduling problem. Based on our extensive simulation study, we observe that our algorithms exhibit excellent performance and demonstrate that considering data allocation in task scheduling is significant for saving energy. We conduct experiments on two heterogeneous multiprocessor systems. Copyright © 2016 John Wiley & Sons, Ltd.     

Communication and migration energy aware task mapping for reliable multiprocessor systems

Heterogeneous multiprocessor systems-on-chip (MPSoCs) are emerging as a promising solution in deep sub-micron technology nodes to satisfy design performance and power requirements. However, shrinking transistor geometry and aggressive voltage scaling are negatively impacting the dependability of these MPSoCs by increasing the chances of failures. This paper proposes an offline (design-time) task remapping technique to minimize the communication energy and task migration overhead of an application mapped on a heterogeneous multiprocessor system for all processor fault-scenarios. The proposed technique involves two steps–(1) Communication Energy driven Design Space Exploration (CDSE) to select an initial mapping and (2) Communication energy and Migration overhead aware Task Mapping (CMTM) for different fault-scenarios. The CDSE is formulated as a Mixed Integer Quadratic Programming (MIQP) problem and solved using an energy-gradient based heuristic. The CMTM problem is solved using a fast heuristic with the starting mapping selected using CDSE step. The proposed two steps technique is compared with state-of-the-art approaches through rigorous simulations with synthetic and real application graphs. Results demonstrate that the proposed CDSE reduces design space exploration time by 99% with a maximum variation of 5% from the optimal solution obtained by solving the MIQP problem directly. Further, the proposed CMTM reduces communication energy by an average 35% and migration overhead by an average 20% for all single and double fault-scenarios as compared to the existing fault-tolerant techniques. The CMTM also achieves over 30x reductions in execution time for large problem sizes with a maximum deviation of 15% from the minimum communication energy achievable with the given application on a given architecture. For streaming multimedia applications, the proposed technique delivers 50% higher throughput per unit energy as compared to the existing approaches.     

Reliability-aware task scheduling for energy efficiency on heterogeneous multiprocessor systems

The Journal of Supercomputing - Recent studies mainly focus on high performance or low power consumption for task scheduling on heterogeneous multiprocessor systems (HMSs). Dynamic voltage and...     

异构多核下兼顾应用公平性和能耗的调度方法研究

异构多核处理器通常由高性能的大核和低能耗的小核组成,在其上进行合理的线程调度可以有效地提高资源利用率,节省能耗。之前论文提出的大小核上的公平性调度并没有考虑核上有不同频率/电压状态的情况,而现在支持DVFS调节的处理器越来越普遍,因此很有必要将线程间公平度的计算进行扩展和改进。提出在每个核有若干种不同的DVFS状态时异构多核处理器上线程公平度的计算方法,对已有的性能预测模型进行改进,采用自适应算法调整模型中的系数,并在此基础上提出了一种调度策略,维持各线程之间的公平度和处理器功率满足提前设定的阈值,同时选取能效最优化的配置,实现减小应用运行能耗的目的。实验结果表明,与所提出的调度策略相比,采用static、DVFS-only、swap-only三种调度方法时,在总的运行时间几乎相同的情况下,平均要多产生20%以上能耗,对于有些应用甚至达到了50%。     

Multi-objective pump scheduling optimisation using evolutionary strategies

Multi-objective Evolutionary Algorithms (MOEAs) are used to solve an optimal pump-scheduling problem with four objectives to be minimized: electric energy cost, maintenance cost, maximum power peak, and level variation in a reservoir. Six different MOEAs were implemented and compared. In order to consider hydraulic and technical constraints, a heuristic algorithm was developed and combined with each implemented MOEA. Evaluation of experimental results of a set of metrics shows that the Strength Pareto Evolutionary Algorithm achieves better overall performance than other MOEAs for the parameters considered in the test problem, providing a wide range of optimal pump schedules to chose from.     

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.     

On multiprocessor task scheduling using efficient state space search approaches

Obtaining an optimal schedule for a set of precedence-constrained tasks is a well-known NP-complete problem in its general form. In view of the intractability of the problem, most of the previous work relies on heuristics that try to find reasonably high quality solutions in an acceptable amount of time. While optimal polynomial-time algorithms are known only for a few simple cases (and in other cases can only be obtained through an exhaustive search with prohibitively high time complexity), they may be critically important for applications in which performance is the prime objective. Optimal solutions can also serve as a reference to test the performance of various heuristics. Moreover, an optimal schedule for a program at hand needs to be determined only once (and off-line) but the program using that schedule is in general executed several times. In this paper, we propose optimal algorithms for static scheduling of task graphs with arbitrary parameters to multiple homogeneous processors. The first algorithm is based on the A^* search technique and uses a computationally efficient cost function for guiding the search with reduced complexity. Additionally, we propose a number of effective state-pruning techniques to reduce the search space. For further lowering the complexity, we propose an efficient parallelization of the search algorithm. We parallelize the algorithm with reduced interprocessor communication as well as with static and dynamic load-balancing schemes to evenly distribute the search states to the processors. We also propose an approximate algorithm that guarantees a bounded deviation from the optimal solution but executes in a considerably shorter time. Based on an extensive experimental evaluation of the algorithms, we conclude that the parallel algorithm with pruning techniques is an efficient scheme for generating optimal solutions of reasonably large problems while the approximate algorithm is effective if slightly degraded solutions are acceptable.     

On multiprocessor temperature-aware scheduling problems

We study temperature-aware scheduling problems under the model introduced in [Chrobak et al. AAIM 2008], where unit-length jobs of given heat contributions and common release dates are to be scheduled on a set of parallel identical processors. We consider three optimization criteria: makespan, maximum temperature and (weighted) average temperature. On the positive side, we present polynomial time approximation algorithms for the minimization of the makespan and the maximum temperature, as well as, optimal polynomial time algorithms for minimizing the average temperature and the weighted average temperature. On the negative side, we prove that there is no approximation algorithm of absolute ratio $\frac{4}{3}-\epsilon $ for the problem of minimizing the makespan for any $\epsilon > 0$ , unless $\mathcal{P}=\mathcal{NP}$ .     

Optimal virtual cluster-based multiprocessor scheduling

Scheduling of constrained deadline sporadic task systems on multiprocessor platforms is an area which has received much attention in the recent past. It is widely believed that finding an optimal scheduler is hard, and therefore most studies have focused on developing algorithms with good processor utilization bounds. These algorithms can be broadly classified into two categories: partitioned scheduling in which tasks are statically assigned to individual processors, and global scheduling in which each task is allowed to execute on any processor in the platform. In this paper we consider a third, more general, approach called cluster-based scheduling. In this approach each task is statically assigned to a processor cluster, tasks in each cluster are globally scheduled among themselves, and clusters in turn are scheduled on the multiprocessor platform. We develop techniques to support such cluster-based scheduling algorithms, and also consider properties that minimize total processor utilization of individual clusters. In the last part of this paper, we develop new virtual cluster-based scheduling algorithms. For implicit deadline sporadic task systems, we develop an optimal scheduling algorithm that is neither Pfair nor ERfair. We also show that the processor utilization bound of us-edf{m/(2m−1)} can be improved by using virtual clustering. Since neither partitioned nor global strategies dominate over the other, cluster-based scheduling is a natural direction for research towards achieving improved processor utilization bounds.

Communication-aware task scheduling and voltage selection for total energy minimization in a multiprocessor system using Ant Colony Optimization

Energy consumption is a key parameter when highly computational tasks should be performed in a multiprocessor system. In this case, in order to reduce total energy consumption, task scheduling and low-power methodology should be combined in an efficient way. This paper proposes an algorithm for off-line communication-aware task scheduling and voltage selection using Ant Colony Optimization. The proposed algorithm minimizes total energy consumption of an application executing on a homogeneous multiprocessor system. The artificial agents explore the search space based on stochastic decision-making using global heuristic information with total energy consumption and local heuristic information with interprocessor communication volume. In search space exploration, both voltage selection and the dependencies between tasks are considered. The pheromone trails are updated by normalizing the total energy consumption. The pheromone trails represent the global heuristic information in order to utilize all entire energy consumption information from previous evaluated solutions. Experimental results show that the proposed algorithm outperforms traditional communication-aware task scheduling and task scheduling using genetic algorithms in terms of total energy consumption.     

GreenSched: An intelligent energy aware scheduling for deadline-and-budget constrained cloud tasks

The constant growth of the energy crisis within the ICT Sector has persistently gained importance thereby prompting endeavors to curb growing energy demands and associated expenditures. This paper attempts to propose an intelligent energy aware task allocation and resource provisioning technique running in GreenSched model. The GreenSched model tends to exploit the heterogeneity of tasks and multi-core capacity of the varied nodes in the cloud environment and attempts to proactively schedule the deadline-and budget- constrained tasks on identified less energy consuming or energy aware nodes. It implements a Forward-only Counter Propagation Network (CPN) based intelligent scheduler unit that runs a scheduling technique to identify the best nodes for the task allocation process, one with least energy consumption and deadline- and budget -fulfilling capability. The nodes are clustered and classified by comparing their energy consumption values. The proposed algorithm has been implemented using the CloudSim toolkit and Kohonen and CP-ANN Toolbox with the help of Matlab^TM platform. The experimental results exhibit that the proposed technique offers reduced energy consumption along with an overall improvement in the performance by meeting the deadline-and-budget constraints imposed by the users.     

On parallelizing the multiprocessor scheduling problem

Existing heuristics for scheduling a node and edge weighted directed task graph to multiple processors can produce satisfactory solutions but incur high time complexities, which tend to exacerbate in more realistic environments with relaxed assumptions. Consequently, these heuristics do not scale well and cannot handle problems of moderate sizes. A natural approach to reducing complexity, while aiming for a similar or potentially better solution, is to parallelize the scheduling algorithm. This can be done by partitioning the task graphs and concurrently generating partial schedules for the partitioned parts, which are then concatenated to obtain the final schedule. The problem, however, is nontrivial as there exists dependencies among the nodes of a task graph which must be preserved for generating a valid schedule. Moreover, the time clock for scheduling is global for all the processors (that are executing the parallel scheduling algorithm), making the inherent parallelism invisible. In this paper, we introduce a parallel algorithm that is guided by a systematic partitioning of the task graph to perform scheduling using multiple processors. The algorithm schedules both the tasks and messages, and is suitable for graphs with arbitrary computation and communication costs, and is applicable to systems with arbitrary network topologies using homogeneous or heterogeneous processors. We have implemented the algorithm on the Intel Paragon and compared it with three closely related algorithms. The experimental results indicate that our algorithm yields higher quality solutions while using an order of magnitude smaller scheduling times. The algorithm also exhibits an interesting trade-off between the solution quality and speedup while scaling well with the problem size     

A genetic algorithm for multiprocessor scheduling

The problem of multiprocessor scheduling can be stated as finding a schedule for a general task graph to be executed on a multiprocessor system so that the schedule length can be minimized. This scheduling problem is known to be NP-hard, and methods based on heuristic search have been proposed to obtain optimal and suboptimal solutions. Genetic algorithms have recently received much attention as a class of robust stochastic search algorithms for various optimization problems. In this paper, an efficient method based on genetic algorithms is developed to solve the multiprocessor scheduling problem. The representation of the search node is based on the order of the tasks being executed in each individual processor. The genetic operator proposed is based on the precedence relations between the tasks in the task graph. Simulation results comparing the proposed genetic algorithm, the list scheduling algorithm, and the optimal schedule using random task graphs, and a robot inverse dynamics computational task graph are presented     

Performance and energy aware cluster-level scheduling of compute-intensive jobs with unknown service times

In this paper we examine three local resource allocation policies, which are based on shortest queue, in a cluster with heterogeneous servers. Two of them are optimized for performance and the third one is optimized for energy conservation. We assume that there are two types of processors in the cluster, with different performance and energy characteristics. We consider that service times of jobs are unknown to the scheduler. A simulation model is used to evaluate the performance and energy behavior of the policies. Simulation results indicate that the differences among the policies depend on system load and there is a trade-off between performance and energy consumption.     

具有温度感知特性的实时调度研究

处理器温度的上升严重危害着处理器的性能。DTM（Dynamic Thermal Management）是一种硬件层面的热管理机制,它会带来一定的性能损失。提出了一种操作系统层面的针对实时任务的动态热管理机制——LTEDF（Low Thermal Early Deadline First）。LTEDF通过在线实时获取性能计数器的值,计算处理器当前温度来动态调度队列中的线程,提出了MST（Maximum Scheduling Threshold）启发式方法。基于HotSpot温度模型对算法进行了仿真实验,结果显示,该算法不仅可以满足任务的时间限制而且可以满足温度限制,并且较传统的EDF（Early Deadline First）LTEDF算法可以创建更加统一的功率密度图,MST启发式算法可以明显减少线程迁移带来的开销。     

Declustering: a new multiprocessor scheduling technique

The authors present a new compile-time scheduling heuristic called declustering, which schedules acyclic precedence graphs that fit the synchronous data flow (SDF) model onto multiprocessor architectures. This technique accounts for interprocessor communication (IPC) overheads and considers interconnection constraints in the architecture so that shared resource contention can be avoided. The algorithm initially invokes a new clustering method that uses graph-analysis techniques to isolate parallelism instances. When constructing an initial set of clusters, this procedure explicitly addresses the tradeoff between exploiting parallelism and incurring communication cost. By hierarchically combining these clusters and then systematically decomposing this hierarchy, the declustering method exposes parallelism instances in order of importance and attains a cluster granularity that fits the characteristics of the architecture. It is shown that declustering retains the clustering advantage of avoiding IPC, yet overcomes the inflexibility associated with traditional clustering approaches