Parallel and Distributed Computing: Speedup and Its Limits

Intermediate35 min3 exercises45 XP

Prerequisites

Python Lists: Create, Access, Modify, and Loop Through Lists Python For Loops: Iterate Over Anything with Examples Python Functions: Define, Call, and Return Values

0/3 exercises

A big job finishes sooner when several workers share it, but only the parts that can happen at the same time get any faster. Computers follow the same rule, and with a list of task times you can work out exactly how much faster a computer gets with more processors, and where the gains stop.

What are sequential, parallel and distributed computing?

These are three computational models, three ways of organizing the work a program does.

Sequential computing performs operations in order, one at a time. Each step waits for the one before it to finish.

Parallel computing breaks a program into several smaller sequential operations, and performs some of them at the same time. Your laptop's processor has several cores that can each run part of a program, and a graphics card has thousands of small ones for drawing pixels.

Distributed computing uses multiple devices to run a program. A search engine spreads its copy of the web across thousands of servers, and an animation studio sends the frames of a film to a building full of computers, each rendering its own frames.

Think of a class making 60 sandwiches for a picnic. One student making them all is sequential. Four students at one counter, each making their own stack, is parallel. Four students each making sandwiches at home and bringing them to school is distributed: separate places, working at the same time, with the results combined at the end.

To compare the efficiency of solutions, compare how long each one takes to do the same task.

How long do sequential and parallel solutions take?

A sequential solution takes as long as the sum of all of its steps.

A parallel solution has two kinds of work. A parallel solution always consists of a parallel portion, the tasks that can run at the same time, and a sequential portion, the tasks that cannot. A photo-editing app shows both. It must load the image first and save it last, but the filter in the middle can work on four parts of the image at once, one part per processor.

A parallel solution takes as long as its sequential tasks plus the longest of its parallel tasks. The parallel tasks start together, so that part is over when the slowest one finishes.

The speedup of a parallel solution measures the gain: the time the task took sequentially divided by the time it took in parallel. A speedup of 2 means twice as fast.

Sequential time, parallel time and speedup

load_image = 4 # sequential: must happen first

filter_parts = [12, 15, 11, 14] # parallel: one part of the image per processor

save_image = 3 # sequential: must happen last

sequential_time = load_image + sum(filter_parts) + save_image

parallel_time = load_image + max(filter_parts) + save_image

speedup = sequential_time / parallel_time

print(f"Sequential: {load_image} + {sum(filter_parts)} + {save_image} = {sequential_time} seconds")

print(f"Parallel: {load_image} + {max(filter_parts)} + {save_image} = {parallel_time} seconds")

print(f"Speedup: {sequential_time} / {parallel_time} = {speedup:.2f}")

Output

Sequential: 4 + 52 + 3 = 59 seconds
Parallel:   4 + 15 + 3 = 22 seconds
Speedup:    59 / 22 = 2.68

Four processors did not make the app four times faster. The slowest part of the filter (15 seconds) sets the pace of the parallel portion, and loading and saving cannot be shared at all.

Exercise 1: Parallel Running Time

Write Code

Write parallel_time(sequential_tasks, parallel_tasks). Both arguments are lists of task times in seconds. The sequential tasks run one after another, and every parallel task has its own processor. Return the total time for the whole solution. Either list may be empty.

parallel_time([10, 5], [30, 20, 25])  ->  45   (10 + 5 + 30)

def parallel_time(sequential_tasks, parallel_tasks):

# Sequential tasks add up; parallel tasks take as long as the longest

pass

Exercise 2: Calculate the Speedup

Write Code

Write speedup(sequential_tasks, parallel_tasks). Doing every task one after another gives the sequential time; running the parallel tasks at the same time, each on its own processor, gives the parallel time. Return the sequential time divided by the parallel time, rounded to 2 decimal places. parallel_tasks always has at least one task.

speedup([10], [30, 30, 30])  ->  2.5   (100 / 40)

def speedup(sequential_tasks, parallel_tasks):

# Work out both times, then divide

pass

What if there are more tasks than processors?

Often there are more tasks than processors. Then each processor works through its share of the tasks one at a time, and the parallel portion lasts as long as the busiest processor. How the tasks are shared out matters.

Say a computer with two processors has four independent tasks taking 30, 20, 25 and 15 seconds. Here are three ways to split them:

Sharing four tasks between two processors

plans = {

"plan 1": ([30, 20], [25, 15]),

"plan 2": ([30, 15], [20, 25]),

"plan 3": ([30, 25], [20, 15]),

}

for name, (processor_a, processor_b) in plans.items():

time_a = sum(processor_a)

time_b = sum(processor_b)

finish = max(time_a, time_b)

print(f"{name}: A runs {processor_a} = {time_a} s, B runs {processor_b} = {time_b} s, done after {finish} s")

Output

plan 1: A runs [30, 20] = 50 s, B runs [25, 15] = 40 s, done after 50 s
plan 2: A runs [30, 15] = 45 s, B runs [20, 25] = 45 s, done after 45 s
plan 3: A runs [30, 25] = 55 s, B runs [20, 15] = 35 s, done after 55 s

Plan 2 finishes first, at 45 seconds, because it splits the 90 seconds of work evenly. No split can beat half of the total work, and no split can beat the longest single task, since one task cannot be shared. On paper, a good approach is to put the longest tasks on different processors and then even out the totals.

Exercise 3: The Best Split for Two Processors

Write Code

