Использование высокопроизводительных технологий

Использование высокопроизводительных технологий.

В данном документе мы рассмотрим вопросы связанные с разработкой высокоэффективных приложений для современных вычислительных систем. Целью исследования является демонстрация зависимости производительности вычислительной системы на реальных приложениях от качества используемого программного обеспечения, и какие проблемы приходится преоделевать при разработке эффективных программ. В качестве примера мы рассмотрим элементарную задачу перемножения двух квадратных матриц. С одной стороны, эта задача чрезвычайно проста, а, с другой стороны, она наглядно демонстрирует, что разработка высокоэффективных приложений представляет собой весьма не тривиальную задачу. Кроме того, для этой задачи достаточно просто ввести удобный параметр для отслеживания производительности компьютера на конкретном приложении. Мы будем фиксировать производительность систем в Мегафлопсах (1 Mflops - миллион операций с плавающей точкой за одну секунду). Для оценки этой величины мы будем измерять время выполнения фиксированного числа реальных операций выполняемых системой. Для данной задачи эта величина хорошо определена:
Число операций = (2* N - 1)*N*N,
где N - размерность матриц
Фиксирование просто времени выполнения программы не совсем удобно, поскольку программа может выполняться при различных исходных данных (например размерностях матриц) и тогда очень сложно сопоставлять результаты тестов.
Конечно, это не совсем корректный тест - поскольку используются не все арифметические операции (только умножение и сложение), но его результаты весьма поучительны. Будем выполнять перемножение достаточно больших матриц (1000х1000) и сравнивать полученную производительность с той, которую декларируют производители компьютеров. Для компьютера Alpha производительность одного процессора оценивается в 1000 Mflops, для SUN Ultra60 - 800 Mflops, для Pentium III 500 Mhz - 500 Mflops. Будем называть эти величины пиковой или потенциальной производительностью. Для решения нашей задачи любой программист написал бы на языке Фортран77 что-то подобное приведенному ниже:

      PROGRAM MATMULT
      IMPLICIT NONE
      INTEGER I,J,K,N,NM
      PARAMETER ( N=1000)
      REAL*8 A(N,N),B(N,N),C(N,N),S
      REAL*8 TIME,DSECND,OP,MF

OP = (2.D0*N-1)*N*N

      DO 1 I = 1,N
      DO 1 J = 1,N
      A(I,J) = DBLE(I)
      B(I,J) = 1./DBLE(J)
1   CONTINUE

WRITE(*,*) 'N = ',N
TIME = DSECND()

      DO 2 I = 1,N
      DO 2 J = 1,N
      S =0.0d0
      DO 3 K = 1,N
3   S = S + A(I,K)*B(K,J)
      C(I,J) = S
2   CONTINUE

      TIME = DSECND() - TIME
      MF = OP/(TIME*1000000.0)
      WRITE(*,10) C(1,1),C(1,N),C(N,1),C(N,N)
10 FORMAT(2X,2F16.6)
      WRITE(*,*) ' TIME CALCULATION: ', TIME,
     *' MFLOPS: ',MF
      END

      double precision function dsecnd()
      real tarray(2)
      dsecnd = etime(tarray)
      return
      end
Откомпилируем программу в стандартном режиме:

f77 -o mxm mxm.f

и посмотрим результат на разных системах (таблица 1)

	SUN Ultra60	Linux	Alpha
время реш. (сек.)	261.42	153.21	108.41
производит. (Mflops)	7.65	13.05	18.44

Результат мягко говоря обескураживающий. Ни о каких сотнях и тысячах Mflops речь не идет и близко.
Попробуем теперь, что могут выжать компиляторы при автоматической оптимизации. Компилируем в режиме ортимизации (SUN и Alpha: -fast -O4, LINUX: -O). Таблица 2.

SUN Ultra60 Linux Alpha

время реш. (сек.) 134.76 58.84 90.84

производит. (Mflops) 14.83 33.97 22.00

