Operations on basic data structures such as queues, priority queues, stacks, and counters can dominate the execution time of a parallel program due to their frequency and their coordination and contention overheads.There are considerable performance payoffs in developing highly-optimized, asynchronous, distributed, cache-conscious, parallel implementations of such data structures.Such implementations may employ a variety of tricks to reduce latencies and avoid serial bottlenecks, as long as the semantics of the data structure are preserved.The complexity of the implementation and the difficulty in reasoning about asynchronous systems increases concerns regarding possible bugs in the implementation.In this paper, we consider black box procedures for testing whether a parallel data structure behaved correctly.We present the first systematic study of algorithms and hardness results for such testing procedures, focusing on queues, priority queues, stacks, and counters, under various important scenarios.Our results demonstrate the importance of selecting test data such that distinct values are inserted into the data structure (as appropriate).In such cases, we present an O(n) time algorithm for testing linearizable queues, an O(nlog n) time algorithm for testing linearizable priority queues, and an O(np') time algorithm for testing non-linearizable queues, where n is the number of data structure operations and p is the number of processors.In contrast, we show that testing such data structures for executions with arbitrary input values is NP-complete.Our results also help clarify the thresholds between scenarios that admit polynomial time solutions and those that are NPcomplete.Our algorithms are the first nontrivial algorithms for these problems.

In order to support multiple real-time applications on a single platform, ,the operating system must provide Quality of Service (&OS) guarantees so that the system resources can be provisioned among applications to achieve desired levels of predictable performance.The traditional QoS parameters include fairness, delay, and throughput.In this paper we introduce a new QoS criterion called cumulative service.The cumulative service criterion relates the total service obtained by a process under a scheduling policy to the ideal service that the process would have accumulated by executing on each resource at a reserued rate.We say that a scheuling policy provides a cumulative service guarantee if the performance of the real system differs from the ideal system by at most a constant amount.A cumulative service guarantee is vital for applications (e.g., a continous media file service) that require multiple resources and demand predictable aggregated throughput over aII these resources.E.xisting scheduling algorithms that guarantee traditional QoS paramaters do not provide cumulative service guarantees.We present a new scheduling algorithm called Move-To-Rear List Scheduling which provides a cumulative service guarantee as well as the traditional guarantees such as fairness (proportional sharing) and bounded delay.The complexity of MTR-LS is o(ln(n))where n is the number of processes.

No abstract available.

In the presence of semantic information, serializability is too strong a correctness criterion and unnecessarily restricts concurrency. We use the semantic information of a transaction to provide different atomicity views of the transaction to other transactions. The proposed approach improves concurrency and allows interleavings among transactions which are non-serializable, but which nonetheless preserve the consistency of the database and are acceptable to other users. We develop a graph-based tool whose acyclicity is both a necessary and sufficient condition for the correctness of an execution. Our theory encompasses earlier proposals that incorporate semantic information of transactions. Furthermore it is the first approach that provides an efficient graph based tool for recognizing correct schedules without imposing any restrictions on the application domain. Our approach is widely applicable to many advanced database applications such as systems with long-lived transactions and collaborative environments.

The problem of scheduling tasks on m processors to minimize the schedule length (makespan) is NP-complete. Here we study the behavior of list schedules under the assumptions that there are no task precedence constraints and that task times are chosen from a uniform distribution. We show that, given a desired degree of confidence $1 - \varepsilon $, we can find a minimum sample size N such that if $n \geqq N$ and the n task times $\bar X = (X_1 , \cdots ,X_n )$ are chosen from any uniform distribution, then \[ {\bf P}\left[ {\frac{{L(\bar X)}}{{{\operatorname{OPT}}(\bar X)}} < 1 + \frac{{4(m - 1)}}{n}} \right] > 1 - \varepsilon \] where $L(\bar X)$ is the length of any list schedule and ${\operatorname{OPT}}(\bar X)$ is the length of the optimal schedule. Thus for n sufficiently large, the performance of any list schedule can be made arbitrarily close to that of the optimal policy with any desired degree of confidence. For example, for $m = 2$ and $\varepsilon = 0.01$, the ratio is bounded by 1.11 when $n = 36$ and bounded by 1.03 when $n = 100$.

The problems of minimizing the expected makespan and minimizing the expected tic for a finite set of independent tasks with exponential service-time distributions on m ~ 2 it processors are considered.It is shown that a scheduling policy minimizes the expected flow timq only if it is shortest expected processing time tint, and that a policy minimizes the expected make and only if it is longest expected processing time fast.

In this paper several results are proven showing a correspondence between problems involving task systems with single-stage processors and similar ones using pipelined processors. For example, an optimal schedule for a task system with arbitrary precedence constraints using a single pipelined processor with two stages is found by the familiar Coffman–Graham algorithm for a system with two single-stage processors. Precedence constraints in the form of inforests, out-forests, and directed acyclic graphs are examined. Task systems with release times and deadlines for each task are also considered.

In this paper we consider the problem of sequencing classes of tasks with deadlines in which there is a set-up time or a changeover cost associated with switching from tasks in one class to another. We consider the case of a single machine and our results delineate the borderline between polynomial-solvable and $NP$-complete versions of the problem. This is accomplished by giving polynomial time reductions, pseudo-polynomial time algorithms and polynomial time algorithms for various restricted cases of these problems.

A sequencing problem wherein there is a single processor and a finite number of jobs needing service is considered. Each job consists of a sequence of tasks generated probabilistically by a finite state Markov chain. Each state in the Markov chain is identified with a task and has a service-time requirement and a deferral cost, both of which are random variables. The goal is to minimize the expected value of the sum of the weighted finishing times of all the tasks. The sequencing discipline is nonpreemptive. It is shown that there exists an optimal priority sequencing rule based on a rank defined for each task; an efficient algorithm for calculating the rank is given.

The majority of computers that have been built have performed all computations in devices called accumulators, or registers. In this paper, it is shown that the problem of generating minimal-length code for such machines is hard in a precise sense; specifically it is shown that the problem is NP-complete. The result is true even when the programs being translated are arithmetic expressions. Admittedly, the expressions in question can become complicated.

The problem of generating "optimal" programs for the evaluation of arithmetic expressions on a machine with a finite depth stack is studied.Efficient algorithms are given for constructing optimal programs in the case where the expressions are trees, there are no data dependencies, and the operators have limited algebraic properties.

A scheduling rule is given for determining the processing order of tasks which have the precedence structure of chains. It is assumed that the service times follow known distributions, that they are all independent, that costs are accrued by tasks at a constant rate until their service requirements are satisfied, that all the tasks are available at time 0 and that the service is interruptible at task-specific sets of points. The rule consists of computing for each chain an “optimal assignment” for its tasks and a rank function which depends on this assignment. Choosing at each point in time the chain with the smallest rank produces an optimal schedule. It is proved that the “optimal assignments” have the desirable property that as long as a task does not exceed its allotted service time, no preemption should take place.

In this paper we study the problem of scheduling a set of independent tasks on m ≥ 1 processors to minimize the mean finishing-time (mean time in system). The importance of the mean finishing-time criterion is that its minimization tends to reduce the mean number of unfinished tasks in the system. In the paper we give a reduction of our scheduling problem to a transportation problem and thereby extend the class of known non enumerative scheduling algorithms [1]. Next we show that the inclusion of weights (weighted mean finishing-time) complicates the problem and speculate that there may be no non enumerative algorithm for this case. For the special case of identical processors we study the maximum finishing-time properties of schedules which are optimal with respect to mean finishing-time. Finally we give a scheduling algorithm having desirable properties with respect to both maximum finishing-time and mean finishing-time.

This paper discusses the expression of algorithms by flowcharts, and in particular by flowcharts without explicit go-to's (D-charts).For this purpose we introduce a machine independent definition of algorithm which is broader than usual.Our conclusion is that Dcharts are in one technical sense more restrictive than general flowcharts, but not if one allows the introduction of additional variables which represent a history of control flow.

A digital system can be viewed as an interaction of two structures, a data flow structure and a control structure. In this paper we adopt this point of view and concentrate on defining a structure theory for asynchronous control networks, which is formed by interconnecting certain basic control modules. Each control module performs a single primitive control function.