Splitting work across processes

To use several processors, you split one job into chunks, give each chunk to a separate worker and merge the answers. Splitting a job well is the skill behind every parallel program, from a laptop to a GPU.

A shop wants the total of a day's 40,000 orders. Four workers can each add a quarter of them, then one more step adds the four answers.

Chunks are shares of the data, cut so that no item is in two chunks and none is left out. Each worker gives a partial result for its own chunk.

A final step merges the partial results. For a sum, merging is adding. Cutting the data and merging the answers cost time, and both are serial.

# Cut 12 order totals into 3 chunks, add each chunk, then merge.
totals = [5, 8, 3, 9, 4, 7, 6, 2, 10, 1, 8, 5]
chunks = [totals[0:4], totals[4:8], totals[8:12]]
partials = []
for chunk in chunks:
    partials.append(sum(chunk))
print("chunks:", chunks)
print("partial sums:", partials)
print("merged:", sum(partials), "in one piece:", sum(totals))
# Cut the list into 2 chunks of 6 instead, then run again.

A process is a running program with its own memory. A thread runs inside a process and shares that memory.

Standard Python lets only one thread run Python code at a time. So for work that needs the processor, Python programs use several processes. Each has its own copy of the data and its own answer to send back.

The lab's chunks.py cuts the numbers 1 to 40 into four chunks of ten and gives them to a pool of two workers. A worker that finishes takes the next chunk.

The partial sums come back in chunk order, 55, 155, 255 and 355, whichever worker finished first. Their sum is 820, the same as summing the whole list in one piece.

docker exec jupyter python3 steps/chunks.py

docker exec jupyter python3 -c "d = list(range(1, 11)); print(d[0:5], d[5:10])"

A sum merges by adding. An average does not: the average of the chunk averages is wrong when the chunks differ in size.

Each chunk must send back what the merge needs. For an average that is the sum and the count. The example below shows the wrong and the right way.

# The average of chunks is NOT the average of the chunk averages.
chunk_a = [10, 20, 30, 40]
chunk_b = [100]
wrong = (sum(chunk_a) / len(chunk_a) + sum(chunk_b) / len(chunk_b)) / 2
right = (sum(chunk_a) + sum(chunk_b)) / (len(chunk_a) + len(chunk_b))
print("average of the averages:", wrong)
print("sum and count merged:", right)