Оптимизация в различной степени ускорила решение задачи, но все равно производительность удручающе мала. Причем наибольшую производительность демонстрирует как раз не самая быстрая машина (Pentium III под Linux). Чтобы понять в чем проблема проведем такой эксперимент - уменьшим значительно размер матриц. Решим задачу для матриц 100х100. Результаты в Таблице 3.

SUN Ultra60 Linux Alpha

время реш. (сек.) 0.008 0.03 0.006

производит. (Mflops) 230.3 66.33 295.3

Полученные результаты уже обнадеживают. Для компьютеров SUN и Alpha отношение между потенциальной и полученной производительностью составляет около 3, а не десятки раз, как в таблице 1. Для Linux кластера тоже произошло ускорение, но не в такой степени как для SUN и Alpha. Причина состоит в том, что на компьютерах SUN и Alpha процессоры имеют сравнительно большую кэш-память ( 4 Мб ), которая работает со скоростью процессора, в то время как скорость работы основной памяти безнадежно отстала от скорости работы процессора. Для маленьких задач данные целиком помещаются в кэш-память и производительность существенно возрастает. Отсюда может показаться, что дорогостоящие компьютеры могут быстро считать только мелкие задачи. Покажем что это не так. В принципе можно писать программы, на которых будет достигаться практически пиковая производительность и на больших задачах.

Вернемся к исходной задаче и обратим внимание на то, что в операторе помеченном меткой 3, выполняется выборка элементов строки из отстоящих далеко друг от друга элементов массива (массивы в Фортране размещаются по столбцам). Это не позволяет буферизовать их в быстрой кэш-памяти. Перепишем вычислительную часть программы слудующим образом:
      DO 2 I = 1,N
      DO L = 1,N
      ROW(L) = A(I,L)
      END DO
      DO 2 J = 1,N
      C(I,J) =0.0d0
      DO 3 K = 1,N
3   C(I,J) = C(I,J) + ROW(K)*B(K,J)
2   CONTINUE
т.е мы завели промежуточный массив, в который предварительно выбираем строку матрицы А. Результат в Таблице 4.

SUN Ultra60 Linux Alpha

время реш. (сек.) 33.76 54.41 11.16

производит. (Mflops) 59.21 36.74 179.13

Результаты заметно улучшились (по сравнению с Таблицей 2) для SUN и особенно для Alpha и почти не изменились для Linux. Это подтверждает наше предположение о важности эффективного использования кэш-памяти.
Как раз на эффективное использование кэш-памяти нацелены поставляемые с высокопроизводительными системами библиотеки BLAS. До недавнего времени это обстоятельство было одним из основных аргументов в конкурентной борьбе фирм-производителей высокопроизводительных систем с компьютерами "желтой" сборки. В настоящее время ситуация резко изменилась. Нашлись "умельцы", которые написали и бесплатно распространяют самонастраивающуюся библиотеку BLAS (ATLAS), и которая может устанавливаться на любом компьютере, под любой операционной системой.

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

      DO 2 I = 1,N
      DO L = 1,N
      ROW(L) = A(I,L)
      END DO
      DO 2 J = 1,N
3   C(I,J) = DDOT(N,ROW(1),1,B(1,J),1)
2   CONTINUE
а при компиляции добавим соответствующую библиотеку (пример дан для Linux-кластера)

g77 -O -o mxm mxm.f -lmkl32_p3 -lpthread

Таблица 5

	SUN Ultra60	Linux	Alpha
время реш. (сек.)	33.61	16.8	10.37
производит. (Mflops)	59.46	119	192.8

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

 CALL DGEMM ('N','N', N, N, N, ONE, A, N, B, N, ZERO, C, N)

Здесь уместно заметить, что на всех перечисленных системах имеется по две библиотеки содержащих нужную нам подпрограмму. Native (родные) библиотеки для SUN, Linux и Alpha соответственно sunperf, mkl, cxml и библиотека ATLAS. На разных системах более эффективной оказывается либо та, либо другая библиотека. Приведем результаты сначала для фирменных библиотек. Таблица 6.

	SUN Ultra60	Linux	Alpha
время реш. (сек.)	6.79	4.9	2.32
производит. (Mflops)	295.3	407.1	861.3

Теперь для библиотеки ATLAS. Таблица 7.

