/* 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 <stdio.h>
#include <stdlib.h>
#include <float.h>
#include <math.h>

#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<NPROCS; i++) {
    arrival[i] = time;
    lifetime[i] = choose_lifetime ();
    A[i] = choose_parallelism ();
    sig[i] = choose_sigma ();

    time += choose_from_exponential ();
  }
}

void print_arrivals ()
{
  int i;

  for (i=0; i<NPROCS; i++) {
    printf ("%10.3lf\t%10.2lf\t%10.2lf\t%10.2lf\n",
	     arrival[i], lifetime[i], A[i], sig[i]);
  }
}

main (int argc, char *argv[])
{
  int seed;
  double mu;

  if (argc == 6) {
    seed = atoi (argv[1]);      /* random # seed */
    rho = atof (argv[2]);       /* load */
    logtmin = atof (argv[3]);   /* log of minimum run time */
    logtmax = atof (argv[4]);   /* log of maximum run time */
    maxpar = atof (argv[5]);    /* log of maxmum parallelism */
  } else if (argc == 1) {
    seed = 17;
    rho = 0.75;
    logtmin = 0.0;
    logtmax = 10.0;
    maxpar = NUM_PES;
  } else {
    printf ("Usage: sim [seed load logtmax logtmin maxpar].\n");
    exit (1);
  }

  srandom (seed);

  /* mu is average lifetime, lambda is 1/interarrival time */
  mu = avg_lifetime ();
  lambda = rho * maxpar / mu;

  generate_arrivals ();
  print_arrivals ();

  return 0;
}