Limits of Parallel Processing

Four lessons counted the items of distribution one by one: the records moved in the shuffle, the coordination overhead item added per job, the values a file layout makes you read. All three could be reduced and each held two defensible decisions. This lesson measures the serial fraction, which cannot be reduced.

Not every step of a job is divisible. The schema of the source is read once, the job plan is derived once, the result table is built and written once; these steps run once however many units are added, and do not shorten. The measure of the lesson is the serial fraction — the ratio of the indivisible part of the job to the whole job — and the second number derived from it is the speedup ceiling: the highest speedup, in times, reachable even as the number of units goes to infinity.

• AS25. The report chain is built from the items the previous four lessons counted and is fiction: the row count is 3,199, the header value is 150 (from the best row group size of the fourth lesson), the coordination overhead item is 100 (from the four-stage, eight-partition chain of the third lesson), and the records moved in the shuffle are 40 (from the second lesson). It is a model.
• AS26. The unit of work is a touch; raw milliseconds are not written and the number measured is the speedup in times.
• AS27. Speedup is computed from the serial fraction $s$ and the number of units $p$ as $1 / (s + (1 - s) / p)$; as $p$ goes to infinity the ceiling becomes $1 / s$.
• AS28. The divisible steps are assumed spread equally among the units. Partition imbalance was measured in the Scale and Performance topic of the Data Analysis with Python course and is ignored here; this assumption gives the ceiling optimistically.
• AS29. Whether the indivisible items grow with job size is a decision, tested with two assumptions: a fixed series, and a series that grows by the formulas of the third and fourth lessons.
• AS30. The number of units needed to reach 90% of the ceiling is found by scanning multiples of two.

The Serial Fraction of the Job

# ceiling.py — the serial fraction of the job and the speedup ceiling. MODEL: the report
# chain is split into steps, each step is given a number of touches and whether it is divisible;
# the measure is the speedup in times, not raw time.
N = 3199
STEPS = (("reading the source schema", 150, "no"),
         ("deriving the job plan and distributing tasks", 100, "no"),
         ("reading and filtering the rows", N, "yes"),
         ("local reduction", N, "yes"),
         ("records moved in the shuffle", 40, "yes"),
         ("final reduction (5 keys)", 5, "yes"),
         ("building and writing the single report table", 60, "no"))

print(f"{'step':<46}{'touches':>9}{'divisible':>10}")
for name, d, b in STEPS:
    print(f"{name:<46}{d:>9}{b:>10}")
TOTAL = sum(d for _, d, _ in STEPS)
SERIAL = sum(d for _, d, b in STEPS if b == "no")
S = SERIAL / TOTAL
print(f"total touches {TOTAL}, indivisible {SERIAL}, serial fraction "
      f"{100 * S:.2f} percent, speedup ceiling {1 / S:.2f} times")

step                                            touches divisible
reading the source schema                           150        no
deriving the job plan and distributing tasks        100        no
reading and filtering the rows                     3199       yes
local reduction                                    3199       yes
records moved in the shuffle                         40       yes
final reduction (5 keys)                              5       yes
building and writing the single report table         60        no
total touches 6753, indivisible 310, serial fraction 4.59 percent, speedup ceiling 21.78 times

The serial fraction is not a property of code but a list of steps. The three steps total 310 touches, 4.59% of the job of 6,753 touches. Each has its own reason for not being divided: the schema sits in a single place of the source, the job plan has to see all the partitions, the result table has to be a single output.

4.59% looks like a small number. Its counterpart is 21.78 times: however many units you divide this job into, the speedup cannot pass it. A serial fraction of 4.59% cuts off one twenty-second of the speedup from the start.

Speedup Ceiling

# speedup.py — the same job is run with different serial fractions and an increasing number of
# units. speedup(p) = 1 / (s + (1 - s) / p); the ceiling is 1 / s as p goes to infinity.
UNITS = (1, 2, 4, 8, 16, 64, 256, 1024, 4096)


def speedup(s, p):
    return 1.0 / (s + (1.0 - s) / p)


