15724338
Stochastic Scheduling with Variable Profile and Precedence Constraints
In this paper, we consider the stochastic profile scheduling problem of a partially ordered set of tasks on uniform processors. The set of available processors varies in time. The running times of the tasks are independent random variables with exponential distributions. We obtain a sufficient condition under which a list policy stochastically minimizes the makespan within the class of preemptive policies. This result allows us to obtain a simple optimal policy when the partial order is an interval order, an in-forest, or an out-forest.
17231470
Dynamic scheduling of parallel computations
Structures of parallel programs are usually represented by task graphs in the scheduling literature. Such graphs are sometimes obtained at compile time. In many other cases, however, they can be determined only at run time. In this paper, we consider the scheduling of parallel computations whose task graphs are generated at run time. We analyze the case where the task graph is a random out-tree. When the number of offspring of a task has a geometric distribution whose parameter is decreasing and convex in the level, then the breadth-first policy stochastically minimizes the makespan. If, however, this parameter is increasing and concave, then the depth-first policy stochastically minimizes the makespan.
17293889
Complexity of Task Graph Scheduling with Fixed Communication Capacity
Consider a scheduling problem of parallel computations in multiprocessor systems. Let a parallel program be modeled by a task graph, where vertices represent tasks and arcs the communications between tasks. An interprocessor communication time incurs when two tasks assigned to two different processors have to communicate. Such a scheduling problem has recently been studied in the literature, mostly for the case where interprocessor communication times are fully determined. In this paper, we consider the scheduling problem with communication resource constraints. More specifically, we consider the case where all interprocessor communications take place on a network of bounded capacity. We consider two variants of the problem: communications with independent-data semantics and common-data semantics. We show that even for very specific subproblems, viz. scheduling of general graphs on two processors and scheduling of binary trees on an infinite number of processors, the minimization of the makespan of parallel programs in such a multiprocessor system is strongly -hard. We first establish the results for the case of capacity 1, referred to as the single-bus system. We then extend the results to the more general case of fixed communication capacities. As a consequence, the general scheduling problem of parallel programs with communication resource constraints is strongly -hard. These results are to be contrasted with the corresponding scheduling problems without contraint on the communication capacity, where the two-processor case has unknown time complexity and the infinite-processor case is polynomial. Our results are also extended to the case of broadcasting communications, and can be applied to multiprocessor systems with shared memory.
29521719
Improving the Stability Characteristics of Asynchronous Traffic in FDDI Token Ring
The Fiber Distributed Data Interface (FDDI) token ring protocol supports two classes of traffic : synchronous and asynchronous. The time constraint mechanism of FDDI garantees the transmission delay of synchronous traffic. A Target Token Rotation Time (TTRT) being fixed, the FDDI protocol ensures that the token rotation time is always bounded above by twice TTRT. In this paper, we consider the stability issues of the asynchronous traffic in the FDDI protocol. We obtain sufficient and necessary stability conditions which indicates how the choice of TTRT affects the stability of the system. We suggest an improvement of the FDDI protocol for which the token rotation time is also bounded by twice TTRT. We show that the stability conditions of the new protocol are weaker (and thus it enables to transmit more asynchronous packets). This protocol is also easier to implement.
14587701
Routing and Transmitting Problems in de Bruijn Networks
De Bruijn graphs, both directed and undirected, have received considerable attention as architecture for interconnection networks. In this paper, we focus on undirected de Bruijn networks of radix d and dimension 0, denoted by UB(d, 0). We first discuss the shortest-path routing problem. We present properties of the shortest paths between any two vertices of UB(d, 0) and propose two shortest-path routing algorithms, one of which has linear time complexity. Secondly, we study the transmitting problem. We establish a lower bound for the optimal transmitting time which implies in particular that the optimal transmitting problem is trivial for UB(d, 0) when d/spl ges/5. We present a transmitting scheme on undirected binary de Bruijn networks UB(2, n) with transmitting time n-1 for n/spl ges/5, and conjecture that the optimal transmitting time is n-1 for UB(2, n), and n for U8(3, n) and UB(4, n).
12816052
Worst-Case Analysis of Scheduling Heuristics of Parallel Systems
Abstract It is well-known that most scheduling problems arising from parallel systems are NP -hard, even under very special assumptions. Thus, various suboptimal algorithms, in particular heuristics, were proposed in the literature. Worst-case error bounds are established in this paper for heuristics of makespan minimization of parallel computations. Different parallel computation models are investigated, including interprocessor communication, task duplication, multiprocessor tasks and parallel tasks. Due to the heterogeneity of these systems, scheduling heuristics can be far away from the optimal solutions. These bounds provide insights to the design of scheduling heuristics in order to obtain good performance guarantee than arbitrary heuristics. Moreover, the performance guarantee of these special heuristics is independent of model parameters such as the maximal duplication degree, processor requirement and parallelization degree.
6930232
Expressive expression mapping with ratio images
Facial expressions exhibit not only facial feature motions, but also subtle changes in illumination and appearance (e.g., facial creases and wrinkles). These details are important visual cues, but they are difficult to synthesize. Traditional expression mapping techniques consider feature motions while the details in illumination changes are ignored. In this paper, we present a novel technique for facial expression mapping. We capture the illumination change of one person's expression in what we call an expression ratio image (ERI). Together with geometric warping, we map an ERI to any other person's face image to generate more expressive facial expressions.
3166137
Integrating Temporal Logics
In this paper, we study the predicative semantics of different temporal logics and the relationships between them. We use a notation called generic composition to simplify the manipulation of predicates. The modalities of possibility and necessity become generic composition and its inverse of converse respectively. The relationships between different temporal logics are also characterised as such modalities. Formal reasoning is carried out at the level of predicative semantics and supported by the higher-level laws of generic composition and its inverse. Various temporal domains are unified under a notion called resource cumulation. Temporal logics based on these temporal domains can be readily defined, and their axioms identified. The formalism provides a framework in which human experience about system development can be formalised as refinement laws. The approach is demonstrated in the transformation from Duration Calculus to Temporal Logic of Actions. A number of common design patterns are studied. The refinement laws identified are then applied to the case study of water pump controlling.
7545798
Verification of fault tolerance and real time
A transformational method is given for specifying and verifying fault-tolerant, real-time programs. Such a program needs to be provably correct according to both its functional and real-time requirements, despite the possible occurrence of system failures. The paper demonstrates that a suitably expressive logic for real-time systems makes it possible to naturally model the state changes caused by system failures and determine their effect on the functional and real-time properties of executions.
1204986
A floating-point CORDIC based SVD processor
An SVD processor system is presented in which each processing element is implemented using a simple CORDIC unit. The internal recursive loop within the CORDIC module is exploited, with pipelining being used to multiplex the two independent microrotations onto a single CORDIC processor. This leads to a high performance and efficient hardware architecture. In addition, a novel method for scale factor correction is presented which only need be applied once at the end of the computation. This also reduces the computation time. The net result is an SVD architecture based on a conventional CORDIC approach, which combines high performance with high silicon area efficiency.
11711500
Verification of schedulability for real-time programs
Assume that a real-time programPT consisting of a number of parallel processes is executed on a system having a setPr of processors which are shared between the processes by a real-time schedulerST. Assume that PT must meet some timing deadlines. We show that such an implementation ofPT can be represented as a transformationL(PT) and that the deadlines ofPT will be met if they are satisfied by the timing properties of the transformed program. The condition for feasibility of a real-time program executed under a scheduler is formalized and rules are provided for verification. The schedulerST can be specifiedgenerically and applied to different programs, making it unnecessary to introduce low-level operations such as scheduling primitives into the programming language. Thus real-time program specification and Schedulability can be considered in the same framework and the timing properties of a program can be determined at the specification level. By separating the specification of the scheduler from that of the program, the feasibility of an implementation can be proved by considering a scheduling policy rather than its implementation details.