An optimal boundary fair scheduling algorithm for multiprocessor real-time systems

With the emergence of multicore processors, the research on multiprocessor real-time scheduling has caught more researchers’ attention recently. Although the topic has been studied for decades, it is still an evolving research field with many open problems. In this work, focusing on periodic real-time tasks with quantum-based computation requirements and implicit deadlines, we propose a novel optimal scheduling algorithm, namely boundary fair (Bfair), which can achieve full system utilization as the well-known Pfair scheduling algorithms. However, different from Pfair algorithms that make scheduling decisions and enforce proportional progress (i.e., fairness) for all tasks at each and every time unit, Bfair makes scheduling decisions and enforces fairness to tasks only at tasks’ period boundaries (i.e., deadlines of periodic tasks). The correctness of the Bfair algorithm to meet the deadlines of all tasks’ instances is formally proved and its performance is evaluated through extensive simulations. The results show that, compared to that of Pfair algorithms, Bfair can significantly reduce the number of scheduling points (by up to 94%) and the overhead of Bfair at each scheduling point is comparable to that of the most efficient Pfair algorithm (i.e., PD²). Moreover, by aggregating the time allocation of tasks for the time interval between consecutive period boundaries, the resulting Bfair schedule can dramatically reduce the number of required context switches and task migrations (as much as 82% and 85%, respectively) when compared to those of Pfair schedules, which in turn reduces the run-time overhead of the system.     

An evolutionary algorithm for generalized comparison-based self-diagnosis of multiprocessor systems

In this article, we consider the problem of self-diagnosis of multiprocessor and multicomputer systems under the generalized comparison model. In this approach, a system consists of a collection n independent heterogeneous processors (or units) interconnected via point-to-point communication links, and it is assumed that at most t of these processors are permanently faulty. For the purpose of diagnosis, system tasks are assigned to pairs of processors and the results are compared. The agreements and disagreements among units are the basis for identifying faulty processors. Such a system is said to be t-diagnosable if, given any complete collection of comparison results, the set of faulty processors can be unambiguously identified. We present an efficient fault identification method based on genetic algorithms. Analysis and simulations are provided, first, to evaluate the genetic parameters of the diagnosis algorithm; second, to show the efficiency of the genetic approach. The new strategy is shown to correctly identify the set of faulty processors, making it an attractive and viable addition or alternative to present fault diagnosis techniques.     

An optimal algorithm for global termination detection inshared-memory asynchronous multiprocessor systems

In the literature, the problem of global termination detection in parallel systems is usually solved by message passing. In shared-memory systems, this problem can also be solved by using exclusively accessible variables with locking mechanisms. In this paper, we present an algorithm that solves the problem of global termination detection in shared-memory asynchronous multiprocessor systems without using locking. We assume a reasonable computation model in which concurrent reading does not require locking and concurrent writing different values without locking results in an arbitrary one of the values being actually written. For a system of n processors, the algorithm allocates a working space of 2n+1 bits. The worst case time complexity of the algorithm is n+2√+1, which we prove is the lower bound under a reasonable model of computation     

A Spark-based Apriori algorithm with reduced shuffle overhead

The Journal of Supercomputing - Mining frequent itemset is considered as a core activity to find association rules from transactional datasets. Among the different well-known approaches to find...     

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     

Decentralised sampled-data control for large-scale systems with nonlinear interconnections

This paper presents a decentralised sampled-data control technique for a class of large-scale systems, which are considered to consist of linear subsystems and nonlinear interconnections. The decentralised sampled-data controller design problem is established using a closed-loop subsystem. Based on the controller design problem, the stability condition is derived for a closed-loop large-scale system, and the maximum interconnection bound is guaranteed to satisfy the stability condition. Also, its sufficient condition is formulated in terms of linear matrix inequalities. Finally, the effectiveness of the proposed technique is verified by using an example of the multi-machine power system.     

Queuing simulation model for multiprocessor systems

The processor queuing model provides memory-hierarchy and system-design evaluation of memory-intensive commercial online-transaction-processing workloads on large multiprocessor systems. It differs from detailed cycle-accurate and direct-execution simulations in that it does not simulate instruction execution. Instead, as in analytical models, the authors build processor and workload characteristics that are easy to collect and estimate. Because the authors believe that the processor model's function is to accurately generate memory traffic to the rest of the system, they model a minimal set of processor and workload characteristics that captures the important interactions between a complex processor and the system-memory hierarchy.     

粒子群优化多处理机任务调度算法

提出基于粒子群优化的多处理机调度算法,采用列表调度,同时把粒子群的矢量表达方式转换为基于调度优先级的模型。调度结果显示能提高全局搜索能力,加快进化速度,优于模拟退火等启发式算法结果。     

Decentralized output-feedback neural control for systems with unknown interconnections.

