NASA Contractor Report 178035

NASA-CR-178035

ICASE REPORT NO. 86-7 19860012779

ICASE

AN OPTIMAL REPARTITIONING DECISION POLICY

David M. Nicol

Paul F. Reynolds, Jr. AP_ _ ]_6

U,t_GLEY _ES__ARC CENHTER

LIBRARYNA, SA

H.....

, _'

,wl'O, _I, VIRGINIA

Contract Nos. NASI-17070 and NASI-18107

February 1986

INSTITUTE FOR COMPUTER APPLICATIONS IN SCIENCE AND ENGINEERING

NASA Langley Research Center, Hampton, Virginia 23665

Operated by the Universities Space Research Association

National Aeronautics and

Space Administration

LangleyResearchCenter •

Hampton, Virginia 23665

An Optimal Repartitioning Decision Policy

David M. Nicol

Institute for Computer Applications in Science and Engineering

Paul F. Reynolds, Jr.

University ot' Virginia

Abstract

A central problem to parallel processing is the determination of an effective partitioning of workload to processors. The effectiveness of any given partition is dependent on the stochastic nature

of the workload. We treat the problem of determining when and if the stochastic behavior of the

workload has changed enough to warrant the calculation of a new partition. We model the problem as a Markov decision process, and derive an optimal decision policy. Quantification of this

policy is usually intractable; we empirically study a heuristic policy which performs nearly

optimally. Our results suggest that the detection of change is the predominant issue in this problem.

This researchwas supportedin part by the NationalAeronauticsand Space Administrationunder

NASA ContractsNAS1-17070 and NAS1-18107 whilethe firstauthorwas inresidenceat ICASE, Mail

Stop 132C, NASA LangleyResearchCenter,Hampton, VA 23665.Itwas alsosupportedin partby the

VirginiaCenter for InnovativeTechnology,whileboth authorswere in residenceat the Universityof

VirginiaD,epartment ofComputer Science,ThorntonHall,CharlottesvillVAe, 22903.
-2-

I. Introduction

We consider a multiprocessor system without a dynamic scheduling facility; e.g., a loosely

coupled message passing system. We presume that some computation has been partitioned onto

the processors, and that this partition cannot be easily changed while the computation is executing. The computation's execution time under this partition is presumed to be dependent on the

stochastic behavior of the computation. As long as the stochastic behavior is the same as when

the partition was chosen, we suppose that a different partition will not yield an execution time

performance gain. If the stochastic behavior does change, a new partition may better exploit the

new behavior. The problem is to detect change in the computation's stochastic behavior, determine the performance benefits of implementing a new partition, and weigh those benefits against

the overhead costs of calculating and implementing a new partition. We treat the repartitioning

decision problem as a Markov decision process. This problem should be distinguished from the

partitioning (or task assignment) problem, which addresses how to partition a workload among

processors. Rather, we are examining the issue of when to abandon one partition and adopt

another. These two problems are closely related, as the overall performance depends both on how

well and how often a workload is partitioned. Previous work in partitioning has focused only on

the first problem. Our work considers how often a partitioning algorithm should be applied, as a

function of the quality of the partitioning and the behavior of the computation under that partitioning.

Consider a computation which can be described as a sequence of "cycles" which are probabilistically identical, and which are independent of the computation's partitioning. Examples of

such computations include iterative numerical methods, reM-time systems which execute periodic

monitoring tasks, and simulation programs [12]. The partitioning of such computations for parallel processing may take into account many factors, e.g. data dependencies, and system resource

requirements. Once a partition is chosen, it may be quite difficult and/or expensive to dynamically move small portions of the computation's workload. Yet, the chosen partition may become

quite unsatisfactory if the stochastic nature of the computation changes. We are then presented

with the problem of needing to repartition, but are constrained to devising a completely new partition. The related literature falls into two categories, neither of which addresses this particular

problem. The work reported in [5], [6], [9], and [25] essentially presumes that jobs arrive at a central dispatcher which assigns jobs to processors. Our problem eschews the job arrival model, and

does not allow a dynamic routing mechanism. A more recent body of work including [7], [14],

[22], [23], [26] allows decentralized assignment decisions to be made dynamically. Again, our

problem presumes that incremental dynamic reassignment is not feasible. Static and dynamic

task assignment algorithms are presented in [1], [2], [4], [10], [11], [13], [17], [24]. The dynamic

assignment algorithms consider restricted classes of computations; the static partitioning algorithms might be used in conjunction with our repartitioning decision policy if the computations

partitioned by such methods change their behavior. Our work is a variation on aspects of the

broad treatment of change detection under uncertainty given in [18]. Our model modifies this

analysis by using a different decision cost structure, and by assuming a random computation

duration. Our work's main contribution is as the first application of statistical analysis and Markov decision theory to the performance issue of when to reconfigure a workload distribution in a

parallel processing environment.

Suppose we measure the performance of a partitioned cyclic computation by observing the

sum of processor utilizations over every cycle. Letting Z; denote the ith utilization measurement,

we suppose that the sequence Z1, Z2, .-. forms a weakly stationary stochastic process [20].

Intuitively, this means that every Zi and Zi have the same mean, the same variance, and that
-3-

