Eight workers made it three times faster

# Self-authored for the EML case corpus (no external origin). A job that takes
# an hour on one worker is spread across eight, the parallel part divides
# perfectly with no coordination cost, and the job now takes twenty minutes.
# Why eight workers gave three times and not eight is computed below.
#
# The parallelisation is careful. The parallel part is split exactly eight
# ways; there is no overhead between workers; every worker is fully used on its
# share; and the intent is exactly 'eight workers, eight times faster'.
#
# A fifth of the job must run in one place before or after the rest, and that
# fifth takes the same twelve minutes however many workers wait for it - so
# eight workers give a speedup of three and a third, and no number of workers
# gives more than five.

60 => minutes_on_one_worker
2000 => serial_share_per_myriad
8 => workers

int(minutes_on_one_worker * serial_share_per_myriad / 10000) => serial_minutes
minutes_on_one_worker - serial_minutes => parallel_minutes_on_one_worker
int(parallel_minutes_on_one_worker / workers) => parallel_minutes_on_eight
serial_minutes + parallel_minutes_on_eight => minutes_on_eight_workers
int(minutes_on_one_worker * 100 / minutes_on_eight_workers) => speedup_hundredths
int(minutes_on_one_worker * 100 / serial_minutes) => speedup_ceiling_hundredths
workers * 100 => speedup_expected_hundredths

"job on one worker               : " + str(minutes_on_one_worker) + " minutes" ^0
"serial share                    : " + str(serial_share_per_myriad) + " per ten thousand, " + str(serial_minutes) + " minutes" ^0
"parallel share                  : " + str(parallel_minutes_on_one_worker) + " minutes on one worker" ^0
"" ^0
"on " + str(workers) + " workers, parallel part       : " + str(parallel_minutes_on_eight) + " minutes" ^0
"on " + str(workers) + " workers, serial part         : " + str(serial_minutes) + " minutes, unchanged" ^0
"job on " + str(workers) + " workers                 : " + str(minutes_on_eight_workers) + " minutes" ^0
"speedup                         : " + str(speedup_hundredths) + " hundredths, expected " + str(speedup_expected_hundredths) ^0
"speedup ceiling, any workers    : " + str(speedup_ceiling_hundredths) + " hundredths" ^0
"" ^0

# ---- what the parallelisation verified ----

"the eight-way split" ^0
"  parallel part : split exactly eight ways" ^0
"  overhead : none between workers" ^0
"  utilisation : every worker fully used on its share" ^0
"  intent : eight workers, eight times faster" ^0
"  idle workers during the parallel part : 0" ^0
"  verdict : THE PARALLEL PART RUNS EIGHT TIMES FASTER" ^0
"" ^0
"  a perfect split with no overhead is the part done right" ^0
"  here, and it is why the parallel " + str(parallel_minutes_on_one_worker) + " minutes really became " + str(parallel_minutes_on_eight) ^0
"" ^0

# ---- what the serial part does ----

"the part that does not divide" ^0
"  what it is : the fifth of the job that must run in one" ^0
"    place" ^0
"  what eight workers do to it : nothing; it takes " + str(serial_minutes) + " minutes" ^0
"    while seven workers wait" ^0
"  so the job : " + str(serial_minutes) + " plus " + str(parallel_minutes_on_eight) + ", " + str(minutes_on_eight_workers) + " minutes" ^0
"  with a thousand workers : " + str(serial_minutes) + " plus almost nothing, a ceiling of" ^0
"    " + str(speedup_ceiling_hundredths) + " hundredths" ^0
"  the serial fifth : sets the limit whatever the count" ^0
"" ^0

# ---- what the team got ----

"the result" ^0
"  workers added : " + str(workers) + " times" ^0
"  speedup : " + str(speedup_hundredths) + " hundredths" ^0
"  is the split imperfect : no; it is perfect" ^0
"  is the shortfall overhead : no; it is the part that was" ^0
"    never going to divide" ^0
"" ^0

# ---- null control ----

# The same job with the serial fifth itself reduced (from a fifth to a
# twentieth), which raises both the eight-worker speedup and the ceiling.
333 => nc_speedup_with_a_serial_fifth_hundredths
593 => nc_speedup_with_a_serial_twentieth_hundredths
2000 => nc_ceiling_with_a_serial_twentieth_hundredths

