A design fix to supervisory control for fault-tolerant scheduling of real-time multiprocessor systems with aperiodic tasks

In the article ‘Supervisory control for fault-tolerant scheduling of real-time multiprocessor systems with aperiodic tasks’, Park and Cho presented a systematic way of computing a largest fault-tolerant and schedulable language that provides information on whether the scheduler (i.e., supervisor) should accept or reject a newly arrived aperiodic task. The computation of such a language is mainly dependent on the task execution model presented in their paper. However, the task execution model is unable to capture the situation when the fault of a processor occurs even before the task has arrived. Consequently, a task execution model that does not capture this fact may possibly be assigned for execution on a faulty processor. This problem has been illustrated with an appropriate example. Then, the task execution model of Park and Cho has been modified to strengthen the requirement that none of the tasks are assigned for execution on a faulty processor.     

计算资源共享平台中工作流任务调度研究

提出了计算资源共享平台中具有时间约束的工作流任务调度方法,该方法利用了非集中式的树型应用层覆盖网络拓扑结构,从而可以高效而快速的收集资源的可用信息。采用全局调度器与本地调度器结合的方式,通过定义资源的收集功能过程,使每个节点中的本地调度器能够把自身的资源可用信息提供给全局的调度器,工作流中任务的最后期限时间约束和任务的恢复时间以一种时间间隙的机制来完成。仿真结果表明,分治模式和解方程类的迭代模式的工作流任务能够在平台上成功调度运行,具有比较快的响应时间和低的通信负载。     

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.     

Supervisory control for real-time scheduling of periodic and sporadic tasks with resource constraints

In the framework of supervisory control of timed discrete event systems, this paper addresses the design problem of a real-time scheduler that meets stringent time constraints of periodic tasks and sporadic tasks which exclusively access shared resources. For this purpose, we present the timed discrete event models of execution of periodic tasks and sporadic tasks and resource access for shared resources. Based on these models, we present the notion of deadlock-free and schedulable languages that contain only deadline-meeting sequences which do not reach deadlock states. In addition, we present the method of systematically computing the largest deadlock-free and schedulable language, and it is also shown that schedulability analysis can be done using this language. We further show that the real-time scheduler achieving the largest deadlock-free and schedulable language is optimal in the sense that there are no other schedulers to achieve schedulable cases more than those achieved by the optimal scheduler.     

The design and implementation of a distributed image understanding system

Computer vision is concerned with extracting information about a scene by analyzing images of that scene. Performing any computer vision task requires an enormous amount of computation. Exploiting parallelism appears to be a promising way to improve the performance of computer vision systems. Past work in this area has focused on applying parallel processing techniques to image-operator level parallelism. In this article, we discuss the parallelism of computer vision in the control level and present a distributed image understanding system (DIUS).In DIUS, control-level parallelism is exploited by a dynamic scheduler. Furthermore, two levels of rules are used in the control mechanism. Meta-rules are concerned mainly with which strategy should be driven and the execution sequence of the system; control rules determine which task needs to be done next. A prototype system has been implemented within a parallel programming environment, Strand, which provides various virtual architectures mapping to either a shared-memory machine, Sequent, or to the Sun network.     

A dynamic execution time estimation model to save energy in heterogeneous multicores running periodic tasks

Nowadays, real-time embedded applications have to cope with an increasing demand of functionalities, which require increasing processing capabilities. With this aim real-time systems are being implemented on top of high-performance multicore processors that run multithreaded periodic workloads by allocating threads to individual cores. In addition, to improve both performance and energy savings, the industry is introducing new multicore designs such as ARM’s big.LITTLE that include heterogeneous cores in the same package.A key issue to improve energy savings in multicore embedded real-time systems and reduce the number of deadline misses is to accurately estimate the execution time of the tasks considering the supported processor frequencies. Two main aspects make this estimation difficult. First, the running threads compete among them for shared resources. Second, almost all current microprocessors implement Dynamic Voltage and Frequency Scaling (DVFS) regulators to dynamically adjust the voltage/frequency at run-time according to the workload behavior. Existing execution time estimation models rely on off-line analysis or on the assumption that the task execution time scales linearly with the processor frequency, which can bring important deviations since the memory system uses a different power supply.In contrast, this paper proposes the Processor–Memory (Proc–Mem) model, which dynamically predicts the distinct task execution times depending on the implemented processor frequencies. A power-aware EDF (Earliest Deadline First)-based scheduler using the Proc–Mem approach has been evaluated and compared against the same scheduler using a typical Constant Memory Access Time model, namely CMAT. Results on a heterogeneous multicore processor show that the average deviation of Proc–Mem is only by 5.55% with respect to the actual measured execution time, while the average deviation of the CMAT model is 36.42%. These results turn in important energy savings, by 18% on average and up to 31% in some mixes, in comparison to CMAT for a similar number of deadline misses.     

Service scheduling and rescheduling in an applications integration framework

