# Example 912 — Eight workers made it three times faster `eight_workers_made_it_three_times_faster.eml` - 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. ## EML ```eml # 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 ``` ## Python (deterministic transpilation) ```python 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.") ``` ## stdout (executed) ```text 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. ``` ## Round-trip `ok: true` — round-trip fixpoint reached (python1 == python2) ## Trace event types eml:run:start · eml:assign · eml:output · eml:run:done