多处理器系统的在线节能调度算法

随着多处理器系统计算性能的提高,能耗管理已变得越来越重要,如何满足实时约束并有效降低能耗成为实时调度中的一个重要问题。基于多处理器计算系统,针对随机到达的任务,提出一种在线节能调度算法(OLEAS)。该算法在满足任务截止期限的前提下,尽量将任务调度到产生能耗最少的处理器,当某个任务在所有处理器上都不能满足截止期限要求时,则调整处理器之间的部分任务,使之尽量满足截止期限要求。同时,OLEAS尽量使单个处理器上的任务按平均电压/频率执行,以降低能耗,只有当新到任务不满足截止期限要求时,才逐个调高前面任务的电压/频率。模拟实验比较了OLEAS、最早完成时间优先(EFF)、最高电压节能(HVEA)、最低电压节能(LVEA)、贪心最小能耗(MEG)和最小能耗最小完成时间(ME-MC)的性能,结果表明OLEAS在满足任务截止期限和节省能耗方面具有明显的综合优势     

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     

一种多处理器平台上的传感器事务调度算法

如何有效地调度传感器事务以维护数据的时态一致性是信息物理融合系统研究中的一个重要问题。已有的调度算法基本上都是针对单处理器平台来设计的。提出一种多处理器平台上的传感器事务调度算法,算法通过合理地分配和调整事务实例执行所需处理器资源来保证数据的时态一致性约束,通过预先计算出全局重复调度序列来降低运行开销,给出了算法的可调度性分析。实验结果表明,该算法具有较高的调度成功率,其产生的更新负载也较低。     

基于软实时多处理器系统的动态低功耗算法

结合DVS技术和(m,k)-firm模型，提出一个保证完成率、适用于软实时多电压多处理器系统中有依赖关系任务集的动态低功耗算法VAP_DY。该算法权衡应用的性能需求、执行时间的不确定性和系统对合理执行失败的容忍来动态调整每个处理器运行时的供电电压,以降低多处理器系统的总功耗。分析和实验结果表明，VAP_DY能够在保证时间和完成率约束的条件下有效降低系统功耗。     

多处理器系统可靠性约束下的节能调度算法

针对多处理器系统中随机到达的任务,设计了可靠性约束下的节能调度算法(ESACR)。该算法在满足任务截止期限的前提下选择一个预计产生能耗最小的处理器以节能,在单个处理器上运用最早截止期限优先策略进行调度并尽量使各个任务的执行电压/频率均衡,当新到任务在处理器上不能满足截止期限要求时则逐个调高前面未执行任务的电压/频率。同时,为保证系统的可靠性,ESACR给正在执行的任务预留错误恢复时间以保证当发生瞬时错误时该任务能被恢复。实验结果表明,与最高电压节能调度(HVEA)、最小能耗最小完成时间调度(ME-MC)、最早完成时间优先调度(EFF)相比,ESACR在保证系统可靠性的前提下节能效果最好。     

A parallel Ada system on an experimental multiprocessor

This paper describes the development of a parallel Ada system on an experimental MIMD multiprocessor. The system enables a single unmodified Ada program, with a number of tasks, to execute in parallel on different processors. Allocation and migration strategies are controlled by mechanisms in the run-time system, and are thus transparent to the Ada programmer. The parallel Ada system is based on a validated portable front-end compiler. Implementation issues related to the multiprocessor environment are pointed out, and solutions to these issues are suggested. The experimental multiprocessor environment, consisting of both hardware and software, is described. Applicable resource allocation strategies in, and feasible experiments with, the Ada system are discussed. The complete experimental system provides unique possibilities to experiment with, and monitor the effects of, design decisions at different levels in a multiprocessor environment.     

A heuristic-based hybrid genetic-variable neighborhood search algorithm for task scheduling in heterogeneous multiprocessor system

Effective task scheduling, which is essential for achieving high performance in a heterogeneous multiprocessor system, remains a challenging problem despite extensive studies. In this article, a heuristic-based hybrid genetic-variable neighborhood search algorithm is proposed for the minimization of makespan in the heterogeneous multiprocessor scheduling problem. The proposed algorithm distinguishes itself from many existing genetic algorithm (GA) approaches in three aspects. First, it incorporates GA with the variable neighborhood search (VNS) algorithm, a local search metaheuristic, to exploit the intrinsic structure of the solutions for guiding the exploration process of GA. Second, two novel neighborhood structures are proposed, in which problem-specific knowledge concerned with load balancing and communication reduction is utilized respectively, to improve both the search quality and efficiency of VNS. Third, the proposed algorithm restricts the use of GA to evolve the task-processor mapping solutions, while taking advantage of an upward-ranking heuristic mostly used by traditional list scheduling approaches to determine the task sequence assignment in each processor. Empirical results on benchmark task graphs of several well-known parallel applications, which have been validated by the use of non-parametric statistical tests, show that the proposed algorithm significantly outperforms several related algorithms in terms of the schedule quality. Further experiments are carried out to reveal that the proposed algorithm is able to maintain high performance within a wide range of parameter settings.     

A parallel algorithm for sparse symbolic Cholesky factorization on a multiprocessor

We develop an algorithm for computing the symbolic Cholesky factorization of a large sparse symmetric positive definite matrix. The algorithm is intended for a message-passing multiprocessor system, such as the hypercube, and is based on the concept of elimination forest. In addition, we provide an algorithm for computing these forests along with a discussion of the algorithm's complexity and a proof of its correctness.     

A genetic algorithm for the proportionate multiprocessor open shop

