This paper investigates the task scheduling problem for real-time systems that provide rate of progress guarantees on task execution. A parameterized task system model, called the (r, g) task system, is introduced that allows rate of progress requirements to be specified in terms of two simple parameters: an execution rate r and a granularity g. The granularity parameter is a new metric that allows the specification of "fine-grain" timing constraints on the task's execution and is a generalization of the stretch metric used in recent research on task scheduling. It is shown that the product rlg(l/g) is an important determiner of the existence of good online scheduling algorithms. Specifically, there is an upper bound on this product above which there are no good online algorithms, but below which an online algorithm with logarithmic competitive ratio exists. This paper also demonstrates a fundamental difference between two contrasting strategies for admission control: greedy versus nongreedy. It is shown that "greed does not pay": there is a scheduling algorithm with a nongreedy admission policy that provably outperforms the well-known greedy EDF scheduling algorithm.

This paper investigates the task scheduling problem for real-time systems that provide rate of progress guarantees on task execution. A parameterized task system model, called (r, g) task system, is introduced that allows rate of progress requirements to be specified in terms of two simple parameters: an execution rate r and a granularity g. The granularity parameter is a metric that allows the specification of "fine-grain" timing constraints on the task's execution and is a generalization of the stretch metric used in research on task scheduling. It is shown that the product r lg (l/g) is an important determiner of the existence of good online scheduling algorithms. Specifically, there is an upper bound on this product above which there are no good online algorithms but below which an online algorithm with logarithmic competitive ratio exists. This paper also demonstrates a fundamental difference between two contrasting strategies for admission control: greedy vs. nongreedy. It is shown that "greed does not pay": there is a scheduling algorithm with a nongreedy admission policy that provably outperforms the well-known greedy EDF scheduling algorithm.

This paper addresses the problem of scheduling parallel programs represented as directed acyclic task graphs for execution on distributed memory parallel architectures. Because of the high communication overhead in existing parallel machines, a crucial step in scheduling is task clustering, the process of coalescing fine grain tasks into single coarser ones so that the overall execution time is minimized. The task clustering problem is NP-hard, even when the number of processors is unbounded and task duplication is allowed. A simple greedy algorithm is presented for this problem which, for a task graph with arbitrary granularity, produces a schedule whose makespan is at most twice optimal. Indeed, the quality of the schedule improves as the granularity of the task graph becomes larger. For example, if the granularity is at least 1/2, the makespan of the schedule is at most 5/3 times optimal. For a task graph with n tasks and e inter-task communication constraints, the algorithm runs in O(n(n lg n+e)) time, which is n times faster than the currently best known algorithm for this problem. Similar algorithms are developed that produce: (1) optimal schedules for coarse grain graphs; (2) 2-optimal schedules for trees with no task duplication; and (3) optimal schedules for coarse grain trees with no task duplication.

We consider the problem of permutation routing on a star graph, an interconnection network which has better properties than the hypercube. In particular, its degree and diameter are sublogarithmic in the network size. We present optimal randomized routing algorithms that run in O(D) steps (where D is the network diameter) for the worst-case input with high probability. We also show that for the n-way shuffle network with N = nn nodes, there exists a randomized routing algorithm which runs in O(n) time with high probability. Another contribution of this paper is a universal randomized routing algorithm that could do optimal routing for a large class of networks (called leveled networks) which includes the star graph. The associative analysis is also network-independent. In addition, we present a deterministic routing algorithm, for the star graph, which is near optimal. All the algorithms we give are oblivious. As an application of our routing algorithms, we also show how to emulate a PRAM optimally on this class of networks.

Control grammars, a generalization of context-free grammars recently introduced for use in natural language recognition, are investigated. In particular, it is shown that a hierarchy of non-context-free languages, called control language hierarchy (CLH), generated by control grammars can be recognized in polynomial time. Previously, the best-known upper bound was exponential time. It is also shown that CLH is in NC(2), the class of languages recognizable by uniform boolean circuits of polynomial size and O(log2 n) depth.

An optimal parallel recognition/parsing algorithm is presented for languages generated by tree adjoining grammars (TAGs), a grammatical system for natural language. TAGs are strictly more powerful than context-free grammars (CFGs), e.g., they can generate $\{a'' b'' c'' | n \geqq 0\}$, which is not context-free. However, serial parsing of TAGs is also slower, having time complexity $O(n^{6})$ for inputs of length n (as opposed to $O(n^{3})$ for CFGs). The parallel algorithm achieves optimal speedup: it runs in linear time on a five-dimensional array of $n^5$ processors. Moreover, the processors are finite-state; i.e., their function and size depends only on the underlying grammar and not on the length of the input.

We give efficient simulations of systolic arrays by unit-cost random-access machines (RAM’s). For example, we show that a one-dimensional systolic array operating in linear time can be simulated by a RAM in $O({{n^2 } / {\log ^2 n}})$ time. For the case of a two-dimensional systolic array, the simulation time is $O({{n^3 } / {\log ^{{3 / 2}} n}})$.

We show that a one-way two-dimensional iterative array of finite-state machines (2-DIA) can recognize and parse strings of any context-free language in linear time. What makes this result interesting and rather surprising is the fact that each processor of the array holds only a fixed amount of information (independent of the size of the input) and communicates with its neighbors in only one direction. This makes for a simple VLSI implementation. Although it is known that recognition can be done on a 2-DIA, previous parsing algorithms require the processors to have unbounded memory, even when the communication is two-way. We also consider the problem of finding approximate patterns in strings, the string-to-string correction problem, and the longest common subsequence problem, and show that they can be solved in linear time on a 2-DIA.

We present a tool that is useful in the design and analysis of systolic systems. Specifically, we give characterizations of systolic arrays in terms of (single processor) sequential machines which are easier to program and to analyze. We give several examples to illustrate the utility of the design tool. In particular, we show how systolic designs for such problems as integer bitwise multiplication, dynamic programming, and language recognition can easily be derived using the characterizations. We also present some new results concerning the properties and computational power of systolic arrays which can be obtained using the characterizations.

We offer a methodology for simplifying the design and analysis of systolic systems. Specifically, we give characterization of systolic arrays in terms of (single processor) sequential machines which are easier to analyze and to program. We give several examples to illustrate the design methodology. In particular, we show how systolic arrays can be easily designed to implement priority queues, integer bitwise multiplication, dynamic programming, etc. Because the designs are based on the sequential machine, the constructions we obtain are much simpler then those that have appeared in the literature. We also give some results concerning the properties and computational power (e.g., speed-up, hierarchy, etc.) of systolic arrays.