def units_for_90(s):
    p = 1
    while speedup(s, p) < 0.9 / s and p < 10 ** 7:
        p *= 2
    return p


SHARES = (0.02, S, 0.10, 0.30)
print("units".ljust(8) + "".join(f"s={s:.4f}".rjust(10) for s in SHARES))
for p in UNITS:
    print(f"{p:<8}" + "".join(f"{speedup(s, p):>10.2f}" for s in SHARES))
print(f"{'ceiling':<8}" + "".join(f"{1 / s:>10.2f}" for s in SHARES))
print(f"{'p90':<8}" + "".join(f"{units_for_90(s):>10}" for s in SHARES))

units     s=0.0200  s=0.0459  s=0.1000  s=0.3000
1             1.00      1.00      1.00      1.00
2             1.96      1.91      1.82      1.54
4             3.77      3.52      3.08      2.11
8             7.02      6.05      4.71      2.58
16           12.31      9.48      6.40      2.91
64           28.32     16.44      8.77      3.22
256          41.97     20.15      9.66      3.30
1024         47.72     21.35      9.91      3.33
4096         49.41     21.67      9.98      3.33
ceiling      50.00     21.78     10.00      3.33
p90            512       256       128        32

The right column is the most instructive. When the serial fraction is 30%, 4,096 units give 3.33 times: four thousand ninety-six units, three and a half times. With two units the same job speeds up 1.54 times; the last 4,094 units add only 1.79 times. A serial fraction of 30% means 70% of the job is divisible, which sounds like a job that can be distributed.

The left column shows the same thing from the other side. When the serial fraction is 2% the ceiling is 50 times and 4,096 units give 49.41 times. The difference between 2% and 30% is not fifteen times, it is a fifteen-times difference in the ceiling: 50 against 3.33. The serial fraction rises linearly; the ceiling falls in inverse proportion.

The last row gives the practical side. The number of units needed to reach 90% of the ceiling grows as the serial fraction gets smaller: at 30% 32 units are enough, at 2% 512 are needed. A small serial fraction gives a high ceiling, but it asks for more units to reach it.

The Added Unit and the Ceiling Itself

# limit.py — as the ceiling is approached the times gained by an added unit melt away; and the
# serial fraction changes with job size because the divisible items grow and the
# indivisible items do not.
print(f"serial fraction {100 * S:.2f} percent; ceiling {1 / S:.2f} times")
print(f"{'units':<8}{'speedup':>10}{'rise over previous':>23}"
      f"{'per added unit':>22}{'distance to ceiling':>21}")
prev_p, prev_h = 1, 1.0
for p in UNITS[1:]:
    h = speedup(S, p)
    print(f"{p:<8}{h:>10.2f}{h - prev_h:>23.3f}"
          f"{(h - prev_h) / (p - prev_p):>22.5f}{1 / S - h:>21.2f}")
    prev_p, prev_h = p, h

import math
FIXED = sum(d for _, d, b in STEPS if b == "no")


def growing(n):
    """The coordination overhead item of lesson 03 and the header value of lesson 04 grow with job size."""
    partition = max(8, math.ceil(n / 400000))
    return 4 * partition * 3 + 4 + 3 * math.ceil(n / 64) + 60


print(f"{'job size':<12}{'divisible':>13}{'fixed serial':>13}{'fixed ceiling':>15}"
      f"{'growing serial':>16}{'growing ceiling':>17}{'p90':>9}")
for n in (3199, 31990, 319900, 3199000, 31990000):
    div = 2 * n + 45
    s1, s2 = FIXED / (div + FIXED), growing(n) / (div + growing(n))
    print(f"{n:<12}{div:>13}{FIXED:>13}{1 / s1:>15.1f}{growing(n):>16}"
          f"{1 / s2:>17.2f}{units_for_90(s2):>9}")
LARGEST = 31990000
saturation = (2 * LARGEST + 45 + growing(LARGEST)) / growing(LARGEST)
print(f"the fixed-serial assumption makes the ceiling grow in direct proportion to job size; under the "
      f"growing-serial assumption the ceiling saturates at {saturation:.2f} times and 90 percent of it "
      f"is reached at 512 units")