An adaptive backstepping neural-network control approach is extended to a class of large-scale nonlinear output-feedback systems with completely unknown and mismatched interconnections. The novel contribution is to remove the common assumptions on interconnections such as matching condition, bounded by upper bounding functions. Differentiation of the interconnected signals in backstepping design is avoided by replacing the interconnected signals in neural inputs with the reference signals. Furthermore, two kinds of unknown modeling errors are handled by the adaptive technique. All the closed-loop signals are guaranteed to be semiglobally uniformly ultimately bounded, and the tracking errors are proved to converge to a small residual set around the origin. The simulation results illustrate the effectiveness of the control approach proposed in this correspondence.     

Globally scheduled real-time multiprocessor systems with GPUs

Graphics processing units, GPUs, are powerful processors that can offer significant performance advantages over traditional CPUs. The last decade has seen rapid advancement in GPU computational power and generality. Recent technologies make it possible to use GPUs as co-processors to CPUs. The performance advantages of GPUs can be great, often outperforming traditional CPUs by orders of magnitude. While the motivations for developing systems with GPUs are clear, little research in the real-time systems field has been done to integrate GPUs into real-time multiprocessor systems. We present two real-time analysis methods, addressing real-world platform constraints, for such an integration into a soft real-time multiprocessor system and show that a GPU can be exploited to achieve greater levels of total system performance.     

Practical prefetching techniques for multiprocessor file systems

Improvements in the processing speed of multiprocessors are outpacing improvements in the speed of disk hardware. Parallel disk I/O subsystems have been proposed as one way to close the gap between processor and disk speeds. In a previous paper we showed that prefetching and caching have thepotential to deliver the performance benefits of parallel file systems to parallel applications. In this paper we describe experiments withpractical prefetching policies that base decisions only on on-line reference history, and that can be implemented efficiently. We also test the ability of those policies across a range of architectural parameters.     

Spin-based reader-writer synchronization for multiprocessor real-time systems

Reader preference, writer preference, and task-fair reader-writer locks are shown to cause undue blocking in multiprocessor real-time systems. Phase-fair reader writer locks, a new class of reader-writer locks, are proposed as an alternative. Three local-spin phase-fair lock algorithms, one with constant remote-memory-reference complexity, are presented and demonstrated to be efficiently implementable on common hardware platforms. Both task- and phase-fair locks are evaluated and contrasted to mutex locks in terms of hard and soft real-time schedulability—each under both global and partitioned scheduling—under consideration of runtime overheads on a multicore Sun “Niagara” UltraSPARC T1 processor. Formal bounds on worst-case blocking are derived for all considered lock types.     

Energy-aware task migration for multiprocessor real-time systems

A task migration method is proposed for energy savings in multiprocessor real-time systems. The method is based on the portioned scheduling technique which classifies each task as a fixed task or a migratable task. The basic task migration problem with specific parameters is formulated as a linear programming problem to minimize average power. Then, the method is extended to more general case with a complete migration algorithm. Moreover, a scheduling algorithm is proposed for migratable tasks. Simulation results on two processor models demonstrated significant energy savings over existing methods.     

B-banyan and B-delta networks for multiprocessor systems

A new class of graphs, B-banyan, and a new class of multistage interconnection networks based on B-banyans, B-delta networks, in multiprocessor environments are proposed in this paper. A B-banyan is a regular rectangular SW-banyan augmented with a backward link at each vertex, in a way that preserves the destination control. A backward link can be taken when there is a conflict at a node, or when a faulty link or node is encountered. As such, backward links in B-delta networks significantly increase the network performance while at the same time providing a degree of fault tolerance. The performance of B-delta networks is analyzed and shown to be comparable to that of single-buffered delta networks. Different switches and control complexities of these two types of delta networks are discussed.     

Predictable synchronization mechanisms for multiprocessor real-time systems

Predictability is of paramount concern for hard real-time systems. In one approach to predictability, every aspect of a real-time system and every primitive provided by the underlying operating system must be bounded and predictable in order to achieve overall predictability. In this paper, we describe several concurrency control synchronization mechanisms developed for a next generation multiprocessor real-time kernel, the Spring Kernel. The important features of these mechanisms include semaphore support for mutual exclusion with linear waiting and bounded resource usage, termed strong semaphores. Three, more efficient, strong semaphore solutions are proposed in this paper. Two of them are based on the main theorem of the paper, the Deferred Bus theorem. These two solutions can either be implemented in hardware or software. The third solution, a pure software solution, is an extension to the existing Burns' algorithm. A performance comparison and a complexity analysis in terms of time, space and bus traffic are presented.This work is part of the Spring Project directed by Prof. Krithi Ramamritham and Prof. John A. Stankovic at the University of Massachusetts and is funded in part by the Office of Naval Research under contract N00014-85-K-0398 and by the National Science Foundation under grant DCR-8500332.