Parallel and distributed computing
Выполнение задач последовательно
- Большинство простых программ являются последовательными: они выполняют один шаг, затем следующий, затем еще один.
- Компьютер завершает шаг 1 перед тем, как начать шаг 2.
- Это легко понять, но для больших задач это может быть медленно.
Sequential (one worker):
task A -> task B -> task C -> task D
|-------|--------|--------|--------|
total time = A + B + C + D
Параллельные вычисления
- Параллельные вычисления делят работу так, что несколько частей выполняются одновременно.
- В современном компьютере есть несколько процессоров (также называемых ядрами), способных выполнять работу.
- Если четыре работника берут по одной задаче, четыре задачи могут быть завершены примерно за время выполнения одной.
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
Ускорение
- Ускорение спрашивает: во сколько раз параллельная версия быстрее?
- ускорение = (время последовательного выполнения) / (время параллельного выполнения).
- Пример: задача занимает 8 секунд при последовательном выполнении, но 2 секунды при разделении. Ускорение = 8 / 2 = в 4 раза.
Не всегда 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 (computers cooperate over a network):
[computer 1] [computer 2] [computer 3]
\ | /
\ | /
shared network / job
Each computer does part of the work.
Компромиссы
- Плюс: параллельные и распределенные системы могут быть намного быстрее и справляться с огромными объемами задач.
- Сложнее: код становится более сложным; компоненты требуют координации; результаты необходимо объединять.
- Ограничения: ускорение ограничено частями, которые нельзя разделить, а также задержками сети между компьютерами.
Ключевые слова
- Последовательный: шаги выполняются один за другим, строго по порядку.
- Параллельный: части выполняются одновременно на нескольких процессорах.
- Ускорение: время последовательного выполнения, деленное на время параллельного выполнения.
- Распределенный: множество отдельных компьютеров сотрудничают через сеть.
Распространенные ошибки
- Параллельное ускорение полезно только для задач, которые можно разбить на независимые части.
- Каждый дополнительный процессор дает все меньше прибавки в скорости.
Теперь попробуйте сами
- Примените формулы ускорения в виде небольших функций.
- Смоделируйте задачу, состоящую из фиксированной подготовки и разделяемой работы. Нажмите Проверить ответ.
Сложность 3/5 · 200 монет + небольшой бонус за первое завершение сегодня
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, плюс the splittable part divided among the workers. Example: parallel_time(2, 8, 4) → 4.0 (2 + 8/4).
Нажмите Запустить, чтобы увидеть результат здесь.
Сложность 3/5 · 200 монет + небольшой бонус за первое завершение сегодня
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.
Нажмите Запустить, чтобы увидеть результат здесь.
Сложность 3/5 · 200 монет + небольшой бонус за первое завершение сегодня
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).
Нажмите Запустить, чтобы увидеть результат здесь.