Thinking concurrently

Concurrent and parallel processing, what can happen at once, benefits and trade-offs, and pipelining.

A2.8Recursion and computational thinkingA level25 min

A robot at a competition has jobs to do before a match: charge the battery, flash new firmware, print a part, calibrate the compass. One person doing them one after another takes all afternoon. A team that notices the battery can charge while the part prints finishes much sooner. Thinking concurrently is spotting which parts of a problem can happen at the same time, and knowing what that gains and what it costs.

Concurrent and parallel

• Concurrent processing means more than one task is in progress over the same period of time. On a single processor core the tasks take turns, switching so quickly that they all appear to run at once.
• Parallel processing means tasks literally run at the same instant, on separate cores or separate processors.

Parallel processing is one way of achieving concurrency; time-slicing on one core is the other. The robot does the second all the time: one loop that checks the distance sensor, then the LED, then the buzzer, round and round many times a second.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

# two jobs sharing one processor: turning in a circle, and beeping every half second
turn_right(30)                     # no angle, so it keeps turning and does not wait
last_beep = clock()
while clock() < 3:
    if clock() - last_beep >= 0.5:
        tone(660, 0.05)
        last_beep = clock()
    wait(0.05)
stop()
print("turned and beeped for", clock(), "seconds")

Run this in the simulator

turn_right(30) with no angle starts the motors and returns at once, so the loop can give the beeping job its turn. A command that waits until it has finished, such as forward(60, distance=20), would block every other job until it was done.

Which parts can happen at the same time?

Two parts of a problem can be done concurrently when neither depends on the other's result and they do not need the same resource at the same moment. To find them:

1. list the tasks and how long each takes;
2. for each task, list the tasks that must finish before it can start (its dependencies);
3. tasks with no dependency between them can run concurrently; a task must wait for the latest of its dependencies to finish.

The chain of dependent tasks with the longest total time sets the soonest the whole job can finish, however many workers there are. That chain is called the critical path.

Benefits and trade-offs

The speed-up from adding workers is limited by the part that has to be done in sequence. If a tenth of a job cannot be split, then even with unlimited workers it can never run more than ten times faster. This limit is known as Amdahl's law.

Pipelining

Pipelining splits a process into stages, where the output of each stage is the input of the next. Once the pipeline is full, every stage is busy with a different item at the same time. A processor's fetch, decode and execute stages work like this, and so does a factory line.

def pipeline_minutes(items, stages, minutes_per_stage):
    one_at_a_time = items * stages * minutes_per_stage
    # the first item takes every stage; after that one item comes out per stage time
    pipelined = stages * minutes_per_stage + (items - 1) * minutes_per_stage
    return one_at_a_time, pipelined

for items in [1, 10, 100]:
    slow, fast = pipeline_minutes(items, 3, 2)
    print(items, "items: one at a time", slow, "min, pipelined", fast, "min")

Run this in the simulator

A single item gains nothing, because it still passes through every stage. With 100 items, a three-stage pipeline is nearly three times faster. That calculation is a small performance model: predicting how a system will behave before building it.

Task: getting ready at the same time

The jobs before a match are held in a dictionary. Each job maps to a tuple (minutes, needs): how long it takes, and a list of the jobs that must finish before it can start.

• charge 40 min, needs nothing; flash 10 min, needs nothing; calibrate 5 min, needs flash;
• print 30 min, needs nothing; assemble 15 min, needs print and flash;
• test 10 min, needs assemble, charge and calibrate.

With as many workers as you like, a job starts the moment the last job it needs has finished. Write a recursive function finish(job) that takes a job name and returns the earliest time, in minutes from the start, that the job can be finished. Then print:

1. one worker: <n> min, the time with one worker doing the jobs one at a time;
2. test finishes at <n> min, using finish("test");
3. unlimited workers: <n> min, the latest finish of any job;
4. speed-up: <s>, one worker's time divided by unlimited workers' time, to 2 decimal places.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

jobs = {
    "charge": (40, []),
    "flash": (10, []),
    "calibrate": (5, ["flash"]),
    "print": (30, []),
    "assemble": (15, ["print", "flash"]),
    "test": (10, ["assemble", "charge", "calibrate"]),
}

def finish(job):
    minutes, needs = jobs[job]
    return minutes

Task: two jobs, one processor

Drive the robot towards the wall and flash its LED at the same time, on one processor.

• Start the motors with drive(60, 0), which does not wait. Do not use forward.
• Loop while distance() is more than 15 cm. Every time half a second has passed (use clock()), switch the LED between "yellow" and "off". Count each change to yellow as one flash. Let a little time pass each time round with wait(0.05).
• When the loop ends, stop(), set the LED to "green" and print stopped after <n> flashes.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

flashes = 0
forward(60, distance=50)

Challenges

1. Add a second worker limit: with exactly two workers, when can the test finish? Work it out by hand first.
2. Which job is on the critical path? Would making charge faster finish the test sooner?
3. In the flashing task, what goes wrong if the loop has no wait? What if it waits 2 seconds each time round?