Optimal Processor Assignment for a Class of Pipelined Computations.
The availability of large-scale multitasked parallel architectures introduces the followingprocessor assignment problem. We are given a long sequence of data sets, each of whichis to undergo processing by a collection of tasks whose intertask data dependencies forma series-parallel partial order. Each individual task is potentially parallelizable, with aknown experimentally determined execution signature. Recognizing that data sets can bepipelined through the task structure, the problem is to find a "good" assignment ofprocessors to tasks. Two objectives interest us: minimal response time per data set,given a throughput requirement, and maximal throughput, given a response timerequirement. Our approach is to decompose a series-parallel task system into its essential"serial" and "parallel" components; our problem admits the independent solution andrecomposition of each such component. We provide algorithms for the series analysis, and use an algorithm due to Krishnamurti and Ma for the parallel analysis. For a p processor system and a series-parallel precedence graph with n constituent tasks, we give a O(np/sup 2/) algorithm that finds the optimal assignment (over a broad class ofassignments) for the response time optimization problem; we find the assignmentoptimizing the constrained throughput in O(np/sup 2/ log p) time. These techniques areapplied to a task system in computer vision.
Introduction
In recent years much research has been devoted to the problem of mapping large computations onto
a system of parallel processors. Various aspects of the general problem have been studied, including
different parallel architectures, task structures, communication issues and load balancing [8, 13].
Typically, experimentally observed performance (e.g., speedup or response time) is tabulated as
a function of the number of processors employed, a function sometimes known as the execution
signature [10], or response time function. In this paper we use such functions to determine the
number of processors to be allocated to each of several tasks when the tasks are part of a pipelined
computation. This problem is natural, given the growing availability of multitasked parallel ar-
chitectures, such as PASM [29], the NCube system [14], and Intel's iPSC system [5], in which it
is possible to map tasks to processors and allow parallel execution of multiple tasks in different
logical partitions.
We consider the problem of optimizing the performance of a complex computation applied to
each member of a sequence of data sets. This type of problem arises, for instance, in imaging
systems, where each image frame is analyzed by a sequence of elemental tasks, e.g., fast Fourier
transform or convolution. Other applications include network software, where packets are pipelined
through well-defined functions such as checksum computations, address decoding and framing.
Given the data dependencies between the computation's multiple tasks, we may exploit parallelism
both by pipelining data sets through the task structure, and by applying multiple processors to
individual tasks.
There is a fundamental tradeoff between assigning processors to maximize the overall through-put
(measured as data sets per unit time), and assigning processors to minimize a single data set's
response time. We manage the tradeoff by maximizing one aspect of performance subject to the
constraint that a certain level of performance must be achieved in the other aspect. Under the
assumptions that each of n tasks is statically assigned a subset of dedicated processors and that
an individual task's response time function completely characterizes performance (even when using
shared resources such as the communication network) we show that p processors can be assigned
to a series-parallel task structure in O(np 2 so as to minimize response time while achieving
a given throughput. We are also able to find the assignment that maximizes throughput while
achieving a given minimal response time, in O(np 2 log p) time.
The assumption of a static assignment arises naturally in real-time applications, where the overhead
of swapping executable task code in and out of a processor's memory threatens performance.
this assumption, the optimization problem becomes much more difficult.
Our method involves decomposing a series-parallel graph into series and parallel components
using standard methods; we present algorithms for analyzing series components and use Krishnamurthy
and Ma's algorithm [20] to analyze the parallel components.
We assume that costs of communication between tasks are completely captured in the given
response-time functions. Thus, our techniques can be expected to work well on compute-bound
task systems; our example application is representative of this class, having a computation to
communication ratio of 100. Our techniques may not be applicable when communication costs
that depend on the particular sets of processors assigned to a task (e.g., contention) contribute
significantly to overall performance.
A large literature exists on the topic of mapping workload to processors, see, for instance
[1, 3, 4, 6, 15, 17, 18, 23, 24, 26, 27, 31, 33]. A new problem has recently emerged, that of
scheduling of tasks on multitasked parallel architectures where each task can be assigned a set of
processors. Some formulations consider scheduling policies with the goal of achieving good average
response time and good throughput, given an arrival stream of different, independent parallel
jobs, e.g., [28]. Another common objective, exemplified in [2, 11, 20, 25], is to find a schedule of
processor assignments that minimizes completion time of a single job executed once. The problem
we consider is different from these specifically because we have a parallel job which is to be repeatedly
executed. We consider issues arising from our need to pipeline the repeated executions to get good
throughput, as well as apply parallel processing to the constituent tasks to get good per-execution
response time. Yet another distinguishing characteristic of our problem is an underlying assumption
that a processor is statically assigned to one task, with the implication that every task is always
assigned at least one processor.
Two previously studied problems are close to our formulation. The assignment of processors
to a set of independent tasks is considered in [20]. The single objective is the minimization of the
makespan, which minimizes response time if the tasks are considered to be part of a single parallel
computation, or maximizes throughput if the tasks are considered to form a pipeline. The problem
of assigning processors to independent chains of modules is considered in [7]; this assignment
minimizes the response time if the component tasks are considered to be parallel, and maximizes
the throughput if the component chains are considered to form pipelines. Pipeline computations are
also studied in [19, 30]. In [30], heuristics are given for scheduling planar acyclic task structures and
in [19], a methodology is presented for analyzing pipeline computations using Petri nets together
with techniques for partitioning computations. We have not discovered treatments that address
optimal processor assignment for general pipeline computations, although our solution approach
(dynamic programming) is related to those in [3] and [33].
This paper is organized as follows. Section x2 introduces notation, and formalizes the response-time
problem and the throughput problem. Section x3 presents our algorithms for series systems,
and x4 shows how to optimally assign processors to series-parallel systems. Section x5 shows how
the problem of maximizing throughput subject to a response-time constraint can be solved using
solutions to the response-time problem. Section x6 discusses the application of our techniques to
an actual problem, and Section x7 summarizes this work.
Problem Definition
We consider a set of tasks, t that comprise a computation to be executed using up to
identical processors, on each of a long stream of data sets. Every task is applied to every data
set. We assume the tasks have a series-parallel precedence relation constraining the order in which
we may apply tasks to a given data set; tasks unrelated in the partial order are assumed to process
duplicated copies (or, different elements) of a given data set. Under these assumptions we may
pipeline the computation, so that different tasks are concurrently applied to different data sets.
Each task is potentially parallelizable; for each t i we let f i (n) be the execution time of t i using n
identical processors. f i is called a response-time function (also known as an execution signature [10]).
We assume that f 0 and f n+1 are dummy tasks that serve respectively to identify the initiation and
completion of the computation; correspondingly we take f 0
conditions ensure that no processor is ever assigned to t 0 or
and that at least one processor is assigned to every other task.
An example of the response time functions for a computation with 5 tasks on up to 8 processors
is shown in Table 1. Each row of the table is a response time function for a particular task. Observe
Number of processors
tasks
43

Table

1: Example response time functions. Table gives tasks' execution time (in seconds) as a
function of the number of processors used.
that individual functions need not be convex, nor monotonic.
We may describe an assignment of numbers of processors to each task by a function A: A(i)
gives the number of processors statically and exclusively allocated to t i
. A feasible assignment is
one where
Given A, t i 's execution time is f i (A(i)), and the maximal data set throughput is
g. The response time for a data set is obtained by computing the length R(A) of
the longest path through the graph where each t i is a node weighted by f i (A(i)), and the edges are
defined by the series-parallel precedence relation.
Given some throughput constraint - and processor count q, we define T -
(q) to be the set of all
feasible assignments A that use no more than q processors, and achieve  (A) -. The response-time
problem is to find F - (p) the minimum response time over all feasible assignments in T - (p),
that is, the response time for which there is an assignment A for which R(A) is mimimal over
all assignments with p or fewer processors that achieve throughput - or greater. This problem
arises when data sets must be processed at least as fast as a known rate - to avoid losing data;
we wish to minimize the response time among all those assignments that achieve throughput -.
Similarly, given response time constraint fl and processor count q we define R fl (q) to be the set of all
feasible assignments A using no more than q processors, and achieving R(A) - fl. The throughput
problem is to find A 2 R fl (p) for which  (A) is maximized. This problem arises in real-time control
applications, where each data set must be processed within a maximal time frame in order to meet
\Gamma\Psi
@@@ @R
\Gamma\Psi
@
@ @R
@
@ @R
\Gamma\Psi
\Gamma\Psi

Figure

1: Example of series-parallel task system T
processing deadlines. We will focus on solutions to the response time problem first and later show
how these may be used to solve the throughput problem.
Since a response-time function completely defines a task, elemental or composite, we will also
use the term "task" to refer to compositions of the more elemental tasks t i
. Let - i
denote such a
composite task and let F i be its optimal response time function. Our general approach is illustrated
through an example. Consider the series-parallel task T in Figure 1 with response-time functions
given

Table

are dummy tasks). We may think of t 2 and t 3 as forming a parallel
subtask-call it - 1 . Given the response time functions for t 2 and t 3 , we will construct an optimal
response time function called F 1 for - 1 , after which we need never explicitly consider t 1 or t 2
separately from each other-F 1 completely captures what we need to know about both of them.
Next, we view - 1 and t 1 as a series task, call it - 2 , and compute the optimal response time function
. The process of identifying series and parallel subtasks and constructing response-time
functions for them continues until we are left with a single response time function that describes
the optimal behavior of T . By tracking the processor assignments necessary to achieve the optimal
response times at each step, we are able to determine the optimal processor allocations for T . A
solution method for parallel tasks has already been given in [20]; we present algorithms for series
tasks.
We will assume that every response-time function is monotone nonincreasing, since, as argued
in [20], any other response-time function can be made decreasing by disregarding those assignments
of processors that cause higher response times. Also, observe that response time functions may
include inherent communication costs due to parallelism, as well as the communication costs that are
suffered by communicating with predecessor and successor tasks. These assumptions are reasonable
when the communication bandwidth is sufficiently high for us to ignore effects due to contention
between pairs of communicating tasks. Our methods may not produce good results when this
assumption does not hold.
3 Individual Parallel Tasks and Series Tasks
The problem of determining an optimal response-time function for parallel tasks has already essentially
been solved in the literature [20]. We describe this solution briefly. Let t be the
tasks used to compose a parallel task - . For each t i we know u -
number of
processors needed so that every elemental task involved in t i has response-time no greater than
1=-. We initialize by allocating processors to each t i . If we run out of processors first then
no processor allocation can meet the throughput requirement. Otherwise, the initial allocation uses
the fewest possible number of processors that do meet this requirement. We then incrementally add
the remaining processors to tasks in such a way that at each step the response time (the maximum
of task response times) is reduced maximally. This algorithm has an O(p log p) time complexity.
Series task structures are interesting in themselves because many pipelines are simple linear
chains [19]. We first describe an algorithm that constructs the optimal response time function F -
for a linear task structure T when each function f i (x) is convex in x. While convexity in elemental
functions is intuitive, nonconvex response-time functions arise from parallel task compositions.
Consequently, a different algorithm for series compositions of nonconvex response-time functions
will be developed later.
Like the parallel composition algorithm, we first assign the minimal number of processors needed
to meet the throughput requirement. The mechanism for this is identical. Supposing that this step
does not exhaust the processor supply, define x i to be the number of processors currently assigned
to t i , initialize x
x i to be the total number of processors already
allocated. We then set F - to reflect an inability to meet the throughput
Number of processors

