AP Computer Science Principles · Unit 4 lecture · Part 10 of 11 · 6 min

4.3 Distributed computingWhen one computer is not enough

Mr. Thompkins
Some problems are too big for any one computer, not just slow. Too much data to store, or so much calculation it would take years. For those, we team up many separate computers over a network.

Distributed computing is a computational model in which multiple devices are used to run a program. The devices are separate computers connected by a network, and each one does part of the work. Distributed computing allows problems to be solved that could not be solved on a single computer, because of either the processing time or the storage needed. It also lets much larger problems be solved quicker than they could be on one computer.

coordinatorPC 1slice 1PC 2slice 2PC 3slice 3PC 4slice 4PC 5slice 5PC 6slice 6send a slicesend back resultsseparate computers, joined by a networksending and combining still take time
A coordinator sends each computer a slice of the job and collects the results. The sending and combining are a sequential part of their own.
?Wait, how is that different from parallel computing?
Parallel computing splits a program across several processors, often inside one machine. Distributed computing splits it across several separate devices that talk over a network. Distributed systems run in parallel too, but they add the cost of sending data between machines.
ProblemWhy one computer is not enoughHow it is split
Weather and climate forecastsToo many calculations to finish before the forecast is neededEach machine simulates one region of the map
A search engine's index of the WebFar too much data to store on one machineEach machine stores and searches part of the index
Volunteer science projectsYears of computing time on one machineHome computers each analyze one small slice of data
Rendering an animated movieHours per frame, over 100,000 framesEach machine renders different frames
Distributed computing at work. Notice the two reasons: too much processing time, or too much storage.

The same timing ideas apply, with one more cost: sending the data out and collecting the results takes time, and that part doesn't shrink when you add machines. Distributed systems are also a fault tolerance story: if one machine in a thousand fails, its slice can be handed to another machine, a kind of redundancy.

Pause and think
A scientist asks thousands of volunteers to let their home computers analyze slices of telescope data overnight. Is that parallel computing, distributed computing, or both? What new risk does it add?
I thought about it. Show me
It's distributed computing, and the slices run in parallel, so both ideas apply. A new risk: some home computers will turn off, lose their connection or return results late, so the project must send some slices to more than one computer and check the answers.
Compute the speedup of a distributed solution
A lab must classify 1,000,000 images. One computer takes 0.5 seconds per image. With 200 computers, each classifies an equal share, and sending the images out and collecting results takes 300 seconds in total that cannot be shared. (a) How long does one computer take? (b) How long does the distributed solution take? (c) What is the speedup?
  1. (a) 1,000,000 × 0.5 = 500,000 seconds. That is about 5.8 days.
    Why?
    500,000 ÷ 86,400 seconds in a day ≈ 5.79.
  2. (b) Each computer gets 1,000,000 ÷ 200 = 5,000 images, which take 5,000 × 0.5 = 2,500 seconds.
  3. All 200 run at the same time, so the parallel part is 2,500 seconds. Add the 300 seconds of sending and collecting: 2,800 seconds, under 47 minutes.
  4. (c) Speedup = 500,000 ÷ 2,800 ≈ 178.6.
    Why?
    Not 200, because of the 300 seconds that every run must pay. The more computers you add, the more that fixed cost matters.

Answer: (a) 500,000 seconds (about 5.8 days). (b) 2,800 seconds. (c) A speedup of about 179.

Stuck? Get a hint
  1. Start with the one-computer time: images × seconds per image.
  2. Each of the 200 computers does 5,000 images, all at the same time.
  3. Parallel time = 300 + the time for one computer's share.
Check yourself
Which situation is the best use of distributed computing?
  1. AA calculator app adding two numbers
  2. BA student sorting a list of 30 names on a laptop
  3. CThousands of servers each storing and searching part of an index too large for any one computer
  4. DA program that runs one instruction at a time on one processor
Show the answer

C. Distributed computing is for problems too big for one machine, in processing time or storage. The fourth choice describes sequential computing, and the first two are tiny jobs one device handles easily.

  • Distributed computing: several separate devices on a network each run part of a program.
  • It solves problems too large for one computer in processing time or storage, and solves big problems faster.
  • Sending and combining data adds sequential time that limits the speedup.