their covariance depends only on l i - J[. We anticipate that at some unknown future time the

stochastic behavior of this computation will change, at which point it may be advantageous to

redistribute the computational workload. A change of this sort can be expected if the probabilistic behavior of the inputs driving the system change; such a change could also occur as a result of

an intrinsic change in the behavior of the computation. In this paper we consider the problem of

detecting and reacting to such a change. We develop a real-time change monitoring decision process which balances the expected costs of redistribution against the expected benefits. Within the

constraints imposed by the change detection method, the decision policies we describe are shown

to minimize the computation's expected execution time.

In section II we present a statistical means of determining when a computation's stochastic

behavior changes. Section III shows how to dynamically maintain the probability of a change

having already occurred. Section IV discusses our assumptions about the duration of the computation; section V formulates the repartitlonlng decision problem as a Markov decision process.

Sections VI and VII analyze this model, and characterize a decision policy which minimizes the

expected computation execution time. As the calculation of the optimal decision policy is usually

intractable, we propose a heuristic policy in section VIII. Section IX reports empirical results

which suggest that our heuristic tends to perform very close to optimally. Section X talks about

the possibility of multiple changes during a computation, and section XI contains our conclusions.

IT. Detecting Change

In this section we discuss a statistical approach to detecting change in the computation's

stochastic behavior. The proposed method is not an integral part of our dynamic partitioning

solution, it could be replaced with any other statistical change detection technique. Our method

does have the advantage of computational simplicity with minimal storage requirements.

The change monitoring process examines the sequence {Zi} of performance measures. Each

random variable Zi is drawn from a common distribution F whose exact characterization is not

known. We say that a change occurs at cycle j if Zi's distribution is different from Zi_l's. We

presume that at most one change will occur in the course of the computation. The probabilistic

nature of this problem requires us to statistically determine when a change occurs. However, F is

general, and the performance observations are correlated. For statistical tractability, we presume

that the sequence {Zi} is first transformed into a sequence {Xi} of approximately normal and

independent observations. This is accomplished using the batch means [8] transformation, where a

sequence of d observations is replaced by its mean value. Thus the transformed observation X i is

defined by

1 d-1

= ° zd.,+i.

If Zd.i+ i has mean p and variance a2 for i = 1, • • • ,d-l, then X i is approximately normal with

mean p and variance aZ/d.

Our change monitor examines the observations {Xi} as they become available to determine

if and when their underlying normal distribution changes. Solutions to the so-called model

identification problem [3] in statistics can be used to detect this change. In our situation, model

identification decides whether two groups of independent normal observations are drawn from a

single normal distribution.
-4-

Using a model identification approach, we create a test cluster of c adjacent normal observations. The ith cluster Ci is defined to be the collection

ci = {X .i, "" ,Xo.(i+l)-x}.

We assume the existence of a base cluster B of size c derived from initial observations taken

before a change could have occurred. The model identification test determines whether observations in B and Ci are identically distributed. Positive indication of distributional difference is evidence for the change having already occurred. The AIC model identification approach described

in [3] attempts to describe the data set BUC i with a probabilistic model having as few parameters as possible while still fitting the data. We consider two competing models of BUC i. One

model states that BUC_ is a set of 2"c observations drawn from a normal distribution N(pj,a_).

This model has two parameters,/_j and a_. The competing four parameter model states that B is

a set of normal g(pB,a_) observations and that Ui is a set of normal g(pe,azc) observations,

PBCPc and aB_2 a 2¢. For each model we calculate the statistic

AIC = -2-/(P) + 2-P

where P is the number of model parameters, and l(P) is the maximized log-likelihood function

[12] using P parameters. The model achieving the minimum AIC statistic is taken as the most

parsimonious.

The statistic AICj for the two parameter model is given by

AICj = c'ln(_) + 4

and the competing model's statistic is given by

• +8 AIC, =-_

where h_, &g, b_ are the sample variances for the sets BUCi, B, and Ci, respectively. One

advantage of the AIC model selection criterion is its simplicity. The significance level of the

statistic is effectively chosen by its derivation, and no statistical tables need to be stored. Furthermore, the calculations take linear time in the size of the clusters.

The model identification criterion may fail to correctly determine whether a cluster Ci

represents the existence of a change. In a Bayesian framework, the AIC test gives us some indication of change, with uncertainty. If we have a prior probability of change, we can calculate a posterior probability of change as a function of the test result. This calculation requires knowledge of

the statistical test's accuracy. We let a denote the probability that the model selection statistic

falsely indicates a change (type I error); we let fl denote the probability that the statistic fails to

detect a change (type II error).

ITI. Calculating the Probability of Change

We now consider the calculation of the probability of change. A measurement of system

utilization is taken every cycle. The mechanics of the batch means transformation produce a

transformed observation every d cycles; a new test cluster C is thus available every c'd cycles.

The beginning of cycle n'c'd is called the nth decision step or time n, and is the nth epoch at

which a test cluster is evaluated for change. The c'd cycles between decision steps are known as a

decision interval. We define Pn to be the probability that a change has occurred by decision step

n. Pn is calculated as a function of Pn-1, and the result of the statistical change test performed at

time n. This function's description requires the evaluation of P*(Pn-1), the probability that a
-5-

changewillhave occurred by time n,givenonlythevalueofPn-l"P*(Pn-1)can be calculated

at time n-l, but must presume some priorknowledgeofthedistributionofthe timeofchange.

Supposingthatsuchforeknowledgeisnot preciselyknown, itisbothreasonableand convenientto

assume thatthefailurerateofthetime ofchangedistributionissome constant€. By conditioningon thetimeofchange,we have

P* (Pn-1) = Pn-1 + _'(1 -- Pn-1) (1)

= (1 - _)'Pn-1 -}-_"

P*(Pn-1) is the probability of change by time n, before a change test is performed at time n. P,

depends both on P*(P_-I) and the result of the change test performed at decision step n. The

posterior probability p, is calculated using Bayes' Theorem [21] . If the test at decision step n

indicates change, P, is given by pC(p,_l):

P*CP.-I)'(1 - fl)

p. = pC(p._1) = . . • (2)

iv (p._1)'(1 - /3) -{-(1 - p (p._I))'oL

Given a negative indication of change, p. is defined by pC(p._l):

