The partitioned scheduling of sporadic task systems on multiprocessors

Abstract The DBF ^* algorithm of sporadic task systems on multiprocessors uses the approximation of the exact demand bound function on uniprocessor as a criterion. The systems which are feasible under the partitioned paradigm are flagged as “infeasible” sometimes. In this paper, we present a novel efficient DBF(eDBF) partitioned scheduling algorithm. A criterion which tracks the demand bound function exactly as needed is used to avoid the incorrect judgment in determining whether a processor can accommodate an additional task in the new algorithm. We give the pseudo code of the new algorithm on least-number processors and fixed-number processors respectively. Then, we prove the correctness of, and evaluated the effectiveness of this new algorithm. The experimental results demonstrate that eDBF has better performance than DBF ^* and Density algorithms.     

Efficiently tolerating failures in asynchronous real-time distributed systems

We present a proactive resource allocation algorithm, called BEA, for fault-tolerant asynchronous real-time distributed systems. BEA considers an application model where trans-node application timeliness requirements are expressed using benefit functions, and anticipated workload during future time intervals are expressed using adaptation functions. Furthermore, BEA considers an adaptation model where subtasks of application tasks are replicated at run-time for tolerating failures as well as for sharing workload increases. Given such models, the objective of the algorithm is to maximize the aggregate real-time benefit and the ability to tolerate host failures during the time window of adaptation functions. Since determining the optimal solution is computationally intractable, BEA heuristically computes suboptimal resource allocations in polynomial-time. We show that BEA can achieve almost the same fault-tolerance ability as full replication, and accrue most of real-time benefit that full replication can accrue. In the meanwhile, BEA requires much fewer replicas than full replication, and hence is cost effective.     

Performing tasks on synchronous restartable message-passing processors

Summary. This work considers the problem of performing t tasks in a distributed system of p fault-prone processors. This problem, called do-all herein, was introduced by Dwork, Halpern and Waarts. The solutions presented here are for the model of computation that abstracts a synchronous message-passing distributed system with processor stop-failures and restarts. We present two new algorithms based on a new aggressive coordination paradigm by which multiple coordinators may be active as the result of failures. The first algorithm is tolerant of stop-failures and does not allow restarts. Its available processor steps (work) complexity is and its message complexity is . Unlike prior solutions, our algorithm uses redundant broadcasts when encountering failures and, for p =t and largef, it achieves better work complexity. This algorithm is used as the basis for another algorithm that tolerates stop-failures and restarts. This new algorithm is the first solution for the do-all problem that efficiently deals with processor restarts. Its available processor steps is , and its message complexity is , wheref is the total number of failures. Received: October 1998 / Accepted: September 2000     

A Task Allocation Method for Stream Processing with Recovery Latency Constraint

Stream processing applications continuously process large amounts of online streaming data in real time or near real time. They have strict latency constraints. However, the continuous processing makes them vulnerable to any failures, and the recoveries may slow down the entire processing pipeline and break latency constraints. The upstream backup scheme is one of the most widely applied fault-tolerant schemes for stream processing systems. It introduces complex backup dependencies to tasks, which increases the difficulty of controlling recovery latencies. Moreover, when dependent tasks are located on the same processor, they fail at the same time in processor-level failures, bringing extra recovery latencies that increase the impacts of failures. This paper studies the relationship between the task allocation and the recovery latency of a stream processing application. We present a correlated failure effect model to describe the recovery latency of a stream topology in processor-level failures under a task allocation plan. We introduce a recovery-latency aware task allocation problem (RTAP) that seeks task allocation plans for stream topologies that will achieve guaranteed recovery latencies. We discuss the difference between RTAP and classic task allocation problems and present a heuristic algorithm with a computational complexity of O(n log² n) to solve the problem. Extensive experiments were conducted to verify the correctness and effectiveness of our approach. It improves the resource usage by 15%–20% on average.     

Incremental compiler transformations for multiple instruction retry