Table

2: Response time function F 1 for parallel task - 1
requirement, and set F -
Next, for each t i
the change in response time achieved by allocating one more processor to t i . Build a max-priority
heap [16] where the priority of t i is jd(i; x i )j. Finally, enter a loop where, on each iteration the task
with highest priority is allocated another processor, its new priority is computed, and the priority
heap is adjusted. We iterate until all available processors have been assigned. Each iteration of the
loop allocates the next processor to the task which stands to benefit most from the allocation. When
the individual task response functions are convex, then the response time function F -
it greedily
produces is optimal, since the algorithm above is essentially one due to Fox [12], as reported in [32].
Simple inspection reveals that the algorithm has an O(p log n) time complexity. Unlike the similar
algorithm for parallel tasks, correctness here depends on convexity of component task response
times.
The need to treat nonconvex response-time functions arises from the behavior of composed
parallel tasks. Return to our example in Figure 1 and consider the parallel composition - 1 of
elemental tasks t 2 and t 3 , with throughput requirement 0:01. The response-time function F 1 is
shown in Table 2. Note that F 1 is not convex, even though f 2 and f 3 are. This nonconvexity is due
to the peculiar nature of the maximum of two functions and cannot be avoided when dealing with
parallel task compositions. We show below that nonconvexity can be handled, with an additional
cost in complexity.
We begin as before, allocating just enough processors so that the throughput constraint is met.
Assuming so, for any denote the subchain comprised of t
and compute its optimal response time function, C j , subject to throughput constraint -. Using the
principle of optimality[9], we write a recursive definition for u -
min
The dynamic programming equation is understood as follows. Suppose we have already computed
the function C j \Gamma1 . This implicitly asserts that we know how to optimally allocate any number
processors to T j \Gamma1 . Next, given x processors to distribute between tasks t j and
every combination subject to the throughput constraints: i processors for t j and x \Gamma i processors
for . The principle of optimality tells us that the least-cost combination gives us the optimal
assignment of x processors to T j . Since the equation is written as a recursion, the computation will
actually build response time tables from 'bottom up', starting with task t 1 in the first part of the
equation.
This procedure requires O(np 2 ) time. We have been unable to find a solution that gives a better
worst-case behavior in all cases. Some of the difficulties one encounters may be appreciated by study
of our previous example. Consider the construction of - 2 , comprised of the series composition of
As before, let F 1 denote the response time function for - 1 . Table 3 gives the values of
8. The set of possible sums associated with allocating
a fixed number of processors x lie on an assignment diagonal moving from the lower left (assign
processors to - 1 , one to t 1 ) to the upper right (assign one processor to - 1 , of the
table, illustrated by use of a common typeface on a diagonal. Brute force computation of - 2 (x)
consists of generating all sums on the associated diagonal, and choosing the allocation associated
with the least sum. In the general case this is equivalent to looking for the minimum of a function
known to be the sum of a function that decreases in i (e.g. f 1 (i)) and one that increases (e.g.
Unlike the case when these functions are known to be convex as well, in general their
sum does not have any special structure we can exploit-the minimum can be achieved anywhere,
implying that we have to look for it everywhere. It would seem then that dynamic programming
may offer the least-cost solution to the problem.
We note in passing that a straightforward optimization may reduce the running time, but does
29
43 72 59 54

Table

3: Sum of response time functions f 1 and F 1 . The minimum value on each assignment
diagonal is marked by *.
not have a better asymptotic complexity. If both functions being summed are convex, then the
minimum values on adjacent assignment diagonals must be adjacent in a row or column. This
fact can considerably accelerate the solution time, since given the minimum on the x-processor
assignment diagonal we can find the minimum on the diagonal by generating
and comparing only two additional entries (this is a consequence of the greedy algorithm described
earlier). Although we cannot in general assume that both functions are convex, we can view them
as being piece-wise convex. Thus, if t 1 is convex over [a; b], and - 1 is convex over [c; d], then
is convex over [a; b] \Theta [c; d] and we can efficiently find minima on assignment diagonals restricted
to this subdomain. Working through the details (which are straightforward), one finds that the
complexity of this approach is O(rnp), where r is the maximum number of convex subregions
spanned by any given assignment diagonal. Of course, in the worst case leaving us still
with an O(np 2 ) algorithm.
4 Series-Parallel Tasks
Algorithms for the analysis of series and parallel task structures can be used to analyze task-
structures whose graphs form series-parallel directed acyclic graphs. We show that the response
c
c c
ae
ae

Figure

2: Binary decomposition tree
time function for any such graph (with n nodes) can be computed in O(np 2 ) time. A number
of different but equivalent definitions of series-parallel graphs exist. The one we will use is taken
from [34], in which a series-parallel DAG can be parsed as a binary decomposition tree (BDT) in
time proportional to the number of edges. The leaves of such a tree correspond to the DAG nodes
themselves and internal tree nodes describe either parallel (P) or series (S) compositions. Figure 2
illustrates the BDT (labeling S and P nodes by task names used in discussion) corresponding to
the task in Figure 1.
The structure of a BDT specifies the precise order in which we should apply our analyses. The
idea is to build up the overall optimal response-time function from the bottom up. Conceptually
we mark every BDT node as being computed or not, with leaf nodes being the only ones marked
initially. We then enter a loop where each iteration we identify an unmarked BDT node whose
children are both marked. We apply a series composition or parallel composition to those childrens'
response-time functions depending on whether the node is of type S or P, and mark the node. The
algorithm ends when the root node is marked.
In the example, - 1 's response time function is generated using the parallel algorithm on t 2 and
3 , the series composition is applied to t 1 and - 1 , (for composite task - 2 ), which is then composed
via another series composition with t 4 , creating - 3 ; finally, t 5 is combined via a parallel composition
with - 3 to create the response time function for the overall task structure. At each step one must
record the actual number of processors assigned to each task in order to compute the optimal
assignment; this is straightforward and needs no discussion.
From the above, we see that the cost of determining the optimal assignment from a BDT is
O(np 2 ), as every response-time function composition has worst case cost O(p 2 ) and there are
such compositions performed.
5 The Throughput Problem
Real time applications often require that the processing of every data set meet a response-time
deadline. At system design time it becomes necessary to assess the maximal throughput possible
under the constraint. This is our throughput problem. In this section we show how solutions to
the response-time problem can be used to solve this new problem in O(np 2 log p) time.
Our approach depends on the fact that minimal response times behave monotonically with
respect to the throughput constraint.
Lemma 5.1 For any pipeline computation let F - (p) be the minimal possible response time using p
processors, given throughput constraint - and the assumption of static processor-to-task mapping.
Then for every fixed p, F -
(p) is a monotone nondecreasing function of -.
Proof: Let p be fixed. As before, let u be the minimum number of processors required for all
elemental tasks comprising t i to meet throughput constraint -. For every t i ,
a monotone nondecreasing function of -. Recall that T - (p) is the set of all assignments that
meet the throughput constraint - using no more than p processors. Whenever
must have
(p), because of the monotonicity of each u - (t i ). Since F - (p) is the
minimum cost among all assignments in T - (p), we have F - 2
(p).
This result can be viewed as a generalization of Bokhari's graph-based argument for monotonicity
of the minimal "sum" cost, given a "bottleneck" cost [4].
Suppose for a given pipeline computation we are able to solve for F - (p), given any -. The set of
all possible throughput values is f1=f i needed
to generate and sort them. Given response time constraint - fl, and tentative throughput -, we may
determine whether F - (p) -
fl. Since F - (p) is monotone in -, we use a binary search to identify the
greatest -   for which F -   (p) -
fl. The associated processor assignment maximizes throughput
(using p processors), subject to response time constraint - fl. There being O(log p) solutions of the
response-time problem, the complexity for the throughput problem is O(np 2 log p).
6 An Application
In this section we report the results of applying our methods to a motion estimation system in
computer vision. Motion estimation is an important problem in which the goal is to characterize
the motion of moving objects in a scene. From a computational point of view, continually generated
images from a camera must be processed by a number of tasks. A primary goal is to ensure that
the computational throughput meets the input data rate. Subject to this constraint, we desire that
the response time be as small as possible. The application itself is described in detail in [8, 21].
It should be noted that there are many approaches to solving the motion estimation problem. We
are only interested in an example, and therefore, the following algorithm is not presented as the
only or the best way to perform motion estimation. A comprehensive digest of papers on the
topic of motion understanding can be found in [22]. The following subsection briefly describes the
underlying computations.
6.1 A Motion Estimation System
Our example problem is a linear pipeline with nine stages, each stage is a task. The data sets
input to the task system are a continuous stream of stereo image pairs of a scene containing
the moving vehicles. The tasks perform well-known vision computations such as 2-D convolution,
extracting zero crossings and feature matching, similar to computations in the Image Understanding
Benchmark [35]. All nine tasks were implemented on a distributed memory machine, the Intel
iPSC/2 hypercube [5]. We applied the system above to a problem using outdoor images [8]. The
relevant response-time functions are shown in Table 4 for selected processor sizes. Measurements
include all overheads, computation time and communication times.
Response Times for Individual Tasks (sec.)
No. of Task 1 Task 2 Task 3 Task 4 Task 5 Task 6 Task 7 Task 8 Task 9
Proc.
64* 2.12 0.11 0.007 0.61 2.12 0.11 0.007 4.13 0.71

Table

4: Completion times for individual tasks on the Intel iPSC/2 of various sizes, in seconds (*
indicates extrapolated values)

Figure

3: Minimal response time as a function of the throughput constraint
6.2 Experimental Results
We applied the series task algorithm using Table 4, for a range of possible throughput constraints.
As an example of the output generated by the algorithm, Table 5 shows the processor assignment
for individual tasks for various sizes of the Intel iPSC/2. The last row of the table also shows
the minimum response time, given constraint frames/second. The response times shown
are those predicted by our algorithms. Nevertheless, observed response times using the computed
allocations were observed to be in excellent agreement with these figures-the relative error was
less than 5% in all measurable cases.
The processor allocation behavior is intuitive. Tasks t 1 , t 5 , and t 8 have much larger response
times than the others. As increasingly more processors are allocated to the problem, these three
tasks receive the lion's share of the additional processors.

Figure

3 illustrates the tension between response time and throughput by plotting the minimal
response time function for the entire pipeline computation, as a function of the throughput con-
straint. For any problem there will be a throughput - min achieved when processors are allocated
entirely to minimize response time. The flat region of the curve lies over throughput constraints
- min . The response time curve turns up, sometimes dramatically, as the throughput constraint
moves into a region where response time must be traded off for increased throughput.
Multiprocessor Size (No. of Procs.)
Task Proc. Time Proc. Time Proc. Time Proc. Time
No. Asgn. (Sec.) Asgn. (Sec.) Asgn. (Sec.) Asgn. (Sec.)

Table

5: An example processor allocation for minimizing response time for several sizes of iPSC/2
processors
allocated to individual tasks are shown)

Summary

In this paper we consider performance optimization of series-parallel pipelined computations. The
problem arises when a system of individually parallelizable tasks is to be applied repeatedly to a
long sequence of data sets. Given a large supply of processors, parallelism can be exploited both
by pipelining the data sets through the task structure, and by allocating multiple processors to
individual tasks. We treat the dual problems of minimizing response time subject to a throughput
constraint, and maximizing throughput subject to a response time constraint.
We showed that problems with p processors and n tasks satisfying series-parallel precedence
constraints can be solved in low-order polynomial time: response time (subject to a throughput
constraint) is minimized in O(np 2 ) time, and throughput (subject to a response time constraint)
is maximized in O(np 2 log p) time. To place the work in a realistic setting we evaluated the performance
of our assignment algorithms on the problem of stereo image matching. The results
predicted by our analysis were observed to be very close to measured on actual systems.
Future endeavors include the provision of algorithms for general task structures and investigation
of dynamic assignment algorithms. Also, we believe that our results can be extended to task models
that include "branching", such as are encountered with CASE statements. This feature essentially
forces us to treat response times and throughputs as being stochastic. We also believe that our
approach can be extended to consider the effects of certain types of communication contention.



--R

A partitioning strategy for nonuniform problems on multiprocessors.
Scheduling multiprocessor tasks to minimize schedule length.
A shortest tree algorithm for optimal assignments across space and time in a distributed processor system.
Partitioning problems in parallel
Benchmarking the iPSC/2 hypercube multiprocessor.
On embedding rectangular grids in hypercubes.
Algorithms for mapping and partitioning chain structured parallel com- putations
Parallel architectures and parallel algorithms for integrated vision systems.
Dynamic Programming: Models and Applications.
Dynamic partitioning in a transputer environment.
Complexity of scheduling parallel task systems.
Discrete optimization via marginal analysis.
Solving Problems on Concurrent Processors (Vol.
Architecture of a hypercube supercomputer.
On the embedding of arbitrary meshes in boolean cubes with expansion two dilation two.
Fundamentals of Computer Algorithms
On mapping systolic algorithms onto the hypercube.
A multistage linear array assignment problem.
Pipelined data-parallel algorithms
The processor partitioning problem in special-purpose partitionable systems
Point matching in a time sequence of stereo image pairs.
Motion Understanding
Embedding rectangular grids into square grids with dilation two.
Improved algorithms for mapping parallel and pipelined computa- tions
Utilizing multidimensional loop parallelism on large scale parallel processor systems.

Minimal mesh embeddings in binary hypercubes.
Characterizations of parallelism in applications and their use in scheduling

Scheduling Algorithms for PIPE (Pipelined Image-Processing Engine)
Multiprocessor scheduling with the aid of network flow algorithms.
Optimal partitioning of cache memory.
Allocating programs containing branches and loops within a multiple processor system.
The recognition of series parallel digraphs.
An integrated image understanding benchmark for parallel computers.
--TR
Allocating programs containing branches and loops within a multiple processor system
Scheduling multiprocessor tasks to minimize schedule length
A partitioning strategy for nonuniform problems on multiprocessors
Nearest-neighbor mapping of finite element graphs onto processor meshes
Solving problems on concurrent processors. Vol. 1: General techniques and regular problems
Partitioning Problems in Parallel, Pipeline, and Distributed Computing
Scheduling algorithms for PIPE (Pipelined Image-Processing Engine)
Minimal Mesh Embeddings in Binary Hypercubes
On Embedding Rectangular Grids in Hypercubes
Characterizations of parallelism in applications and their use in scheduling
Complexity of scheduling parallel task systems
Utilizing Multidimensional Loop Parallelism on Large Scale Parallel Processor Systems
Embedding Rectangular Grids into Square Grids with Dilation Two
Dynamic partitioning in a transputer environment
A multistage linear array assignment problem
The DARPA image understanding benchmark for parallel computers
Improved Algorithms for Mapping Pipelined and Parallel Computations
Optimal Partitioning of Cache Memory
Dynamic Programming
Computer Algorithms
Parallel Architectures and Parallel Algorithms for Integrated Vision Systems
Motion Understanding
On Mapping Systolic Algorithms onto the Hypercube
Pipelined Data Parallel Algorithms-II

--CTR
Ian Foster , David R. Kohr, Jr. , Rakesh Krishnaiyer , Alok Choudhary, Double standards: bringing task parallelism to HPF via the message passing interface, Proceedings of the 1996 ACM/IEEE conference on Supercomputing (CDROM), p.36-es, January 01-01, 1996, Pittsburgh, Pennsylvania, United States
Jaspal Subhlok , Gary Vondran, Optimal mapping of sequences of data parallel tasks, ACM SIGPLAN Notices, v.30 n.8, p.134-143, Aug. 1995
Jaspar Subhlok , Gary Vondran, Optimal latency-throughput tradeoffs for data parallel pipelines, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.62-71, June 24-26, 1996, Padua, Italy
G. Srinivasa N. Prasanna, Compilation of parallel multimedia computationsextending retiming theory and Amdahl's law, ACM SIGPLAN Notices, v.32 n.7, p.180-192, July 1997
Thomas Gross , David R. O'Hallaron , Jaspal Subhlok, Task Parallelism in a High Performance Fortran Framework, IEEE Parallel & Distributed Technology: Systems & Technology, v.2 n.3, p.16-26, September 1994
Wei-Keng Liao , Alok Choudhary , Donald Weiner , Pramod Varshney, Performance Evaluation of a Parallel Pipeline Computational Model for Space-Time Adaptive Processing, The Journal of Supercomputing, v.31 n.2, p.137-160, December  2004
Sandeep Koranne, A Note on System-on-Chip Test Scheduling Formulation, Journal of Electronic Testing: Theory and Applications, v.20 n.3, p.309-313, June 2004
Jaspal Subhlok , David R. O'Hallaron , Thomas Gross , Peter A. Dinda , Jon Webb, Communication and memory requirements as the basis for mapping task and data parallel programs, Proceedings of the 1994 conference on Supercomputing, p.330-339, December 1994, Washington, D.C., United States
Jaspal Subhlok , David R. O'Hallaron , Thomas Gross , Peter A. Dinda , Jon Webb, Communication and memory requirements as the basis for mapping task and data parallel programs, Proceedings of the 1994 ACM/IEEE conference on Supercomputing, November 14-18, 1994, Washington, D.C.
John W. Chinneck , Vitoria Pureza , Rafik A. Goubran , Gerald M. Karam , Marco Lvoie, A fast task-to-processor assignment heuristic for real-time multiprocessor DSP applications, Computers and Operations Research, v.30 n.5, p.643-670, April
Martin Fleury , Andrew C. Downton , Adrian F. Clark, Performance Metrics for Embedded Parallel Pipelines, IEEE Transactions on Parallel and Distributed Systems, v.11 n.11, p.1164-1185, November 2000
Jinquan Dai , Bo Huang , Long Li , Luddy Harrison, Automatically partitioning packet processing applications for pipelined architectures, ACM SIGPLAN Notices, v.40 n.6, June 2005
data sets;parallel architectures;series-parallel partial order;series-parallel task system;data dependencies;index termspipeline processing;series analysis;pipelined computations;task structure;multitasked parallel architectures;computer vision;parallel analysis;resource allocation;processor assignment problem