Параллельное программирование может быть не столь пугающим

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

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

В теории, удвоение количества ядер вдвое повышает эффективность чипа, но распараллеливание вычислений, так чтобы они эффективно выполнялись на обоих ядрах, является не легкой задачей. С другой стороны, как говорит трио ученых из Массачусетского технологического института, Техниона, Израиль, и Microsoft Research, это не так сложно, как опасались.

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

Тем не менее, неблокируемые алгоритмы не соответствуют теоретическим предсказаниям: они обещают только то, что, по крайней мере, одно ядро повысит свою производительность на данной вычислительной задаче в фиксированный отрезок времени. Но если они (алгоритмы) не превысят этого обещания, то вся дополнительная вычислительная мощность, которую предоставляют несколько ядер, растратится попусту.

В последние годы компьютерные теоретики продемонстрировали хитроумные альтернативы, называемые алгоритмы без ожидания (wait-free), которые гарантируют, что все ядра будут добиваться прогресса на фиксированном отрезке времени. Но их получение из последовательного кода чрезвычайно сложно, и коммерческие разработчики в значительной степени пренебрегали ими.

В статье, представленной на Ежегодном симпозиуме ACM по теории вычислений, Нир Шавит (Nir Shavit), профессор в отделе электротехники и компьютерных наук из МТИ, его бывший студент Дэн Алистер (Dan Alistarh), который теперь в Microsoft Research, и Керен Цензор-Гиллел (Keren Censor-Hillel) из Техниона продемонстрировали новый аналитический метод, предположив, что в широком диапазоне реальных случаев неблокируемые алгоритмы фактически показывают производительность алгоритмов без ожидания.

«На практике программирование будет выполняться, как если бы все было без ожидания, - говорит проф. Шавит. - Статья требует обладания некоторой долей интуиции о том, как чип планирует работу, так что программисты встретили ее доброжелательно».

Ключевым моментом исследователей было то, что производительность чипа в целом можно охарактеризовать проще, чем производительность отдельных ядер. Это потому, что распределение различных потоков, или участков кода, исполняемых параллельно, симметрично. «Не имеет значения, находится ли поток 1 в состоянии A, а поток 2 в состоянии B, или если вы просто поменяете состояния местами, - говорит Алистер. - Мы отметили лишь то, что объединив симметричные состояния, вы можете многое упростить».

В реальном чипе распределение потоков по ядрам является «сложным взаимодействием задержек и политики планирования», отмечает Алистер. На практике, однако, решения, достигнутые путем этого сложного взаимодействия, в конечном итоге, выглядят как будто бы случайными. Поэтому исследователи смоделировали планирование потоков как процесс, который содержит элемент случайнности: в любое время есть некоторая вероятность того, что новый поток будет начат в любом ядре.

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

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

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

Ready, set, buy! Посібник для початківців - як придбати Copilot для Microsoft 365