Previous work on compiler-based multiple instruction retry has utilized a series of compiler transformations, loop protection, node splitting, and loop expansion, to eliminate anti-dependencies of length ≤ N in the pseudo register, the machine register, and the post-pass resolver phases of compilation.¹ The results have provided a means of rapidly recovering from transient processor failures by rolling back N instructions. This paper presents techniques for improving compilation and run-time performance in compiler-based multiple instruction retry. Incremental updating enhances compilation time when new instructions are added to the program. Post-pass code rescheduling and spill register reassignment algorithms improve the run-time performance and decrease the code growth across the application programs studied. Branch hazards are shown to be resolvable by simple modifications to the incremental updating schemes during the pseudo register phase and to the spill register reassignment algorithm during the post-pass phase.     

Optimal virtual cluster-based multiprocessor scheduling

Scheduling of constrained deadline sporadic task systems on multiprocessor platforms is an area which has received much attention in the recent past. It is widely believed that finding an optimal scheduler is hard, and therefore most studies have focused on developing algorithms with good processor utilization bounds. These algorithms can be broadly classified into two categories: partitioned scheduling in which tasks are statically assigned to individual processors, and global scheduling in which each task is allowed to execute on any processor in the platform. In this paper we consider a third, more general, approach called cluster-based scheduling. In this approach each task is statically assigned to a processor cluster, tasks in each cluster are globally scheduled among themselves, and clusters in turn are scheduled on the multiprocessor platform. We develop techniques to support such cluster-based scheduling algorithms, and also consider properties that minimize total processor utilization of individual clusters. In the last part of this paper, we develop new virtual cluster-based scheduling algorithms. For implicit deadline sporadic task systems, we develop an optimal scheduling algorithm that is neither Pfair nor ERfair. We also show that the processor utilization bound of us-edf{m/(2m−1)} can be improved by using virtual clustering. Since neither partitioned nor global strategies dominate over the other, cluster-based scheduling is a natural direction for research towards achieving improved processor utilization bounds.

Efficient parallel term matching and anti-unification

In this paper we present optimal processor x time parallel algorithms for term matching and anti-unification of terms represented as trees. Term matching is the special case of unification in which one of the terms is restricted to contain no variables. It has wide applicability to logic programming, term rewriting systems and symbolic pattern matching. Anti-unification is the dual problem of unification in which one computes the most specific generalization of two terms. It has application to inductive inference and theorem proving. Our algorithms run in O(log² N) time using N/log² N processors on a shared-memory model of computation that prohibits simultaneous reads or writes (EREW PRAM). These algorithms are the first polylogarithmic-time EREW algorithms with a processor x time product of the same order as that of their sequential counterparts, thereby permitting optimal speed-ups using any number of processors up to N/log² N. We also use the techniques developed in the paper to provide an N/log N-processor, O(log N)-time algorithm for a shared-memory model that allows both simultaneous reads and simultaneous writes (CRCW PRAM).Supported by NSF Grant IRI-88-09324 and NSF/DARPA Grant CCR-8908092.     

Heuristic search for scheduling flexible manufacturing systems using lower bound reachability matrix

For scheduling flexible manufacturing systems efficiently, we propose new heuristic functions for A^* algorithm that is based on the T-timed Petri net. In minimizing makespan, the proposed heuristic functions are usually more efficient than the previous functions in the required number of states and computation time. We prove that these heuristic functions are all admissible and one of them is more informed than that using resource cost reachability matrix. We also propose improved versions of these heuristic functions that find a first near-optimal solution faster. In addition, we modify the heuristic function of Yu, Reyes, Cang, and Lloyd (2003b) and propose an admissible version in all states. The experimental results using a random problem generator show that the proposed heuristic functions perform better as we expected.     

Enumerate and Expand: Improved Algorithms for Connected Vertex Cover and Tree Cover

We present a new method of solving graph problems related to Vertex Cover by enumerating and expanding appropriate sets of nodes. As an application, we obtain dramatically improved runtime bounds for two variants of the Vertex Cover problem. In the case of Connected Vertex Cover, we take the upper bound from O ^*(6 ^k ) to O ^*(2.7606 ^k ) without large hidden factors. For Tree Cover, we show a complexity of O ^*(3.2361 ^k ), improving over the previous bound of O ^*((2k) ^k ). In the process, faster algorithms for solving subclasses of the Steiner tree problem on graphs are investigated. Supported by the DFG under grant RO 927/6-1 (TAPI).     