The multiprocessor open shop (MPOS) scheduling problem is NP-complete, a category of hard combinatorial optimization problems that have not received much attention in the literature. In this work, a special MPOS—a proportionate one—is introduced for the first time. Two original mixed integer programming formulations for the proportionate MPOS are developed and their complexity is discussed. Due to the complexity of the MPOS, this paper develops a compu-search methodology (a genetic algorithm (GA)) to schedule the shop with the objective of minimizing the makespan. In this novel GA, a clever chromosome representation of a schedule is developed that succinctly encodes a schedule of jobs across multiple stages. The innovative design of this chromosome enables any permutation of its genes to yield a feasible solution. This simple representation of an otherwise very complex schedule enables the genetic operators of crossover and mutation to easily manipulate a schedule as the algorithm iteratively searches for better schedules. A testbed of difficult instances of the problem are created to evaluate the performance of the GA. The solution for each instance is compared with a derived lower bound. Computational results reveal that the algorithm performs extremely well, demonstrating its potential to efficiently schedule MPOS problems. More importantly, successful experiments on large-scale problem instances suggest the readiness of the GA for industrial use.     

A parallel graph partitioning algorithm for a message-passing multiprocessor

We develop a parallel algorithm for partitioning the vertices of a graph intop2 sets in such a way that few edges connect vertices in different sets. The algorithm is intended for a message-passing multiprocessor system, such as the hypercube, and is based on the Kernighan-Lin algorithm for finding small edge separators on a single processor.⁽¹⁾ We use this parallel partitioning algorithm to find orderings for factoring large sparse symmetric positive definite matrices. These orderings not only reduce fill, but also result in good processor utilization and low communication overhead during the factorization. We provide a complexity analysis of the algorithm, as well as some numerical results from an Intel hypercube and a hypercube simulator.Publication of this report was partially supported by the National Science Foundation under Grant DCR-8451385 and by AT&T Bell Laboratories through their Ph.D scholarship program.     

A parallel algorithm of simulated annealing for multiprocessor scheduling

Algorithms of simulated annealing for solving problems of multiprocessor scheduling are considered, an approach to parallelization is proposed, and the results of comparisons between the classical sequential, sequential, and parallel algorithms of simulated annealing using a partition of the initial space of solutions into regions are presented.     

A large-area integrated multiprocessor system for videoapplications

This 16.89 cm² multiprocessor system performs coding of high-resolution video streams in real time. Redundancy and self-reconfiguration techniques ensure high reliability with a suitable yield. We used our own built-in self-test approach, which allows parallel testing of the processor cores     

基于粒子群优化的异构多处理器任务调度算法

为提高异构多处理器任务调度的执行效率,充分发挥多处理器并行性能,提出一种基于粒子群优化的异构多处理器任务调度算法——FPSOTTS算法。该算法以求得任务最短完成时间为目标,首先通过建立新的编码方式和粒子更新公式实现粒子搜索空间到离散空间的映射,使连续的粒子群优化算法适用于离散的异构多处理器任务调度问题;同时通过引入禁忌算法进行局部搜索,克服粒子群算法的早熟收敛现象,避免陷入局部最优。实验结果表明,FPSOTTS算法的执行效率优于Min-min算法和遗传算法,有效地降低任务的执行时间。FP-SOTTS算法很好地解决了异构多处理器任务调度问题,并且适合于大规模并行任务调度。     

基于粒子群优化算法的异构多处理器任务调度

为提高异构多处理器任务调度的执行效率,充分发挥多处理器并行性能,提出一种基于粒子群优化的异构多处理器任务调度算法-PSOASA算法.PSOASA算法以求得任务最短完成时间为目标,首先通过建立新的编码方式和粒子更新公式实现粒子搜索空间到离散空间的映射,使连续的粒子群优化算法适用于离散的异构多处理器任务调度问题,同时通过引入模拟退火算法,克服粒子群算法的“早熟”收敛现象,避免求得的解陷入局部最优.实验结果表明,PSOASA算法的执行效率优于目前广泛采用的遗传算法,有效地降低任务的执行时间,减少了迭代次数,适用于异构多处理器环境大规模任务调度.     

A space-efficient parallel sequence comparison algorithm for a message-passing multiprocessor

We present a parallel algorithm for computing an optimal sequence alignment in efficient space. The algorithm is intended for a message-passing architecture with one-dimensional-array topology. The algorithm computes an optimal alignment of two sequences of lengthsM andN inO((M+N) ² /P) time andO((M+N)/P) space per processor, where the number of processors isP>=max(M, N). Thus, whenP=max(M, N) it achieves linear speedup and requires constant space per processor. Some experimental results on an Intel hypercube are provided.This research was supported by NIH Grant LM05110 from the National Library of Medicine.     

M-CASH: A real-time resource reclaiming algorithm for multiprocessor platforms

Resource reclaiming schemes are typically applied in reservation-based real-time uniprocessor systems to support efficient reclaiming and sharing of computational resources left unused by early completing tasks, improving the response times of aperiodic and soft tasks in the presence of overruns. In this paper, we introduce a novel and efficient reclaiming algorithm, named M-CASH, for multiprocessor platforms. M-CASH leverages the resource reservation approach offered by the Multiprocessor CBS server offering significant improvements. The correctness of the algorithm is formally proven and its performance is evaluated through extensive synthetic simulations.

A Partitioning Selection Algorithm on Multiprocessors

The so-called(m,n)selection problem is the problem of selecting the m smallest(orlargest)elements from n given numbers(n>m).With the development of parallel computers,much attention has been paid to the design of efficient algorithms of(m,n)problem for thesemachines.The parallel selection algorithm has been successful on networks,but seldom studiedon the multiprocessing systems.This paper,based on a partitioning approach,proposes apartitioning algorithm of selection on multiprocessors using Valiant's merging and sortingschemes.By means of this algorithm,(m,n)selection problem can be completed in parallel n/2processors in time O(loguloglogm-log(n/m)loglog(n/m)).