serial fraction 4.59 percent; ceiling 21.78 times
units      speedup     rise over previous        per added unit  distance to ceiling
2             1.91                  0.912               0.91222                19.87
4             3.52                  1.604               0.80180                18.27
8             6.05                  2.539               0.63466                15.73
16            9.48                  3.421               0.42762                12.31
64           16.44                  6.968               0.14517                 5.34
256          20.15                  3.704               0.01929                 1.64
1024         21.35                  1.202               0.00157                 0.43
4096         21.67                  0.323               0.00011                 0.11
job size        divisible fixed serial  fixed ceiling  growing serial  growing ceiling      p90
3199                 6443          310           21.8             310            21.78      256
31990               64025          310          207.5            1660            39.57      512
319900             639845          310         2065.0           15157            43.21      512
3199000           6398045          310        20639.9          150115            43.62      512
31990000         63980045          310       206388.2         1500556            43.64      512
the fixed-serial assumption makes the ceiling grow in direct proportion to job size; under the growing-serial assumption the ceiling saturates at 43.64 times and 90 percent of it is reached at 512 units

The first table gives what the added unit gains. The second unit adds 0.91 times; each unit in the 4,096th unit group adds 0.00011 times. After 256 units each added unit gains less than two thousandths and the distance to the ceiling has fallen to 1.64 times. What follows is not a measurable gain, only an asymptotic approach to the ceiling.

The second table is the hidden decision of the lesson. “The bigger the dataset, the more distribution gains” is true, but how much it gains depends on an assumption. If the indivisible items are held fixed, the ceiling grows in direct proportion to job size and rises to 206,388 times at 31,990,000 rows. Yet the third lesson measured that the coordination overhead item grows with the number of partitions and the fourth that the row group header grows with the number of row groups. When these two formulas are taken into account the ceiling saturates at 43.64 times and enlarging the job size no longer moves it.

The ratio between the two numbers is 4,729 times, and both come from the same model, dataset and chain. The only difference is whether the indivisible items are assumed to grow with job size, an assumption no speedup report writes spontaneously.

When distribution is unnecessary can be read from here too. In the 3,199 rows of the fictional dataset the ceiling appears as 21.78 times, but the third lesson counted that at this job size only 61.5 rows fall to one coordination overhead item and that the target of 10,000 rows per item is met at 520,000 rows; the first lesson wrote that with the chosen decision the dataset would stop fitting on a single machine at 22,525,682 rows. The three numbers point in the same direction: this dataset is not distributed. A high ceiling does not call for distribution; what calls for it is the job itself exceeding a single machine.

Summary

• The serial fraction is not a property of code but a list of steps: reading the schema, the job plan, and writing the single report table total 310 touches, 4.59% of the job of 6,753 touches.
• A serial fraction of 4.59% pins the speedup ceiling to 21.78 times; at 2% the ceiling is 50, at 30% it is 3.33 times, and even 4,096 units cannot pass the ceiling.
• Reaching the ceiling is not free either: 90% of it takes 32 units at a 30% serial fraction and 512 units at a 2% serial fraction.
• The gain of the added unit melts away: the second unit adds 0.91 times, after 256 units each unit adds less than two thousandths, and the distance to the ceiling falls to 1.64 times.
• The behavior of the ceiling with job size is an assumption decision: if the indivisible items are held fixed the ceiling rises to 206,388 times, if they grow with the formulas of the third and fourth lessons it saturates at 43.64 times; there are 4,729 times between the two numbers.
• A high ceiling does not call for distribution: in the 3,199-row dataset, although the ceiling is 21.78 times, the item threshold is 520,000 and the volume threshold is 22,525,682 rows.

Course Wrap-Up

In each of the eighteen lessons two numbers stood side by side, what was in the data and what reached the reader, each read from its own lesson.