Fault-Tolerant Dynamic Rescheduling for Heterogeneous Computing Systems

As the scale and complexity of heterogeneous computing systems grow, failures occur frequently and have an adverse effect on solving large-scale applications. Hence, fault-tolerant scheduling is an imperative step for large-scale computing systems. The existing fault-tolerant scheduling algorithms belong to static scheduling, and they allocate multiple copies of each task to several processors no matter whether processor failures affect the execution of tasks. Such active replication strategies not only waste resource but also sacrifice the makespan. What is more, they cannot guarantee the successful execution of applications. In this paper, we propose a fault-tolerant dynamic rescheduling algorithm named FTDR, which can overcome above drawbacks. FTDR keeps listening to the processor failure, and reschedules the suspended tasks once failures occur. Because FTDR reschedules the tasks that are suspended because of failures, it can tolerate an arbitrary number of failures. Randomly generated DAGs are tested in our experiments. Experimental results show that the proposed algorithm achieves good performance in terms of makespan and resource consumption compared with its direct competitors.     

An adaptive load distribution algorithm for resolving bursty workload

Most existing dynamic load distribution (LD) algorithms assume fairly stable task arrival pattern. With this assumption, single task assignments are adequate to provide reasonably good performance. They are, however, inadequate when tasks arrive in bursts. In this paper, we propose a LD algorithm based on batch task assignments. The algorithm is tailored to systems subject to bursty workload. The key of this algorithm is the dynamic negotiation on the amount of workload to be transferred between a sender–receiver pair. Dynamic negotiations ensure the algorithm's adaptive behavior, thus allow task congestions to be resolved quickly. Consequently, CPU utilization can be increased and average task response time reduced substantially. The dynamic negotiations are conducted by the GR Protocol, which also avoids processor thrashing and state waggling – two undesirable phenomena that commonly exist in LD algorithms. © 1999 John Wiley & Sons, Ltd.     

Efficient parallel algorithms can be made robust

Summary The efficient parallel algorithms proposed for many fundamental problems, such as list ranking, integer sorting and computing preorder numberings on trees, are very sensitive to processor failures. The requirement of efficiency (commonly formalized usingParallel-timexProcessors as a cost measure) has led to the design of highly tuned PRAM algorithms which, given the additional constraint of simple processor failures, unfortunately become inefficient or even incorrect. We propose a new notion ofrobustness, that combines efficiency with fault tolerance. For the common case of fail-stop errors, we develop a general and easy to implement technique to make robust many efficient parallel algorithms, e.g., algorithms for all the problems listed above. More specifically,for any dynamic pattern of fail-stop errors on a CRCW PRAMwith at least one surviving processor, our method increases the original algorithm cost by at most a log² multiplicative factor. Our technique is based on a robust solution of the problem ofWrite-All, i.e., usingP processors, write 1's in all locations of anN-sized array. In addition we show that at least a log/log log multiplicative overhead will be incurred for certain patterns of failures by any algorithm that implements robust solutions toWrite-All withP=N. However, by exploiting parallel slackness, we obtain an optimal cost algorithm when Paris C. Kanellakis is a professor of computer science at Brown University. His primary research interests are in the application of logic to computer science, such as high-level query languages for database systems, parallel evaluation of logic programs, and type inference for programming languages. He has published many articles on these subjects and is the author of the chapter Elements of Relational Database Theory in theHandbook of Theoretical Computer Science (Elsevier, 1990). He has also contributed to the theory of distributed computing and to combinatorial optimization. Alex Allister Shvartsman is an engineer at Digital Equipment Corporation. His professional interests include design and development of efficient distributed systems, distributed resource management, and theoretical foundations of fault-tolerant parallel computation. At Digital he architected and managed the development of distributed control systems that automated several of Digital's manufacturing processes. He is currently on an academic leave at Brown University.An extended abstract of a part of this work appears as: Kanellakis and Shvartsman (1989) in the Proceedings of the 8th ACM Symposium on Principles of Distributed Computing, Edmonton 1989This author was supported by NSF grant IRI-8617344, an Alfred P. Sloan fellowship and ONR grant N00014-83-K-0146 ARPA Order No. 4786This author was supported by DEC GEEP Doctoral program and ONR grant N00014-91-J-1613     

