Multiprocessor scheduling and rescheduling with use of cellular automata and artificial immune system support

The paper presents cellular automata (CA)-based multiprocessor scheduling system, in which an extraction of knowledge about scheduling process occurs and this knowledge is used while solving new instances of the scheduling problem. There are three modes of the scheduler: learning, normal operating, and reusing. In the learning mode, a genetic algorithm is used to discover CA rules suitable for solving instances of a scheduling problem. In the normal operating mode, discovered rules are able to find automatically, without a calculation of a cost function, an optimal or suboptimal solution of the scheduling problem for any initial allocation of program tasks in a multiprocessor system. In the third mode, previously discovered rules are reused with support of an artificial immune system (AIS) to solve new instances of the problem. We present a number of experimental results showing the performance of the CA-based scheduler.     

Sequential and parallel cellular automata-based schedulingalgorithms

We present an approach to designing cellular automata-based multiprocessor scheduling algorithms in which extracting knowledge about the scheduling process occurs. We consider the simplest case when a multiprocessor system is limited to two-processors. To design cellular automata corresponding to a given program graph, we propose a generic definition of program graph neighborhood, transparent to the various kinds, sizes, and shapes of program graphs. The cellular automata-based scheduler works in two modes: learning mode and operation mode. Discovered rules are typically suitable for sequential cellular automata working as a scheduler, while the most interesting and promising feature of cellular automata are their massive parallelism. To overcome difficulties in evolving parallel cellular automata rules, we propose using coevolutionary genetic algorithm. Discovered this way, rules enable us to design effective parallel schedulers. We present a number of experimental results for both sequential and parallel scheduling algorithms discovered in the context of a cellular automata-based scheduling system     

An anomaly prevention approach for real-time task scheduling

This research responds to practical requirements in the porting of embedded software over platforms and the well-known multiprocessor anomaly. In particular, we consider the task scheduling problem when the system configuration changes. With mutual-exclusive resource accessing, we show that new violations of the timing constraints of tasks might occur even when a more powerful processor or device is adopted. The concept of scheduler stability and rules are then proposed to prevent scheduling anomaly from occurring in task executions that might be involved with task synchronization or I/O access. Finally, we explore policies for bounding the duration of scheduling anomalies.     

模糊反馈控制实时调度算法

为了解决模糊不确定任务集在不可预测环境下的动态抢占调度问题,应用模糊规则和模糊调度理论,提出一个基于模糊反馈控制的调度算法,并建立相应的调度架构.该架构由基本调度器和模糊反馈控制两部分组成.用模糊调度算法作为基本调度器的调度算法,将任务集按不同优先级等级进行划分,优先级等级高的任务优先调度,从而使得更多的重要任务得到调度;模糊控制器与任务流调节策略一起构成模糊反馈控制部分.仿真结果表明,模糊反     

Scheduling Algorithms with Fault Detection and Location Capabilities for Real-Time Multiprocessor Systems

Several schemes for detecting and locating faulty processors through self-diagnosis in multiprocessor systems have been discussed in the past. These schemes attempt to start multiple copies (versions) of the tasks on available idle processors simultaneously and compare the results generated by the copies to detect or locate faulty processors. These schemes are based on FCFS scheduling strategy. But, they cannot be applied directly to real-time multiprocessor systems where tasks have timing constraints. In this paper, we present a new scheduling algorithm that not only schedules real-time tasks, but also attempts to perform self-diagnosis if the system is not heavily loaded. We define load as a function of the tasks' laxities. We have carried out extensive simulations and compared the results of our algorithm with those of the myopic algorithm, a real-time task scheduler. Simulation results show that our algorithm that exploits both the tasks' laxity and spare capacity (unused processors) offers performance (guarantee ratio) comparable to that of the myopic algorithm in addition to achieving fault detection and location     

Dynamic task scheduling using online optimization

Algorithms for scheduling independent tasks on to the processors of a multiprocessor system must trade-off processor load balance, memory locality, and scheduling overhead. Most existing algorithms, however, do not adequately balance these conflicting factors. This paper introduces the self-adjusting dynamic scheduling (SADS) class of algorithms that use a unified cost model to explicitly account for these factors at runtime. A dedicated processor performs scheduling in phases by maintaining a tree of partial schedules and incrementally assigning tasks to the least-cost schedule. A scheduling phase terminates whenever any processor becomes idle, at which time partial schedules are distributed to the processors. An extension of the basic SADS algorithm, called DBSADS, controls the scheduling overhead by giving higher priority to partial schedules with more task-to-processor assignments. These algorithms are compared to two distributed scheduling algorithms within a database application on an Intel Paragon distributed memory multiprocessor system.     

Priority-Driven Scheduling of Periodic Task Systems on Multiprocessors