Pn = PT(Pn-1) = * PS(Pn-I!'_ 1-- p (pn_l)'/_ -1- (I - p (Pn-1))'( _) (3)

As the test clusters become available for statistical testing, equations (1)-(3) allow us to maintain

the probability that the change has already occurred.

At each decision step we will decide whether to repartition the computational load. This

decision should be based on the costs and benefits of repartitioning. Presuming we receive no substantial performance benefits if a change has not occurred, we see that the probabilities (P,}

should play a pivotal role in determining whether (and when) repartitioning is worthwhile. Sections V and VI confirm this intuition.

IV. Number of Cycles

We presume that the computation will require a random number N decision steps, irrespective of its partitioning. We assume that N is bounded above by some constant M. Our analysis

also assumes that the distribution of N has an increasing failure rate function. That is, the failure

rate probability

Prob(N = n)

Prob{N >1n}

is an increasing function of n. An intuitive explanation of this requirement is that the longer the

computation continues, the more likely it is that the computation will stop with the next decision

step.

We use an equivalent statement of increasing failure rate probabilities. To express this

equivalency, we first define the _>L(stochastically larger) relation between random variables. If X

and Y are random variables, we say that X _>L Y if for all increasing functions g,

Big(X)] /> Big(Y)]. Let N, denote the random variable N conditioned on g/> n. [201 shows that

assuming N has an increasing failure rate function is equivalent to assuming that Nn _>LN,+I for

all n >/0.
-6-

Finally, we let Nn denote the expected value of N, given that N/> n.

V. A Markov Decision Process

Our notation concerning Markov decision processes is taken largely from [19]. Consider a

stochastic process whose state we observe at each of a sequence of times t = 0, 1, • • •. Let I be

the set of all possible states. At each time 3",the state of the process is discerned to be some

s E I. Then a decision is made, choosing some action a from a finite set A; the choice of action a

while in state s incurs a cost c(s,a), c(s,a) may be random; we assume that E[c(s,a)] is finite for

all states s and actions a. The decision process then passes into another state. The probability

p,q(a) of passing into state q from s is dependent on the action a chosen in state s. The expected

total cost of a decision policy is the expected sum of the costs incurred at each decision step. An

optimal decision policy minimizes the expected total cost.

We restrict our attention to the class of stationary decision policies, those policies which are

deterministic functions of the discerned state. A useful theorem concerning optimal stationary

decision policies is given by [19].

THEOREM 1 : Let V(s) be the expected total cost of the process which starts in state s, and

which is governed by the optimal stationary policy. Then,

vcs)=.mcAinJ [ c(s,a) } . C4)

D

The function V(s) is known as the optimal cost function. From state s, the optimal stationary

decision is the choice of action which minimizes the right hand side of equation (4).

We now formulate the repartitioning decision problem as a Markov decision process. Table

I summarizes the notation used by this decision process formulation. The decision process time

steps will be precisely the decision steps. The decision costs are functions(in part) of % and er,

the expected execution times of a decision interval after a change, with the original and with the

new partition, respectively. We presume that eo > er. A state of the process has the form

<p,n>, reflecting the decision step n, and posterior probability of change, p = Pn" The decision

process chooses to test, or to retain. The retain decision causes the current partition to be kept for

the next decision interval. Our cost structure is concerned only with execution times after a

change. Therefore, if the anticipated change has not occurred, the retain decision exacts cost 0.

Otherwise, the retain decision causes the next decision interval execution to have a mean execution time of %. The expected cost of the retain decision in state <p,n> is p'%.

The decision process may decide to test. This decision causes the running system to halt; a

new partition is calculated, and is tested against the old partition on recent workload profiles. We

let Dd denote the delay caused by calculating and testing a new partition. Partition comparison

can be placed in a decision theoretic context, as described in [15]. If the new partition is found

superior, the change is considered to have occurred, and the decision process is considered to be

stopped. A stopped process incurs an additional time cost Dr quantifying the time required to

implement the new partition. A stopped process also incurs an execution cost er for every remaining decision interval in the computation. At time n, the expected value of this execution cost is

equal to cr'(JVn - n + 1). If the change has occurred, the test decision incurs an expected cost

D_ + Dr + er'(IVn - n + 1). A premature test decision incurs only the calculation delay D_. In

this case the probability of change by time n is taken to be zero, and the decision process
-7-

Notation Definition

n Decision Step Number

N Random number of decision steps

M Upper Bound on N

An N given N/> n

Nn E[N.]

e, Decision Interval Post-Change Execution Time, Original Partition

e, Decision Interval Post-Change Execution Time, New Partition

D_ Delay to Calculate and Test New Partition

D, Delay to Implement New Partition

a Change Test Type I Error

fl Change Test Type II Error

€ Time of Change Failure Rate Probability

p*(p) Pre-Observation Probability of Change At Next Decision Step

pC(p) Posterior Probability of Change After Positive Change Observation

pT(p) Posterior Probability of Change After Negative Change Observation

qC(p) Probability of Observing Change Next Observation

qT"(p) Probability of Not Observing Change Next Observation

V(<p,n>) Optimal Cost Function

E_[<p,n>] Expected Future Value of V(<',n+l>) from <p,n>

R(<p,n>) Optimal Future Costs Given Retain at <p,n>

T(<p,n>) Optimal Future Costs Given Test at <p,n>

Table I

continues. The expected cost of choosing to test in state <p,n> is thus given by

D, + p'( er'(Nn- n +1) +D r).

We now consider the state transition probabilities. The state following a retain decision

from <p,n> depends on the result of the change detection test to be performed at time n + 1.

From state <p,n>, the probability of observing a change at time n + 1 is given by qe(p), found

by conditioning on the time of change:

