Improved priority assignment for global fixed priority pre-emptive scheduling in multiprocessor real-time systems

This paper is an extended version of a paper that appeared in the proceedings of the IEEE Real-Time Systems Symposium 2009. This paper has been updated with respect to advances made in schedulability analysis, and contains a number of significant additional results.     

Resource sharing among real-time components under multiprocessor clustered scheduling

In this paper we propose a general synchronization protocol for resource sharing among independently-developed real-time applications (components) on multi-core platforms. This protocol is a generalization of a previously proposed synchronization protocol (MSOS). In our proposed protocol, each component is statically allocated on a dedicated subset of processors (called cluster). A component has its own internal scheduler by which its tasks are scheduled. In this paper we focus on multiprocessor global fixed-priority preemptive scheduling algorithms to be used to schedule the tasks inside each component. Sharing the local resources is handled by the Priority Inheritance Protocol (PIP). For sharing the global resources (inter-component resource sharing) we have studied usage of FIFO and Round-Robin queues for access the resources across the components and usage of FIFO and prioritized queues inside the components. We have derived schedulability analysis for the different queue handling alternatives and compared their performance by using experimental evaluations. Finally, we have shown that the integration phase can be formulated in the form of a nonlinear integer programming problem where solution techniques in this domain can be used to minimize the total number of processors required to guarantee the schedulability of all components. As a proof of concept we have only provided the formulation for FIFO queues.     

Cache-conscious off-line real-time scheduling for multi-core platforms: algorithms and implementation

Real-Time Systems - Most schedulability analysis techniques for multi-core architectures assume a single worst-case execution time (WCET) per task, which is valid in all execution conditions. This...     

多处理器全局单调比率的可调度性分析

针对全局单调比率(RM)调度的多处理器系统中最高优先级任务数量少于处理器数量时,Bertogna等给出的最坏情况计算任务受到的干涉过于悲观,证明了任务受到最高优先级任务的干涉不会出现最坏情况,它受到非最高优先级任务干涉仍可能出现最坏情况。分析得出了任务受到最高优先级任务干涉的最大可能值,由此得到了一个更紧的可调度性判断条件。实验结果表明,提出的方法提高了判为可调度的任务集数量。     

Stretching algorithm for global scheduling of real-time DAG tasks

Real-Time Systems - Parallelism is becoming more important nowadays due to the increasing use of multiprocessor systems. A Directed Acyclic Graph (DAG) is a general model of parallel tasks with...     

Control latency for task assignment and scheduling of multiprocessor real-time control systems

For task assignment and scheduling problems of multiprocessor real-time control systems, a new performance index called the control latency, is proposed. In order to ensure smooth operation and good performance of real-time control systems, one must analyse the problem of combined task assignment and scheduling during the conceptual system design stage. The proposed performance index, the control latency, is defined as a weighted sum of feedback, command and monitoring latencies. Given a set of tasks for a specific control application, each task execution time and intra-/interprocessor communication latencies, an algorithm for combined task assignment and scheduling can be solved by minimizing this performance index, thereby providing the minimum time delay and best performance.     

On the configuration-LP for scheduling on unrelated machines

Closing the approximability gap between \(3/2\) and 2 for the minimum makespan problem on unrelated machines is one of the most important open questions in scheduling. Almost all known approximation algorithms for the problem are based on linear programs (LPs). In this paper, we identify a surprisingly simple class of instances which constitute the core difficulty for LPs: the so far hardly studied unrelated graph balancing case in which each job can be assigned to at most two machines. We prove that already for this basic setting the strongest LP-relaxation studied so far—the configuration-LP—has an integrality gap of 2, matching the best known approximation factor for the general case. This points toward an interesting direction of future research. For the objective of maximizing the minimum machine load in the unrelated graph balancing setting, we present an elegant purely combinatorial 2-approximation algorithm with only quadratic running time. Our algorithm uses a novel preprocessing routine that estimates the optimal value as good as the configuration-LP. This improves on the computationally costly LP-based algorithm by Chakrabarty et al. (Proceedings of the 50th Annual Symposium on Foundations of Computer Science (FOCS 2009), pp 107–116, 2009) that achieves the same approximation guarantee.     

