Статьи

Параллелизм для чайников

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

Но что такое распараллеливание? Как частота тактовой частоты влияет на среднего программиста? В этой статье мы рассмотрим несколько фактов и заблуждений о теме, от А начинающего «s точки зрения .

На уровне инструкции

Процессоры с более чем одним функциональным блоком (скажем, с большим количеством каналов) могут использовать свои избыточные возможности, выпуская и выполняя более одного выполнения одновременно. Эти возможности прозрачны для программиста, который просто пишет последовательный код, как он всегда делал; эта модель называется суперскалярным процессором.

Тем не менее, если вы когда-либо писали несколько строк сборки, вы знаете, что инструкции машинного уровня похожи на все императивные языки более высокого уровня в том смысле, что они имеют функциональные зависимости между собой:

mov ax, bx #good old 8086 assembly
add ax, 42 #cannot dispatch it to the ALU simultaneously

Конфликты в регистрах и ячейках памяти очень часто встречаются в близких инструкциях, поэтому их нельзя распараллеливать автоматически. Это было бы очень приятно, поскольку все просто запускают последовательные программы и получают линейное ускорение с количеством ядер. Тем не менее, такой выигрыш в производительности ограничен, особенно потому, что он должен выполняться процессором «на лету» : статическая оптимизация на основе компилятора потребует управления сотнями различных двоичных версий (например, версия для каждого числа ядер).

Суть в том, что старая добрая последовательность инструкций по сборке приобретает еще один уровень абстракции, заключающийся в неупорядоченном выполнении и в общем в планировании на разных ядрах.

На уровне потока

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

  • несколько потоков, которые работают над общей памятью и синхронизируются с блокировками или аналогичными системами. Эта модель параллелизма была реализована на протяжении десятилетий для того, чтобы использовать одноядерный процессор, в то время как некоторые потоки блокировали ожидание ввода, и, вероятно, является одной из самых популярных причин сбоя в программах из-за состязаний, голодания, тупиков …
  • несколько процессов , которые отличаются по потокам из-за отсутствия разделяемой памяти, но не очень сильно в реализации. Они общаются с помощью явных сообщений и обычно непрерывно манипулируются во всех разделах времени, написанных после 1980 года
  • актер модель, как один из Erlang, где актеры замещать процессы в качестве базовой единицы расчета (есть целая математическая теория за параллелизмом на основе действующих лиц).

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

На уровне кластера

Когда даже мощная машина этого не делает, репликация приложения в кластере является единственным средством повышения производительности или одновременной поддержки большего количества пользователей . Другими причинами перехода к параллельному использованию нескольких машин являются только их стоимость (N недорогих серверов стоит меньше, чем один сервер в N раз быстрее) и встроенная избыточность этой модели. Например, многие веб-приложения распределяют HTTP-запросы по кластеру серверов, так что в случае сбоя затрагивается только 1 / N пользователей до восстановления.

И все же распараллеливание приложения на нескольких машинах не банально. Для части без состояния, такой как HTTP-сервер, выполняющий код PHP, это просто вопрос копирования файлов и балансировки запросов; для такого компонента, как база данных, написаны целые книги по этой проблеме.

Уберите суть : бросить больше оборудования на проблему — это хорошая идея, но она не всегда решит ее волшебным образом.

Закон Амдаля

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

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

Простая формула для ускорения путем введения N независимых процессоров:

1/((1-P) + P/S)

Если вы примените его просто к времени выполнения, вы получите, что время T на одном модуле выполнения становится:

T' = PT/N + (1-P)T

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

Вывод : статический анализ не годится для параллелизма, как для профилирования; Вы должны выяснить, достаточно ли большая часть вашего кода, чтобы получить значительную производительность, прежде чем распараллеливать ее.

Вывод

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