1.2. Оценка эффективности параллельной программы

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

1. задачи, решение которых на однопроцессорных компьютерах в принципе возможно, однако требует больших временных затрат (осредненная оценка здесь примерно такова: задачу целесообразно распараллеливать, если время ее решения на современной однопроцессорной машине превышает 5-7 суток); к этой же группе следует отнести задачи, которые необходимо решать многократно на различных наборах исходных данных;

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

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

Решение задач первой группы осуществляется, как правило, на МВС с небольшим количеством процессоров, и здесь все большее распространение получают вычислительные кластеры, собранные на основе традиционных одно- или двухпроцессорных персональных компьютеров. Для решения задач второй группы применяются мощные суперкомпьютеры, входящие в список самых высокопроизводительных вычислительных систем в мире Top-500 (http://www.top500.org), которые состоят из сотен и тысяч процессоров. В данном пособии мы будем ориентироваться на решение задач первой группы.

Каким же образом можно оценить положительный эффект от перехода с последовательной программы к параллельной?

Вернемся к примеру, рассмотренному в предыдущем параграфе. Проведем оценку общего времени вычислений для последовательной и параллельной программы. Пусть производительность одного процессора в рассматриваемых нами системах равна операций в секунду. Будем считать, что время, затрачиваемое процессором на выполнение операций сложения и умножения, одинаково. В последовательной программе выполняется 64 операции умножения и 32 операции сложения. Таким образом, общее время вычислений (без учета времени вывода результатов на экран) составит

.

Несложно убедиться, что для современных процессоров это время оказывается весьма и весьма малым. В самом деле, для приближенной оценки реальной (не пиковой!) производительности современных процессоров можно использовать величину, равную половине его тактовой частоты^*). Так, если в нашем распоряжении имеется процессор класса Pentium 4 с тактовой частотой 3,2 ГГц, то его среднюю производительность можно оценить как GFlops (миллиардов операций с плавающей точкой в секунду). Подставляя данное значение производительности в приведенную выше формулу получим, что с решением нашей последовательной задачи указанный процессор справится за 6010^-9 с или 60 нс.

Теперь оценим время, за которое выполнится наш параллельный алгоритм. В этом случае у нас имеется два типа операций: последовательные и параллельные. Параллельно у нас выполняются первая операция суммирования и две операции умножения (всего 96 операций, выполняющиеся параллельно на 32 процессорах), а последовательно (на нулевом процессоре) выполняются последние операции сложения (всего 31 операция). Таким образом, время работы параллельной программы будет складываться из времени работы ее параллельной и последовательной частей:

.

Таким образом, мы ожидаем, что наша параллельная программа будет работать в

раза быстрее, чем ее последовательный аналог.

Отношение времени выполнения последовательной программы ко времени выполнения параллельной программы напроцессорахназываетсяускорением при использовании процессоров:

.

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

,

где – время выполнения параллельной программы на одном процессоре (в большинстве случаев оно превышаетв силу уже упоминавшегося повышения количества операций в параллельном алгоритме по сравнению с последовательным).

Для рассматриваемого примера получим

Видно, что оценка оказалась более оптимистичной (почти на треть), чем более аккуратная оценка.

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

.

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

Таким образом, в общем случае имеем

.

Это соотношение носит название закона Амдаля.

Из закона Амдаля следует, что для получения больших ускорений доля последовательных операций в параллельной программе должна быть весьма малой. Пусть мы хотим получить ускорение в 50 раз на 100-процессоорной системе. Тогда из закона Амдаля следует, что величина должна быть порядка 0,01, т.е. программа должна быть распараллелена на 99%! Добиться такого уровня распараллеливания в практических задачах бывает достаточно сложно.

Другим важным параметром, с помощью которого оценивается качество параллельной программы, является эффективность использования процессоров:

.

Данный параметр показывает среднюю загруженность процессоров при работе параллельной программы.

Для нашего примера имеем

Таким образом, почти 90 % времени процессоры МВС будут простаивать.

Следует отметить, что оценка (или) является средней. В нашем примере нулевой процессор будет загружен на 100 %, поскольку он работает постоянно, в то время как время работы остальных процессоров составит порядка 8,8 % этого времени.

Теперь обратимся к другому, возможно, самому важному вопросу, на который необходимо обращать внимание при написании параллельной программы – на организацию обмена данными. Во всех предыдущих оценках мы пренебрегали временем передачи данных. Тем не менее, оно может оказаться весьма значительным. Так, если мы запустим параллельную программу нашего примера, скажем, наAlpha-кластере УГАТУ, то мы не только не получим ожидаемого ускорения, но время работы параллельной программы окажется примерно в 30 000 раз больше, чем последовательного аналога! Причиной этого будут временные задержки при передаче данных.

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

Так, уже упоминавшийся Alpha-кластер УГАТУ имеет топологию “звезда”, коммуникационную среду Fast Ethernet 100 Мбит/с и коммутатор со временем латентности равным (100-300)10^-6 с. В рассматриваемой нами простейшей параллельной программе у нас имеется 31 передача целочисленного значения от каждого ненулевого процессора нулевому. Соответственно, время собственно передачи данных (без учета времени подготовки сообщения и передачи служебной информации) составит

нс.

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

Между двумя последовательными передачами коммутатор дает случайную задержку, называемую временем латентности:

мкс.

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

.

Для нашего примера , поскольку. Всего осуществляетсяпередача, поэтому суммарное время, затрачиваемое на коммуникации в параллельной программе, равно

мкс = с.

Общее время выполнения параллельной программы складывается из времени расчетови времени коммуникаций:

.

Производительность процессора Alpha-кластера оценивается как GFlops, поэтому время выполнения последовательной программы будет оцениваться величиной с. Следовательно, в рассматриваемом примере время расчетов, поэтому. Обратим внимание на то, что время работы всей последовательной программы оказывается сопоставимо со временем передачи одного числа. Таким образом, для ускорения имеем

,

т.е. получаем уже упоминавшейся ранее результат.

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

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

1. объем вычислений, выполняемых на отдельном процессоре МВС, должен существенно превышать время, затрачиваемое на передачу данных с этого процессора; для программы в целом должно выполняться условие

;

2. количество передач данных должно быть сведено к минимуму;

3. доля последовательного кода в параллельной программе должна быть как можно меньше;

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