Redundant modeling in permutation weighted constraint satisfaction problems

In classical constraint satisfaction, redundant modeling has been shown effective in increasing constraint propagation and reducing search space for many problem instances. In this paper, we investigate, for the first time, how to benefit the same from redundant modeling in weighted constraint satisfaction problems (WCSPs), a common soft constraint framework for modeling optimization and over-constrained problems. Our work focuses on a popular and special class of problems, namely, permutation problems. First, we show how to automatically generate a redundant permutation WCSP model from an existing permutation WCSP using generalized model induction. We then uncover why naively combining mutually redundant permutation WCSPs by posting channeling constraints as hard constraints and relying on the standard node consistency (NC*) and arc consistency (AC*) algorithms would miss pruning opportunities, which are available even in a single model. Based on these observations, we suggest two approaches to handle the combined WCSP models. In our first approach, we propose m\text -NC_{\text c}^*m\text {-NC}_{\text c}^* and m\text -AC_{\text c}^*m\text {-AC}_{\text c}^* and their associated algorithms for effectively enforcing node and arc consistencies in a combined model with m sub-models. The two notions are strictly stronger than NC* and AC* respectively. While the first approach specifically refines NC* and AC* so as to apply to combined models, in our second approach, we propose a parameterized local consistency LB(m,Φ). The consistency can be instantiated with any local consistency Φ for single models and applied to a combined model with m sub-models. We also provide a simple algorithm to enforce LB(m,Φ). With the two suggested approaches, we demonstrate their applicabilities on several permutation problems in the experiments. Prototype implementations of our proposed algorithms confirm that applying 2\text -NC_{\text c}^*,  2\text -AC_{\text c}^*2\text {-NC}_{\text c}^*,\;2\text {-AC}_{\text c}^*, and LB(2,Φ) on combined models allow far more constraint propagation than applying the state-of-the-art AC*, FDAC*, and EDAC* algorithms on single models of hard benchmark problems.     

A Hierarchical Extension of the <Emphasis Type="Italic">D</Emphasis><Superscript>*</Superscript> Algorithm

In this paper a contribution to the practice of path planning using a new hierarchical extension of the D^* algorithm is introduced. A hierarchical graph is stratified into several abstraction levels and used to model environments for path planning. The hierarchical D^* algorithm uses a down-top strategy and a set of pre-calculated trajectories in order to improve performance. This allows optimality and specially lower computational time. It is experimentally proved how hierarchical search algorithms and on-line path planning algorithms based on topological abstractions can be combined successfully.     

基于多启发式信息融合的攻击路径发现算法研究

攻击路径发现对于提高信息系统安全具有重要意义,传统攻击路径发现技术存在考虑因素有限以及可扩展性不高的问题,导致其在网络攻击复杂化和网络规模扩大化的趋势下应用价值有限。针对该问题,本文提出一种基于多启发式信息融合的攻击路径发现算法,该算法结合攻击路径发现背景知识,将漏洞威胁程度,漏洞成功率以及主机资产作为启发式函数计算依据引导攻击路径搜索,达到减少搜索范围、提高路径可用性的目的;并且基于SMHA^*（Share Multi-Heuristic A^*,SMHA^*）框架实现多种启发式信息融合,共同引导攻击路径搜索。通过与现有规划算法进行对比实验,验证了本算法能够更加灵活而全面地考虑攻击路径发现中的现实因素,且规划效率也能够满足实际需求,能够有效提高规划结果的可行性以及应用价值。     

Dynamic processor allocation in scalable multiprocessors using boolean algebra *

In this paper, we study a new model for dynamic processor allocation in k-ary n-dimensional mesh or torus multiprocessors. The model uses Boolean functions to represent free processors and allocates processors by applying Boolean operations on the functions. The processor allocation algorithms based on the Boolean model can be implemented easily using binary decision diagrams(BDDs)and related software packages. To enhance the efficiency of the allocation algorithms, a reordering procedure will be introduced to change the ordering of Boolean variables in the BDD representation and thereby change the free subcube composition. Such a change leads to an improved free processor recognition capability. Complexities of the proposed allocation algorithms will be analyzed. Performance of the algorithms will be evaluated using simulation and compared with other approaches.     

