/* This file contains a workload generator written
by Allen B. Downey as part of the research for the
following papers:
@inproceedings{Downey97c,
AUTHOR = {Allen B. Downey},
TITLE = {A parallel workload model and its implications for
processor allocation},
booktitle = {The Sixth IEEE International Symposium on High
Performance Distributed Computing (HPDC '97)},
YEAR = {1997},
Note = {Also available as University of California
technical report number CSD-96-922}
}
@inproceedings{Downey97a,
author = {Allen B. Downey},
title = {Using Queue Time Predictions for Processor Allocation},
year = {1997},
booktitle = {Proceedings of the Workshop on Job Scheduling Strategies
for Parallel Programming at IPPS '97},
note = {Also available as University of California technical
report number CSD-97-929}
}
@techreport{Downey97b,
AUTHOR = {Allen B. Downey},
INSTITUTION = {University of California at Berkeley},
TITLE = {A model for speedup of parallel programs},
number = {CSD-97-933},
note = {Unpublished},
YEAR = {1997},
}
All three papers are available from http://www.sdsc.edu/~downey
During the development of this code, I was supported by
the following grants:
NSF grant ASC-89-02825 and
Advanced Research Projects Agency/ITO,
Distributed Object Computation Testbed,
ARPA order No. D570,
Issued by ESC/ENS under contract \#F19628-96-C-0020.
One of these agencies, and/or U.C. Berkeley, probably own the copyright,
but in any case, you may copy, modify, spindle and mutilate it however you
see fit, as long as this notice appears at the beginning.
If you use this code and publish the results, please cite one of
the above papers or the web page as the source.
Also, I would appreciate it if you would send me some mail and tell me
what you are using it for. Thanks! (downey@colby.edu) */
#include
#include
#include
#include
#define NUM_PES 64 /* number of processors in simulated machine */
#define NPROCS 1000 /* number of processes that will be generated */
int seed;
double rho;
double lambda;
double logtmin, logtmax;
double maxpar;
double arrival[NPROCS];
double lifetime[NPROCS];
double A[NPROCS];
double sig[NPROCS];
/* DRANDOM: choose a random floating-point number between zero and
one (including both), based on a 31-bit random integer */
double drandom ()
{
return (double) (random() & 0x7fffffff) / (double) 0x7fffffff;
}
/* CHOOSE FROM EXPONENTIAL : choose a value from an exp distribution
with the given parameter lambda */
double choose_from_exponential ()
{
double x;
do x = drandom (); while (x == 0.0);
return -log (drandom ()) / lambda;
}
/* CHOOSE FROM LOG UNIFORM : low and high are the exponents of the
range; i.e. low = 0 and high = 3 would have a range from 1 second
to exp(3) seconds */
double choose_from_log_uniform (double low, double high)
{
double x = drandom () * (high-low) + low;
return exp(x);
}
/* CHOOSE LIFETIME : log uniform distribution between tmin and tmax */
double choose_lifetime ()
{
return choose_from_log_uniform (logtmin, logtmax);
}
/* AVG_LIFETIME: calculates the average lifetime in a log uniform
distribution with parameters tmin and tmax */
double avg_lifetime ()
{
return (exp (logtmax) - exp(logtmin)) / (logtmax - logtmin);
}
/* CHOOSE PARALLELISM : log uniform distribution between 1 and maxpar */
double choose_parallelism ()
{
return choose_from_log_uniform (0.0, log(maxpar));
}
/* CHOOSE SIGMA : uniform distribution between 0 and 2 */
double choose_sigma ()
{
return (drandom() * 2.0);
}
/* Sa: calculate the slowdown on n processors given average parallelism A
and coefficient of variation (squared) cv2 */
float Sa (int n, float A, float cv2)
{
if (cv2 <= 1.0) {
/* low variance model */
if (n <= A) {
return A*n / (A + cv2/2 * (n-1));
} else if (n < 2*A - 1) {
return A*n / (cv2 * (A - 0.5) + n * (1 - cv2/2));
} else {
return A;
}
} else {
/* high variance model */
if (n < A*cv2 + A - cv2) {
return n*A * (cv2+1) / (cv2 * (n+A-1) + A);
} else {
return A;
}
}
}
/* RUN_TIME: calcualte the run time of the job indexed by proc,
given pes number of processors */
float run_time (int proc, int pes)
{
float speedup = Sa (pes, A[proc], sig[proc]);
return lifetime[proc] / speedup;
}
void generate_arrivals ()
{
int i;
double time = 0.0;
for (i=0; i