Lesson	Number in the source	Number read back	Difference
Chart 01 Chart Type Selection	east - north 4.463 m³	2.500 m³ from the area channel	-1.963 m³
Chart 02 Distribution Visualization	2 peaks, outlier 45.47 m³	0 peaks in the box summary	2 peaks lost
Chart 03 Categorical Visualization	39 pairs that must be told apart	35 pairs in the stacked chart	4 pairs, error 47.2%
Chart 04 Relationship Visualization	1,101 points	309 filled cells	792 points, 71.9%
Chart 05 Time Series Visualization	trend -0.140 m³/period	-0.1347 m³/period	0.0053, cost 12 periods
Chart 06 Geographic Visualization	average 19.713 m³	18.484 m³ weighted by area	-1.228 m³
Chart 07 Misleading Visuals	north 20.210 m³	8.019 m³ on the truncated axis	-12.191 m³
Chart 08 Accessible Charts	8 series	4 series when tone is not read	4 series, 0 with redundancy
Reporting 01 Dashboard Design	12 criteria	9 criteria in the layout by decision	3 criteria left out
Reporting 02 Key Performance Indicators	coverage 60.948	up to 93.766 by six routes	32.818 points
Reporting 03 Business Intelligence Tools	final value 63.055	36.042 in the pre-aggregated one	27.013 points
Reporting 04 Building Narrative with Data	16 premises	2-4 inferences when one step is missing	11 wrongly assumed, 9 in favor
Reporting 05 Report Reproducibility	59 items to pin	10 of 11 items move it	36.042 ↔ 100.000
Scale 01 Big Data Concept	286.0 bytes per row	threshold 22,525,682 rows	7,508,560 ↔ 240,273,951
Scale 02 Map–Reduce Model	3,199 records	40 records in the shuffle	79.97 times
Scale 03 Distributed Analysis Engines	8 operations	4 stages, 100 items	61.5 rows/item
Scale 04 Columnar Storage Formats	22,393 values	1,174 values in the best layout	19.07 times
Scale 05 Limits of Parallel Processing	6,753 touches	ceiling 21.78 times	43.64 ↔ 206,388

The third column is the rule of the course: a display is as correct as the number the reader can read back from it; a display that cannot be read back counts as unreported. In the first eight rows what is read back is an m³ value, a number of peaks, or a number of series, and the difference column gives what the channel lost. In the middle five rows the reader is a decision maker, and what is read back is a decision, not a single number: how many criteria are seen, where a criterion can be moved without moving what it measures, whether the same report can be produced a second time.

In the last five rows the number read back comes not from a display but from the scale: the records moved, the coordination overhead item, the values read, the speedup in times. The rule does not change. The divisibility of a computation is known only as far as it is counted, and the item that is not counted turns up not inside the computation but inside the bill.

The six courses of the Data Analytics curriculum read the same axis in six different places.

Course	Lessons	Measure axis	Unit
Introduction to Data Analytics	9	the number moves at the moment of definition	definition
Analysis with Spreadsheets	11	where the decision sits	recoverability of the decision
Data Collection and Preparation	17	the row count changes on the way	rows in and out
Data Analysis with Python	22	what the abstraction gains and hides	gain and hidden decision
Statistical Analysis and Exploratory Data Analysis	13	the margin of variation of the number	share
Visualization, Reporting and Analysis at Scale	18	the number the channel makes you read back	read-back error
Total	90

Ninety lessons established a single rule six times: if the decision that produced a number is not written next to it, that number is not a finding but a choice. It was tested in a different place in each course — in the definition, the cell of the spreadsheet, the preparation step, the default of the call, the margin of variation, and the encoding channel — and each time it was paid in the same form: from the same data, to the same question, two defensible decisions gave two numbers, both printed side by side. The 4.463 m³ difference between the east and the north stood in all of these ninety lessons and said nothing by itself anywhere.

Ninety lessons measured every step from data to decision and showed at each that the decision moves the number. But all of these decisions were made by a human: which rows will be counted, which threshold will be chosen, which channel will be used, by which key the job will be divided. Which number a procedure that learns the decision from the data moves, and where the decisions of that procedure itself stand, was never asked. The next curriculum, Machine Learning and Data Science, opens with this question.