Grid technologies are evolving towards a service oriented architecture (SOA) and the traditional client/server architecture of heterogeneous computing (HC) can be transformed into a grid service oriented architecture. In this architecture, when more than one service fulfills the user request, a service which can make scheduling decisions is essential. A scheduling service has been proposed in a framework which achieves the dynamic deployment and scheduling of scientific and engineering applications. The framework treats all components (resource service and scheduler service) as WSRF-compliant services which support the applications integration with underlying native platform facilities and facilitate the construction of the hierarchical scheduling system. In order to enhance the system performance, we replace the MWL scheduling algorithm with an MCT algorithm and integrate a rescheduling mechanism in the framework. The experiments show that the MCT algorithm can achieve a smaller makespan and the rescheduling mechanism ensures the task execution even if an application is removed from the Resource Service.     

An integrated fine-grain runtime system for MPI

Fine-grain MPI (FG-MPI) extends the execution model of MPI to allow for interleaved execution of multiple concurrent MPI processes inside an OS-process. It provides a runtime that is integrated into the MPICH2 middleware and uses light-weight coroutines to implement an MPI-aware scheduler. In this paper we describe the FG-MPI runtime system and discuss the main design issues in its implementation. FG-MPI enables expression of function-level parallelism, which along with a runtime scheduler, can be used to simplify MPI programming and achieve performance without adding complexity to the program. As an example, we use FG-MPI to re-structure a typical use of non-blocking communication and show that the integrated scheduler relieves the programmer from scheduling computation and communication inside the application and brings the performance part outside of the program specification into the runtime.     

多引擎服务组合的执行优化

提出了多引擎的Web服务管理系统,解决了系统中服务组合的执行优化问题。分析了该多引擎系统中服务组合的调度执行,提出了动态规划算法。在分派和执行Web服务前,生成流水执行的子序列方案,使调度执行Web服务的引擎的最大负载最小。实验结果表明,与随机算法相比,该算法使性能显著提高。     

网络控制系统的一种变采样周期动态调度策略

提出一种基于网络运行状态的网络控制系统动态调度器的设计方法．首先利用监测器在线获取当前的网络利用率、网络诱导误差和数据包执行时间，基于获取的网络状态，预测下一监测周期内的网络利用率和数据包执行时间．然后按照网络运行性能和控制性能的需求，基于网络利用率和数据包执行时间的预估值分配网络资源，计算控制系统新的采样周期．当数据包传输发生冲突时，采用MEF（Maximum Error First）作为辅助调度策略，确定数据包的发送优先级．最后通过一组仿真结果验证了所设计的动态调度器的有效性．     

Three practical workflow schedulers for easy maximum parallelism

Runtime scheduling and workflow systems are an increasingly popular algorithmic component in HPC because they allow full system utilization with relaxed synchronization requirements. There are so many special-purpose tools for task scheduling, one might wonder why more are needed. Use cases seen on the Summit supercomputer needed better integration with MPI and greater flexibility in job launch configurations. Preparation, execution, and analysis of computational chemistry simulations at the scale of tens of thousands of processors revealed three distinct workflow patterns. A separate job scheduler was implemented for each one using extremely simple and robust designs: file-based, task-list based, and bulk-synchronous. Comparing to existing methods shows unique benefits of this work, including simplicity of design, suitability for HPC centers, short startup time, and well-understood per-task overhead. All three new tools have been shown to scale to full utilization of Summit, and have been made publicly available with tests and documentation. This work presents a complete characterization of the minimum effective task granularity for efficient scheduler usage scenarios. These schedulers have the same bottlenecks, and hence similar task granularities as those reported for existing tools following comparable paradigms.     

Feedback EDF Scheduling of Real-Time Tasks Exploiting Dynamic Voltage Scaling