魂芯分簇VLIW DSP上指令调度的优化

魂芯DSP处理器是一款32 bit静态超标量、分簇结构的、支持SIMD的VLIW处理器。魂芯DSP芯片有4个执行簇和3个内存块,但簇间数据传输和寻址会占用总线带宽。魂芯DSP上每个簇中有大量的计算部件,但是现有的编译器框架中指令调度算法是针对非分簇结构的,无法充分利用魂芯DSP的分簇结构特点,产生出高效的指令级并行代码。根据魂芯处理器架构分簇的特点,提出了在魂芯DSP上进行指令分簇和指令调度的启发式算法,并且在开源Open64编译器框架上进行了实现。实验结果表明,该算法在魂芯DSP编译器上的实现可以显著提高一些在DSP上有着计算密集型程序的性能。     

Pragmatic integrated scheduling for clustered VLIW architectures

Clustered architecture processors are preferred for embedded systems because centralized register file architectures scale poorly in terms of clock rate, chip area, and power consumption. Scheduling for clustered architectures involves spatial concerns (where to schedule) as well as temporal concerns (when to schedule). Various clustered VLIW configurations, connectivity types, and inter‐cluster communication models present different performance trade‐offs to a scheduler. The scheduler is responsible for resolving the conflicting requirements of exploiting the parallelism offered by the hardware and limiting the communication among clusters to achieve better performance. In this paper, we describe our experience with developing a pragmatic scheme and also a generic graph‐matching‐based framework for cluster scheduling based on a generic and realistic clustered machine model. The proposed scheme effectively utilizes the exact knowledge of available communication slots, functional units, and load on different clusters as well as future resource and communication requirements known only at schedule time. The proposed graph‐matching‐based framework for cluster scheduling resolves the phase‐ordering and fixed‐ordering problem associated with earlier schemes for scheduling clustered VLIW architectures. The experimental evaluation in the context of a state‐of‐art commercial clustered architecture (using real‐world benchmark programs) reveals a significant performance improvement over the earlier proposals, which were mostly evaluated using compiled simulation of hypothetical clustered architectures. Our results clearly highlight the importance of considering the peculiarities of commercial clustered architectures and the hard‐nosed performance measurement. Copyright © 2007 John Wiley & Sons, Ltd.     

High-fidelity real-time simulation on deployed platforms

We present a certified reduced basis method for high-fidelity real-time solution of parametrized partial differential equations on deployed platforms. Applications include in situ parameter estimation, adaptive design and control, interactive synthesis and visualization, and individuated product specification. We emphasize a new hierarchical architecture particularly well suited to the reduced basis computational paradigm: the expensive Offline stage is conducted pre-deployment on a parallel supercomputer (in our examples, the TeraGrid machine Ranger); the inexpensive Online stage is conducted “in the field” on ubiquitous thin/inexpensive platforms such as laptops, tablets, smartphones (in our examples, the Nexus One Android-based phone), or embedded chips. We illustrate our approach with three examples: a two-dimensional Helmholtz acoustics “horn” problem; a three-dimensional transient heat conduction “Swiss Cheese” problem; and a three-dimensional unsteady incompressible Navier–Stokes low-Reynolds-number “eddy-promoter” problem.     

Distributed algorithmic mechanism design for scheduling on unrelated machines

In classical mechanism design the outcome of the mechanism is computed by a trusted central party. In this paper, we consider the design of distributed mechanisms in which the outcome is computed by the agents themselves. We propose Distributed MinWork (DMW), a mechanism for solving the problem of scheduling on unrelated machines. We show that DMW is a faithful implementation of the MinWork mechanism, which was proposed by Nisan and Ronen in their seminal work (Nisan and Ronen (2001) [30]). We show that in addition to being faithful, DMW protects the anonymity of the losing agents and the privacy of their bids. Furthermore, we show that DMW is efficient as it has polynomial communication and computation costs.     

Queue-based local scheduling and global coordination for real-time operation control in a container terminal

