Probabilistic Loop Scheduling for Applications with Uncertain Execution Time.
AbstractOne of the difficulties in high-level synthesis and compiler optimization is obtaining a good schedule without knowing the exact computation time of the tasks involved. The uncertain computation times of these tasks normally occur when conditional instructions are employed and/or inputs of the tasks influence the computation time. The relationship between these tasks can be represented as a data-flow graph where each node models the task associated with a probabilistic computation time. A set of edges represents the dependencies between tasks. In this research, we study scheduling and optimization algorithms taking into account the probabilistic execution times. Two novel algorithms, called probabilistic retiming and probabilistic rotation scheduling, are developed for solving the underlying nonresource and resource constrained scheduling problems, respectively. Experimental results show that probabilistic retiming consistently produces a graph with a smaller longest path computation time for a given confidence level, as compared with the traditional retiming algorithm that assumes a fixed worst-case and average-case computation times. Furthermore, when considering the resource constraints and probabilistic environments, probabilistic rotation scheduling gives a schedule whose length is guaranteed to satisfy a given probability requirement. This schedule is better than schedules produced by other algorithms that consider worst-case and average-case scenarios.
Introduction
In many practical applications such as interface systems, fuzzy systems, articial intelligence systems, and
others, the required tasks normally have uncertain computation times (called uncertain or probabilistic
tasks for brevity). Such tasks normally contain conditional instructions and/or operations that could take
dierent computation times for dierent inputs. A dynamic scheduling scheme may be considered to address
the problem; however, the decision of the run-time scheduler which depends on the local on-line knowledge
may not give a good overall schedule. Although many static scheduling techniques can thoroughly check
for the best assignment for dependent tasks, existing methods are not able to deal with such uncertainty.
Therefore, either worst-case or average-case computation times for these tasks are usually assumed. Such
assumptions, however, may not be applicable for the real operating situation and may result in an inecient
schedule.
For iterative applications, statistics for the uncertain tasks are not dicult to collect. In this paper,
two novel loop scheduling algorithms, probabilistic retiming (PR) and probabilistic rotation scheduling
(PRS), are proposed to statically schedule these tasks for non-resource (assume unlimited number of target
processors) and resource constrained (assume limited number of target processors) systems respectively.
These algorithms expose the parallelism of the probabilistic tasks across iterations as well as take advantage
of the inherent statistical data. For a system without resource constraints, PR can be applied to optimize the
input graph (i.e., reduce the length of the longest path of the graph such that the probability of the longest
path computation time being less than or equal to some given computation time, c; is greater than or equal
to a given condence probability ). The resulting graph implies a schedule for the non-resource constrained
system where the longest path computation time determines its schedule length. On the other hand, the
PRS algorithm is used to schedule uncertain tasks to a xed number of multiple processing elements. It
produces a schedule length from the given graph and incrementally reduces the length so that the probability
of it being less than the previous length is greater than or equal to the given condence probability.
In order to be compatible with the current high performance parallel processing technology, we assume
that synchronization is required at the end of each iteration. Such a parallel computing style is also known
as synchronous parallelism [10, 19]. Both PR and PRS take an input application which can be modeled
as a probabilistic data-ow
graph (PG), which is a generalized version of a data-ow
graph (DFG) where a
node corresponds to a task (a collection of statements), and a set of edges representing dependencies between
these tasks and determine a schedule. The loop-carried dependences (dependency distances) between tasks
in dierent iterations are represented by short bar lines on the corresponding edges. Since the computation
times of the nodes can be either xed or varied, a probability model is employed to represent the timing of
the tasks.

Figure

1(b) shows an example of a PG consisting of 4 nodes. Note that such a graph models the code
segment presented in Figure 1(a) where, for example, A in the PG corresponds to A 1 and A 2 of the code
segment. Two bar lines on the edge between nodes D and A represent the dependency distances between
these two nodes. The computation time of nodes A and C are known to be xed (2 time units). In this code,
the uncertainty occurs in the computation of nodes B and D. Assume that each arithmetic operation and
the assignment operation (=) take 1 time unit. Furthermore, the computation time of the comparison and
random number generating operations are assumed negligible. Hence, it may take either 4 or 2 time units
to execute node B. Put another way, about 20% of the time (51 out of 256), statement B 2 will be executed
s
and node B will take 4 time units; otherwise node B takes only 2 time units (B 3 has only one operation).
Likewise, approximately 25% (64 out of 256), node D takes 4 time units, and about 75%, it will take 2 time
units. Each entry in Figure 1(c) shows a probability associated with each node's possible computation time
(the probability distribution). By taking into account these varying timing characteristics, the proposed
technique can be applied to a wide variety of applications in high-level synthesis and compiler optimization.
(a) Code segment
A
(b) PG
Time Nodes
(c) Timing information
A
(d) Retimed PG

Figure

