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):做完一步,再做下一步,再做下一步。
- 计算机会先完成第 1 步,才开始第 2 步。
- 这很容易理解,但对于大任务来说可能会很慢。
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)计算把工作拆开,让多个部分同时运行。
- 现代计算机有好几个处理器(processor,也叫核心),每一个都能做工作。
- 如果四个工人每人做一个任务,四个任务大约可以在一个任务的时间内完成。
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.
加速比
- 加速比(speedup)问的是:并行版本快了多少倍?
- 加速比 = (顺序所用时间) / (并行所用时间)。
- 例子:一个任务按顺序要 8 秒,拆开后只要 2 秒。加速比 = 8 / 2 = 4 倍。
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.
并不总是快 N 倍
- 处理器更多并不总是意味着快 N 倍。
- 一个任务的有些部分无法拆开 —— 它们必须按顺序进行。
- 而且,拆分工作以及把结果重新合并起来,都要花一些额外的时间。
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)计算使用许多台各自独立的计算机,它们通过网络相互协作。
- 它们可能在不同的房间、城市,甚至不同的国家。
- 例子:万维网(许多服务器)、拆分到成千上万台机器上的大数据任务,以及大型科学项目。
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.
关键词
- 顺序(sequential):步骤一个接一个,按顺序运行。
- 并行(parallel):多个部分在多个处理器上同时运行。
- 加速比(speedup):顺序时间除以并行时间。
- 分布式(distributed):许多台独立的计算机通过网络协作。
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.
现在轮到你
- 把加速比的公式写成几个小函数来用一用。
- 给"一部分是固定准备 + 一部分可拆分"的任务建立模型。按检查答案。
A job has a setup part that must run in order, and a splittable part that workers can share at the same time. Write parallel_time(setup, splittable, workers) that returns the total time: the setup, plus the splittable part divided among the workers. Example: parallel_time(2, 8, 4) → 4.0 (2 + 8/4). · 一个任务有一个必须按顺序运行的 setup(准备)部分,和一个可以由 workers 个工人同时分担的 splittable(可拆分)部分。编写 parallel_time(setup, splittable, workers),返回总时间:准备时间,加上可拆分部分除以工人数。例如:parallel_time(2, 8, 4) → 4.0(2 + 8/4)。
Click Run to see the output here. · 点击“运行”查看此处输出。
Write speedup(sequential, parallel) that returns how many times faster the parallel version is: the sequential time divided by the parallel time. Example: speedup(8, 2) → 4.0. · 编写 speedup(sequential, parallel),返回并行版本快了多少倍:顺序时间除以并行时间。例如:speedup(8, 2) → 4.0。
Click Run to see the output here. · 点击“运行”查看此处输出。
Even with unlimited workers, the setup part still cannot be split. Write max_speedup(setup, splittable) for the best possible speedup: the whole job time divided by the setup time (endless workers shrink the splittable part to almost nothing, leaving only the setup). Example: max_speedup(2, 6) → 4.0 ((2+6)/2). · 即使有无限多的工人,setup(准备)部分仍然无法拆分。编写 max_speedup(setup, splittable),返回最大可能的加速比:整个任务的时间除以准备时间(无限多的工人把可拆分部分缩到几乎为零,只剩下准备部分)。例如:max_speedup(2, 6) → 4.0((2+6)/2)。
Click Run to see the output here. · 点击“运行”查看此处输出。