qC(p) = p*(p)'(1 - fl) + (1 - p*(p))'cl. (5)

From <p,n> the probability qC(p) of not observing a change at time n + 1 is just 1 - qC(p).

Given a retain decision in <p,n>, the decision process passes into state <pC(p),n+l> with probability q'(p); it passes into state <pT"(p),n+l> with probability qT"(p).

The optimal cost function's state transition component is concisely represented by the following function. Let

E,(<p,n>) = qC(p).V(<pC(p),n+l>) + qT"(p).V(<pT"(p),n+l>). (6)

E,(<p,n>) is interpreted as the minimized expected future costs at time n+l, as seen from state

<p,n> after a retain decision.
-8-

The decision to retain in <p,n> incurs an expected cost p'e,; the minimal expected future

costs are given by E_(<p,n>). The expected future cost of the policy which retains in <p,n>,

and thereafter uses the optimal stationary policy is thus

RC<p,n> ) = p'e o + EvC<P,n> ). (7)

Similarly, the decision to test in <p,n> incurs an expected cost D_ + p'Cer'CNn-n+l ) + Dr). No

other costs are incurred if the process stops. If instead the process rejects the new partition, the

probability of change is taken to be zero, the state transition probabilities into time n+l are

identical to those after a retain decision from state <0,n>. Thus the minimal expected future

costs in this case are simply Ev(<0,n> ). The expected future cost of the policy which retains in

<p,n> and thereafter uses the optimal stationary policy is thus

D, + p'(er-CN,-n+l) + Dr)) + (1 - p)'EvC<O,n>). (8) T(<p,n>)

In terms of equations (7) and (8), Theorem 1 states that

V(<p,n>) = min{ T(<p,n>), R(<p,n>) } , (9)

so that the optimal stationary decision in state <p,n> is to retain if and only if

R(<p,n>) <. f(<p,n>).

Equations (6)-(9) illustrate the recursive relationship satisfied by the optimal cost function.

Since the number of decision steps is bounded above by M, we can define V(<p,M+I>) = 0 for

all p _ [0,1], and can solve for V(<p,n>) when 0 _<n _<M. We next show that the solution of

V(<p,n>) is nicely characterized without explicit quantification.

VI. Properties of V(<p,n>)

We will demonstrate that the optimal stationary decision policy is given by a sequence

_r0,zq, • • • of thresholds from the interval [0, 1]. The optimal decision in state <p,n> is to test

if and only if p > _rn. This structure is revealed by analysis of T(<p,n>) and R(<p,n>) for fixed

n as a functions of p. We will show that for every n, there exists ;rn such that whenever p _<_rn

then R(<p,n>) <. T(<p,n>), and whenever p > r n then R(<p,n>) > T(<p,n>). Our vehicle for

this result is the demonstration that for fixed n, T(<p,n>) is linear in p, and R(<p,n>) is concave in p. We analyze the values of these functions at their endpoints and argue that T(<p,n>)

and R(<p,n>) can intersect at most once, at p = r n.

Some of our analysis conditions on the value of N. We use the notation f(<p,n>{ N=m) to

denote the value of function f at state <p,n> given that N = m.

Our first observation is that for any fixed n, T(<p,n>) is a linear function of p. This is

apparent from equation (S), as the value Ev(<0,n> ) is independent of p. Thus

LEMMA 1 : For fixed n, T(<p,n>) is a linear function of p.

o

We next observe that for fixed n, R(<p,n>) is a piece-wiselinear continuous concave (plcc)

function of p. This result follows primarily from the following lemma reported in [18] and stated

in terms of our notation:
-9-

LEMMA 2 : Suppose that N = m. If V(<p,n+l> IN=m) is a plcc function of p, then

E,(<p,n> I N=m) is a plcc function of p.

t3

We use this lemma to establish another.

LEMMA 3 : For every fixed n 1>0, V(<p,n>) and R(<p,n>) are plcc functions of p.

PROOF: We first condition on N= m for some m. We then inductively show that

V(<p,n> I N=m) and R(<p,n> I g=m) are plcc functions of p. For the base case we consider

n = m. For any p _ [0,1],

R(<p,m>l N=m) = p'e. + E,(<p,m>l g=m)

= p.e o

since V(<p,m+l> IN=m) = 0 for all p. Thus R(<p,m>[ N=m) is plcc in p. We also observe

that T(<p,m> I N=m) is plcc since it is linear. The class of plcc functions is closed under the

pointwise minimum operation; V(<p,rn> I N=m) must also be plcc, establishing the induction

base.

For the induction hypothesis we suppose that both R(<p,n+l>] N=m) and V(<p,n+l>] N=m)

are plcc functions of p for some n _<m - 1. Lemma 2, and the closure of plcc functions under

addition and pointwise minimum again ensure that R(<p,n>) and V(<p,n>) are plcc functions

of p, completing the induction.

To complete the proof, we note that the class of plcc functions is also closed under scalar multiplication, and observe that

M

V(<p,n>) = _ Prob{g= m}'V(<p,n>lg=m)

m=O

and

M

R(<p,n>) = Prob{N= m}.R(<p,n>[ N=rn)

m,=O

[]

We next analyze the values of T(<p,n>) and R(<p,n>) at p = 1. We show that V(<l,n>)

is a well-behaved function of n.

LEMMA 4 : Either

(i) V(<l,n>) = T(<l,n>) for all n for which Prob{N = n}=i=0;or

(ii) V(<l,n>)= R(<l,n>)forallnforwhichProb{N=.)€0; or

(iii) There exists an no (possibly co) such that for all n < no, V(<l,n>) = T(<l,n>), and for all

n/> no for which Prob{N = n}=i=0, V(<l,n>) = R(<l,n>).

PROOF: We condition on N = m, for any 0 _<rn _<M. Let K be the largest integer such that

(co - er)'K _ D_ + D r. Simple algebra (omitted here) establishes the inductive proof that for all

nsuchthatm-K<n_<m,
-10-

V(<l,.>lg=m)=RC<l,n>lN=m)= eo'(m - n + 1);