Many embedded systems are constrained by limits on power consumption, which are reflected in the design and implementation for conserving their energy utilization. Dynamic voltage scaling (DVS) has become a promising method for embedded systems to exploit multiple voltage and frequency levels and to prolong their battery life. However, pure DVS techniques do not perform well for systems with dynamic workloads where the job execution times vary significantly. In this paper, we present a novel approach combining feedback control with DVS schemes targeting hard real-time systems with dynamic workloads. Our method relies strictly on operating system support by integrating a DVS scheduler and a feedback controller within the earliest-deadline-first (EDF) scheduling algorithm. Each task is divided into two portions. The objective within the first portion is to exploit frequency scaling for the average execution time. Static and dynamic slack is accumulated for each task with slack-passing and preemption handling schemes. The objective within the second portion is to meet the hard real-time deadline requirements up to the worst-case execution time following a last-chance approach. Feedback control techniques make the system capable of selecting the right frequency and voltage settings for the first portion, as well as guaranteeing hard real-time requirements for the overall task. A feedback control model is given to describe our feedback DVS scheduler, which is used to analyze the system's stability. Simulation experiments demonstrate the ability of our algorithm to save up to 29% more energy than previous work for task sets with different dynamic workload characteristics. This work was supported in part by NSF grants CCR-0208581, CCR-0310860 and CCR-0312695. Preliminary versions of parts of this work appeared in the ACM SIGPLAN Joint Conference Languages, Compilers, and Tools for Embedded Systems (LCTES'02) and Software and Compilers for Embedded Systems (SCOPES'02) (Dudani et al., 2002), in the Workshop on Compilers and Operating Systems for Low Power 2002 (Zhu and Mueller, 2002) and in the IEEE Real-Time Embedded Technology and Applications Symposium 2004 (Zhu and Mueller, 2004a).     

Transient solution of multiprocessor systems with state-dependent arrivals

In this paper, the transient solution is obtained for a multiprocessor system with multiple Poisson streams of task and exponential execution times. Each task requires exactly one processor for its execution and the scheduling policy is FCFS. The scheduler schedules a newly arriving task into any one of the idle processors, and the task is rejected if there is no idle processor. For this model, the exact time-dependent solution of system size probabilities at various streams, their means, variances and correlations are obtained using the properties of tridiagonal determinants.     

Scheduling concurrent applications on a cluster of CPU–GPU nodes

Heterogeneous architectures comprising a multi-core CPU and many-core GPU(s) are increasingly being used within cluster and cloud environments. In this paper, we study the problem of optimizing the overall throughput of a set of applications deployed on a cluster of such heterogeneous nodes. We consider two different scheduling formulations. In the first formulation, we consider jobs that can be executed on either the GPU or the CPU of a single node. In the second formulation, we consider jobs that can be executed on the CPU, GPU, or both, of any number of nodes in the system. We have developed scheduling schemes addressing both of the problems. In our evaluation, we first show that the schemes proposed for first formulation outperform a blind round-robin scheduler and approximate the performances of an ideal scheduler that involves an impractical exhaustive exploration of all possible schedules. Next, we show that the scheme proposed for the second formulation outperforms the best of existing schemes for heterogeneous clusters, TORQUE and MCT, by up to 42%. Additionally, we evaluate the robustness of our proposed scheduling policies under inaccurate inputs to account for real execution scenarios. We show that, with up to 20% of inaccuracy in the input, the degradation in performance is marginal (less than 7%) on the average.     

基于层次化的网格资源三层调度模型

在分析现有的资源调度方案及模型的基础上,提出了基于层次化的网格资源三层调度模型．它由主调度器、次级调度器和计算节点组成。主调度器根据任务的性质和需求,并参考下层次级调度器的执行情况,将部分任务分发到各次级调度器上,实现了主调度器与次级调度器之间的并行工作。基于该模型提出轮循任务分发策略。通过分析和模拟．该资源调度模型及任务分发策略在调度性能上明显优于集中式调度方案。     

Preference-oriented real-time scheduling and its application in fault-tolerant systems

In this paper, we consider a set of real-time periodic tasks where some tasks are preferably executed as soon as possible (ASAP) and others as late as possible (ALAP) while still meeting their deadlines. After introducing the idea of preference-oriented (PO) execution, we formally define the concept of PO-optimality. For fully-loaded systems (with 100% utilization), we first propose a PO-optimal scheduler, namely ASAP-Ensured Earliest Deadline (SEED), by focusing on ASAP tasks where the optimality of ALAP tasks’ preference is achieved implicitly due to the harmonicity of the PO-optimal schedules for such systems. Then, for under-utilized systems (with less than 100% utilization), we show the discrepancies between different PO-optimal schedules. By extending SEED, we propose a generalized Preference-Oriented Earliest Deadline (POED) scheduler that can obtain a PO-optimal schedule for any schedulable task set. The application of the POED scheduler in a dual-processor fault-tolerant system is further illustrated. We evaluate the proposed PO-optimal schedulers through extensive simulations. The results show that, comparing to that of the well-known EDF scheduler, the scheduling overheads of SEED and POED are higher (but still manageable) due to the additional consideration of tasks’ preferences. However, SEED and POED can achieve the preference-oriented execution objectives in a more successful way than EDF.     

Parallel evidence propagation on multicore processors

We propose a parallel evidence propagation method on general-purpose multicore processors. Evidence propagation is a major step in exact inference, a key problem in exploring probabilistic graphical models. We explore the parallelism in evidence propagation at various levels. First, given an arbitrary junction tree, we construct a directed acyclic graph (DAG) with weighted nodes, each denoting a computation task for evidence propagation. Since the execution time of the tasks varies significantly, we develop a workload-aware scheduler to allocate the tasks to the cores of the processors. The scheduler monitors the workload of each core and dynamically allocates tasks to support load balance across the cores. In addition, we integrate a module in the scheduler to partition the tasks converted from cliques with large potential tables so as to achieve improved load balance. We implemented the proposed method using Pthreads on both AMD and Intel quadcore processors. For a representative set of junction trees, our method achieved almost linear speedup. The execution time of our method was around twice as fast as an OpenMP-based implementation on both the platforms.     

多道相关任务系统的一种并行调度方法*

该文针对分布式系统提出了一种描述任务动态特征的数据结构指派表AT(assignment table)及一个并行调度算法DRA(dynamic readjusting algorithm).经仿真运行,证明该算法能使分布式系统的并行处理能力得到提高.