Parallel and distributed computing

Doing work in order

• Most simple programs are sequential: they do one step, then the next, then the next.
• The computer finishes step 1 before it starts step 2.
• This is easy to understand, but it can be slow for big jobs.

Sequential (one worker):
  task A  ->  task B  ->  task C  ->  task D
  |-------|--------|--------|--------|
  total time = A + B + C + D

Parallel computing

• Parallel computing splits work so several parts run at the same time.
• A modern computer has several processors (also called cores) that can each do work.
• If four workers each take one task, four tasks can finish in about the time of one.

Parallel (four workers at once):
  worker 1: task A
  worker 2: task B
  worker 3: task C
  worker 4: task D
  |--------|
  total time ≈ the longest single task

Speedup

• Speedup asks: how many times faster is the parallel version?
• speedup = (sequential time) / (parallel time).
• Example: a job takes 8 seconds in order, but 2 seconds split up. Speedup = 8 / 2 = 4 times.

Not always N times faster

• More processors does not always mean N times faster.
• Some parts of a job cannot be split — they must happen in order.
• Also, splitting work and joining results back together takes some extra time.

Job = setup (must be in order) + main work (can split)

       setup            main work (split over 4)
      |-----|     |--------------------------------|
                  |--------|  <- this part gets 4x
      The setup part stays the same length.

Distributed computing

• Distributed computing uses many separate computers that cooperate over a network.
• They may sit in different rooms, cities, or countries.
• Examples: the web (many servers), big data jobs split over thousands of machines, and large science projects.

Distributed (computers cooperate over a network):

  [computer 1]   [computer 2]   [computer 3]
        \             |             /
         \            |            /
              shared network / job

  Each computer does part of the work.

Trade-offs

• Good: parallel and distributed systems can be much faster, and can handle huge jobs.
• Harder: the code is more complex; parts must be coordinated; results must be combined.
• Limits: speedup is capped by the parts that cannot be split, and by network delays between computers.

Key words

• Sequential: steps run one after another, in order.
• Parallel: parts run at the same time on several processors.
• Speedup: sequential time divided by parallel time.
• Distributed: many separate computers cooperate over a network.

Common mistakes

• Parallel speed-up only helps work that can be split into independent parts.
• Each extra processor adds less and less speed.

Now you try

• Put the speedup formulas to work as small functions.
• Model a job that is part fixed setup and part splittable work. Press Check answer.