SUN Ultra60 Linux Alpha

время реш. (сек.) 2.72 5.36 2.24

производит. (Mflops) 734.8 372.9 894.0

Вот теперь мы получили результаты для производительности близкие к тем, которые декларируются производителями вычислительных систем. По сравнению с первой таблицей ускорение работы программы для систем SUN, Pentium III и Alpha составило соответственно 96, 31 и 48 раз!!! Пожалуй это максимум, что можно выжать на однопроцессорном варианте. Дальнейшее ускорение решения задачи возможно только при эффективном распараллеливании программы.

Существует множество технологий разработки параллельных программ. Мы здесь приведем данные для программы, использующей параллельную версию подпрограммы перемножения матриц из пакета ScaLAPACK. Но это уже совершенно другая программа, практически не имеющая почти ничего общего с однопроцессорным вариантом. В данной таблице приведены данные решения той же самой задачи на 2-х процессорах. Таблица 8.

SUN Ultra60 Linux Alpha

время реш. (сек.) 1.62 3.7 1.30

производит. (Mflops) 1227.4 541.6 1539.1

Итак, в окончательном варианте мы смогли решить задачу на компьютере SUN за 1.62 сек, или в 161 раз быстрее по сравнению с первоначальным результатом, а на компьютере Alpha за 1.3 сек. или в 83 раза быстрее. Несколько замечаний следует сказать по поводу Linux-кластера. Двухпроцессорный вариант на нем оказался менее эффективным, чем на других системах и, по-видимому, нет смысла решать эту задачу на большем числе процессоров. Это связано с медленной коммуникационной средой. Доля накладных расходов на пересылки данных слишком велика по сравнению с вычислительными затратами. Однако эта доля уменьшается при увеличении размеров матрицы, поскольку вычислительные затраты растут пропорционально N**3, а коммуникационные пропорционально N**2. При увеличении параметра N до 4000 весьма эффективно задача решается даже на 4-х процессорах. Суммарная производительность получается 1231 Mflops или по 307 Mflops на процессор, что, конечно, весьма неплохо.

Для параллельного программирования ситуация в некотором смысле парадоксальная - чем более эффективно программа работает на одном процессоре, тем труднее обеспечить эффективность ее распараллеливания. Для иллюстрации этого вернемся к самому эффективному варианту программы, не использующему ни каких библиотечных подпрограм (результаты в Таблице 4), и распараллелим эту программу. Для данной программы эта задача не представляет особой трудности. Результат измерения производительности для различного числа процессоров представлен в Таблице 9.

число процессоров SUN Ultra60 Linux Alpha

1 59.5 34.0 199.06

2 378.6 66.9 357.9

4 - 130.6 -

Эти данные показывают, что эффективность распараллеливания высока и производительность системы хорошо растет при увеличении числа процессоров, однако она значительно ниже той, которую позволяет получить однопроцессорная программа с использованием высокопроизводительных библиотек. Резкий скачок производительности на Ultra60 объясняется тем, что после распараллеливания данные как-то очень удачно расположились в кэш-памяти. Поистине неисповедимы пути Господни.
Итак, на основе всех представленных данных можно сделать ряд выводов:
1) Производительность вычислительной системы определяется главным образом качеством программы, а не ее физическими характеристиками. По-видимому, влияние этого фактора значительно уменьшится, когда научатся делать оперативную память более быструю, чем процессор.
2) Априори никогда нельзя заранее предсказать на какой вычислительной системе конкретная программа будет работать быстрее. Пиковую производительность следует понимать как потенциальную возможность. Насколько этот потенциал будет использован той или другой программой - это вопрос к программисту.
3) Имеет смысл распараллеливать программу, если из однопроцессорного варианта выжато все что можно. Очень даже вероятно, что параллельная программа будет работать медленне, чем однопроцессорная.

24.04.2002
Вопросы и замечания направляйте по адресу: root@rsusu1.rnd.runnet.ru

число процессоров	SUN Ultra60	Linux	Alpha
1	59.5	34.0	199.06
2	378.6	66.9	357.9
4	-	130.6	-