"null control - shrink the serial part, not add workers" ^0
"  speedup on eight, serial fifth : " + str(nc_speedup_with_a_serial_fifth_hundredths) + " hundredths" ^0
"  speedup on eight, serial twentieth : " + str(nc_speedup_with_a_serial_twentieth_hundredths) + " hundredths" ^0
"  ceiling, serial twentieth : " + str(nc_ceiling_with_a_serial_twentieth_hundredths) + " hundredths" ^0
"  no worker was added; the part that sets the limit was" ^0
"  made smaller" ^0
"" ^0

# ---- the rule ----

"what a perfect eight-way split guarantees" ^0
"  the parallel part runs eight times faster : exactly, no" ^0
"    overhead, full utilisation" ^0
"  the job runs eight times faster : not addressed; the" ^0
"    serial fifth takes " + str(serial_minutes) + " minutes on any number of workers," ^0
"    so the speedup is " + str(speedup_hundredths) + " hundredths and can never pass " + str(speedup_ceiling_hundredths) ^0
"" ^0

"the part that cannot be shared sets the pace for the whole once the rest is" ^0
"shared; adding hands to the divisible part shrinks it toward nothing and" ^0
"leaves the indivisible part standing, and the ceiling is the inverse of what" ^0
"cannot be split" ^0
"" ^0

"The parallel part is split perfectly eight ways with no overhead - it really" ^0
"runs eight times faster. But a fifth of the job is serial and takes " + str(serial_minutes) + " minutes" ^0
"whoever waits, so the job takes " + str(minutes_on_eight_workers) + " minutes not " + str(int(minutes_on_one_worker / workers)) + ", a speedup of " + str(speedup_hundredths) ^0
"hundredths with a ceiling of " + str(speedup_ceiling_hundredths) + ", until the serial part itself is shrunk." ^0

minutes_on_one_worker = 60
serial_share_per_myriad = 2000
workers = 8
serial_minutes = int(minutes_on_one_worker * serial_share_per_myriad / 10000)
parallel_minutes_on_one_worker = minutes_on_one_worker - serial_minutes
parallel_minutes_on_eight = int(parallel_minutes_on_one_worker / workers)
minutes_on_eight_workers = serial_minutes + parallel_minutes_on_eight
speedup_hundredths = int(minutes_on_one_worker * 100 / minutes_on_eight_workers)
speedup_ceiling_hundredths = int(minutes_on_one_worker * 100 / serial_minutes)
speedup_expected_hundredths = workers * 100
print("job on one worker               : " + str(minutes_on_one_worker) + " minutes")
print("serial share                    : " + str(serial_share_per_myriad) + " per ten thousand, " + str(serial_minutes) + " minutes")
print("parallel share                  : " + str(parallel_minutes_on_one_worker) + " minutes on one worker")
print("")
print("on " + str(workers) + " workers, parallel part       : " + str(parallel_minutes_on_eight) + " minutes")
print("on " + str(workers) + " workers, serial part         : " + str(serial_minutes) + " minutes, unchanged")
print("job on " + str(workers) + " workers                 : " + str(minutes_on_eight_workers) + " minutes")
print("speedup                         : " + str(speedup_hundredths) + " hundredths, expected " + str(speedup_expected_hundredths))
print("speedup ceiling, any workers    : " + str(speedup_ceiling_hundredths) + " hundredths")
print("")
print("the eight-way split")
print("  parallel part : split exactly eight ways")
print("  overhead : none between workers")
print("  utilisation : every worker fully used on its share")
print("  intent : eight workers, eight times faster")
print("  idle workers during the parallel part : 0")
print("  verdict : THE PARALLEL PART RUNS EIGHT TIMES FASTER")
print("")
print("  a perfect split with no overhead is the part done right")
print("  here, and it is why the parallel " + str(parallel_minutes_on_one_worker) + " minutes really became " + str(parallel_minutes_on_eight))
print("")
print("the part that does not divide")
print("  what it is : the fifth of the job that must run in one")
print("    place")
print("  what eight workers do to it : nothing; it takes " + str(serial_minutes) + " minutes")
print("    while seven workers wait")
print("  so the job : " + str(serial_minutes) + " plus " + str(parallel_minutes_on_eight) + ", " + str(minutes_on_eight_workers) + " minutes")
print("  with a thousand workers : " + str(serial_minutes) + " plus almost nothing, a ceiling of")
print("    " + str(speedup_ceiling_hundredths) + " hundredths")
print("  the serial fifth : sets the limit whatever the count")
print("")
print("the result")
print("  workers added : " + str(workers) + " times")
print("  speedup : " + str(speedup_hundredths) + " hundredths")
print("  is the split imperfect : no; it is perfect")
print("  is the shortfall overhead : no; it is the part that was")
print("    never going to divide")
print("")
nc_speedup_with_a_serial_fifth_hundredths = 333
nc_speedup_with_a_serial_twentieth_hundredths = 593
nc_ceiling_with_a_serial_twentieth_hundredths = 2000
print("null control - shrink the serial part, not add workers")
print("  speedup on eight, serial fifth : " + str(nc_speedup_with_a_serial_fifth_hundredths) + " hundredths")
print("  speedup on eight, serial twentieth : " + str(nc_speedup_with_a_serial_twentieth_hundredths) + " hundredths")
print("  ceiling, serial twentieth : " + str(nc_ceiling_with_a_serial_twentieth_hundredths) + " hundredths")
print("  no worker was added; the part that sets the limit was")
print("  made smaller")
print("")
print("what a perfect eight-way split guarantees")
print("  the parallel part runs eight times faster : exactly, no")
print("    overhead, full utilisation")
print("  the job runs eight times faster : not addressed; the")
print("    serial fifth takes " + str(serial_minutes) + " minutes on any number of workers,")
print("    so the speedup is " + str(speedup_hundredths) + " hundredths and can never pass " + str(speedup_ceiling_hundredths))
print("")
print("the part that cannot be shared sets the pace for the whole once the rest is")
print("shared; adding hands to the divisible part shrinks it toward nothing and")
print("leaves the indivisible part standing, and the ceiling is the inverse of what")
print("cannot be split")
print("")
print("The parallel part is split perfectly eight ways with no overhead - it really")
print("runs eight times faster. But a fifth of the job is serial and takes " + str(serial_minutes) + " minutes")
print("whoever waits, so the job takes " + str(minutes_on_eight_workers) + " minutes not " + str(int(minutes_on_one_worker / workers)) + ", a speedup of " + str(speedup_hundredths))
print("hundredths with a ceiling of " + str(speedup_ceiling_hundredths) + ", until the serial part itself is shrunk.")

