Параллельные алгоритмы работают лучше, чем от них ожидают

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

С другой стороны, это и не так сложно, как принято полагать — утверждают специалисты в области информатики из MIT, Microsoft Research и Technion (Израиль).

В коммерческом ПО для многоядерных чипов часто применяются так называемые алгоритмы без блокировок, «lock free», которые относительно просто генерируются на основе стандартного последовательного кода (во многих случаях это делается автоматически).

Но такие параллельные алгоритмы не дают гарантий высокой эффективности. Они обещают, что, за фиксированный промежуток времени, по меньшей мере одно ядро будет продвигаться в решении задачи. Если же это условие не выполняется, алгоритмы lock free высасывают все вычислительные ресурсы, которые могут предоставить дополнительные ядра.

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

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

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

Ключевая идея доклада состоит в том, что производительность для чипа в целом можно охарактеризовать проще, чем для индивидуальных ядер. Причина этого — в симметричности распределения различных потоков, исполняемых параллельно.

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

В этом случае, моделирование давало для многих «беззамочных» алгоритмов те же гарантии производительности, что и для wait free. Такой благоприятный прогноз оставался в силе, даже если принималось, что вероятность получения потока менялась от ядра к ядру.

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

Стратегія охолодження ЦОД для епохи AI