Difference between DYNAMIC and ADAPTIVE load balancing???
The Daily Planet
Hi there. Subject says it all. I have seen many papers about dynamic and
adaptive load balancing, but I couldn't understand the difference.
Are these really two different categories in load balancing, or are these
two words used interchangeably in the literature. Please post your
response, so that other people can post their views about the responses.
Thanks.
Amin
Phillip E Krueger
The difference between static and dynamic (I'll get to adaptive in a second)
load distributing (or global scheduling) algorithms is the use of system
state information. While static algorithms make no use of such information,
dynamic algorithms use such information to improve individual job transfer
decisions.
Adaptive algorithms constitute a subset of dynamic algorithms. Adaptive
algorithms go further in their use of system state information: Such
information may be used to modify the parameters of the algorithm, or even to
choose which load distributing strategy is used. For example, you might find
that load distributing algorithm A is best under system conditions X, while
algorithm B is better under conditions Y. An adaptive algorithm might choose
which strategy to pursue based on whether the conditions it observes are closer
to X or Y. As a more detailed example, sender-initiated algorithms tend to
perform better than receiver-initiated algorithms when the overall system load
is low, though receiver-initiated algorithm performs better when the system
load is high (sender-initiated algorithms are disastrous at high loads). An
adaptive algorithm might choose to follow a sender-initiated strategy when the
load is low, but switch to a receiver-initiated strategy if the load becomes
high.
Examples of adaptive algorithms can be found in:
N. G. Shivaratri and P. Krueger, "Two Adaptive Location Policies for Global
Scheduling Algorithms," Proc. 10th International Conference on Distributed
Computing Systems, pp. 502-509 (May 1990).
-- Phil Krueger
--
Assistant Professor
Ohio State University ph...@cis.ohio-state.edu
Dept. of Computer and Info. Science ..!osu-cis!cis.ohio-state.edu!philk
2036 Neil Ave. Columbus, OH 43210-1277 (614) 292-2565
Xander Evers
The terms dynamic scheduling and adaptive scheduling are sometimes used
in the literature in an inconsistent manner. A dynamic schedular takes
into account the current state of affairs as it perceives it in the system.
This is done during the normal operation of the system under a dynamic and
unpredictable load.
An adaptive solution to the load balancing problem is one in which the
algorithms and parameters used to implement the scheduling policy change
dynamically according to the previous and current behavior of the system,
in response to previous decisions made by the scheduling system. In contrast
to an adaptive scheduler, a non-adaptive scheduler would be one which does
not necessarily modify its basic control mechanism on the basis of the
history of system activity.
In an adaptive system, the scheduling policy itself reflects changes in
its environment--the running system. Whereas a dynamic solution takes
environmental inputs into account when making decisions, an adaptive
solution takes environmental stimuli into account to modify the scheduling
policy itself. It is easy to see that it is impossible to have a static
adaptive scheduler, there are only dynamic adaptive load balancing algorithms.
Greetings,
Xander Evers
National Institute for Nuclear Physics and High-Energy Physics
P.O. Box 41882, 1009 DB Amsterdam, The Netherlands
Andy Bond
>
>The terms dynamic scheduling and adaptive scheduling are sometimes used
>in the literature in an inconsistent manner. A dynamic schedular takes
>into account the current state of affairs as it perceives it in the system.
Eager et al. (IEEE TOSE May 1986) refer to adaptive load sharing as
reacting to changes in the system state while others have referred to
the same type of load sharing as dynamic. I share the view of other
responders to this article that adaptive algorithms are more than just
dynamically adjusting to changes in system state. I view adaptive
algorithms as adding an extra dimension to dynamic algorithms by
modifying the allocation algorithm and not just the parameters to the
algorithm. In my work an adaptive allocator constructs unique
allocation algorithms for task clusters. As resource requirements of
the task cluster change the algorithm adapts to the new cluster
profile.
andy
Pankaj Mehra
information in making scheduling decisions.
There are two kinds of dynamic policies: ADAPTIVE and non-adaptive. The
latter always use the same (fixed, load-dependent) policy; the former
may adjust policy parameters in order to gradually improve their
performance.
The key point is that while non-adaptive policies use only the
information about the run-time state (`load'), adaptive policies use
that plus information about current performance (`speed-up').
In adaptive policies, the rules for adjusting policy parameters may be
static or dynamic. An example of the former will be: "shift to a
conservative migration rule when system-wide load patterns are varying
too rapidly." An example of the latter will be: "increase sender-side
threshold when migrated jobs cause slowdown rather than speed-up." Some
researchers refer to the performance-driven adaptation exhibited by the
second policy as "learning."
Since both non-adaptive policies and adaptive policies with static
rules really use only load information, it is confusing to distinguish
between them. One way to avoid such confusion is to RESTRICT THE USE
OF THE WORD `ADAPTIVE' TO POLICIES THAT USE PERFORMANCE FEEDBACK in
order to drive their adjustment of policy parameters. EXAMPLES of
adaptive policies (in this restricted sense of the word `adaptive') are:
%K MTS90
%A R. Mirchandaney
%A D. Towsley
%A J. A. Stankovic
%T Adaptive Load Sharing in Heterogeneous Distributed Systems
%J J. Parallel and Distributed Computing
%V 9
%P 331-346
%I Academic Press, Inc.
%D 1990
%K MeW92
%A P. Mehra
%A B. W. Wah
%T Adaptive Load-Balancing Strategies for Distributed Systems
%J Proc. 2nd Int'l Conf. on Systems Integration
%I IEEE Computer Society
%C Morristown, NJ
%D June 1992
%P 666-675
COUNTEREXAMPLES are:
%K EaL86
%A D. L. Eager
%A E. D. Lazowska
%A J. Zahorjan
%T Adaptive Load Sharing in Homogeneous Distributed Systems
%J Trans. on Software Engineering
%I IEEE
%V SE-12
%P 662-675
%D May 1986
%K SaG88
%T Midgard: A Genetic Approach to Adaptive Load Balancing for Distributed Systems
%A A.V. Sannier\0II
%A E.D. Goodman
%J Machine Learning
%D 1988
%I Kluwer Academic Pub.
%C Boston, MA
%P 174-180
--
Pankaj Mehra
________________________________________________________________________
Phone: (217)244-7176 FAX: (217)244-7175 E-mail: p-m...@uiuc.edu
Rick LaRowe
>The terms dynamic scheduling and adaptive scheduling are sometimes used
>in the literature in an inconsistent manner. A dynamic schedular takes
>into account the current state of affairs as it perceives it in the system.
It appears to me that the difference between a dynamic and an adaptive
algorithm or policy is largely a question of whether you use the latest
buzzword or not. Say I've got two "dynamic" algorithms A and B, each
with a couple of parameters that affect their behavior. Based upon
some of the responses to the original post on this topic, lots of folks
would not consider these "adaptive" policies, even if they "react" to
the system state. But if I go and create policy C that uses some new
parameter values to select between policies A and B, it suddenly
becomes "adaptive", because the "basic control flow of the policy
changes in reaction to system state." But had I originally gone out
and implemented the basic functionality of policy C without mentioning
policies A and B, my description to it would have sounded alot like the
description I just gave for A and B (namely, they have parameters that
affect the way the policy behaves given certain system conditions).
So my question to the folks who claim there is really a difference;
where do you draw the line? When is a reaction to a change in system
state part of the basic algorithm, and when is it a change in the basic
control flow of the policy? In particular, I'd be curious to know
whether the NUMA memory management policy we (Carla Ellis and I)
studied in our SOSP '91 paper is dynamic or adaptive. We called it
dynamic (adaptive wasn't such a hot buzzword when we started that work
8-)), but given the extent to which its behavior can change (sometimes
replicating, sometime migrating, sometimes using remote reference
depending on the workload encountered), I can imagine calling in
adaptive.
Anyway, if there is a difference between dynamic and adaptive, I'd
certainly like to see a clearer definition.
Rick LaRowe
------------------------------------------------------------------------------
Center for High Performance Computing internet: rla...@chpc.org
Worcester Polytechnic Institute rla...@wpi.edu
Suite 170 phone: (508) 624-7400 x610
293 Boston Post Road West (508) 831-5837 (campus)
Marlborough, MA 01752 (508) 624-6354 (fax)
------------------------------------------------------------------------------