Зачем нужны параллельные алгоритмы

Урок объясняет, почему параллельные вычисления стали не роскошью, а необходимостью.

Параллельный алгоритм — алгоритм, спроектированный так, чтобы несколько вычислителей одновременно выполняли разные части одной задачи и тем сокращали общее время.

Бесплатный обед закончился

Тридцать лет программисты получали ускорение бесплатно: новый процессор выходил с большей тактовой частотой, и та же программа просто начинала работать быстрее. Этот период закончился около 2005 года. Частота упёрлась в стену примерно на 3-4 ГГц, и дальше её не поднять без перегрева: рассеиваемая мощность растёт примерно как куб частоты. Дальнейший прогресс пошёл вширь, а не ввысь — производители стали добавлять ядра. Современный серверный процессор имеет десятки ядер, видеокарта — тысячи. Но вот ключевой факт: одно ядро у вас почти не стало быстрее за пятнадцать лет. Чтобы программа ускорилась, она обязана сама уметь раскладывать работу на много ядер. Это и есть предмет курса.

Три силы, которые делают параллелизм обязательным

Предел частоты. Физика запрещает бесконечно разгонять одно ядро. Энергия, которую транзисторы выделяют в тепло, растёт быстрее, чем выгода от частоты. Поэтому индустрия выбрала много медленных ядер вместо одного быстрого.

Масштаб данных. Объёмы выросли на порядки: логи, геномы, изображения, обучающие выборки для нейросетей. Последовательный проход по терабайту, даже если он линеен, занимает часы. Разрезав данные на сотни кусков и обработав их одновременно, мы превращаем часы в минуты.

GPU и специализированные ускорители. Графический процессор — это машина для массового параллелизма: тысячи простых ядер, выполняющих одну операцию над разными данными. Обучение современных моделей без GPU немыслимо, а GPU невозможно использовать, не мысля параллельными алгоритмами.

Маленькая иллюстрация выигрыша

Пусть нужно посчитать сумму миллиона чисел. Последовательно это миллион сложений. Если разрезать массив на 8 частей, посчитать 8 частичных сумм одновременно и сложить их — каждое ядро делает лишь восьмую часть работы. Ниже мы эмулируем эту идею последовательно (в браузере настоящих потоков нет), но логика разбиения ровно та, что выполнялась бы на 8 ядрах.

data = list(range(1, 1_000_001))  # 1..1000000
parts = 8
chunk = len(data) // parts

# каждое "ядро" суммирует свой кусок (здесь — по очереди)
partial = []
for p in range(parts):
    start = p * chunk
    end = start + chunk
    partial.append(sum(data[start:end]))

print("частичные суммы:", partial)
print("итог:", sum(partial))
print("проверка:", sum(data))

Вывод:

частичные суммы: [7812562500, 23437562500, 39062562500, 54687562500, 70312562500, 85937562500, 101562562500, 117187562500]
итог: 500000500000
проверка: 500000500000

На реальной машине восемь частичных сумм считались бы одновременно, и общее время сократилось бы почти в восемь раз. Финальное сложение восьми чисел ничтожно. Это базовый рисунок почти любого параллельного алгоритма: разрежь, посчитай независимо, собери.

Важно понимать, что не каждая задача поддаётся этому рисунку. Сложить независимые числа легко, потому что порядок сложений не влияет на результат и куски не зависят друг от друга. Но если бы каждый элемент зависел от предыдущего (например, мы накапливали бегущую сумму и хотели именно последовательность промежуточных итогов), наивное разрезание дало бы неверный ответ. Поэтому первый вопрос при проектировании параллельного алгоритма — не «как разрезать?», а «что здесь вообще независимо?». Именно поиск независимости, а не механическое деление, отличает удачное распараллеливание от провального.

Ещё одна причина учиться этому именно сейчас: параллелизм перестал быть уделом суперкомпьютеров. Восемь и больше ядер есть в обычном ноутбуке, видеокарта с тысячами ядер стоит на каждом игровом ПК, а облако даёт сотни ядер по запросу за копейки. Узким местом стало не железо, а умение программиста им воспользоваться. Код, написанный последовательно, использует один процент мощности современной машины — остальное простаивает.

Как работает под капотом

Ускорение возникает не от магии, а от того, что несколько физических устройств работают в одну единицу времени. Если у задачи есть участки, которые обязаны выполняться по порядку (например, результат шага B зависит от шага A), эти участки распараллелить нельзя — и именно они ограничивают выигрыш. Поэтому проектирование параллельного алгоритма — это в первую очередь поиск независимых кусков работы.

Частые ошибки

Думать, что «параллельно» автоматически значит «быстрее». Если задача крошечная, накладные расходы на координацию съедят весь выигрыш.
Путать параллелизм с тем, что компьютер «и так делает много дел сразу». Операционная система переключает процессы, но это не ускоряет ваш конкретный счёт.
Ожидать ускорения в N раз на N ядрах. Так почти не бывает — почему, разберём в уроке про закон Амдала.

Итоги

Рост частоты остановился по физическим причинам; прогресс идёт за счёт числа ядер.
Масштаб данных и GPU делают параллельные алгоритмы обязательным навыком.
Идея почти любого параллельного алгоритма: разрезать на независимые части, посчитать, собрать.