Simulator for purging and non-purging fork-join queueing systems.

Fork-join queueing systems are models for several kinds of real-world systems, such as multi-path routing and parallelized computing architectures. The canonical model has a system with k parallel servers and jobs arriving that are composed of k tasks. Upon arrival the k tasks are queued at the k servers. A job can depart when each of its tasks has finished processing.

There are several variations on the model. This package simulates many types of fork-join systems and has interchangeable arrival and service processes and leaky bucket process regulators.

IntelliJ IDEA

We include a runner script, forkulator.sh, that saves you from having to type out all the JVM options. Here is an example simulating a standard fork-join system with exponential arrival and service processes and k=10. The results will be saved to files with names staring with "testrun".

./forkulator.sh -A x 0.5 -S x 1.0 -i 1 -n 1000 -o testrun -q w -t 10 -w 10

 -A,--arrivalprocess <arg>     arrival process
 -h,--help                     print help message
 -i,--samplinginterval <arg>   samplig interval
 -n,--numsamples <arg>         number of samples to produce.  Multiply
                               this by the sampling interval to get the
                               number of jobs that will be run
 -o,--outfile <arg>            the base name of the output files
 -p,--savepath <arg>           save some iterations of the simulation path
                               (arrival time, service time etc...)
 -q,--queuetype <arg>          queue type and arguments
 -S,--serviceprocess <arg>     service process
 -t,--numtasks <arg>           number of tasks per job
 -w,--numworkers <arg>         number of workers/servers

• -q w standard "worker-queue" fork-join system, where each server has a separate queue of tasks assigned to it.
• -q s "single-queue" system, where there is a single queue of tasks and tasks are serviced from that queue as workers become available.
• -q td deterministic thinning without resequencing
• -q tdr deterministic thinning with resequencing
• -q tr random thinning without resequencing
• -q trr random thinning with resequencing
• -q wkl <l_diff> standard purging "worker-queue" (k,l) system with k-l=l_diff
• -q wklnc <l_diff> standard non-purging "worker-queue" (k,l) system with k-l=l_diff
• -q wklncr <l_diff> standard non-purging-running-task "worker-queue" (k,l) system with k-l=l_diff
• -q skl <l_diff> "single-queue" (k,l) system with k-l=l_diff
• -q msw <h> multi-stage worker-queue system with h stages. Each task has the same service time at each stage.
• -q mswi <h> multi-stage worker-queue system with h stages. The tasks' service times at each stage are iid.

-A c <rate>

-A x <rate>

-A e <k> <rate>

-A g <mu> <sigma>

Given one parameter the process will be normalized to have expectation 1.0.

-A w <shape>

Or you can specify both the shape and scale parameters.

-A w <shape> <scale>

Here is an example running with exponential arrivals at rate 0.1, erlang-9 task service at rate 1.0, jobs sampled at interval 100, 100,000 samples, single-queue, 10 workers, 10 tasks/job, and logging the first 100 jobs of the experiment path.

./forkulator.sh -A x 0.1 -S e 9 1.0 -i 100 -n 100000 -o testrun_s -q s -t 10 -w 10 -p 100

Then we can look at the experiment path in gnuplot

gunzip testrun_s_path.dat.gz

gnuplot
plot 'testrun_s_path.dat' using 1:3 with line title "arrival time"
set ylabel "time"
set xlabel "task index"
replot 'testrun_s_path.dat' using 1:7 with line title "task start service"
replot 'testrun_s_path.dat' using 1:8 with line title "task finish service"
replot 'testrun_s_path.dat' using 1:6 with line title "job departure"

Then you can compare this to the standard fork-join model where each worker keeps a separate queue.

./forkulator.sh -A x 0.1 -S e 9 1.0 -i 100 -n 100000 -o testrun_w -q w -t 10 -w 10 -p 100

Then we can look at the experiment path in gnuplot

gunzip testrun_w_path.dat.gz

gnuplot
plot 'testrun_w_path.dat' using 1:3 with line title "arrival time"
set ylabel "time"
set xlabel "task index"
replot 'testrun_w_path.dat' using 1:7 with line title "task start service"
replot 'testrun_w_path.dat' using 1:8 with line title "task finish service"
replot 'testrun_w_path.dat' using 1:6 with line title "job departure"