To maximize the productivity of a container terminal, the operations of various types of equipments should be optimized and synchronized in real time. However, use of optimization techniques such as mathematical programming or search-based meta-heuristics becomes difficult when given a large-scaled problem due to their high computational cost. Addressing this problem, the queue-based local scheduling and global coordination method proposed in this paper stands as a viable alternative. The method consists of the following steps. First, separate schedules are locally generated for each equipment type using a queue-based dispatching heuristic which pays attention to the queue lengths of the quay cranes (QCs) under service. Next, the schedules are executed via a simulation and a notable QC delay is identified. Based on the analysis on the causes of this delay, some compromising adjustments are made to the priorities of relevant jobs. Then, the localized scheduling followed by the adjustment is repeated until the termination condition is met. Adopting simple heuristics in the local scheduling phase, the overall process easily meets the real-time constraint, yet producing an integrated schedule with a better global perspective than the myopic heuristic-only approach.     

Implementation and evaluation of global and partitioned scheduling in a real-time OS

In this work, we provide an experimental comparison between Global-EDF and Partitioned-EDF, considering the run-time overhead of a real-time operating system (RTOS). Recent works have confirmed that OS implementation aspects, such as the choice of scheduling data structures and interrupt handling mechanisms, impact real-time schedulability as much as scheduling theoretic aspects. However, these studies used real-time patches applied into a general-purpose OS. By measuring the run-time overhead of an RTOS designed from scratch, we show how close the schedulability ratio of task sets is to the theoretical hard real-time schedulability tests. Moreover, we show how a well-designed object-oriented RTOS allows code reuse of scheduling components (e.g., thread, scheduling criteria, and schedulers) and easy real-time scheduling extensions. We compare our RTOS to a real-time patch for Linux in terms of the task set schedulability ratio of several generated task sets. In some cases, Global-EDF considering the overhead of the RTOS is superior to Partitioned-EDF considering the overhead of the patched Linux, which clearly shows how different OSs impact hard real-time schedulers.     

Evolutionary resource assignment for workload-based production scheduling

In this paper, we propose an evolutionary method with a simulation model for scheduling jobs including operations specified in terms of workload rather than processing time. It is suggested that processing times should be determined according to the number of assigned resources rather than the workload. The simulation model is used to estimate the result of resource allocation in a time horizon based on preselected rules. The evolutionary methods improve a production schedule in terms of compliance with due dates by selecting an alternative resource allocation rule and changing timing constraints. The results of computational experiments show that compliance with due dates improved by as much as 30 % under the modified production schedule over the initial schedule.     

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

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

Semaphore queue priority assignment for real-time multiprocessorsynchronization

Prior work on real time scheduling with global shared resources in multiprocessor systems assigns as much blocking as possible to the lowest priority tasks. We show that better schedulability can be achieved if global blocking is distributed according to the blocking tolerance of tasks rather than their execution priorities. We describe an algorithm that assigns global semaphore queue priorities according to blocking tolerance, and we present simulation results demonstrating the advantages of this approach with rate monotonic scheduling. Our simulations also show that a simple FIFO usually provides better real time schedulability with global semaphores than priority queues that use task execution priorities     

Lower-bound time-complexity greening mechanism for duplication-based scheduling on large-scale computing platforms

The Journal of Supercomputing - Large-scale computing platforms become essential in nowadays business and scientific activities. The electrical energy consumed by such platforms increases...     

Efficient scheduling algorithms for real-time multiprocessorsystems

Efficient scheduling algorithms based on heuristic functions are developed for scheduling a set of tasks on a multiprocessor system. The tasks are characterized by worst-case computation times, deadlines, and resources requirements. Starting with an empty partial schedule, each step of the search extends the current partial schedule by including one of the tasks yet to be scheduled. The heuristic functions used in the algorithm actively direct the search for a feasible schedule, i.e. they help choose the task that extends the current partial schedule. Two scheduling algorithms are evaluated by simulation. To extend the current partial schedule, one of the algorithms considers, at each step of the search, all the tasks that are yet to be scheduled as candidates. The second focuses its attention on a small subset of tasks with the shortest deadlines. The second algorithm is shown to be very effective when the maximum allowable scheduling overhead is fixed. This algorithm is hence appropriate for dynamic scheduling in real-time systems