Оценка эффективности параллелизации

Скачать статью Predicting and Measuring Parallel Performance [Eng., PDF 310KB]

Аннотация

Создание параллельных версий позволяет приложениям существенно повысить скорость обработки данных. Успех параллелизации обычно определяется ускорением работы параллельной программы по отношению к ее последовательной версии. При этом бывает полезно провести сравнение полученного результата с неким верхним пределом. Это можно проделать с помощью законов Амдала (Amdahl’s Law) и Густафсона (Gustafson’s Law).

Вводные данные

Меньшее время выполнения программы позволяет обрабатывать большие наборы данных (например, большее количество записей, пикселей, или использовать физические модели большего масштаба) за приемлемый промежуток времени. Одним из показателей повышения такого рода производительности является ускорение (speedup).

Вообще говоря, ускорение – это отношение времени последовательного к времени параллельного выполнения программы. Например, если последовательное приложение выполняется за 6720 секунд, а соответствующее параллельное приложение за 126.7 секунд (при использовании 64 потоков и ядер), ускорение составляет 53x (6720/126.7 = 53.038).

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

Близко по смыслу к показателю ускорения стоит метрика эффективности (efficiency). Если ускорение показывает, насколько параллельное выполнение быстрее последовательного, то эффективность показывает, насколько хорошо программа использует вычислительные ресурсы системы. Для расчета эффективности параллельного приложения нужно взять наблюдаемое ускорение и разделить на количество используемых ядер. Это число выражается в процентах. Например, 53-кратное ускорение на 64 ядрах даёт эффективность в 82.8% (53/64 = 0.828). Это означает, что в среднем в процессе выполнения каждое ядро простаивает около 17% времени.

Закон Амдала

Перед началом проекта по параллелизации разработчику может быть интересно оценить ускорение, которое он теоретически сможет достичь. Если процент последовательного кода, который можно исполнять параллельно, известен (или оценен), то он может использовать закон Амдала для расчёта верхней границы ускорения приложения без необходимости предварительного написания какого-либо параллельного кода. В литературе присутствуют несколько вариантов формулы закона Амдала. В каждой из них используется процент (предполагаемого) времени параллельного выполнения (pctPar), последовательного выполнения (1 – pctPar), и количество потоков/ядер (p). Ниже приведена простая формулировка закона Амдала для расчёта ускорения параллельного приложения на p ядрах:

Данная формула представляет собой время последовательного выполнения, нормализованное до 1 и деленное на расчётное время параллельного выполнения с использованием процента нормализованного времени последовательного выполнения. Время параллельного выполнения рассчитывается как процент последовательного выполнения (1 – pctPar) и процент параллельного выполнения, деленные на количество используемых ядер (pctPar/p). Например, если 95% времени последовательного выполнения может выполняться параллельно на 8 ядрах, то оценочное ускорение, согласно закону Амдала, составит около 6x (1 / (0.05 + 0.95/8) = 5.925).

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

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

Закон Густафсона

Если параллельное приложение при использовании восьми ядер способно обработать набор данных объёмом в восемь раз больше прежнего, увеличивается ли при этом время работы последовательной части? Даже если и увеличивается, то непропорционально расту объёма данных. Реальная практика показывает, что время последовательного выполнения остаётся практически постоянным.

Закон Густафсона, также известный как масштабируемое ускорение (scaled speedup), берёт в расчёт рост объёма данных в пропорции к росту количества ядер и рассчитывает (верхнюю границу) ускорения работы приложения, как если бы больший объём данных мог быть обработан последовательно. Формула масштабируемого ускорения выглядит так:

Как и в формуле закона Амдала, p означает количество ядер. Для упрощения записи, s является процентом времени последовательного выполнения в параллельном приложении для указанного размера набора данных. Например, если 1% времени работы на 32 ядрах выполняется последовательно, то ускорение выполнения такого приложения на том же наборе данных по сравнению с выполнением на одном ядре с одним потоком (предполагается, что это возможно) равно:

Посмотрим, что бы нам дал при таких допущениях закон Амдала. Если процент последовательного выполнения равен 1%, то по закону Амдала - 1/(0.01 + (0.99/32)) = 24.43x. Однако это ложный результат, так как данный процент последовательного времени оценён для выполнения на 32 ядрах. Из данного примера не видно, какой процент последовательного выполнения может быть для большего или меньшего количества ядер. Если код является идеально масштабируемым и объём данных увеличивается соответственно количеству ядер, то этот процент может остаться прежним, а закон Амдала будет предсказывать ускорение одноядерной задачи (фиксированного размера) на 32 ядрах.

С другой стороны, если общее время параллельного выполнения известно для 32 ядер, то время полностью последовательного выполнения можно рассчитать, и ускорение этой задачи фиксированного размера (подразумевая, что она может быть рассчитана на одном ядре) можно предсказать с помощью закона Амдала для 32 ядер. Предположив, что общее время выполнения параллельного приложения составляет 1040 секунд на 32 ядрах, тогда 1% этого времени будет последовательным, т.е. 10.4 секунды. Умножая количество секунд (1029.6) параллельного выполнения на 32 ядра, получаем, что общий объём работы, выполняемый приложением, занимает 1029.6*32+10.4 = 32957.6 секунд. Непараллельное время (10.4 секунды) составляет 0.032% общего времени работы. Используя этот результат, закон Амдала даёт нам ускорение в 1/(0.00032 + (0.99968/32)) = 31.686x.

Поскольку для использования закон Густафсона необходимо знать процент последовательного времени при параллельном выполнении, то эта формула обычно используется для расчёта ускорения масштабируемого параллельного выполнения (при увеличении объёмов данных соответственно количеству ядер), по отношению к последовательному выполнению задачи того же размера. Из приведённых выше примеров следует, что строгое использование данных о выполнении программы в формуле закона Амдала даёт гораздо более пессимистическую оценку, чем формула масштабируемого ускорения.

Рекомендации

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

При указании значения ускорения нужно использовать коэффициент умножения. Раньше ускорение выражалось в процентах. В нашем случае использование процентов может привести к путанице. Например, если говорится, что параллельный код на 200% быстрее последовательного, означает ли это, что он работает за половину времени последовательной версии, или за одну треть? Будет ли ускорение в 105% почти равным последовательной работе или в два раза быстрее? Является ли базовое последовательное время ускорением в 0% или в 100%? С другой стороны, если параллельное приложение имеет ускорение в 2x, то ясно, что на работу ушла половина времени (то есть параллельная версия смогла отработать дважды за то время, пока последовательный код работает один раз).

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

Указания по применению

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

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

Дополнительные ресурсы

Parallel Programming Community

John L. Gustafson. "Reevaluating Amdahl's Law." Communications of the ACM, Vol. 31, pp. 532-533, 1988.

Michael J. Quinn. Parallel Programming in C with MPI and OpenMP. McGraw-Hill, 2004.

Для получения подробной информации о возможностях оптимизации компилятора обратитесь к нашему Уведомлению об оптимизации.