The scheduling of systems of periodic tasks upon multiprocessor platforms is considered. Utilization-based conditions are derived for determining whether a periodic task system meets all deadlines when scheduled using the earliest deadline first scheduling algorithm (EDF) upon a given multiprocessor platform. A new priority-driven algorithm is proposed for scheduling periodic task systems upon multiprocessor platforms: this algorithm is shown to successfully schedule some task systems for which EDF may fail to meet all deadlines.     

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     

An efficient grid-scheduling strategy based on a fuzzy matchmaking approach

Computational grids have become an appealing research area as they solve compute-intensive problems within the scientific community and in industry. A grid computational power is aggregated from a huge set of distributed heterogeneous workers; hence, it is becoming a mainstream technology for large-scale distributed resource sharing and system integration. Unfortunately, current grid schedulers suffer from the haste problem, which is the schedule inability to successfully allocate all input tasks. Accordingly, some tasks fail to complete execution as they are allocated to unsuitable workers. Others may not start execution as suitable workers are previously allocated to other peers. This paper is the first to introduce the scheduling haste problem. It also presents a reliable grid scheduler. The proposed scheduler selects the most suitable worker to execute an input grid task using a fuzzy inference system. Hence, it minimizes the turnaround time for a set of grid tasks. Moreover, our scheduler is a system-oriented one as it avoids the scheduling haste problem. Experimental results have shown that the proposed scheduler outperforms traditional grid schedulers as it introduces a better scheduling efficiency.     

An efficient system-oriented grid scheduler based on a fuzzy matchmaking approach

Computational grids have become an appealing research area as they solve compute-intensive problems within the scientific community and in industry. A Grid computational power is aggregated from a huge set of distributed heterogeneous workers; hence, it is becoming a mainstream technology for large-scale distributed resource sharing and system integration. Unfortunately, current grid schedulers suffer from the haste problem, which is the schedule inability to successfully allocate all input tasks. Accordingly, some tasks fail to complete execution as they are allocated to unsuitable workers. Others may not start execution as suitable workers are previously allocated to other peers. This paper is the first to introduce the scheduling haste problem. It also presents a reliable grid scheduler. The proposed scheduler selects the most suitable worker to execute an input grid task using a fuzzy inference system. Hence, it minimizes the turnaround time for a set of grid tasks. Moreover, our scheduler is a system-oriented one as it avoids the scheduling haste problem. Experimental results have shown that the proposed scheduler outperforms traditional grid schedulers as it introduces a better scheduling efficiency.     

基于DVS技术的性能感知反馈调度算法

传统DVS算法在能量管理方面没有考虑实际系统性能的需求,这在一定意义上限制了其节能效果．针对这一问题,提出一种基于DVS技术的性能感知反馈调度算法．在反馈调度器中,分别采用DVS技术和模糊控制技术设计CPU电压调节模块和控制任务周期调节模块,实现对系统CPU速率和控制任务采样周期的动态调节．通过与基于固定采样周期的DVS反馈调度算法进行对比,结果表明该算法在保证系统控制性能的同时进一步降低了系统能耗．     

Task scheduling with precedence constraints to minimize the total completion time

The authors study the problem of scheduling a set of tasks with known execution times and arbitrary precedence constraints to computing systems. The objective function used to measure the performance of a schedule in this paper is the sum of completion times of all tasks, which is called total completion time. Finding the minimum total completion time of tasks with precedence constraints on the uniprocessor system is known to be NP-complete, let alone on the multiprocessor system (Garey and Johnson 1979) Based on the well-known A? algorithm proposed in the field of artificial intelligence (Nilson 1980) two algorithms are developed to solve efficiently the scheduling problems on the uniprocessor system and multiprocessor system. Some evaluation functions are proposed to accelerate the search of an optimal schedule. A table named the backwards range-limited table is used to assist the computation of the evaluation function. Experimental results show that the proposed approaches can achieve the optimal schedule with greatly reduced search tree size, especially when bounding rules are applied.     

基于数据交换与同步的作业调度方案

多机作业调度问题是一个经典的NP难问题,在应用中由于实际需要,会出现各种约束和变形,调度问题的研究成果决定着系统的性能.DataTurbo是作者参与的一个用于解决分布式数据迁移、集成和融合的平台,该平台承担着大数据量的分布式传输任务.在DataTurbo平台基础上,提出一种适用于数据交换与同步的分布式作业调度方案,并构建一个灵活的分布式调度算法框架,解决相关的调度问题.该调度方案是一种在线的、可并发的、作业可分解的多机调度方案.仿真实验结果显示,该调度方案在任务负载大、调度点稀疏情况下优势明显,能适用于数据交换同步作业,可作为数据交换与同步作业的动态调度方案,并为相关启发式算法建立基础模型.     