and that forO_<n_<m-K,

V(<l,n> I N=m) = T(<l,n>[ N=rn) = D_ + Dr + cr.(rn - n + 1)

and

R(<l,n>[ Y=m) = Dd + D, + eo + e,'(rn - n).

Define d(n[ Y=m) to be the conditional difference T(<l,n> I N=m) - R(<l,n>[ Y=m), and d(n)

to be the unconditional difference T(<l,n>) -R(<l,n>). From the equations above, we see

that as a function of m,

d(n IN=m) = D(e,r +_ ne*) r - (e, for -n e+rg)._<(m -mn + l) forrn< n+g

It follows from the definition of K that d(nIN=m) is a decreasing function of m. The unconditional difference d(n) is obtained by taking the expectation of d(n IN=m) with respect to the

residual distribution Nr, of N given N/> n. Recalling our remarks in section 4, we have effectively

assumed that N n _>LNn+l for all n/>0, implying that E[g(Nn) ] <. E[g(N_+I) ] for all decreasing

functions g. In particular, d(n) <<.d(n+l), showing that the difference T(<l,n>) - R(<l,n>) is

an increasingfunctionof n. Then case (i) occursif d(n) is negativefor all n, case (ii) occurs if

d(n) is positive for all n, and case (iii) occurs if d(n) changes sign at n = n0.

o

We summarize the known behavior of V(<p,n>) as a function of p. R(<p,n>) is a plcc

function of p, and T(<p,n>) is linear in p. From this we infer that if T(<l,n>) _<R(<l,n>),

then the functional curves of T(<p,n>) and R(<p,n>) can intersect at most once for p e [0,1]

(otherwise the concavity of R(<p,n>) is violated). The last lemma shows that either

T(<l,n>) /> R(<l,n>) for all n >/0, or that T(<l,n>) _<R(<l,n>) only if n is less than some

threshold no (potentially c_). Furthermore, it is easily seen that

T(<0,n>) - R(<0,n>) = Da > 0

for all n. These observations collectively establish the structure of the optimal stationary decision policy for small enough n: if n _<no let r n be the unique solution to the equation

T(<p,n>) = R(<p,n>). The existence of this solution is ensured by continuity, and the fact that

T exceeds R at p = 0 while R exceeds T at p = 1. The optimal policy is to retain in all states

<p,n> such that p _ rn, and to test in states <p,n> such that p > rrn. Figure I illustrates this

argument, showing plots of R(<p,n>) and T(<p,n>) as functions of p when n _<n 0.

We complete the analysis of V(<p,n>)'s behavior by supposing n > no, so that

R(<l,n>) < T(<l,n>). The following lemma demonstrates that when n > no, R(<p,n>) is

linear in p. Since T is linear and exceeds R at p = 0 and p = 1 for such n, the functional curves

for T(<p,n>) and R(<p,n>) cannot intersect.

LEM_I_A. 5 : If n > no, then R(<p,n>) is linear in p, and V(<p,n>) = R(<p,n>) for all

pe [0,1].

PROOF: We proceed by induction. M is the largest integer such that Prob{N = M} € O, so

that V(<p,M+I>) = 0 for all p and
-11-

R(<p,n>)

T(<p,n>)

I

0 _n 1

P

Figure I

V D,t + p'(e, + D,)(<p,M>) = min p'e,

Presuming that n o <M, we have V(<p,M>) = R(<p,M>) = p'e,, which is linear in p.

For the induction hypothesis, we suppose there is an n > no such that

V(<p,n+l>) = R(<p,n+l>) for all p _ [0,1], and that R(<p,n+l>) is linear in p. Equation (7)

implies that

R(<p,n>) = p'e, + qC(p)'V(<p'(p),n+l>) + qT(p)'V(<pT"(p),n+l>),

and the induction hypothesis states that

V(<p,n+l>) = A'p + B

for some A and B. Equations (2), (3), and (5) show that that p'(p) = p*(p)'(1 -/_) and that

qC(p)

pT"(p)= P'(P)'/_; it follows that q (p)

R(<p,n>) = p'e, + A'p°(p) + B

Then R(<p,n>) is linear in p; since T(<p,n>) exceeds R(<p,n>) at both p = 0 and p = 1, it

follows directly that T(<p,n>) exceeds R(<p,n>) for all p _ [0, 1]. Thus

V(<p,n>) = R(<p,n>), completing the induction.

[]

The discussions developed in this section prove our main analytic result.

THEOREM 2 : For every n, there exists a _rn _ [0,1] such that the optimal stationary decision

in state <p,n> is to retain if p _<rn, and to test if p > _rn.

[]
-12-

VII. Minimization of Expected Execution Time

We have constructed a decision process and exposed the structure of its optimal stationary

policy. We next show that employment of the optimal decision policy minimizes the

computation's expected execution time.

Our model formulation does not impose any execution costs until a change actually occurs.

The optimal decision policy minimizes the expected sum of all overhead delays and all postchange execution delays. The overall expected finishing time is equal to the expected sum of all

execution and overhead delays. However, the pre-change execution delays are independent of any

decision policy. By minimizing the expected overhead and post-change execution delays, we

minimize the expected finishing time.

The optimality of our derived policy is conditioned on constant model parameters.

Modification of these parameters may change the optimal decision policy without changing the

computation in any functional sense. For example, we might decrease the batch means set size d

or the AIC cluster size b to decrease the decision interval length. This modification would

increase the responsiveness of the decision model to change, at the cost of increased error probabilities a and ft. This change in no way affects the functional behavior of the computation. Likewise, our policy depends on both the quality of partitions created by the partitioning algorithm,

and that algorithm's running time. Our decision policy would be a valuable tool in exploring the

tradeoffs between partition quality and the run-time required to achieve that quality.

VIII. A Repartitioning Heuristic

In this section we note that solving for the precise optimal thresholds _rn is not computationally feasible, and examine a simple heuristic which nearly minimizes the expected computation

execution time. We furthermore observe that the timely detection of change is the most important component of our repartitioning decision heuristic.

In theory, the optimal cost equations (9) can be solved recursively. M was defined to be the

largest integer such that Prob{N = M}#0. The recursive solution begins with

V(<p,M>) = min{p'eo, D,t + p'(e_ + D,)},

and then solves for decreasing n using equations (6)-(9). However, V(<p,n>) is piecewise linear

with the number of pieces tending to double at each step of the recursion. An exact solution is

not computationally feasible for any large M. Approximation techniques might be employed, but

even then the solution method could require more computation than its results justify. Furthermore, our decision model impractically presumes that the values of e0 and er are known a priori.

We describe a heuristic which is based on the optimal decision policy structure. Empirical tests

indicate that the heuristic yields total policy costs which are extremely close to the optimal

policy's cost.

The optimal decision policy's structure suggests that a heuristic be focused on the probability of change. We have shown already how this probability can be dynamically maintained. The

first task for our heuristic is to determine when to estimate e° and er. We want the heuristic to

be responsive to a change, and yet we don't want premature estimations of these execution time

means. Before a change occurs, most change detection tests will report no change, and the posterior probability of change is calculated using the function if(p). In [151we show that if(p) is a

contraction mapping[16], implying that so long as no change has occurred, the probability of

change will be close to the fixed point solution q = pC(q). If Pn is significantly greater than this q

we can be reasonably sure that a change did occur. Following this reasoning, we choose an initial
-13-

"- threshold Pe so that er and eo are estimated whenever Pn > Pc. Pc is chosen so that starting with

a prior probability equal to p_'(p)'s fixed point solution, three successive positive indications of

change are needed to exceed Pc" After estimating eo and er, the value of no is determined (in

O(M) time). If the current time step n€exceeds no, the original partition is retained for the rest

of the computation. Otherwise, a high probability threshold p = .8 is chosen. We approximate _rn

for time steps n between ne and no linearly by

(n - no)

p_--p+(1-p)-(n °- nc)

The heuristic policy then mimics the optimal policy, treating each Pn as though it were _rn. A

premature choice of the test decision causes the heuristic to abandon the {p_}, and wait again for

the probability of change to exceed Pc before recalculating the {p_}.

IX. An Empirical Study

We performed an empirical study comparing this heuristic's performance with the optimal

decision policy. The exact optimal decision policy cannot be calculated except for small M. For

large M we used a computationally expensive approximation to the optimal policy. At every step

in the recursive solution, this approximation retained at most 1024 linear segments of an approximation to V(<p,n+l>). These segments were used to calculate the approximately 2048 linear

segments of (the approximation to) V(<p,n>). The 1023 segments closest to p = 1 were

retained; the remainder of V(<p,n>) was approximated by a single line segment extending from

p = 0 to the leftmost of the retained segments. This approximation was designed to closely model

the behavior of optimal cost function in the region of the optimal policy threshold.

Our study varied two parameters: N and G = eo - er. For simplicity, N was considered to

be constant. Given values for N and G, the other model parameters had the following values:

er 200-G _ 0.2

D_ 100 /3 0.05

D, 100

Table H

The rational behind this quantification of Co, e_, Dd, and D_ was that we expect these values to

have the same order of magnitude. € was chosen with the philosophy that if we know very little

about a potential change, a reasonable guess is that it is (approximately) as likely as not that a

change will occur. _ and fl model our experience with using the AIC statistic. Our selection of N

and G as free parameters followed from our intuition (borne out by computational experience)

that optimal behavior is influenced most by these two parameters.

.- We allowed G to take on the values 5, 50, and 100, thereby spanning two orders of magnitude. N was assigned the values 10, 50, 100, and 1000. We first measured the relative difference

%n in finishing time between the computation under the approximated optimal policy and under

the policy which always retains, i.e., does nothing. Relative to the total finishing time, _n is the

maximal percentage gain we can hope to achieve. We then calculated %1/, the percentage of this

maximal gain achieved by our heuristic. Table III contains the result of these calculations; each

measurement is plus or minus 0.5% with a confidence of at least 95%.
-14-

N G %. %tt G %. %u G %. %_t

10 5 n.0 50 4.7 55.2 100 19.2 75.3

50 5 0.48 54.8 50 11.3 93.4 100 32.4 95.5

100 5 0.5 82.9 50 12.2 95.1 100 33.9 97.1

I000 5 0.94 98.3 50 12.5 99.5 I00 34.3 99.5

Table Ill

We can draw a number of conclusions from Table III. Obviously, when the gain G achievable by repartitioning is very small, there is very little difference between using the optimal policy, and the policy which always retains. If G is substantially larger, we can expect significant

improvement in completion time by using a good decision policy. Furthermore, our proposed

heuristic achieves most of the possible repartitloning gain. In fact, the relative difference in

finishing time between our heuristic and the optimal decision policy is usually a fraction of one

percent. The length of the computation also has a significant effect on our performance figures. As

N grows, the performance of our heuristic tends to the optimal performance. It therefore appears

that when G is precisely known, then our heuristic can be expected to yield nearly optimal performance.

The experiments summarized by Table III assumed that the heuristic could accurately

assess e, and er. Since these quantities are difficult to predict, we tested the heuristic's performance when it mlss-estimated 17. Miss-estimatlon of G affects our heuristic by altering the time

step threshold no, which in turn alters the {p,}. We tested the heuristic using the parameter

values illustrated in Table III. For each pair of fixed G and N, we caused the heuristic policy to

miss-estimate G by factors of 10-3, 10-2, 10-I, 10, 102 , and 103. Table IV lists the resulting _//

G N I0 -3 10-2 10-I I0 102 103

50 10 -7.1 -16.7 -19.4 44.5 48.3 44.1

100 10 5.2 -3.5 0 77.0 77.1 74.3

5 50 35.2 35.1 34.6 -67.1 -97.7 -108.2

50 50 10.0 23.1 33.8 93.9 94.2 92.4

100 50 14.1 27.0 82.0 95.6 96.4 95.1

5 100 11.4 21.7 22.3 49.6 42.9 42.6

50 100 53.1 50.5 86.9 95.2 96.4 96.1

100 100 55.7 53.2 95.7 97.2 97.5 97.6

5 1000 92.7 92.6 95.3 98.4 98.3 98.4

50 1000 94.8 98.0 99.6 99.7 99.7 99.7

100 1000 95.2 99.2 99.6 99.7 99.7 99.7

Table IV

as a function of G, N, and the miss-estimation factor.

Study of Table IV leads to several observations. Table IV clearly shows that the performance of the heuristic becomes insensitive to miss-estimation as N increases. This phenomenon

parallels the observation from Table III that the performance of the heuristic increases with N.

Both observations follow from the fact the the expected total gain from a new partition increases

in N, while the expected costs of not being optimally responsive after a change are constant. It is

also clearly more harmful to underestimate G than it is to overestimate it. When N is small,

underestimation leads to the conclusion that no < n,, so that no new partition is adopted. The
-15-

heuristic's costs are somewhat larger in this case than the true "always retain" policy, due to the

costs of estimating G. As N grows, it becomes more likely that, even though G is underestimated, the change occurs soon enough so that a new partition is adopted with a high enough

probability of change. By overestimating G, it becomes possible to adopt a new partition when

the benefits of doing so do not outweigh the costs D_ and D r. This unhappy situation is realized

only when both N and G are small. The most important conclusion we can draw from Table IV

is that for most reasonable values of G and N, gross miss-estimation of G does not seriously

affect our heuristic's performance. This implies that our heuristic's most critical feature is its

ability to detect change.

X. Multiple Changes

Our decision model presumes that at most one change will occur during the computation.

We were dissuaded from incorporating multiple changes as we felt that the additional complexity

might not lead to a better understanding of the problem. This opinion is supported by the

intractability of finding the optimal policy assuming a single change, and the high performance of

our simple heuristic. Nevertheless, we should consider how multiple changes might be handled.

Only minor modifications are required to adapt our heuristic to the possibility of multiple

changes. These modifications are invoked after a change occurs. Unlike the single change policy,

the decision process does not stop after adopting a new partition. It remains active, looking for

the next change. To do this, it must first collect a new base group B of observations which

characterize the post-change behavior. The test cluster which triggered the new partition might

be used as this B. The decision policy then continues just as before. The emperical results which

imply that change detection is the most critical element of a repartitioning decision also suggest

that this approach to multiple changes should work well.

XI. Conclusions

A good partitioning of a computation across multiple processors must make certain assumptions about the computation's running behavior. If that behavior were to radically change in the

middle of the computation 1, those assumptions could be invalidated, so that the partition is no

longer effective in reducing the running time of the computation. We have considered the problem of when to reject an old partition, and adopt a new one. We proposed the use of proven statistical techniques to detect change in a computation's stochastic behavior; we modeled the repartitioning decision problem as a Markov decision process. This decision process takes into account

the critical costs and benefits of repartitioning. We then characterized the decision policy which

minimizes the expected computation finishing time. While this policy can be intuitively

described, it is not easily quantified. We thus proposed and studied a heuristic decision policy

which is modeled after the optimal policy. This heuristic performs remarkably well over a wide

range of parameter values. Furthermore, it is quite insensitive to miss-estimation of the repartitioning gain. This observation leads us to conclude that the ability to detect change is the most

important feature of a repartltionlng policy. If we can detect change, and if we can expect to

" achieve more than marginal gain from repartitioning after a change, then we can expect our proposed policy to achieve most of the possible repartitioning gain.

1. We are currently considering different models of stochastic behavior in "Load Balancing

Computations with Non-Stationary Behavior", D.M. Nieol and J.H. Saltz, ICASE Report in preparation,

1986.
-16-

References

[1] M.J. Berger and S. Bokhari, "The Partitioning of Non-Uniform ProblemsVV,ICASE Report

No. 85-55, November 1985.

[2] S. Bokhari, "Partitioning Problems in Parallel, Pipelined, and Distributed Computing",

ICASE Report No. 85-5_, November 1985. (NASA CR-178023.)

[3] H. Bozedogan and S. Sclove, "Multi-Sample Cluster Analysis Using Akaike's Information

Criterion", Annals of the Institute of Statistical Mathematics 86,1 (1983).

[4] W.W. Chu, L.J. Holloway, M. Lan, and K. Ere, "Task Allocation in Distributed Data Processing vv,Computer, 18, 11, November 1980, 57-69.

[5] Y. Chow and W. Kowhler, "Models for Dyanamic Load Balancing in a Heterogeneous

Multiple Processor System", IEEE Trans. on Computers, C-ZS, 5, (May 1979), 354-361.

[6] T.C. Chou and J. A. Abraham, "Load Balancing in Distributed Systems", IEEE Trans.

on Software Eng., 8, 4 (July 1982), 401-412.

[7] D.L. Eager, E.D. Lazowska, J. Zahorjan, VVAComparison of Receiver-Initiated and

Sender-Initiated Adaptive Load Sharing (Extended Abstract)", Proceedings of the 1985

ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems,

August 1985, 1-3.

[8] G.S. Fishman, "Grouping Observations in Digital Simulation", Management Science 25,

(1978), 510-521.

[9] G.J. Foschini, "On Heavy Traffic Diffusion Analysis and Dynamic Routing in Packet

Switched Networks", in Computer Performance, K. M. Chandy and M. Reiser Eds. New

York: North-Holland, 1977.

[10] D. Gusfield, "Parametric Combinatorial Computing and a Problem of Program Module

Distribution", Journal of the ACM, 80, 3, July 1983, 551-563.

[11] D.I. Moldovan and J.A.B. Fortes, "Partitioning and Mapping Algorithms into Fixed Size

Systolic Arrays", IEEE Trans. on Computers, C-35, 1, (January 1986), 1-12.

[12] J.G. Kalbfleish, Probability and Statistical Inference II, Springer-Verlag, 1979.

[13] P.R. Ms, E.Y.S. Lee, and M. Tsuchiya, "A Task Allocation Model for Distributed Computing Systems", IEEE Trans. on Computers, C-31, 1, January 1982, 41-47.

[14] L.M. Ni, C. Xu, and T.B. Gendreau, VVADistributed Drafting Algorithm for Load Balancing 'v, IEEE Trans. on Software Engineering, SE-11, I0, October 1985, 1153-1161.

[15] D.M. Nicol and P. F. Reynolds, Jr., "The Automated Partitioning of Simulations for

Parallel Execution", University of Virginia Department of Computer Science Tech Report

TR-85-15, August 1985.

[16] G.M. Phillips and P. J. Taylor, Theory and Applications of Numerical Analysis, Academic

Press, 1973.

[17] C.C. Price, U.W. Pooeh, "Search Techniques for a Nonlinear Multiprocessor Scheduling

Problem", Naval Research Logistics Quarterly, 29, 2, June 1982, 213-233.

[18] A. Rapoport, W. E. Stein, and G. J. Burkheimer, Response Models for Detection of

Change, D. Reidel Publishing Company, Boston, 1979.

[19] S. Ross, Applied Probability Models with Optimization Applications, Holden-Day, San

Francisco19, 70.
-17-

[20] S. Ross, Stochastic Processes, Wiley and Sons, New York, 1983.

[21] S.A. Schmitt, An Elementary Introduction to Bayesian Statistics, Addlson-Wesley, 1969.

[22] d.A. Stankovic, "An Application of Bayesian Decision Theory to Decentralized Control of

Job Scheduling", IEEE Trans. on Computers, C-3`(, 2 (Feb 1985), 117-130.

[23] J.A. Stakovic, K. Ramamritham and S. Cheng, "Evaluation of a Flexible Task Scheduling

Algorithm for Distributed Hard Real-Time Systems", IEEE Trans. on Computers, C-3`(,

12 (December I985), 1130-11.(3.

[24] H.S. Stone, "Critical Load Factors in Distributed Computer Systems", IEEE Trans. on

Software Engineering, SE-`(, 3 (May 1978), 254-258.

[25] D. Towsley, "Queueing Network Models with State-Dependent Routing", Journal of the

ACM, 27, 2 (April 1980) 323-337.

[26] A.N. Tantawi and D. Towsley, "Optimal Static Load Balancing", Journal of the ACM,

32, 2 (April 1985), 445-465.
Standard Bibliographic Page

1. ICAsEReNO. p°ReportNASANo.CR-86-7178035 rt 2. Government Accession No. 3. Recipient's Catalog No.

4. Title and Subtitle 5. Report Date

An Optimal Repartitioning Decision Policy February 1986

6. Performing Organization Code

7. Author(s) 8. Performing Organization Report No.

David M. Nicol and Paul F. Reynolds, Jr. 86-7

g. Performing Organization Name and Address 10. Work Unit No.

Institute for Computer Applications in Science

and Engineering 11. Contract or Grant No.

Mail Stop 132C, NASA Langley Research Center NASI-17070, NASI-18107

Hampton, VA 23665-5225 13. Type of Report and Period Covered 12. Sponsoring Agency Name and Address

Cnntr_rtnr Rpnort

National Aeronautics and Space Administration 14 Sponsoring Agency Code

Washington, D.C. 20546 _n=_o1_o__nl

15. Supplementary Notes Jv .......

Langley Technical Monitor: Submitted to IEEE Trans. on

J. C. South Software Engineering

Final Report

16. Abstract

A central problem to parallel processing is the determination of an

effective partitioning of workload to processors. The effectiveness of any

given partition is dependent on the stochastic nature of the workload. We

treat the problem of determining when and if the stochastic behavior of the

workload has changed enough to warrant the calculation of a new partition. We

model the problem as a Markov decision process, and derive an optimal decision

policy. Quantification of this policy is usually intractable; we empirically

study a heuristic policy which performs nearly optimally. Our results suggest

that the detection of change is the predominant issue in this problem.

17. Key Words(Suggestedby Authors(s)) 18. DistributionStatement

Parallel Processing, Partitioning, 66 - Systems Analysis

load balancing, decision process

Unclassified - unlimited

lg. Security Cl_slf.(ofthisreport) 120. Security Cl_sif.(ofthispage) 21. No. ofPages 22. Prlce

Unclassified I Unclassified 18 A02

For sMe by the NationM TechnicM In_rmation Se_ice, Springfield, Virginia 22161

NASA Langley Form 63 (June 1985)

,7