1: A sample code segment, the corresponding PG and its computation time, and the retimed graph.
Considerable research has been conducted in the area of nding a schedule of a directed-acyclic graph
(DAG) for multiple processing systems. (Note that DAGs are obtained from DFGs by ignoring edges of a
containing one or more dependency distances.) Many heuristics have been proposed to schedule DAGs,
e.g., list scheduling, graph decomposition [11, 13] etc. These methods, however, consider neither exploring
the parallelism across iterations nor addressing the problems of probabilistic tasks.
For instruction level parallelism (ILP) scheduling, trace scheduling [9] is used to globally schedule DAGs
by rearraging some operations in the graphs. Percolation scheduling is used in a development environment [1]
for microcode compaction, i.e., parallelism extraction of horizontal microcode. Nevertheless, the graph model
used in these techniques does not re
ect the uncertainty in node computation times. In the class of global
cyclic scheduling, software pipelining [16] is used to overlap instructions, whereby the parallelism is exposed
across iterations. This technique, however, expands the graph by unfolding or unrolling [22] it resulting in
a larger code size. Loop transformations are also common techniques used to construct parallel compilers.
They restructure loops from the repetitive code segment in order to reduce the total execution time of the
schedule [2, 3, 20, 27, 28]. These techniques, however, do not consider that the target systems have limited
number of processors or that task computation times are uncertain.
Modulo scheduling [24{26] is a popular technique in compiler design for exploiting ILP in loops which
results in optimized codes. This framework species a lower bound, called initiation interval (II), to start
with and strives to schedule nodes based on such knowledge. Much research was introduced to improve
and/or expand the capability of modulo scheduling. For example, research was presented which improved
modulo scheduling by producing schedules while considering limited number of registers [7, 8, 21]. In [17],
a combination of modulo scheduling and loop unrolling was introduced and applied in the IMPACT compiler
[4]. These ILP approaches, however, are limited to solving problems without considering uncertain
computation times (probabilistic graph model).
Some research considers the uncertainty inherit in the computation time of nodes. Ku and De Micheli [14,
15] proposed a relative scheduling method which handles tasks with unbounded delays. Nevertheless, their
approach considers a DAG as an input and does not explore the parallelism across iterations. Furthermore,
even if the statistics of the computation time of uncertain nodes is collected, their method will not exploit
this information. A framework that is able to handle imprecise propagation delays is proposed by Karkowski
and Otten [12]. In their approach, fuzzy set theory [29] was employed to model the imprecise computation
times. Although their approach is equivalent to nding a schedule of imprecise tasks to a non-resource
constrained system, their model is restricted to a simple triangular fuzzy distribution and does not consider
probability values.
For scheduling under resource constraints, the rotation scheduling technique was presented by Chao,
LaPaugh and Sha [5, 6] and was extended to handle multi-dimensional applications by Passos, Sha and
Bass [23]. Rotation scheduling attempts to pipeline a loop by assigning nodes from the loop to the system
with a limited number of processing elements. It implicitly uses traditional retiming [18] in order to reduce
the total computation time of the nodes along the longest paths (also called the critical paths), in the DFG.
In other words, the graph is transformed in such a way that the parallelism is exposed but the behavior of
the graph is preserved. In this paper, the rotation scheduling technique is extended so that it can deal with
uncertain tasks.
Since the computation time of a node in a PG is a random variable, the total computation time of this
graph is also a random variable. The concept of a control step (the synchronization of the tasks \within"
each iteration) is no longer applicable. A schedule conveys only the execution order or pattern of the
tasks being executed in a functional unit and/or between dierent units. In order to compute the total
computation time of this ordering, a probabilistic task-assignment graph (PTG) is constructed. A PTG is
obtained from a PG in which non-zero dependency distance edges are ignored and each node is assigned to
a specic functional unit in the system. The PTG also contains additional edges, called
ow-control edges
where a connection from u to v means that u is executed immediately before v using the same functional
unit. Note that in the non-resource constrained scenario, the PTG will be the DAG portion of the PG (a
subgraph that contains only no dependency distance edges).
Let us use the example in Figure 1(b). Assume that the term longest path computation time entails nd-
ing the maximum of the summation of computation times of nodes along paths which contain no dependency
distances. After examining all possible longest paths of this graph, it is likely (60%) that its longest path
computation time is less than or equal to 8. The details of how this value is determined is given in Section 3.
Note that if all nodes in this graph are assigned their worst-case values, the longest path computation time
(or schedule length for non-resource constrained systems) of this graph will be 10. One might wish to reduce
the longest path of this graph in nearly all cases, for example reducing the chance of the clock period being
greater than 6. By applying probabilistic retiming, the longest path computation time of the graph may be
improved with respect to the given constraint. The modied graph after retiming is shown in Figure 1(d).
The longest path computation time of this graph is less than than or equal to 6 with 20% chance.
If we need to schedule nodes from the PG to two homogeneous functional units, a possible PTG can be
constructed as shown in Figure 2(a). Since the input graph is cyclic, an execution pattern of this PTG is
repeated and the synchronization is applied at the end of each iteration as shown in Figure 2(a). The solid
edges in this PTG represent those zero dependency distance edges, called dependency edges, from the input
graph (see Figure 1(b)). In this gure, nodes A; B and D are assigned to PE 0 and node C is bound to PE 1 .
Note that D is implicitly executed after A; therefore, the direct edge from A to D from the original input
s
graph can be omitted. A corresponding static schedule which shows only one iteration from the execution
pattern is shown in Figure 2(c).
A
(a) The PTG
(b) Initial execution pattern
(c) Schedule

Figure

2: An example of PTG, its corresponding repeated pattern and the static execution order.
The resulting longest path computation time of the PTG is less than 9 units with 90% certainty. This
longest path timing and its probability are also known as a schedule length for resource constrained systems.
We can improve the resulting schedule length by applying our probabilistic rotation scheduling algorithm
to the PG and its PTG. In this case the algorithm rst selects the root node A to be rescheduled. Then
one dependency distance from the incoming edges of node A is moved to all its outgoing edges. Figure 3(a)
shows the resulting transformation graph of the PG. This new graph will be used as a reference to later
update the PTG. The new execution pattern is equivalent to reshaping the iteration window as presented
in

Figure

3(b).
A
(a) Rotate A
(b) Reshaping iteration window

Figure

3: The corresponding retimed PG and the repeated pattern after changing iteration window.
By applying the PRS algorithm, node A from the next iteration (see Figure 3(b)) is introduced to the
static execution pattern. Note that node A has no inter-iteration dependencies associated with it. Therefore,
A can be rescheduled to any available functional unit. One possible schedule is to assign node A immediately
after node C in PE 1 . The resulting PTG and the new execution order are shown in Figures 4(a) and 4(b)
respectively. The dotted arrow from C to A in this new PTG represents the
ow-control edge. For this
PTG, the resulting schedule length will be less than 7 with higher than 90% condence.
The remainder of this paper is organized as follows. Section 2 presents the graph model used in this
work. Required terminology and fundamental concepts are also presented. Section 3 discusses probabilistic
retiming and the algorithm for computing a total computation time of a probabilistic graph. The probabilistic
rotation scheduling algorithm and the supported routines will be discussed in Section 4. Experimental results
are discussed in Section 5. Finally, Section 6 draws conclusions of this research.
s
A
(a) PTG
(b) Static execution order

Figure

4: The resulting PTG and its execution order after rescheduling A.
Preliminaries
In this section, the graph model which is used to represent tasks with uncertain computation times is
introduced. Terminology and notations relevant to this work are also discussed. We begin by examining a
DFG that contains tasks with uncertain computation time which can be modeled as a probabilistic graph
(PG). The following gives the formal denition for such a graph.
Denition 2.1 A probabilistic graph (PG) is a vertex-weighted, edge-weighted, directed graph Ti,
where V is the set of vertices representing tasks, E is the set of edges representing the data dependencies
between vertices, d is a function from E to the set of non-negative integers, representing the
number of dependency distance on an edge, and T v is a random variable representing the computation
time of a node v 2 V.
Note that traditional DFGs are a special case of PGs where all probabilities equal one. Each vertex
is weighted with a probability distribution of the computation time, given by T v , where T v is a discrete
random variable corresponding to the computation time of v such that
8x
1. The notation
probability that random variable T assumes value x". The probability distribution
of T is assumed to be discrete in this paper. The granularity of the resulting probability distribution, if
necessary, depends on the needed degree of accuracy.
An edge e 2 E from u to v, u; v 2 V, is denoted by u e
v and a path p starting from u and
ending at v is indicated by the notation u
v: The number of dependency distances of path p (d(p)),
As an example, Figure 1(b) has the set of edges
Ag. The number of dependency distances on each edge
2.
The execution order or execution pattern of a PG are determined by the precedence relations in the
graph. During one iteration of the graph each vertex in the execution order is computed exactly one time.
Multiple iterations are identied by index i, starting from 0. Inter-iteration dependencies are represented by
weighted edges or dependency distances. For any iteration j, an edge e from u to v with dependency distance
conveys that the computation of node v at iteration j depends on the execution of node u at iteration
An edge with no dependency distances represents a data dependency within the same iteration.
A legal data
ow graph must have strictly positive dependency distance cycles, i.e., the summation of the
along any cycle cannot be less than or equal to zero.
2.1 Retiming overview
Retiming operations rearrange registers in a circuit or dependency distances in a data-ow
graph in such a
way that the behavior of the circuit is preserved while achieving a faster circuit. Traditionally, retiming [18]
optimizes a synchronous circuit (graph) ti which has non-probabilistic functional elements,
i.e., each of the vertices associated with a xed numerical timing value. The optimization goal is
normally to reduce the clock period or cycle period (G) (also known as longest path computation time).
The cycle period represents the execution time of the longest path (referred to as the critical path) that
has all zero dependency distance edges. It is dened by the equations
Retiming of a graph ti is a transformation function from vertices to the set of integers,
Z. The retiming function describes the movement of dependency distances with respect to the
vertices so as to transform G into a new graph G represents the number of
dependency distances on the edges of G r . The positive (or negative) value of the retiming function determines
the movement of the dependency distances. During retiming the same number of dependency distances is
pushed from all incoming (outgoing) edges of a node to all outgoing (incoming) edges. If a single dependency
distance is pushed from all incoming edges of node u 2 V to all outgoing edges of node u, then
Conversely, if one dependency distance is pushed from all outgoing to all incoming edges of u, then
The absolute value of the retiming function conveys the number of dependency distances that are pushed.
An algorithm to nd a set of retiming functions to minimize the clock period of the graph presented in [18]
is a polynomial time algorithm which has the time complexity of O(jV jjEj
log jV j).
Consider Figure 5(a) which illustrates a simple graph with four vertices, A; B; C and D: The numbers
next to the vertices in the gure represent the required computation times. Figure 5(b) represents a retimed
version of Figure 5(a) where In this case, the movement of
dependency distances is as follows: is equivalent to removing two dependency distances from
the incoming edge of vertex A, D e
adding them onto edges A e
D: The
retiming functions for nodes C and B are 1. This means that one dependency distance from
A e
pushed through vertex B to edge B e
Similarly, one dependency distance from edge A e
is pushed through vertex C to C e
An equivalent set of retimings in Figure 5(b) is
This equivalent set of retimings produces the same graph by pushing the
dependency distances backward through nodes D; B and C; instead of forward through nodes A; B and C:
The dotted lines in Figure 5(a) represent the critical path of the graph, for which
the critical path becomes illustrated by the dotted line in Figure 5(b).
The following summarizes some essential properties of the retiming transformation.
1. r is a legal retiming if d r (e)  0; 8e 2 E.
2. For an edge u e
3. For a path u
4. In any directed cycle (l) of G and G r , d r
guarantees that the retimed graph will not have any edge containing a negative number of
dependency distances. Properties 2 and 3 explain the movement of such distances. If r(v), v 2 V, has a
A
(a) Before
(b) After

Figure

5: Retiming transformations (before and after retiming) where dotted edges represent the critical
path.
positive value, the distances will be deleted from the incoming edge(s) of v and inserted onto the outgoing
edge(s), and vice versa if r(v) has the negative value. Finally, Property 4 ensures that the number of
dependency distances in any loop of the graph remains constant. That requires that all cycles have at least
one dependency distance. Since retiming is an optimization technique which is subject to unlimited number
of target resources, the resulting longest path computation time after the transformation is the underlying
schedule length. Consider only a DAG part of the retimed graph where edges with non-zero dependency
distances in the retimed graph are ignored. The iteration boundaries of this schedule will be at the root
nodes (beginning of the iteration) and at the leaf nodes (end of the iteration).
2.2 Rotation scheduling
In [5], Chao, LaPaugh and Sha proposed an algorithm, called rotation scheduling, which uses the retiming
algorithm to deal with scheduling a cyclic DFG under resource constraints. The input to the rotation
scheduling algorithm is a DFG and its corresponding static schedule, i.e., a synchronized order of the nodes
in the DFG. Rotation scheduling reduces the schedule length (the number of control steps needed to execute
one iteration of the schedule) by exploiting the parallelism between iterations. This is accomplished by
shifting the scope of a static schedule in one iteration, called the iteration window, down by one control
step. Looking at a static iteration, rotation scheduling analogously rotates tasks from the top of the schedule
of each iteration down to the end. This process is equivalent to retiming those tasks (nodes in the DFG) in
which one dependency distance will be deleted from all their incoming edges and added to all their outgoing
edges resulting in an intermediate retimed graph. Once the parallelism is extracted, the algorithm reassigns
the rotated nodes to new positions so that the schedule length is shorter.
As an example, the cyclic DFG in Figure 6(a) is to be scheduled using two processing elements. Figure
presents one possible static schedule for such a graph. By using rotation scheduling, this schedule
can be optimized. First, the algorithm uses node A from the next iteration. The original graph is retimed by
dependency distance from E e
A is moved to all outgoing edges of A (see Figure 6(c)).
By doing so, node A now can be executed at any control step in this new iteration window. Assume that
rotation scheduling uses a re-mapping strategy that places node A immediately after node C in PE 1 . The
resulting static schedule length is then reduced by one control step as shown in Figure 6(d). In Section 4,
the concept of the schedule length and the re-mapping strategy will be extended to handle probabilistic
s
inputs.
A D
(a) Cyclic DFG
Iter. i th Iter.
(b) Static schedule
A
(c) Retimed
(d) Resulting schedule

Figure

An example to present how rotation scheduling optimizes the underlying schedule length.
3 Non-resource constrained scheduling
Assuming there are innite available resources, a PG can be optimized with respect to a desired longest path
computation time and condence level. In eect, this is an attempt to reduce the longest path computation
time of the graph. The distribution of dependency distances in the PG is done according to a probabilistic
timing constraint where the probability of obtaining the timing result (longest path computation time) being
less than or equal to a given value c is greater than some condence probability value . This resulting
timing information is essentially the schedule length of the non-resource constrained problem. This section
presents an ecient algorithm for optimizing a probabilistic graph with respect to a desired computation
time (c) and its corresponding condence probability (). In order to evaluate the modied graph, we
need to know the probability distribution associated with its computation time. The remaining subsections
discuss these issues.
3.1 Computing maximum reaching time
Let G dag be the DAG portion (the subgraph that has only edges with no dependency distances) of a
probabilistic graph G. Assume that two dummy nodes, v s and vd , are added to G dag where v s connects
to all source nodes (roots) and vd is connected by all sink nodes (leaves). Traditionally, the longest path
computation time of a graph is computed by maximizing the summation of the computation times of the
nodes along the critical (longest) paths between these dummy nodes. Likewise, for a probabilistic graph we
can compute the summation of the computation time for each path from v s to vd in the graph. In this case
the largest summation value is called the maximum reaching time, or mrt, of the graph. The mrt of a PG
exhibits a possible longest path computation time of the graph and its associated probability. Therefore,
unlike the traditional approach, the summation and maximum functions of the computation time along the
paths in a PG become functions of multiple random variables.
s
To compute an mrt of a PG, we need to modify the graph so that v s and vd are connected to the
DAG portion of the original graph. Formally, a set of zero dependency distance edges is used to connect
vertex v s to all roots, and to connect all leaves to vertex vd . Since it is non-trivial to eciently compute
a function of dependent random variables, Algorithm 1 computes the mrt(G) assuming that the random
variables are independent. This algorithm traverses the input graph in a breadth-rst fashion starting from
v s and ending at vd . In general, the algorithm accumulates the probabilistic computation times along each
traversed path. When it reaches a node that has more than one parent, all the values associated with its
parents are maximized.
Algorithm 1 Calculate maximum reaching time of graph G
Require: probabilistic graph PG
Ensure:
2:
e
e
3: 8
4: while Queue 6= ; do
5: get node u from top of the Queue
7: for all u e
do
8: decrement the incoming degree of node v by one
10: if incoming degree of node v becomes 0 then
11: insert node v into the Queue
12: end if
13: end for
14: end while
Lines 1 and 2 produce DAG G 0 from G containing only edges e 2 E, with and the additional
zero dependency distance edges connecting v s to every root node v 2 V r of G and connecting every leaf node
l of G to vd . Line 3 initializes the temp mrt (v s ; u) value for each vertex u in the new graph and sets the
computation time of T vs and T vd to zero. Lines 4{12 traverse the graph in topological order and compute
the mrt of each v with respect to v s (temp mrt (v s ; vd )). Note that the temp mrt for node v with respect to v s
is originally set to zero. It stores the current maximum computation time of all node v's visited parents.
When the rst parent of v is dequeued, v has its indegree reduced by one (Line 8) and temp mrt is updated
(Line 9). Vertex v's other parents are in turn dequeued, and the process is repeated. Eventually, the last
parent of node v will be dequeued and maximized. At this point, node v will be inserted into the queue
since all parents have been considered, i.e., indegree of v equals zero (Line 10). Node v will be eventually
dequeued by Line 5. Line 6 will then add T v to the temp mrt of node v producing the nal mrt with respect
to all paths reaching node v.
Noting that the initial computation times are integers and the probabilities associated with these times
being greater than the given value c are accumulated as one value in the algorithm. Only O(c
need to be stored for each vertex. Therefore, the time complexity for calculating the summation (Line 6), or
the maximum (Line of two vertices is O(c 2 ). Since the algorithm computes the result in a breadth rst
s
fashion, the running time of Algorithm 1 is O(c 2 jVjjEj), while the space complexity is bounded by O(cjV j).
3.2 Probabilistic retiming
Using the concept of the mrt, Algorithm 2 presents the probabilistic retiming algorithm which reduces the
longest path computation time of the given PG to meet a timing constraint. Such a constraint is that
c is the desired longest path computation time of the graph and  is the
condence probability. This requirement can be rewritten as Pr(mrt(v s
The algorithm retimes vertices whose computation time being greater than c has a probability larger than
the acceptable probability value. Initially, the retiming value for each node is set to zero and non-zero
dependency distance edges are eliminated. Then, v s is connected to the root-vertices of the resulting DAG
and vd is connected by the leaf-vertices of the DAG. Lines 7{17 traverse the DAG in a breath-rst search
manner and update the temp mrt for each node as in Algorithm 1. After updating a vertex, the resulting
temp mrt is tested to see if the requirement, Pr(temp mrt (G) > c)  , is met. Line 19, then decreases the
retiming value of any vertex v that violates the requirement unless the vertex has previously been retimed
in the current iteration. The algorithm then repeats the above process using the retimed graph obtained
from the previous iteration. If the algorithm nds the solution for a given clock period, the nal retimed
graph implies the number of required resources to achieve such a schedule length.
Line 19 pushes a dependency distance onto all incoming edges of a node that violates the timing con-
straint. Since all descendents of this node will also be retimed, Line 19 in essence moves a dependency
distance from below vd to above this node. In other words, all nodes from u to vd . Hence
only the incoming edges of vertex u will have an additional dependency distance. Once no nodes are retimed
in the current iteration, the requirement Pr(mrt(v s ; vd ) > c)   is met. The algorithm stops and reports
the resulting retiming functions associated with nodes in the graph. If this requirement is not met, the
algorithm repeats at most jVj times. Since the computation of the maximum reaching time is performed in
every iteration, the time complexity of this algorithm is O(c 2 jVjjEj) while the space complexity remains the
same as in the maximum reaching time algorithm. The resulting retiming function returned by Algorithm 2
guarantees (necessary condition) the following:
Theorem 3.1 Given desired cycle period c, and a condence probability
if Algorithm 2 (probabilistic retiming algorithm) nds a solution then the resulting retimed graph G r
satises the requirement Pr(mrt(G)  c)  .
3.3 Example
Consider the PG and the probability distribution associated with nodes in the graph in Figure 7. For
this experiment, let 6 be the desired longest path computation time and 0:2 be the acceptable
probability. Algorithm 2 works by rst checking and computing the mrt from v s to A and E. Then, it
topologically calculates the mrt of the adjacent nodes of A and E. After it computes the mrt of node I,
Three iterations of Algorithm 2 which computes the results of the maximum reaching time from v s to v
including vd are tabulated in Tables 1{3. After the rst iteration, the retiming value associated with nodes
D, F, H, and I are shown in Column r(v) of Table 1. The values in Columns 2{8 show the probability
s
Algorithm 2 Probabilistic retiming
Require: probabilistic graph, a requirement Pr(temp mrt (G) > c)
Ensure: retiming function r for each node to meet the requirement
1: 8 node v 2 V initialize retiming function r(v) to 0
2: for do
3: retime graph G r with the retiming function r(v)
4: G directed acyclic portion (DAG) of G r
5: prepend dummy node v s to G 0 fconnects to all root nodesg
append dummy node vd to G 0 fconnected by all leaf nodesg
7: for all nodes in G 0 do
8: temp mrt (v s
9: insert v s into Queue
timing of two dummies to zerog
11: end for
12: while Queue 6= ; do
13: get node u from the Queue
14: temp mrt (v s fadding two random variablesg
15: for all u e
do
decrement number of incoming degrees of node v by one
fmaximizing two random variablesg
and u has not been retimed then
dependency distance from all outgoing edges to all incoming edgesg
20: end if
21: if number of incoming edges of node v is 0 then
22: insert node v into a ready Queue
23: end if
24: end for
25: end while
26: end for
I
G
F
A
(a)
Time Nodes
(b)

Figure

7: An example of a 9-node graph and its corresponding probabilistic timing information.
s
that the mrt(v s ; v), 8v 2 V, ranges from 1 to 6 and greater than 6 (> respectively. The retimed graph
associated with the retiming value in Table 1 after the rst iteration is presented in Figure 8(a). Table 2
presents the maximum reaching time from the dummy node v s to each node v 2 V as well as the retiming
function for each vertex after the second iteration. Figure 8(b) presents the retimed graph corresponding to
the retiming function presented in Table 2. By computing the mrt(v s ; v) of the retimed graph in Figure 8(b),
it becomes apparent that nodes B and C need to be retimed. Figure 8(c) illustrates the nal retimed graph
in accordance with the retiming function presented in Table 3. Note that Table 3 also presents the nal
maximum reaching time and retiming value for each vertex which satises the required conguration. From
this nal retimed graph, one could, therefore, allocate a minimum of ve processing elements in order to
compute the graph in six time units with 80% condence.
I
G
F
A
(a)
I
G
F
A
(b)
I
G
F
A
(c)

Figure

8: Retimed graph corresponding to Tables 1{3.
I

Table

1: First iteration showing probability distributions of mrt(v s ;
Resource-constrained scheduling
In this section, we present a probabilistic scheduling algorithm which considers an environment where there
are a limited number of resources. The traditional rotation scheduling framework is extended to handle the
probabilistic environment. We call this algorithm probabilistic rotation scheduling (PRS). Given a PG,
the algorithm iteratively optimizes the PG with respect to the condence probability and the number of
resources.
Before presenting this algorithm, we rst discuss two important concepts that make scheduling under the
probabilistic environment dierent from traditional scheduling problems. First, in the probabilistic model a
I

Table

2: Second iteration showing probability distribution of mrt(v s ;
I

Table

3: Third iteration showing probability distribution of mrt(v s ;
synchronization control step is not available. A node can begin its execution if all of its parents have already
been executed. This is similar to the asynchronous model where data request and handshaking signals are
used to communicate between nodes. The schedule can be viewed as a directed graph where edges show
either the data requirement to execute a node or the order that a node can be executed in a particular
functional unit. Note that a synchronization will be applied at the end of each iteration.Second, the task
re-mapping strategy for PRS should take the probabilistic nature of the problem into account. The following
subsections discuss these concepts in more details.
4.1 Schedule length subject to the condence
The concept of mrt can be used to compute the underlying schedule length. Hence, the conventional way
of calculating schedule length has to be redened to include the mrt notion. In order to do so, we update
the probabilistic data
ow graph by adding the resource information and extra edges between two nodes
executed consecutively in the same functional unit and have no data dependencies between them. This
graph, called the probabilistic task-assignment graph (PTG), represents a schedule under the probabilistic
model.
Denition 4.1 A probabilistic task-assignment graph T; bi; is a vertex-weighted, edge-
weighted, directed acyclic graph, where V is the set of vertices representing tasks, E is the set of edges
representing the data dependencies between vertices, w is a edge-type function from e 2 E to f0; 1g,
where 0 represents the type of dependency edge and 1 represents the type of
a random variable representing the computation time of a node v 2 V, and b is a processor binding
s
function from v 2 V to fPE processing element i and n is the total number
of processing elements.
A

Figure

9: An example of a probabilistic task-assignment graph (PTG) where the nodes are assigned to PE 0
and PE 1 .
As an example, Figure 9 shows an example of the PTG with two functional units PE 0 and PE 1 . Nodes
B and D are assigned to PE 0 . That is Edges consists
of C
here that if there exists
edges all of the nodes are scheduled to the same processor, edge A ! D which was
a true dependence edge can be ignored. Note also that removing redundancy edges is simple and should
be utilized to speed up the calculation of mrt. In Figure 9, edge C e1
A is control-typed since A now has
no dependency to C but has to execute after C due to resource constraints. Other edges represent data
dependencies. Applying the mrt algorithm to the PTG, we can dene the probabilistic schedule length.
This length is expressed in terms of condence probability as follows.
Denition 4.2 A probabilistic schedule length of PTG with respect to a condence level
psl(G; ), is the smallest longest path computation time c such that Pr(mrt(G) > c) < 1 - .
For example, consider the probability distribution of the mrt(G):
Possible computation time
Prob.
Given a condence probability 0:8, the probabilistic schedule length psl(G; 0:8) is 14. This is because the
smallest possible computation time is 14 where Pr(mrt(G) > 14) < 0:2; i.e., 0:04365
0:07818 < 0:2. Therefore with above 80% condence, the computation time of G is less than 14.
4.2 Task re-mapping heuristic: template scheduling
In this subsection we propose a heuristic, called template scheduling (TS), to search for a place to re-schedule
a task. This re-mapping phase plays an important role in reducing the probabilistic schedule length in PRS.
Since the computation time is a random variable, there is no xed control step within an iteration. As long
as a node is placed after its parents, any scheduling location is legal.
In template scheduling, a schedule template is computed using the expectation of the computation time
of each node. This template implies not only the execution order, but also the expected control step that a
node can start execution. In order to determine an expected control step, each node in a PTG is visited in
the topological order and the following is computed.
s
Denition 4.3 The expected control step of node v of PTG computed by:
e
represents the expected computation time of node
This denition assumes node v can start its execution right after all parents nish their execution. By
observing this template, one can ascertain how long (the number of control steps) each processing element
would be idle. The template scheduling decides where to re-schedule a node using \their degree of
exibility".
Denition 4.4 Given a PTG a degree of
exibility of node u with respect to the
processing element PE i , d
ex(u; i), is computed by: d
and u and v are assigned to PE i .
The degree of
exibility conveys the expected size of available time slot within PE i . Figure 10 shows a typical
case where node v has more than one parent. u 1 , u 2 and u 3 are parents of node v and each of these parents

Figure

10: An example of how to obtain the Expected control step.
has the expected computation time 1; 4; and 3 respectively. In the same order, the expected control steps
of these nodes are 3; 4:7; and 3:7 respectively. Therefore, the expected control step According
to Denition 4.3, the degree of
exibility of u with respect to PE 0 , is 8:7 - 3 This value conveys
how long PE 0 has to wait before v can be executed. Note that the degree of
exibility of a node, which is
executed last in any PE, is undened. The following steps compute the new G after rescheduling node v.
Algorithm 3 Rescheduling rotated nodes using the template scheduling heuristic
Require: PTG, rescheduled node v, and condence probability
Ensure: Resulting new PTG with shortest psl
1: Assume that all nodes in the PTG have their expected computation times pre-computed
2: 8 node u 2 V compute Ecs(u) and d
ex(u)
3: for each of target processors (PE i ) do
4: Using the maximum dlfex to select node x which is scheduled to PE i
5: schedule v after x
reconstruct a new PTG (associated with PE i ) with this assignment
7: compare it with others PTG and get the one that has the best psl
8: end for
This rescheduling policy hopes that placing a node in the processor with the expected biggest idle time
slot results in the least potential of increasing the total execution time. If a computation time of the node is
s
much smaller than the expected time slot, this approach may allow the next rescheduled node to be placed
here also. This is similar to the worst-t policy where the scheduler strives to schedule a node to the biggest
slot. In Section 5, we demonstrate the eectiveness of this heuristic over the method that exhaustively nds
the best place for a node. Note that this exhaustive search is not performed globally, rather the search is
done locally in each re-mapping iteration. We call this heuristic a local search (LS).
4.3 Rotation phase
Having discussed the rescheduling heuristic, the following presents the probabilistic rotation scheduling
(PRS). Note that the previous heuristic or any rescheduling heuristic can be used as rescheduling part of
this PRS algorithm. The experiments in Section 5 show the ecacy of the PRS framework with dierent
rescheduling heuristics.
Algorithm 4 Probabilistic Rotation Scheduling
Require: PG and designer's condence probability
Ensure: PTG with a shortest psl
1:
2: G s ( nd initial schedule fnding an initial schedule for PG and keep it in G s g
3: for do
4: R ( all roots of a DAG portion of G s fthese are nodes to be rotatedg
5: retime each of the nodes in R
reschedule these node one by one using the heuristic previously presented
7: compute psl of the new graph with respect to
8: if psl(G
9: G best ( G s fconsidering that G best is initialized to G s rstg
11: end for
In order to use template scheduling, an expected computation time of each task will be precomputed.
After that, an initial schedule is constructed by nd initial schedule. Note that the algorithm for creating the
initial schedule can be any DAG scheduling, e.g., probabilistic list scheduling discussed previously. Rotation
scheduling loops for 2jV j
times to reschedule all nodes in the graph at least once. Like traditional rotation
scheduling, only nodes that have all their incoming edges with non-zero dependency distances are selected
to be rescheduled. One dependency distance will be drawn from each of these edges and placed on their
outgoing edges. Then these rotated nodes will be rescheduled one by one using the template scheduling
technique. After all rotated nodes are scheduled, if the resulting PTG is better than the current one,
Algorithm 4 will save the better PTG.
4.4 Example
Let us revisit the PG example in Section 3.3 as shown in Figure 11(a) and the corresponding computation
time in Figure 11(b). The condence probability is given as list scheduling is applied, the
initial execution order is determined as shown in Figure 12(a). The corresponding PTG is presented in
s

Figure

12(b). Nodes A; B; H and I are assigned to PE 0 , nodes E and F are scheduled PE 1 and nodes C; G
and D are assigned to PE 2 . Edges B e
G and G e
! D are
ow-control edges.
I
G
F
A
(a)
Time Nodes
(b)

Figure

11: An example of the computation time of graph in Figure 1(b).
For this assignment, the mrt of such a PTG is computed as following:
Possible computation time
Therefore, with higher than 80% condence probability, psl(G;
According to the structure of the PTG, either A or E can be rescheduled. In the rst rotation, PRS
selects A to be rescheduled. One dependency distance is moved from all incoming edges of A and pushed
to all outgoing edges of A. The resulting retimed graph PG is shown in Figure 13(a). In this graph, node
A requires no direct data dependency from any node. Therefore, A can be placed at any position in the
schedule. Figure 13(b) shows the expected computation time, the expected control step, and the degree of
exibility of each node in this PTG.
Based on the values in the table from Figure 13(b), it is obvious that an expected waiting time between B
and H in PE 0 would be 2.2 units. The template scheduling, however, decides to place A in a position between
B and H in PE 0 where the psl can be reduced. The resulting PTG and its execution order are shown in

Figure

14 where psl(G; running PRS for iterations, the shortest possible schedule length
was found in the 15 th iteration. In Figure 15, we present the resulting schedule length of the this trial which
is less than 9 with probability greater than 80% (psl(G;
(a) Static execution order
I
A
(b) PTG

Figure

12: Initial assignment and the corresponding execution order.
G
F
A
(a) New PG
d
ex
(b) Ecs and d
ex

Figure

13: The probabilistic graph after A is rotated and the template values.
I
G
A
(a) PTG
(b) Execution order

Figure

14: The PTG, execution order and its mrt after the rst rotation where psl(G;
I
G
F
A
(a) PG
I
G
F
A
(b) PTG
(c) Final execution order

Figure

15: The nal PG, PTG, execution order where psl(G; 9.
5 Experimental Results
In this section we perform experiments both using non-resource and resource constrained scheduling on
two general classes of problems. The rst class are real applications which may have a combination of
nodes with probabilistic computation times and with xed computation times. The second are well known
DSP lter benchmarks. Since these benchmarks contain two uniform types of nodes, namely multiplication
and addition, the basic timing information consisting of three probability distribution are assigned to each
benchmark graphs. In order to show the usability of the proposed algorithm, three applications are proled
to get their probabilistic timing information. The proler reports the processing time requirement in these
applications and the corresponding frequency of this time value. The frequency of timing occurances is
used to obtain a node probability distributions. A node in these graphs may represent a large number
of operations which cause the uncertain computation time as well as operations which have xed timing
information. Each timing information is discretized to a smaller unit such as nanoseconds.
The DSP lter benchmarks used in these experiments include a Biquadratic IIR lter, a 3-stage IIR lter,
a 4 th -order Jaunmann wave digital lter, a 5 th -order elliptic lter, an unfolded 5 th -order elliptic lter with
an unfolding factor equal to 4 4), an all-pole lattice lter, an unfolded all-pole lattice lter
an unfolded all-pole lattice lter dierential equation solver and a Volterra lter. The rest of
the benchmarks are the application for image processing (Floyd-Steinberg), the application to search for a
solution which maximize some unknown function by using genetic algorithm, and the famous example of the
application in the fuzzy logic area, the inverted pendulum problem. All of the experiments were performed
using SUN UltraSparc (TM) .
5.1 Non-resource constrained experiments
In each experiment, for a given condence level is used to search for the best longest
path computation time. In order to do this, the current desired longest path computation time (c) is varied
based on whether or not a feasible solution is found. For instance, if c is too small, the algorithm will report
that no feasible solution exists. In this case, c is increased and Algorithm 2 is re-applied. This process will
repeated, until the smallest feasible c is found.

Table

4 shows the results for traditional retiming using worst-case computation time assumptions (column
c worst) and the probabilistic model with two high condence probabilities . The average
running time for these experiments was determined to be below seconds including the input/output
interfaces. The algorithms are implemented in a straightforward way where array is used to store probability
distributions. Column 3 in the table presents the optimized longest path computation times obtained from
applying traditional retiming using the worst-case computation time for each node in the graph benchmarks.
For columns where 0:8, the probabilistic retiming algorithm is applied to the benchmarks
while each of these condence probabilities is used as its input. The numbers show in both columns are
the given c where Pr(mrt(G)  c)  . The value c from this requirement is the smallest input value which
Algorithm 2 can nd a solution to satisfy such a requirement. Notice that for all benchmarks the longest
path computation time with are still smaller than the computation time in Column 3. In order
to quantify the improvement of the probabilistic retiming algorithm, the \%" columns list the percent of
computation time reductions with respect to the value from Column 3.
Benchmark # nodes c worst c % c %
Biquad IIR 8 78
Di. Equation 11 118 81 31 77 35
3-stage direct IIR 12 54 44 19 41 24
All-pole Lattice 15 157 120 24 117 25
4 th order WDF 17 156 116 26 112 28
Volterra
5 th Elliptic 34 330 240 28 236 29
All-pole Lattice (uf=2)
All-pole Lattice (uf=6) 105 1092 811 26 806 26
5 th Elliptic (uf=4) 170 1633 1185 27 1174 28
Genetic application
Fuzzy application 24 19 17 11 17 11

Table

4: Probabilistic retiming versus worst case traditional retiming. Average completion time for running
probabilistic retiming against these benchmarks is 53.10 seconds.

Table

5 compares the probabilistic retiming algorithm to the traditional retiming algorithm with average
computation times used for each node in the graphs. First, the probabilistic nodes of each input graph
are converted to xed time nodes resulting in G avg , i.e., each node assumes its average computation time
rather than probabilistic computation time. Traditional retiming is then applied to the resulting graph,
resulting in graph G r
The purpose of this table is to compare G r
avg (obtained from running traditional
retiming on G avg ) with retimed PGs. In order to compare with the results produced by the proposed
algorithm, the placement of dependency distance in each G r
avg is preserved while the original probabilistic
computation times are replaced with the average computation times. Put another way, we transformed
each G r
avg back to a probabilistic graph. Algorithm 1 is then used to evaluate these graphs while only the
expected values of each result are shown in the table. Columns 4 and 5 present the expected values of the
results obtained from running probabilistic retiming on each PG where the condence probability of 0:9 and
0:8 are considered. Note that these results are consistently better (smaller value) than the results obtained
from running traditional retiming on each of G avg . Hence, the approach of using the expected values for
each node is neither a good heuristic in the initial design phase nor does it give any quantitative condence
to the resulting graphs.
5.2 Resource-constrained experiments
We tested the probabilistic rotation scheduling (PRS) algorithm on the selected lter and application bench-
marks: the 5 th elliptic lter, 3 stage-IIR lter, Volterra lter, Lattice lter, and Floyd-Steinberg, Genetic
algorithm, Fuzzy logic applications. Table 6 demonstrates the eectiveness of our approach on both 2-adder,
1-multiplier and 2-adder, 2-multiplier systems for those lter benchmarks. The specication of 3 and 4
general purpose processors (PEs) are adopted for the other three application benchmarks. The performance
of PRS is evaluated by comparing the resulting schedule length with the schedule length obtained from
s
Traditional Algorithm 2
Benchmark mrt(G r
avg
Biquad IIR 70.40 52.64 52.30
Di. Equation 76.05 73.07 72.50
3-stage direct IIR 41.90 37.70 38.36
All-pole Lattice 114.45 111.77 111.40
4 th order WDF 106.73 106.44 105.98
Volterra 204.00 202.44 202.00
5 th Elliptic 233.30 228.41 227.59
All-pole Lattice (uf=2) 342.17 338.11 337.62
All-pole Lattice (uf=6) 800.51 794.02 793.39
5 th Elliptic (uf=4) 800.51 794.02 793.39
Genetic application 150.89 144.01 112.46
Fuzzy application 18.03 16.08 16.08

Table

5: Probabilistic retiming versus average-case analysis.
the modied list scheduling technique (capable of handling the probabilistic graphs). We also show the
eectiveness of template scheduling (TS) by comparing its results with other heuristics, namely, local search
(LS), and as-late-as possible scheduling (AL). The average execution times of AL and TS are very comparable
(about 12 seconds running on UltraSparc (TM) ) while LS takes much longer time and does not give the
outstanding results comparing with those from TS.
In each rescheduling phase of PRS, the LS approach strives to reschedule a node to all possible legal
location (local search) and returns the assignment which yields the minimum psl(G; ). This method is simple
and gives a good schedule; however, it is time consuming and not practical to try all possible scheduling
places in every iteration of PRS. Furthermore, a PTG needs to be temporarily updated in every trial in
order to compute the possible schedule length. On the contrary, the AL method reduces the number of trials
by attempting to schedule a task only once at the farthest legal position in each functional unit or processor
while the TS heuristic re-maps the scheduled node after the node with the highest degree of
exibility in
each functional unit.
Columns show the results when considering the probabilistic situations with
condence probabilities 0.8 and 0.9. Column \PL" presents the probabilistic schedule length (psl) after
modied list scheduling is applied to the benchmarks. Columns \LS", \AL", and \TS" show the resulting
psl, after running PRS against those benchmarks using the re-mapping heuristics LS, AL and TS respectively.
Among these three heuristics, the TS scheme produces better results than AL which uses the simplest criteria.
Further, it yields as good as or sometimes even better results than given by the LS approach, while TS taking
less time to select a re-scheduled position for a node. This is because in each iteration the LS method nds
the local optimal place. However, scheduling nodes to these positions does not always result in the global
optimal schedule length.
In

Table

7, based on the system that has 2 adders and 1 multiplier (for lter benchmarks) and 3PEs (for
application benchmarks), we present the comparison results obtained from applying the following techniques
to the benchmarks: modied list scheduling, traditional rotation scheduling, probabilistic rotation scheduling
s
Spec. Benchmarks #nodes
PL PRS PL PRS
Di. Equation 11 169 152 133 133 165 147 131 131
Adds. 3-stage IIR 12 188 184 151 151 184 179 147 147
All-pole Lattice 15 229 225 142 141 225 220 138 138
Volterra
5 th Elliptic 34 318 298 293 293 314 294 289 289
28 28 27
Genetic application
Fuzzy application 24 52 46 43 43
Di. Equation 11 120 103 83 90 117 100 83 91
Adds. 3-stage IIR 12 124 120 87 87 120 110 83 82
Muls. All-pole Lattice 15 229 225 140 139 225 220 136 136
Volterra
5 th Elliptic 34 288 288 274 271 284 274 270 267
26 28 38 24 24 24
Genetic application
Fuzzy application 24

Table

Comparison of the results obtained from applying the following benchmarks: modied list, and
probabilistic rotation scheduling (using dierent re-mapping heuristics). Average completion time for running
AL, LS, and TS heuristics against these benchmarks are 11.96, 42.58, and 12.46 seconds respectively.
s
using template scheduling heuristic, and traditional rotation scheduling considering average computation
times. Columns \L" and \R" show the schedule length obtained from applying modied list scheduling and
traditional rotation scheduling respectively to the benchmarks where all probabilistic computation times are
converted into their worst-case computation times. Obviously, considering the probabilistic case gives the
signicant improvement of the schedule length over the worst case scenario.
Column \PL" presents the initial schedule lengths obtained from using the modied list scheduling ap-
proach. The results in column \PRS" are obtained from Table 6 (PRS using template scheduling heuristic).
In column \AVG", the psls are computed by using the graphs (PTGs) retrieved from running traditional
rotation to the benchmarks where the average computation time is assigned to each node. These results
demonstrate that considering the probabilistic situation while performing rotation scheduling can consistently
give better schedules than considering only worst-case or average-case computation times.
Spec. Benchmarks #nodes worst case
Di. Equation 11 228 180 169 133 136 165 131 131
All-pole Lattice 15 312 204 229 141 153 225 138 149
Volterra
5 th Elliptic 34 438 396 318 293 299 314 289 294
Genetic application
Fuzzy application 24 69 55 52 45 66 52 43 63

Table

7: Comparing probabilistic rotation with traditional rotation running on graphs with average computation
times.
6 Conclusion
We have presented scheduling and optimization algorithms which operate in probabilistic environments.
A probabilistic data-ow
graph is used to model an application which takes this probabilistic nature into
account. The probabilistic retiming algorithm is used to optimize the given application when non-resource
constrained environments are assumed. Given an acceptable probability and a desired longest path computation
time, the algorithm reduces the computation time of the given probabilistic graph to the desired
value. The concept of maximum reaching time is used to calculate timing values of the probabilistic graph.
When a limited number of processing elements is considered, the probabilistic rotation scheduling algorithm
(where the probabilistic concept and loop pipelining are integrated to optimize a task schedule) is proposed.
Based on the maximum reaching time notion, the probabilistic schedule length is used to measure the total
computation time of these tasks being scheduled in one iteration. Given a probabilistic graph, the schedule
is constructed by using the task-assignment probabilistic graph, and the probabilistic schedule length is
computed with respect to a given condence probability . Probabilistic rotation scheduling is applied to
the initial schedule in order to optimize the schedule. It produces the best optimized schedule with respect to
the condence probability. The re-mapping heuristic, template scheduling, is incorporated in the algorithm
in order to nd the scheduling position for each node.
s



--R

Development environment for horizontal microcode.
Optimal loop parallelization.
Unimodular transformations of double loops.
Impact: an architectural framework for multiple instruction issue processor.
Rotation scheduling: A loop pipelining algorithm.
Static scheduling for synthesis of DSP algorithms on various models.
Stage scheduling: a technique to reduce the register requirements of a modulo schedule.
Minimum register requirements for a modulo schedule.
Trace scheduling: a technique for global microcode compaction.
Designing and building parallel program: concepts and tools for parallel software engi- neering
Dynamic list-scheduling with nite resources
Retiming synchronous circuitry with imprecise delays.
A comparison of multiprocessor scheduling heuristics.

Relative scheduling under timing constraints: Algorithm for high-level synthesis
Software pipelining.

Retiming synchronous circuitry.
The art of parallel programming.
A singular loop transformation framework based on non-singular matrices

Static rate-optimal scheduling of iterative data-ow programs via optimum unfolding
Loop pipelining for scheduling multi-dimensional systems via rotation

Some scheduling techniques and an easily schedulable horizontal architecture for high performance scienti
Iterative modulo scheduling: An algorithm for software pipelining loops.
High Performance Compilers for Parallel Computing
A loop transformation theory and an algorithm to maximize parallelism.
Fuzzy sets as a basis for a theory of possibility.
--TR

--CTR
Meikang Qiu , Zhiping Jia , Chun Xue , Zili Shao , Edwin H.-M. Sha, Voltage Assignment with Guaranteed Probability Satisfying Timing Constraint for Real-time Multiproceesor DSP, Journal of VLSI Signal Processing Systems, v.46 n.1, p.55-73, January   2007
Jose L. Aguilar , Ernst L. Leiss, Data dependent loop scheduling based on genetic algorithms for distributed and shared memory systems, Journal of Parallel and Distributed Computing, v.64 n.5, p.578-590, May 2004
Rehab F. Abdel-Kader, Resource-constrained loop scheduling in high-level synthesis, Proceedings of the 43rd annual southeast regional conference, March 18-20, 2005, Kennesaw, Georgia
retiming;probabilistic approach;loop pipelining;scheduling;rotation scheduling