A hierarchical reliability-driven scheduling algorithm in grid systems

In a Grid computing system, many distributed scientific and engineering applications often require multi-institutional collaboration, large-scale resource sharing, wide-area communication, etc. Applications executing in such systems inevitably encounter different types of failures such as hardware failure, program failure, and storage failure. One way of taking failures into account is to employ a reliable scheduling algorithm. However, most existing Grid scheduling algorithms do not adequately consider the reliability requirements of an application. In recognition of this problem, we design a hierarchical reliability-driven scheduling architecture that includes both a local scheduler and a global scheduler. The local scheduler aims to effectively measure task reliability of an application in a Grid virtual node and incorporate the precedence constrained tasks’ reliability overhead into a heuristic scheduling algorithm. In the global scheduler, we propose a hierarchical reliability-driven scheduling algorithm based on quantitative evaluation of independent application reliability. Our experiments, based on both randomly generated graphs and the graphs of some real applications, show that our hierarchical scheduling algorithm performs much better than the existing scheduling algorithms in terms of system reliability, schedule length, and speedup.     

一种可重构资源管理模型及其调度技术

针对多任务操作系统的可重构资源管理,提出了一种管理模型和在线调度算法,具体实现了把任务分配给基于块划分的可重构器件。一方面,可重构器件由一个主CPU控制,主CPU运行在线调度器和放置器;另一方面,可重构器件由具有相同垂直尺寸的固定大小的块构成,但块可以有不同的宽度,目的是为了在资源和任务之间实现更好的匹配;同时在在线调度器和放置器运行两个函数fSPLIT和fSELECT来实现任务在可重构器件上的配置和调度。仿真结果表明,提出的资源管理模型和调度算法不仅能够实现任务集平均响应时间的最小化和有效调度,而且相比于其他调度算法,还能获得更高的资源利用率。     

基于异构CMP的改进蚁群优化任务调度策略

为提高异构CMP任务调度执行效率,充分发挥异构CMP的异构性和并行能力,提出一种基于异构CMP的改进蚁群优化任务调度算法--IACOTS。IACOTS算法首先建立任务调度模型、路径选择规则和信息素更新规则,使蚁群算法能够适用于异构CMP任务调度问题。同时通过采用动态信息素更新、相遇并行搜索策略和引入遗传算法中的变异因子对基本的蚁群算法进行优化,克服蚁群算法搜索时间过长和“早熟”现象。通过仿真实验获得的结果表明,IACOTS算法执行效率优于现有的遗传算法,完成相同的任务需要的迭代次数最少,能有效降低程序执行时间,适用于异构CMP等大规模并行环境的任务调度。     

基于Logistic回归模型的Hadoop本地任务调度优化算法*

当一个工作节点有多个本地任务可执行时,默认情况下,调度器都是按照任务被发现的先后顺序来进行执行,效率低下。针对于此,为了优化对本地任务的调度,提出了基于Logistic回归模型的Hadoop本地任务调度优化算法。首先,选取定义与任务相关的特征向量,然后基于Logistic回归的机器学习方式得到各向量的作用权值,将任务进行优先级排序,并通过过载规则不断更新模型。通过实验证明,提出的算法在改善map 任务的数据本地性的同时,降低了作业运行时间。     

非完全互连同构系统上的静态任务调度

在分布式内存多处理机DMM(distributed memory multiprocessor)系统中,不同处理机上运行的任务之间的通信开销仍然很大,有时甚至抵消了多处理机并行所带来的好处.为了使并行程序在DMM系统上能得以高效的执行,必须采用合理的调度技术将任务分配给处理机.文章首先分别给出了任务调度系统中的任务模型、处理机模型以及调度问题的形式化描述,然后在此基础上研究了任务调度中3个最重要的问题,即(1) 如何顺序选择参与调度的任务,(2) 如何选择路由,(3) 如何分配任务给处理机.其中,路由选择     

Compiler support for task scheduling in hierarchical execution models

Algorithms from scientific computing often exhibit a two-level parallelism based on potential method parallelism and potential system parallelism. We consider the parallel implementation of those algorithms on distributed memory machines. The two-level potential parallelism of algorithms is expressed in a specification consisting of an upper level hierarchy of multiprocessor tasks each of which has an internal structure of uniprocessor tasks. To achieve an optimal parallel execution time, the parallel execution of such a program requires an optimal scheduling of the multiprocessor tasks and an appropriate treatment of uniprocessor tasks. For an important subclass of structured method parallelism we present a scheduling methodology which takes data redistributions between multiprocessor tasks into account. As costs we use realistic parallel runtimes. The scheduling methodology is designed for an integration into a parallel compiler tool. We illustrate the multitask scheduling by several examples from numerical analysis.     

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.