Настройка и ускорение программ в OpenMP

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

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

Основные принципы настройки и ускорения программ в OpenMP

В этом разделе остановимся на основных стратегиях настройки и ускорения программ с использованием OpenMP.

В первую очередь следует отметить, что при настройке программ в OpenMP по возможности следует применять средства автоматизированного распараллеливания программ. В настоящее время все основные компиляторы Fortran и C/C++, предназначенные для разработки параллельных программ с использованием OpenMP, имеют возможности автоматического распараллеливания. Более подробно эти возможности будут рассмотрены в следующей лекции.

Чтобы найти и локализовать наиболее трудоемкие участки программы, можно воспользоваться возможностью профилирования (profiling) программы. В настоящее время этот процесс также в значительной степени автоматизирован. Существуют различные сервисные программы, позволяющие проводить профилирование разрабатываемых параллельных программ. Такие сервисные программы созданы различными производителями системного программного обеспечения, в том числе и компанией Intel. Как уже говорилось в предыдущей лекции, в состав набора программ Intel Threading Tools входит программа Intel Thread Profiler. Отметим также, что в составе программы Intel VTune Performance Analyzer имеются и другие средства профилирования программ. При профилировании программы важно выделить ее критический путь. Критический путь в многопоточной программе - это наиболее протяженный путь на диаграмме выполнения потоков. Для его определения необходимо провести анализ диаграммы выполнения потоков в параллельной программе. Пример такой диаграммы приведен на рис.6.1.

На этом рисунке через T1, T2 и T3 обозначены потоки в программе, а через E1, E2, …, Е12 - события в программе. Длина отрезков на диаграмме соответствует времени выполнения потоков. Обратите внимание, что образование параллельных потоков требует определенных временных затрат, что и отражено на диаграмме.

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

В случае недостаточно эффективного распараллеливания программы с использованием OpenMP следует обратить самое пристальное внимание:

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

Иерархия памяти

Современные параллельные системы могут иметь весьма сложную иерархию памяти. Ниже дана примерная классификация памяти современных высокопроизводительных систем по мере возрастания времени доступа к памяти:

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

Настройка кэш-памяти

Для эффективной загрузки кэш-памяти необходимо в первую очередь принимать специальные меры по выравниванию строк или столбцов массивов. В программах, написанных на алгоритмических языках C/C++, следует выравнивать строки массивов, а в программах, написанных на алгоритмическом языке Fortran, - столбцы.

Для эффективного применения кэш-памяти рекомендуется использовать многомерные массивы в одномерном виде.

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

Рассмотрим пример фрагмента параллельной программы, представленный в примере 6.1. В этом примере элементы массива prss, используемые в петлях цикла по k, разнесены между собой со значительными скачками. Для преодоления указанной трудности и улучшения загрузки кэш-памяти можно применить перестановку циклов, как показано во фрагменте программы, приведенном в примере 6.2.

!$omp parallel do
!$omp private (r1, r2, k, j)
   do j = jlow, jup
      do k = 2, kmax - 1
         r1 = prss(jminu(j),k) + prss(jplus(j),k) - 2. * prss(j,k)
         r2 = prss(jminu(j),k) + prss(jplus(j),k) - 2. * prss(j,k)
         coef (j,k) = ABC (r1/r2)
      enddo
   enddo
!$omp end parallel

!$omp parallel do
!$omp private (r1, r2, k, j)
   do k = 2, kmax - 1
      do j = jlow, jup
         r1 = prss(jminu(j),k) + prss(jplus(j),k) - 2. * prss(j,k)
         r2 = prss(jminu(j),k) + prss(jplus(j),k) - 2. * prss(j,k)
         coef (j,k) = ABC (r1/r2)
      enddo
   enddo
!$omp end parallel

Очень часто загрузку кэш-памяти можно улучшить с помощью транспонирования элементов массивов в петлях вложенных циклов. Рассмотрим такой пример. В примере 6.3 показаны исходный и модифицированный Исходный вариант:

Исходный вариант:

      real rx (jdim, idim)
!$omp parallel do
      do i = 2, n -1
         do j = 2, n
            rx(i, j) = rx(i, j -1) + …
         enddo
      enddo

Модифицированный вариант:
      
      real rx (idim, jdim)
!$omp parallel do
      do i = 2, n - 1
         do j = 2, n
            rx(j, I) = rx(j -1, i) + …
         enddo
      enddo

фрагменты параллельной программы с вложенными циклами, в которых осуществляется обращение к элементам массивов rx. Для оптимизации загрузки кэш-памяти в этом примере массив rx транспонирован.

На компьютерах серии NUMALINK (non-uniform memory access) с неоднородным по времени доступом к памяти важно учитывать следующие особенности:

В программах, написанных с использованием OpenMP, существуют следующие возможности управления потоками:

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

Зависимости по данным

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

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

DO I = 2 , 5 
   A (I) = C * A (I -1) 
ENDDO

Далее представлено элементарное распараллеливание этого цикла:

c$omp parallel sections 
c$omp section 
  A (2) = C * A (1) 
c$omp section 
  A (3) = C * C * A (1) 
c$omp section 
  A (4) = C * C * C *A (1) 
c$omp section 
  A (5) = C * C * C * C * A (1) 
c$omp end sections nowait

Рассмотрим еще один пример программы с циклом, петли которого содержат зависимости по данным. Исходный фрагмент этой программы приведен в примере 6.4.

В примере 6.5 представлен пример распараллеленной версии программы. При распараллеливании вычисления индексов массивов были устранены операторы вычисления индексов по рекуррентным формулам.

Еще один характерный пример фрагмента программы с зависимостью по данным приведен в примере 6.6.

Распараллеливание этого фрагмента можно осуществить путем применения директивы OpenMP reduction к циклу do.

i1 = 0
   i2 = 0
do i =1, n
      i1 = i1 + 1
      B(i1) = …

      i2 = i2 + i
      A(i2) = …
enddo

c$omp parallel do
   do i =1, n
      B( i ) = …
      
      A((i**2 +i)/2) = …
   enddo

do i = 1, n
   xsum = xsum + a (i)
   xmu1 = xmu1 * a (i)
   xmax = max (xmax, a (i))
   xmin = min (xmin, a (i))
enddo

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

При распараллеливании вложенных циклов надо стремиться к вынесению независимых по данным петель циклов на верхний уровень и проводить распараллеливание только на этом уровне. Пример такого цикла приведен во фрагменте программы (пример 6.8). Распараллеливание такого цикла возможно только на самом верхнем уровне, т. е. по индексу k.

do i = 1, n
        a (i) = b (i) + c (i)
        if (a(i) .GT. amax) then
            a(i) = amax
            goto 100
        endif
    enddo
100 continue

do k = 1, n
   do j = 1, n
      do i = 1, n
         a (i, j) = a (i, j) + b (i, k) * c (k, j)
      enddo
   enddo
enddo

Эффективность параллельных программ и масштабируемость

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

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

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

Здесь s - суммарная доля последовательных блоков в параллельной программе. Понятно, что 0<s<1.

Из закона Амдала следует, что при числе параллельных процессоров, стремящемся к бесконечности, максимальное ускорение A не превысит величины 1/s вне зависимости от качества реализации параллельной части программы. При этом, если половина программы представляет из себя последовательную часть s=1/2, то ускорить такую программу более чем в два раза не удастся при любом числе параллельных процессоров.

Еще одна интересная оценка, следующая из закона Амдала: для того чтобы ускорить программу на 8 параллельных процессорах, например в четыре раза, необходимо обеспечить, чтобы последовательная часть программы не превышала 1/7 части программы.

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