FEADS: A Framework for Exploring the Application Design Space on Network Processors

Network processors are designed to handle the inherently parallel nature of network processing applications. However, partitioning and scheduling of application tasks and data allocation to reduce memory contention remain as major challenges in realizing the full performance potential of a given network processor. The large variety of processor architectures in use and the increasing complexity of network applications further aggravate the problem. This work proposes a novel framework, called FEADS, for automating the task of application partitioning and scheduling for network processors. FEADS uses the simulated annealing approach to perform design space exploration of application mapping onto processor resources. Further, it uses cyclic and r-periodic scheduling to achieve higher throughput schedules. To evaluate dynamic performance metrics such as throughput and resource utilization under realistic workloads, FEADS automatically generates a Petri net (PN) which models the application, architectural resources, mapping and the constructed schedule and their interaction. The throughput obtained by schedules constructed by FEADS is comparable to that obtained by manual scheduling for linear task flow graphs; for more complicated task graphs, FEADS’ schedules have a throughput which is upto 2.5 times higher compared to the manual schedules. Further, static scheduling of tasks results in an increase in throughput by upto 30% compared to an implementation of the same mapping without task scheduling.     

Robust gossiping with an application to consensus

We study deterministic gossiping in synchronous systems with dynamic crash failures. Each processor is initialized with an input value called rumor. In the standard gossip problem, the goal of every processor is to learn all the rumors. When processors may crash, then this goal needs to be revised, since it is possible, at a point in an execution, that certain rumors are known only to processors that have already crashed. We define gossiping to be completed, for a system with crashes, when every processor knows either the rumor of processor v or that v has already crashed, for any processor v. We design gossiping algorithms that are efficient with respect to both time and communication. Let t<n be the number of failures, where n is the number of processors. If , then one of our algorithms completes gossiping in O(log²t) time and with O(npolylogn) messages. We develop an algorithm that performs gossiping with O(n^1.77) messages and in O(log²n) time, in any execution in which at least one processor remains non-faulty. We show a trade-off between time and communication in gossiping algorithms: if the number of messages is at most O(npolylogn), then the time has to be at least . By way of application, we show that if n−t=Ω(n), then consensus can be solved in O(t) time and with O(nlog²t) messages.     

Minimizing mean flow-time with parallel processors and resource constraints

Summary The problem to be considered is one of scheduling nonpreemptable tasks in multiprocessor systems when tasks need for their processing processors and other limited resources, and when mean flow time is the system performance measure. For each task the time required for its processing and the amount of each resource which it requires, are given. Special attention is paid to the computational complexity of algorithms for determining the optimal schedules for different assumptions concerning the environment. For the case of scheduling independent, arbitrary length tasks when each task may require a unit of an additional resource of one type, an O(n ³) algorithm is given. For more complicated resource requirements, however, it is proved that the problem under consideration is NP-hard in the strong sense, even for the case of two processors.     

Set multi-covering via inclusion–exclusion

Set multi-covering is a generalization of the set covering problem where each element may need to be covered more than once and thus some subset in the given family of subsets may be picked several times for minimizing the number of sets to satisfy the coverage requirement. In this paper, we propose a family of exact algorithms for the set multi-covering problem based on the inclusion–exclusion principle. The presented ESMC (Exact Set Multi-Covering) algorithm takes O^*((2t)ⁿ) time and O^*((t+1)ⁿ) space where t is the maximum value in the coverage requirement set (The O^*(f(n)) notation omits a polylog(f(n)) factor). We also propose the other three exact algorithms through different tradeoffs of the time and space complexities. To the best of our knowledge, this present paper is the first one to give exact algorithms for the set multi-covering problem with nontrivial time and space complexities. This paper can also be regarded as a generalization of the exact algorithm for the set covering problem given in [A. Björklund, T. Husfeldt, M. Koivisto, Set partitioning via inclusion–exclusion, SIAM Journal on Computing, in: FOCS 2006 (in press, special issue)].