Static Assignment of Stochastic Tasks Using Majorization.
AbstractWe consider the problem of statically assigning many tasks to a (smaller) system of homogeneous processors, where a task's structure is modeled as a branching process, all tasks are assumed to have identical behavior, and the tasks may synchronize frequently. We show how the theory of majorization can be used to obtain a partial order among possible task assignments. We show that if the vector of numbers of tasks assigned to each processor under one mapping is majorized by that of another mapping, then the former mapping is better than the latter with respect to a large number of objective functions. In particular, we show how the metrics of finishing time, the space-time product, and reliability are all captured. We also apply majorization to the problem of partitioning a pool of processors for distribution among parallelizable tasks. Limitations of the approach, which include the static nature of the assignment, are also discussed.
Introduction
We consider the problem of statically assigning tasks to processors when the tasks have unknown
random processing times, a certain type of stochastic structure, and which synchronize with each
other periodically. The stochastic structure we examine embodies the notion of one task spawning
a set of others; we examine static assignments, under the assumption that all offspring of a task
are executed on the same processor as the task. Static assignment of the type we consider is likely
to be used when a task's state is large, thereby making dynamic assignment very costly in terms of
communication. Semi-static assignments frequently also make sense[13, 14], where one periodically
adjusts the load globally (executing a static assignment algorithm) once the performance degradation
due to imbalance is severe enough to justify suffering task migration overheads. We consider
different variations on synchronization, from the situation where a task's generation i offspring
synchronize globally with all other tasks' generation i offspring, to the situation where the tasks
execute independently and synchronize only to establish termination.
This paper examines theoretical issues associated with comparing different static mappings of
a set of complex stochastic tasks. In particular, we show how the theory of majorization can be
used to derive strong results concerning the comparison of different mappings. The strength of
our contribution lies in our providing a formal underpinning to the analysis of mapping complex
stochastic tasks of a form common to parallel processing, and to the optimization of a rich class of
objective functions. The theory we apply for Schur-convex objective functions is drawn from [10];
the main result for symmetric convex objective functions we develop ourselves. Overall, our main
contribution is in demonstrating how majorization can be applied to parallel processing's mapping
problem. We also comment on the limitations of this application.
Previous work on load balancing or task assignment [3, 4, 7, 8, 9, 12, 21] in parallel systems
may be loosely divided into three categories. The first category, with deterministic structure,
involves task structures and execution times which are known prior to assignment. In this case
[15] includes a study of problem complexity under various constraints and heuristic algorithms for
task scheduling. A second class of load balancing formulations, in which task execution times are
random, is characterized by queueing-theoretic considerations [4, 19, 21]. Much of this work pertains
to steady-state expectations of task delays with state-dependent [4, 21] and state-independent [19]
assignment policies. Our work is closest to the third category [7, 8, 9, 13] which also takes task
execution times to be random but focuses on minimizing expected processing times for a fixed set
of tasks. As discussed in [9], the assumption of random execution times and a given set of tasks is
justified in applications such as Monte-Carlo simulations.
Our approach to the problem differs from previous work [7, 8, 9, 13] in several ways. In this
paper, we do not concern ourselves only with the explicit optimization of task assignment, but
rather, with the comparison between different assignments over a wide range of possible objective
functions. Past approaches typically address the question: given K processors and m tasks with
random execution requirements, find the assignment of tasks to processors that minimizes the
expected maximum workload (or makespan). In this paper, as well as addressing optimality we
address another related question: given two assignments, when can we say that one is "better"
than the other, and for what class of objective functions can we make this assertion? Our results
have a simple general form. We can describe a mapping of probabilistically homogeneous tasks to
processors by a vector m, whose ith component is the number of tasks assigned to the ith processor.
Let m and m 0 describe two different mappings. Then if m can be bounded by m 0 using the notion
of majorization [10] (written m OE m 0 , see Definition 2.1), then for all objective functions f in a class
C we may say that the assignment described by m is better than the assignment described by m 0 .
The class C is often quite general, and includes many commonly used objective functions, e.g., the
expected maximum workload. We note that an interest in inequalities or stochastic orderings can be
more useful than merely searching for optimal assignments, because such orderings may be derived
in a variety of cases where it is too expensive to search for an optimal assignment. Inequalities
are also useful when constraints on the assignment (e.g. heterogeneous memory capacity among
processors) prohibit one from adopting an otherwise obvious optimal policy. We note that stochastic
orderings are of independent interest [16] and also, in some of the cases we consider the optimal
strategy is apparent from the derived ordering.
Our interest in obtaining stochastic orderings also stems from the observation that they are often
the only results available for small numbers of random variables and a wide variety of distributions.
Consider the fact that in [8, 9] the results are asymptotic in at least one variable n or K. In fact,
in [9], the results are only asymptotically correct in both the number of tasks n and the number
of processors K. These approaches are based on the use of the central limit theorem [8] and large
deviation theory [9], which are among the few limit results available that hold for a variety of
distributions. In contrast, our approach is concerned with finite (and possibly small) n and K and
we make use of the theory of stochastic majorization [10]. Thus, while some of our results are not
as strong (in terms of optimality) as those obtained from fundamental limit theorems, the accuracy
of our results does not depend on the number of tasks or processors.
New results concerning stochastic majorization are often developed and applied to problems
in queueing systems, e.g. [17, 22], and flexible manufacturing systems [18]. A typical result is
that majorizations on vectors of processor service rates induce inequalities on overall network
throughput. Other performance measures such as utilization and queue lengths are also considered.
The key issue in such work is showing that the performance measures of interest have exploitable
mathematical structure ( e.g., monotonicity and convexity (concavity)) when viewed as a function
of design variables. This paper is similar in spirit, but different in detail. First, our application
of majorization to assess the effects of load imbalance and synchronization in a parallel processing
system is to our knowledge unique. Our model is not a queueing model nor a flexible manufacturing
model, and these applications have no notion of global synchronization. However, like the queueing-
related work, our focus is to show that performance metrics of interest to parallel processing have
mathematical structure to which the theory of majorization can be applied.
We now discuss other specific differences between our work and past efforts. Our structural
model of a single task is that of a branching process: a completing process spawns a random number
of subprocesses. This type of behavior appears in diverse applications such as Branch-and-Bound
searching algorithms [2] where the branching structure is obvious, and dynamic regridding algorithms
in numerical computations [1] where sections of coarse grid serve as "processes" which give
rise to "subprocesses" associated with finer grids. Furthermore, our results permit the analysis of
much more complex objective functions than have typically been studied for stochastic task models.
Our model differs significantly from those in [8, 9, 12]. The tasks in [9] were taken to be individual
independent and identically distributed (i.i.d.) samples drawn from a common distribution,
and synchronization behavior is that of periodic global synchronization. In [8] a complex task is
comprised of a fixed number of tasks with random i.i.d. execution times. However, the analyses in
both [9] and [8] are concerned with overheads (e.g. synchronization and communication costs) that
our model does not include. The present paper is an extension of earlier work obtained under the
assumption that the workload assigned to a processor causes the processor to behave as a Markov
chain [13]. Like this earlier work, our new results show how the quality of a static assignment
persists across numerous stochastic transformations of the workload. The model we study in the
present paper is a distinct improvement over that in [13], as the stochastic behavior of a processor
is now explicitly dependent on the volume of workload it contains.
Other related research has been directed at computing the expected completion time for a
single complex task with a possibly random acyclic structure [6, 20]. Another related publication
[11] studies the problem of scheduling sub-tasks of a single task, where the sub-tasks form a tree.
Lastly, an analytic study of load-balancing statistically homogeneous workload on a hypercube is
presented in [7], where the mean and variance of the difference between the load on a processor
and the average load are derived.
Our work is based on results from the study of stochastic majorization. The fundamental theory
of majorization originates in the economic study of income distribution-a sort of "load" balancing.
We believe majorization finds a natural application in the area of mapping parallel workload, and
that one of our contributions is to demonstrate uses of this powerful theory in parallel processing.
In this respect our work is similar to that in [3]. In [3] the focus is on a new stochastic ordering
based on the class of symmetric L-subadditive functions with applications to routing and designing
processor speeds. The load balancing emphasis in [3] is on scheduling structurally simple tasks
from a queue.
It should be noted that the theory we use and develop has sometimes severe limitations. There
is an underlying requirement of probabilistic uniformity in the basic workload description, and of
symmetry in the cost function. Because of this many practical load balancing problems cannot
be directly addressed by majorization. However, in our experience more complex problems can
sometimes be approached in a piece-meal fashion, applying different majorization results in regions
of the problem where the underlying requirements are satisfied. Many of the results we develop
appear to be "intuitively obvious". While we admit to their intuitive nature, we caution that intuitively
obvious solutions to problems in probability theory are sometimes, in fact, wrong. Results
must rest on a carefully developed basis, and one of the contributions of this paper is to provide
such a basis.
Preliminaries
2.1 Workload and System Model
We model the workload produced by a single task as a branching process [16, pp. 116-117], as
follows. The task begins with a single work unit (WU) of computation. The WU is executed; upon
its completion a random number of other WUs are created, and placed in the task's work list.
In one of the models of synchronization we consider, the task then synchronizes globally with all
other tasks before continuing on to process the newly generated WUs. The initial WU can thus be
thought of as containing the "seeds" for a number of additional WUs, possibly zero, each of which
similarly contain the seeds for additional WUs, and so on. One of the first generation WUs may
then be executed, and its children (which are 2 nd generation WUs) spawned and placed in the task's
work list. A global synchronization may then occur (in general we consider global synchronization
between all WUs of a common generation). The number of children a WU spawns is assumed to be
random, chosen from a probability distribution known as the branching distribution. The process
is repeated until the task's work list is empty. The task workload is comprised of all computation
related to all WUs ultimately descended from the initial task WU. A task's execution may also
be punctuated with idle periods where it waits for other tasks to complete their processing of the
current WU generation.
We assume that the order of WU execution in no way affects the spawning of children: a WU in
the work list is destined to spawn some j children, regardless of the length of time it spends in the
list. This is easily understood if one views the WU generation as reflecting some intrinsic structural
property of the problem, e.g., the branching of a search tree. Because of this independence, every
WU belongs to some "generation" which is independent of execution order. The initial WU is in
generation 0; all children spawned by a generation 1 WU are in generation 2, and so on.
We assume that a given WU may be executed with the same constant cost on any one of K
homogeneous processors, and that every WU is executed on the same processor as is its parent.
Therefore, we map all computation associated with a task when we map the task's initial WU.
Consider the evolution of an initial task WU. Let N q denote the number of WUs in its q th
generation. The size of the q th generation is given as
is the number of WUs generated by the j th WU in the (q \Gamma 1) th
generation. We assume that fZ j;q 1g is a collection of independent and identically
distributed (i.i.d.) random variables (r.v.'s). The following notation will be employed:
ffl K - the number of processors.
the number of initial task WUs.
- an integer assignment vector whose i th component m i gives the number of initial task
WUs assigned to the i th processor. Thus,
the size of generation q, descended from a single initial WU (when the branching
distribution is understood). For any subset A ' IN , SA is the sum of all sizes of generations
the j-fold convolution of a probability mass function f . If X is a random variable, we
will also use X (j) to denote a sum of j independent instances of X .
the random vector of generation q WUs resulting from assignment vector m:
q is an m i -fold convolution of the random variable N q . We denote the i th component
of W q (m) by (W q (m)) i . The notation is extended to arbitrary subsets A ' IN by
A
Majorization permits us to compare different mappings under a variety of objective functions
(even though the mapping vectors have integer components, all functions we consider
have IR K as their domain). Our results focus on comparing values of E [OE(W q (m))] by deriving
conditions for inequalities involving initial task assignments m. Most of these are of the following
given two assignments
when the expectations exist.
Applicable functions OE include any symmetric convex function; the maximum operator, all
powers of the maximum, the sum operator, and the product operator are of particular interest.
Thus a single comparison between the assignment vectors m and m 0 vectors can yield a wealth of
information about the comparative behaviors of complex stochastic tasks under the two mappings.
Our results are applicable to at least two different types of processor synchronization. We study
generational synchronization (GS) where processors engage in a barrier synchronization between
each WU generation. A processor executes all WUs of a given generation, say q, then synchronizes
at the barrier. It is not released from the barrier until all processors have executed all their
generation q WUs and reached the barrier. The process repeats for subsequent generations. This
type of synchronization is appropriate when the computation for a generation q in one task may
depend on results computed by a generation another task. We also study termination
synchronization (TS), where a processor engages in a barrier synchronization only after the work
lists of all its initial tasks are empty. This is appropriate when the tasks are independent of
each other, and the synchronization serves only to aggregate the final results of their respective
computations. Figure 1 illustrates GS and TS synchronization with three complex tasks, mapped
statically to two processors. In fact, our results also apply for mixtures of GS and TS styles. Given
could impose a global synchronization between the execution of the n th
th WUs, in effect imposing barriers at different WU generations but allowing different processors
to execute WUs from different generations in between these barriers. For simplicity of exposition
we have focused only on pure GS and TS synchronization.
A natural question arises given the stochastic structure of our tasks: given tasks with arbitrary
distributions how closely does our workload model approximate the true distributions? For branching
distributions, the answer is, of course, exact. For general distributions, it easy to match the
first two moments (a common approximation technique). Thus, our model will provide a reason-able
(to within the first two moments) approximation to any workload distribution. Beyond saying
the above, we are unable to formally characterize the accuracy of the approximation, for example,
whether the class of branching distributions is dense in the space of distributions.
Not surprisingly, the optimal way of assigning n tasks to K processors is usually to assign n=K
to each. In the face of the obvious one may well ask why we study partial orderings. Primarily,
majorization proves the optimality with respect to a large number of objective functions, thereby
lending theoretical support to intuition. Secondly, majorization works even in the presence of
constraints that both disallow the uniform assignment and complicate one's intuition concerning
optimality. For example, constraints may exist that forbid one or more processors from being
assigned more than ffn=K tasks, where Majorization identifies the optimal assignment
under heterogeneous constraints.
We will also apply these concepts to the issue of partitioning a pool of processors among a
set of complex parallelizable tasks. Here we'll take K to the be number of parallelizable tasks,
Task A
Generation 0
Generation 1
Generation 2
time
Processor 1
Processor 2
Generation Generation Generation
Barrier Barrier Barrier
Generational Synchronization
Processor 1
Processor 2
time
Termination Synchronization
Barrier
a
c
d
e
f
Task C
a
f
d
e a b c

Figure

1: Generational and Termination Synchronization for three complex tasks (A,B,C) mapped
statically with A and B assigned to Processor 1, and C assigned to Processor 2.
and use m to describe the number of processors assigned to each. Constraints on feasible m are
easily envisaged, as the assignment may need to consider "natural" partition sizes that arise from
communication topology, or system usage at the time of the assignment. Once again, while the
optimal solution to the constraint-free version of the problem may be apparent, the theory provides
a means of comparing feasible solutions.
2.2 Stochastic Ordering and Majorization
We now introduce the majorization partial ordering OE using notation largely taken from [10].
Definition 2.1 (majorization) A vector x is majorized by vector y, written as x OE y, iff
1.
2.
where the notation x [i] is taken to be the i th largest element of x.
Definition 2.2 (Schur-convex function) A function OE : is said to be Schur-convex if
x OE y in IR n implies OE(x) - OE(y) in IR.
Examples of Schur-convex functions include
IR.
The following intuition may be provided for majorization. Consider two vectors
and which describe assignments of non-random workload to three processors. By
inspection, we know that x is more 'load-balanced' than y. The question 'how much more load-
balanced?' may be answered by examining their `distance' from the optimal assignment (4; 4; 4).
distances. Then, we might
say that x is more load-balanced than y if d(x) - d(y). Majorization makes this notion precise.
What is true is that x OE y implies d(x) - d(y). In fact, x OE y implies OE(x) - OE(y) for many
other functions OE - giving rise to the class of Schur-convex functions. Informally, a Schur-convex
function is a function that is 'almost' convex and symmetric. The theory that establishes the
precise relationship between majorization and various classes of functions is non-trivial; the reader
is referred to [10]. As mentioned earlier, the power of the theory lies in the richness of the class of
Schur-convex functions and also in the useful generalization of majorization to random vectors.
Let C 0 be the class of increasing functions (increasing in each component) from IR n onto IR. The
well-known stochastic ordering between random variables [16] is defined as follows. For random
vectors X and Y with distribution functions F and G respectively,
st Y iff
such that the integrals are well defined. Majorization over deterministic quantities is extended to
random variables in like manner by using an appropriate class of functions.
where symmetric is defined as: OE is symmetric if OE(x
permutation
of the integers These define respectively the Schur-convex partial
ordering, denoted by OE scx and the convex symmetric partial ordering, denoted by OE cas (the notation
and
is used in [10]). Thus,
and
Note that C 2 ae C 1 and thus, OE scx is a stronger ordering than OE cas . It is also worth noting the
contribution of Chang to this field [3]. He demonstrates a different class of functions for which
most of the OE scx results also hold, but which is easier to check than Schur-convexity and which is
less restrictive than ordinary multidimensional convexity. We do not employ any of these functions
in this paper.
Stochastic orderings based on likelihood ratio play an especially important role in this paper.
Definition 2.3 (likelihood ratio) Consider non-negative integer valued r.v.'s X and Y with
probability mass functions f and g. X is defined to be smaller than Y in likelihood ratio, written
as
Monotonicity of likelihood ratio is also an important property.
Definition 2.4 (ILR) The non-negative integer valued r.v. X is said to have increasing likelihood
ratio (ILR) (and its distribution function f is said to be ILR) iff
Next we define another class of probability mass functions, those which have increasing likelihood
ratio under convolution.
Definition 2.5 (ILRC) Let X be a random variable with probability mass function f defined on
IN. Then X (and f) is said to have increasing likelihood under convolution (ILRC) iff f (i) - lr f (j)
ILR distributions are known to be closed under convolution, even when the number of times convolution
is applied is random (provided the distribution of this number is also ILR) [10].
Lemma 2.1 Let f be an ILR probability mass function. Then
ffl f is ILRC.
ffl For any fixed integer k ? 0, f (k) is ILR.
ffl Let N be an ILR positive integer-valued random variable. Then f (N) is ILR.
Using these facts it is straightforward to prove the following.
Lemma 2.2 Let f be an ILR probability mass function. Then
ffl If f is the branching distribution for a task, then for all generations q, N q is ILR.
ffl For any subset A ' IN, if
i2A N i has finite mean, then SA is ILRC.
Proof: The proof of the first claim is a simple induction on q that uses closure of the ILR property
under random ILR mixtures; the proof of the second rewrites S (i)
A as N q is the least
element of A, and C almost surely whenever j. The result follows from Definition 2.4
and the fact that N q is ILR.
As we will see, the assumption of an ILR branching distribution often yields OE scx orderings.
The ILR condition is true of the discrete Uniform, Poisson, Geometric and Binomial distributions,
showing that our results apply when the branching assumes some well-known distributions.
Next we show how these stochastic orderings may be used to develop stochastic majorizations
between different static mappings.
3 Branching and Stochastic Majorization
In this section we establish conditions under which either OE cas or OE scx orderings can be established
between "workload" vectors under different mappings. The notion of workload will be seen to
be quite general. Throughout this section it is important to remember that the results relate to
intrinsic properties of branching behavior, and do not depend on assumptions about execution
behavior, e.g., synchronization.
The central result for the OE scx ordering is based on the following theorem which is an application
of Theorem 3.J.2 in [10]. The correspondence between our form and the original is pointed out in
the

Appendix

.
Theorem 3.1 Let X be an ILRC random variable with probability mass function f , let
be a vector of nonnegative integers, and for each
with distribution f (m j ) . Suppose this set of r.v.s is independent, and let OE : IR K ! IR be a Schur-
convex function. Then
is a Schur-convex function of m.
Using Theorem 3.1 one obtains the central basic OE scx ordering result.
Theorem 3.2 Consider a set of n tasks, with common ILR branching distribution f , and let m
and m 0 be two mapping vectors such that m OE m 0 . Then
ffl For all generations q, W q (m) OE scx W q (m 0 ).
ffl For any subset A ' IN such that SA has finite mean,
W A (m) OE scx W A (m 0
Proof. Lemma 2.2 shows that the distributions of N q and SA are each ILRC; the result follows
from the definitions of W q (m) and W A (m), and Theorem 3.1.
Observe that the statement of Theorem 3.1 applies more generally to the notion of a random
"cost" associated with each initial WU. It states that if each initial WU incurs a random ILRC
cost, and if the cost to a processor is the sum of the rewards incurred by its (independent) WU's,
then a stochastic majorization on the costs follows from a deterministic majorization of the initial
WUs.
This OE scx result seems to require the assumption of ILR or ILRC branching distributions.
However, by constraining our attention to symmetric convex functions we are able to obtain OE cas
orderings for completely general branching distributions (unlike the OE scx result, these orderings are
our own). The details, which are numerous, are developed in the Appendix. The OE cas counterpart
to Theorem 3.2 is
Theorem 3.3 Consider a set of n tasks, with common nonnegative branching distribution f , and
let m and m 0 be two mapping vectors such that m OE m 0 . Then
ffl For all generations q, W q (m) OE cas W q (m 0 ).
ffl For any subset A ' IN such that SA has finite mean,
W A (m) OE cas W A (m 0
3.1 Heterogenous Constraints
The K-vector m majorized by any other vector whose components
are nonnegative and sum to n. Applied to the assignment problem, this shows that the obvious way
to balance workload is indeed the best, even for complex stochastic tasks. Optimality is less clear,
however, if the obvious assignment is prohibited by constraints. For each processor i let C i be an
upper bound on the number of WUs the processor may be given. Such constraints might arise, for
instance, if the processors have different memory capacities. The obvious mapping is prohibited if
any C i ! n=K. Majorization provides a way to identify the best assignment of complex stochastic
tasks even in the face of such constraints.
Consider any feasible vector K. Suppose there exist i
and j such that y j ? y Construct a new vector x from y by transferring one
unit from y j to y i , i.e., x j. It is shown in [10] (5.D) that
x OE y. This observation gives a rule by which we can iteratively improve a feasible solution, until
no further improvement is possible. We say a vector x resulting from this processed is balanced.
Without loss of generality assume that C 1 - C . It is apparent that x is balanced
if and only if whenever characterization of balanced vectors then
is that there is some index j such that x
Furthermore, if x and y are both balanced, then this index j is the same for both
of them. It follows then that x OE y and y OE x, which shows the essential uniqueness of balanced
vectors. Balanced vectors are thus optimal under heterogeneous constraints.
A simple O(n) algorithm will construct a balanced assignment. Assume the processors are
ordered by increasing constraint value, and initially set x We loop repeatedly
over indices 1 to K. Each pass through the loop we increment x i once, provided This
essentially assigns one unit to the i th processor. We repeat the loop until all n units are assigned.
The main results of this section shows that stochastic branching preserves stochastic majorization
for additive cost systems. As we have seen, useful cost systems are derived from the generation
sizes. The section to follow illustrates how these results can be fruitfully applied to various objective
functions.
4 Objective Functions
We will now establish that a number of interesting objective functions are either Schur-convex or
convex symmetric functions of some notion of workload. These objective functions include finishing
time under different synchronization schemes, the space-time product, and overall reliability. This
diversity of application demonstrates the utility of the theory.
4.1 Finishing Time
One use of majorization is to show that whenever m OE m 0 , the computation's expected finishing
time under m is better than that under m 0 . This can be established using different models of
execution. For example, one easily envisions a computation where the tasks must synchronize
globally with a barrier after every generation, i.e., GS synchronization. This is typical of tasks
associated with numerical computations. We model a processor's cost of processing x WUs in a
generation with a function e(x). Of course e includes execution costs, but it may also incorporate
per-WU communication or I/O costs. We assume that e(x) is increasing and convex in x. For
instance, fi)x is a reasonable model if ff is the per-WU execution cost, and fi is a
per-WU communication cost. Such communication costs arise if message startups dominate the
cost of message passing, and the communication cost suffered by a processor is proportional to the
number of WUs it executes. The case for e being strictly convex can be made if e models disk I/O
(with increasing numbers of WUs on a processor leading to marginally increasing I/O costs due to
fragmentation). For the moment, ignore any additional communication costs and synchronization
costs. Then time is required under mapping m to execute all generation
q WUs. N q can be viewed as a random cost associated with an initial WU, thus Theorem 3.3
tells us that W q (m) OE cas W q (m 0 ). Now suppose that executing a barrier synchronization costs a
processor B units of time, and that additional communication costs (for instance, due to contention)
are modeled by a function C : IR K ! IR of the workload distribution vector. The time required to
execute all generation q WUs under m is then a function
F (W q
By closure, F is symmetric and convex under the assumptions that e is convex and that C is
symmetric and convex. It follows that E [F (W q
this applies for the processing of every generation q, the overall expected finishing times (e.g. the
sum of all generational finishing times) under the two mappings are likewise bounded.
Similar results are obtained under TS synchronization, where processors synchronize only at
termination. One models the costs exactly as above, except that the cost for an initial WU is now
S IN (instead of N q ), the total size of the branching tree rooted in that WU. When the mean of the
branching distribution is strictly less than one, then E[S IN 1. In this case, whenever
the expected finishing time under m is no larger than under m 0 .
It is worth noting that some intuitive communication cost functions are not convex, so that these
results do not apply. For instance, if every WU communicates with every other and communication
between co-resident WUs is free, then the cost e(x i ) to processor i may be better modeled as
This form of e is actually concave in x, and need not even be monotonic.
Nonetheless, we have seen that the theory applies to a wide variety of communication cost functions.
Another metric of interest is the variation in the number of WUs assigned to processors. The
variance, defined below, is also symmetric and convex.
for any generation q, and
for any A ' IN such that SA has finite mean. When the branching distribution is ILR, a similar
result holds true for the standard deviation (square root of variance) of time between synchroniza-
tions, because the standard deviation is Schur-convex ([10], pp. 71).
4.2 Functions of Queue Length
When a WU completes its execution it generates its children and places them on the processor's work
list. Following this, another WU is selected to be executed. There is thus a storage cost associated
with executing complex tasks; more generally, we show here how stochastic majorization can be
applied to objective functions based on measuring queue lengths at every time step. A simple
example of this is the computation's total space-time product, defined as follows. Let Q(t) be the
vector enumerating the number of WUs enqueued at each processor at time t, and let T be the
computation's termination time. Assume now that the cost of processing one WU is exactly 1.
Then the total space-time product is
This idea can be generalized-let s(j)
quantify the cost of holding j WUs in queue for one unit of time. Then the total space-time cost
with respect to s is
We will show that if s is increasing convex with
synchronization the expected space-time cost with respect to s is
no worse under m than it is under m 0 . This result is also demonstrated for GS synchronization
when the branching distribution is ILR.
Under the model assumptions we have made, the probabilistic behavior of a processor's queue is
completely independent of the queueing discipline used. We will assume that the queueing discipline
is Smallest-Generation-First (SGF): whenever a processor selects a WU for execution from its work
list, it chooses one with least generation index. For simplicity, we also assume that the execution
of a WU takes unit time.
The space-time function rise to the usual space-time product, but other space-time
cost functions are also intuitive. For example, one might have to store WU states on disk
whenever the queue length exceeds a threshold L; furthermore, once L is exceeded the cost might
be superlinear, owing to fragmentation costs. A candidate cost function would be
The general assumptions that a space-time cost function be convex, increasing, and
zero for empty queue lists seem to us quite natural.
Our treatment of space-time costs under TS synchronization hinges on the following observa-
tion: if processor k has exactly (W q (m)) k WU units in generation q, then under the SGF queueing
discipline at some point in time the processor's queue will have exactly (W q (m)) k WUs. In partic-
ular, at the instant where the first WU of generation q is about to be executed, the queue consists
entirely of generation q WUs, and contains all of them. We will show that the contribution to the
expected space cost made by processor k while processing generation q WUs (under SGF schedul-
ing) is an increasing convex function of (W q (m)) k , and use this fact to find a majorization on the
vector of expected contributions made by all processors while processing generation q WUs. This,
in turn, will show that the total expected space-time cost under m is no worse than under m 0 ,
when the expectations exist. This is a OE cas result, applicable for any branching distribution.
Suppose (W q r. The processing of the i th WU in generation q produces a
random number X q;i of WU units, who join the processor's queue. The queue length at the instant
the i th WU begins execution is r
, as there were r work units in queue at
the point the first generation q WU was executed, them have been executed, and each
one produced a random number of generation q WUs. Therefore, the conditional expected
space-time cost suffered during the processing of this WU is
For any fixed i, OE is convex in r because for any convex fl and random variable Z, the expectation
is convex in a (assuming the expectation exists). The expected space-time cost of
processing all r members of generation q on processor k is
r
Finally, we claim that C s (r) is a convex function of r. To demonstrate this it suffices to show that
C s (r+2)+C s (r) - 2C s (r+1) for all r. Since OE is convex in r for fixed j we have OE(j; r+2)+OE(j; r) -
This observation reduces the problem to a demonstration that
The fact that s(r) is increasing establishes that both OE(r
proving the convexity of C s (r).
The function T s (r
and convex on IN K , because whenever
g is convex on IR then
is convex on IR K . Observe that T s (W q (m)) is the random
space-time cost with respect to s and generation q resulting from assignment vector m. We have
proven the following result.
Proposition 4.1 Let s be an increasing convex function with suppose the space cost
of holding k WUs in one processor's queue for one time unit is s(k). Define
to measure the space-time cost suffered while executing generation q, under the assignment given
by m. Then whenever
ffl The expected total space-time cost using TS synchronization is no worse under m than under
whenever the expectation exists. (21)
The analysis of space-time costs under GS synchronization requires more work, and the assumption
of an ILR branching distribution. Suppose that (W q K. The
space-time cost to processor k during the interval of time when generation q WUs are executed has
two components. We have already seen the first: C(r k )-the cost accumulated over the period of
length r k while generation q WUs are executed. The second component is the space-time cost suffered
waiting for the most heavily loaded processor to finish. If processor k generates x generation
q+1 WUs, then the space-time cost it suffers waiting at the barrier is (max i fr i Recalling
the definition of OE (equation (17)) we may write the expected total space-time cost of processing
generation q WUs under GS synchronization (conditioned on (W q
Observe that OE(r k is the branching random variable . G is Schur-
convex on IN K , a fact we show using the following characterization of Schur-convex functions on
IN K (3.A.2.b in [10]): A function ff on IN K is Schur-convex if and only if ff is symmetric and
increasing in r 1 - t=2 for each fixed t; r
Fix r . If the difference G(r 1
is always nonnegative, then the condition above tells us that G is Schur-convex. We need to examine
two cases, and the alternative. Assuming the former, straightforward algebra shows
that the difference is bounded from below by
Both of the two summations above are positive, because OE(i; r) increases in r. Since OE(i; r) is convex
in r and r 1 ? r 2 , it also follows that OE(i; r every i. Thus
the positive summation above dominates the negative summation, and the desired inequality will
hold if
?From the definition we see that OE(r; r) is a linear function of r, and is hence convex. We therefore
have
?From this inequality we see that the desired bound will hold if (OE(r
. The convexity of s implies that
as needed. The argument for the case when r 1 6= is almost exactly the same, and so is
omitted. The Schur-convexity of G gives us a stochastic majorization for GS synchronization.
Proposition 4.2 Let s be an increasing convex function with suppose the space cost
of holding k WUs in one processor's queue for one time unit is s(k), and suppose the branching
distribution is ILR. Define
to measure the space-time cost with respect to s of executing some generation q under GS synchro-
nization, where the each processor i has r i generation q WUs. Then G is Schur-convex on IN K , so
that whenever m OE m 0 ,
ffl The expected total space-time cost using GS synchronization is no worse under m than under
G(W q (m 0 ))] whenever the expectation exists. (25)
4.3 Reliability
Yet another application of majorization is to the question of whether the hardware will successfully
execute the entire computation. We suppose that the computation "fails" if any processor having
a non-empty queue fails. Observe that this definition permits the computation to successfully
complete even if a processor dies before the entire computation is finished, provided the failing
processor is itself already finished. We will show that if the branching distribution is ILR and a
processor's time-to-failure distribution has an increasing hazard rate function, the the probability of
failure under m is no greater than that under m 0 , whenever Conversely, if the branching
distribution is ILR and the processor failure distribution has a decreasing hazard rate function, then
the reliability under m 0 is better than that under m. The result is proven for TS synchronization.
Suppose that processor i's time to failure is the random variable Z i , with an monotone hazard
rate function -(u). It is well known that
Z t-(u) dsg: (26)
If -(u) is nondecreasing in u, then \Gamma
-(u) du is concave in t, which is to say that log PrfZ ? tg
is concave. Conversely, if -(u) is decreasing, then log PrfZ ? tg is convex.
It follows (3.E.1 in [10]) that when -(u) increases, the product
Y
is Schur-concave, or equivalently, that \GammaR(t decreases then
If processor i is assigned m i WUs initially, it ends up processing S (m i )
IN WUs total. This is also
processor i's processing time under the assumptions of SGF scheduling, TS synchronization, and
unit execution cost per WU. Given S (m i )
equation (27) gives the probability
that every processor executes all WUs without processor failure. The unconditional probability is
obtained by taking the expectation with respect to the joint distribution of S IN (m):
Prfevery processor executes all its WUs before
Lemma 2.2 asserts that S IN is ILRC if the branching distribution is ILR. It follows from Theorem 3.1
that when -(u) is increasing, E[R(S IN (m))] is a Schur-concave function of m. This proves the
following proposition.
Proposition 4.3 Suppose the hazard rate function -(u) for the time to processor failure is increas-
ing, and suppose the branching distribution is ILR. Let fl(m) be the probability that every processor
executes all its WUs without processor failure. Then under TS synchronization and SGF scheduling,
The inequality is reversed if -(u) is decreasing.
5 Assignment of Processor Pools
Our last application of stochastic majorization concerns a problem where a large number n of
processors are to be partitioned among a smaller number K of complex tasks. Parallel processing
can be applied to the tasks to accelerate execution time. We assume that a task requires that all
of its generation i WUs to be executed before any of its generation are, but that all
generation i WUs may be processed in parallel. As before, the overall system may use either TS
or GS synchronization.
Let g(X; m) give the time required by m processors to execute X WUs. We assume that g(X; m)
is convex in m, e.g., g(X; m) = X=m, and that g(0; m) = 0.
Suppose there are K initial WUs. We may describe our assignment of n processors to these
WUs with vector m, whose i th component gives the number of processors assigned to the i th WU.
Also let N q;i denote the random number of WUs associated with generation q of task i. Under GS
synchronization, the time required to complete the q th generation is
Under our assumptions, E[fl q (m)] is a symmetric convex function of m (B.4 Proposition in [10]),
showing that E[fl q (m)] - E[fl q (m 0 It follows immediately that the overall
expected finishing time under GS synchronization is no worse under m than under m 0 .
Under TS synchronization the finishing time is
A sum of convex functions remains convex, whence E[ae(m)] is symmetric and convex in m. When
are assured that the expected finishing time under TS synchronization is no worse
using m than it is with m 0 .
6

Summary

This paper explores the application of majorization to the problem of assigning a large number of
complex (but probabilistically identical) tasks onto a multiprocessor. Using a model of workload
based on branching processes, we show how to establish a partial ordering among possible assignment
of tasks to processors. We show that the quality of an initial assignment persists through
stochastic transformations of the workload, and that the ordering can be taken with respect to a
wide range of objective functions including those measuring finishing time, space-usage, and relia-
bility. The results are developed for two different models of task synchronization, and the finishing
time results incorporate communication as well as synchronization costs. We also show how the
theory applies to the processor partitioning problem. The utility of the theory lies in the generality
of the objective functions that can be considered, and in the fact that optimal solutions can be
identified even when constraints are placed on potential assignments. We have also pointed out
limitations of the our assignments are static (work spawned by a WU stays on the same
processor) and that the stochastic structure of our tasks is not as general as we would like it to be.
A

Appendix


In this appendix we prove some claims made earlier in the paper.
The ILRC condition upon which the OE scx results depend involves the notion of totally positive
functions. Chapter of [10] is the source for the following definition.
Definition A.1 (Totally Positive Function) Let A and B be subsets of the real line. A function
is said to be totally positive of order k, denoted TP k , if for all m,
all
0: (30)
We will use the following result (18.A.4.a in [10]).
Lemma A.1 If K is TPm and L is TP n , and oe is a oe-finite measure, then the convolution
Z
is TP minfm;ng .
The relationship between total positivity and ILRC distributions is direct. Given any integer-valued
nonnegative probability mass function f we may define the function ff f : IN \Theta IN ! [0; 1]:
ff f is TP 2 iff
for all n. But this is equivalent to saying that f (i) - lr f (j) , i.e., that f is ILRC.
The reason for our interest in ILRC distributions f is that their convolution functions ff f satisfy
three criteria required by Theorem 3.J.2 of [10]
ffl ff f is totally positive of order 2;
R
measure v on IN .
Theorem 3.J.2's conclusion is that if counting measure, and
Z
Y
Y
is Schur-convex on IN K . Theorem 3.1 is a restatement of this result, where 8u;
probability, we recognize that fl(m) expresses the expected value of OE(y).
OE cas
Results
We next consider the OE cas ordering. In this case, we are able to obtain the analogue of Theorem 3.2,
save that the OE cas result holds for completely general branching distributions. We first must
introduce a little more terminology, and develop an intermediate result.
A random vector is said to have exchangeable components if the joint distribution
of is invariant under permutations of its components. Our basic OE cas results
rest on the following observation.
Lemma A.2 Let X,Y be nonnegative random variables, and be a random vector
with nonnegative exchangeable components. Assume that X, Y and Z are independent r.v.'s and
define
Proof. Let
be a convex symmetric function. Define the function
as
. Since Z has exchangeable components, / is also a convex
symmetric function.
Now U OE V a.s. from which it follows
The result extends easily to IR n
.
Lemma A.3 Let X,Y be any nonnegative random variables, let
be a
random vector with independent components such that Z 1 and Z 2 have the same distribution. Assume
that X, Y , and the components of Z are mutually independent and define
Proof: be a symmetric convex function. Now, OE is symmetric and convex in the
first two arguments. Therefore, we can condition the values of Z j , 3 - j - K to be z j and apply
the previous lemma to obtain
Removal of the conditioning on Z j , 3 - j - K yields the desired result.
We are now prepared to prove Theorem 3.3. Let m 0 be any mapping vector where there are
processors i, j such that m 0
. Without loss of generality we may take
let m 00 be the mapping vector obtained from m 0 by moving one WU from processor 1 to processor
2. We will apply lemma A.2. Interpret Z
-fold convolutions of initial WU costs, X
as the convolution of m 0
as a single initial WU cost, and each Z j
as the convolution of m 0
initial WU workloads. The application of lemma A.3 yields
The incremental movement of a task from a heavily loaded processor to a more lightly loaded
processor corresponds to the more general notion of a "transfer" [10]. It is known that whenever
x OE y, then x can be constructed from y with a finite number of transfers, where each transformed
vector is always dominated under OE by its predecessor. Consequently if m 0 is a mapping vector
with one demonstrates that W (m) OE cas W (m 0 ) through a repeated application of
Lemma A.3 to the sequence of transfers that transmute m 0 into m. This proves the result.



--R

"Adaptive mesh refinement for hyperbolic partial differential equa- tions"
Algorithmic:Theory and Practice
"A New Ordering for Stochastic Majorization: Theory and Applications"
"Models for Dynamic Load Balancing in a Heterogeneous Multiple Processor System"
Computers and Intractability
"An Approximation of the Processing Time for a Random Graph Model of Parallel Computation"
"From Local to Global: An Analysis of Nearest Neighbour Balancing on Hypercube"
"Optimal Partitioning of Randomly Generated Distributed Programs"
"Allocating Independent Subtasks on Parallel Processors"

"Evaluation of Parallel Execution of Program Tree Structures"
"Optimal Partitioning of Random Programs Across Two Processors"
"Dynamic Remapping of Parallel Computations with Varying Resource Demands"
"Communication Efficient Global Load Balancing"


"Stochastic Majorization of Random Variables with Proportional Equilibrium Rates"
"Optimality of Balanced Workloads in Flexible Manufacturing Systems"
"Optimal Static Load Balancing in Distributed Computer Sys- tems"
"Analytic Queueing Network Models for Parallel Processing of Task Systems"
"On the Optimal Assignment of Customers to Parallel Servers"
"Majorization and Arrangement Orderings in Open Queueing Networks"
--TR

--CTR
Philip J. Boland , Harshinder Singh , Bojan Cukic, Comparing Partition and Random Testing via Majorization and Schur Functions, IEEE Transactions on Software Engineering, v.29 n.1, p.88-94, January
majorization;performance of parallel systems;processor allocation;load balancing;task allocation;task assignment;resource allocation