[Beowulf] Arrival distribution to a typical beowulf system.

[Robert G. Brown]

On Mon, 5 Dec 2005, enver ever wrote:

> Hello there
>
> I am a PhD student working on mathematical modelling for performance 
> evaluation of  Beowulf
>
> clusters.
>
> My question is a bit general
>
> Can we assume that the job arrivals to a typical Beowulf system can be 
> exponential?

No.  First of all, I don't believe that there is any such beast as a
"typical beowulf system".  There are many distinct genera of cluster
computers; many if not most clusters are engineered to perform one
particular purpose optimally (quite possibly at the expense of other
purposes, at least insofar as money gets spent optimizing functionality
in one way that could have been spent optimizing it another).

To give you some idea of the breadth, a cluster computer running a
series of more or less identical tasks for a single researcher will
typically be distributed more or less periodically -- if you like, a
suitably coarse-grained fourier transform of arrival times will show a
distinct peak.  Example:  I run a Monte Carlo simulation on each node
that quenches 10^4 steps and then generates 10^6 samples, then dies.  A
simple looping script then resubmits a new simulation to accumulate
another megasample, "forever" (until I decide looking over the
statistics of the results that I have enough samples).  Each job runs in
(say) 18 hours; nobody else uses my cluster, so "arrivals" are periodic,
not exponential, per node, and are initially in phase but gradually
phase-drift apart as small delays cause nodes to finish at slightly
different times.

A second example might involve a whole cluster used for a tightly
coupled computation, submitted by hand by a single researcher.  Job is
started on Monday, runs until Thursday and completes.  Researcher spends
a day processing the data, running it into a visualization engine,
plotting it, deciding what to do next.  Friday they start another job
with different parameters (that might take only two days to finish
instead of 3-4).  The distribution in this case has some odd constraints
-- submission only during working hours (whatever they might be) so
there is likely to be a window of 6 to 16 hours where submission never
occurs.  Completion, however, can occur anytime (anytime after some
minimum time, maybe a day).  There is a lag of hours to days after
completion.  Completion can take a day to a week.  BUT there are NO
RANDOM INSERTIONS -- the cluster is used in a purely sequential tasking
mode by a single person, non-exponential indeed.

A third might be a "compute center" cluster, which is what I think you
are imagining.  In this model, "many" researchers share a cluster, and
in some of the largest ones (multinational Grids) we can at least
IMAGINE that the users are spread out more or less uniformly around the
planet and that there are enough of them that the implicit loose
periodicity of their own work cycles (diurnal and otherwise) is broadly
distributed with respect to start time and run time.  We'll also assume
that the cluster has a batch processing queue.  In that case many
possible modes suggest themselves depending on the DETAILS of the
workload completion time distribution and the degree of balance between
the user population and the resource.  If it is underutilized (has idle
time) you'll PROBABLY get something approximating a Poissonian
distribution (independent arrival times with some probability) with some
clustered bunching (Joe submits work not for one node but for twenty all
at once) and antibunching (after Joe submits he is unlikely to resubmit
until a certain minimal interval has gone by, that is, his job
completes).

If it is oversubscribed as far as user demand is concerned, then it
almost certainly has HUMAN or MANAGEMENT processes that limit submission
rates to some peak value lest the queue grow without bound.  These will
clip what otherwise might have been a perfectly lovely Poissonian by
again forcing a certain degree of antibunching, and the cluster dynamics
and job submissions en masse may or many not maintain a degree of
bunching (again on the basis of policy -- if people are running "real
parallel" applications on the cluster, they'll need to be able to
"reserve" enough nodes to be able to start the whole computation at
once, effectively blocking nodes out of the scheduling process and
resynchronizing them in a periodic antibunched state).

Overall, I'd expect exponential to more or less NEVER describe cluster
utilization, which is far more likely to be mixed periodic or a
convolution of mixed periodic and Poissonian.

It MIGHT be interesting to actually measure this on a few different
cluster models and compare the results to (say) network dynamics, which
is not completely dissimilar -- predominantly Poissonian to the extent
that packet arrival times associated with independent processes on many
independent machines are uncorrelated, but with a very definite
periodicity and both bunching and antibunching per machine and (at the
edge of the collision time domain at high loads) per network itself.

HTH,

    rgb

>
> thanks in advance
>
> many regards
>
>
> _______________________________________________
> Beowulf mailing list, Beowulf at beowulf.org
> To change your subscription (digest mode or unsubscribe) visit 
> http://www.beowulf.org/mailman/listinfo/beowulf
>

-- 
Robert G. Brown	                       http://www.phy.duke.edu/~rgb/
Duke University Dept. of Physics, Box 90305
Durham, N.C. 27708-0305
Phone: 1-919-660-2567  Fax: 919-660-2525     email:rgb at phy.duke.edu