job on one worker               : 60 minutes
serial share                    : 2000 per ten thousand, 12 minutes
parallel share                  : 48 minutes on one worker

on 8 workers, parallel part       : 6 minutes
on 8 workers, serial part         : 12 minutes, unchanged
job on 8 workers                 : 18 minutes
speedup                         : 333 hundredths, expected 800
speedup ceiling, any workers    : 500 hundredths

the eight-way split
  parallel part : split exactly eight ways
  overhead : none between workers
  utilisation : every worker fully used on its share
  intent : eight workers, eight times faster
  idle workers during the parallel part : 0
  verdict : THE PARALLEL PART RUNS EIGHT TIMES FASTER

  a perfect split with no overhead is the part done right
  here, and it is why the parallel 48 minutes really became 6

the part that does not divide
  what it is : the fifth of the job that must run in one
    place
  what eight workers do to it : nothing; it takes 12 minutes
    while seven workers wait
  so the job : 12 plus 6, 18 minutes
  with a thousand workers : 12 plus almost nothing, a ceiling of
    500 hundredths
  the serial fifth : sets the limit whatever the count

the result
  workers added : 8 times
  speedup : 333 hundredths
  is the split imperfect : no; it is perfect
  is the shortfall overhead : no; it is the part that was
    never going to divide

null control - shrink the serial part, not add workers
  speedup on eight, serial fifth : 333 hundredths
  speedup on eight, serial twentieth : 593 hundredths
  ceiling, serial twentieth : 2000 hundredths
  no worker was added; the part that sets the limit was
  made smaller

what a perfect eight-way split guarantees
  the parallel part runs eight times faster : exactly, no
    overhead, full utilisation
  the job runs eight times faster : not addressed; the
    serial fifth takes 12 minutes on any number of workers,
    so the speedup is 333 hundredths and can never pass 500

the part that cannot be shared sets the pace for the whole once the rest is
shared; adding hands to the divisible part shrinks it toward nothing and
leaves the indivisible part standing, and the ceiling is the inverse of what
cannot be split

The parallel part is split perfectly eight ways with no overhead - it really
runs eight times faster. But a fifth of the job is serial and takes 12 minutes
whoever waits, so the job takes 18 minutes not 7, a speedup of 333
hundredths with a ceiling of 500, until the serial part itself is shrunk.

Trace event types