Write best_two_processor_time(tasks). A computer has two processors and a list of independent task times. Each task runs on exactly one processor, and each processor runs its tasks one after another. Return the least possible time for all the tasks to finish.

best_two_processor_time([20, 30, 40, 50])  ->  70   (20 + 50 and 30 + 40)

There is a neat way to try every split, using binary: with n tasks, each whole number from 0 to 2 ** n - 1, written with n bits, describes one split. A 1 in position i sends task i to processor B, and a 0 sends it to processor A.

def best_two_processor_time(tasks):

# Try every split; keep the smallest finishing time

pass

Why do extra processors stop helping?

Suppose a program has 20 seconds of work that must stay sequential and 80 seconds of work that can be split evenly among any number of processors. Watch the speedup as processors are added:

The sequential portion limits the speedup

SEQUENTIAL = 20 # seconds that cannot be shared

PARALLEL_WORK = 80 # seconds that can be split evenly

one_processor = SEQUENTIAL + PARALLEL_WORK

for processors in [1, 2, 4, 8, 16, 100, 1000]:

time = SEQUENTIAL + PARALLEL_WORK / processors

print(f"{processors:>5} processors: {time:6.2f} s speedup {one_processor / time:.2f}")

Output

    1 processors: 100.00 s   speedup 1.00
    2 processors:  60.00 s   speedup 1.67
    4 processors:  40.00 s   speedup 2.50
    8 processors:  30.00 s   speedup 3.33
   16 processors:  25.00 s   speedup 4.00
  100 processors:  20.80 s   speedup 4.81
 1000 processors:  20.08 s   speedup 4.98

The first few processors help a lot. After that, each one saves less, and even 1,000 processors cannot get below 20 seconds or past a speedup of 5. When you increase the use of parallel computing in a solution, its efficiency is still limited by the sequential portion. At some point, adding parallel portions no longer meaningfully increases efficiency.

That does not make parallel computing a small win. Solutions that use parallel computing can scale more effectively than sequential ones. If an app has to filter 10 times as many photos, a sequential solution takes 10 times as long, while a parallel solution can add processors and keep the parallel portion's time from growing as fast.

What can distributed computing do that one computer cannot?

Some problems are too big for any single computer. Distributed computing allows problems to be solved that could not be solved on one computer, because of either the processing time or the storage they need. The full copy of the web that a search engine searches is far too large for one machine's storage. A detailed climate simulation would take one computer years. A volunteer project like Folding@home spreads protein simulations across home computers around the world.

Distributed computing also lets much larger problems be solved faster than one computer could solve them: thousands of servers can each search their own slice of the data at the same moment.

It comes with challenges:

Communication takes time. Devices have to send data and results over a network, and that time is part of the total.

Work has to be split and combined. Someone has to write the program that divides the job and puts the answers back together.

Some tasks have to wait for others, which is the sequential portion again.

More devices means more failures. With thousands of machines, some are always broken, so the system needs the kind of fault tolerance the Internet has.

Check your understanding

A program has four tasks. Tasks P (30 seconds), Q (50 seconds) and R (20 seconds) are independent, and each can run on its own processor at the same time. Task S (10 seconds) can start only after P, Q and R have all finished. What is the least amount of time the program can take?

A60 secondsB50 secondsC100 secondsD110 seconds

A computer has two processors that can work in parallel. It must run four independent tasks that take 20, 30, 40 and 50 seconds. Each task runs on one processor. What is the least amount of time needed to finish all four?

A70 secondsB50 secondsC80 secondsD140 seconds

A task takes 120 seconds when it is run sequentially and 40 seconds when it is run in parallel. What is the speedup of the parallel solution?

A3B80C1/3D160

Which of the following statements about parallel computing are true? Select two answers.

Select 2 answers.

AA parallel solution includes a sequential portion that limits how much faster it can become.BAdding more processors always makes a parallel solution meaningfully faster.CSolutions that use parallel computing can scale more effectively than sequential solutions.DA parallel solution takes as long as the sum of all of its tasks.

Scientists need to analyze 2 petabytes of telescope images, far more data than a single computer can store. Which approach fits this problem best?

ADistributed computing, spreading the images and the work across many computersBSequential computing on the fastest single computer availableCCompressing the images with a lossy algorithm until they fit on one computerDAnalyzing a small sample of the images and ignoring the rest

The list times holds the times, in seconds, of four independent tasks. What is displayed when the code segment runs, and what does it represent?

times ← [15, 40, 25, 10]
total ← 0
longest ← 0
FOR EACH t IN times
{
  total ← total + t
  IF(t > longest)
  {
    longest ← t
  }
}
DISPLAY(total / longest)

A2.25, the speedup when each task runs on its own processorB90, the time to run the tasks sequentiallyC40, the time to run the tasks in parallelD0.44, the speedup when each task runs on its own processor

Run this pseudocode

A program has a sequential portion that takes 30 seconds, and a portion that takes 60 seconds on one processor but can be split evenly among any number of processors. Which of the following statements is true?

AHowever many processors are used, the program takes more than 30 seconds.BWith 60 processors, the program takes 1 second.CWith 2 processors, the program takes 45 seconds.DEach time the number of processors doubles, the total time is cut in half.

Exam topics: 4.3 Parallel and Distributed Computing (CSN-2.A, CSN-2.B)

What are sequential, parallel and distributed computing?

How long do sequential and parallel solutions take?

What if there are more tasks than processors?

Why do extra processors stop helping?

What can distributed computing do that one computer cannot?

Check your understanding

Related Tutorials