СКИПОДы 2007 полная версия (1127795), страница 49
Текст из файла (страница 49)
Внутренний цикл по J нераспараллеливается (выполняется условие Рассела для переменной S), а внешний цикл по I можнораспараллелить, так как переменная S в нем получает значение перед входом во внутренний цикл.Рассмотрим общую структуру ВК (рис. 5.5). Как правило, ВК состоит из синтаксическогоанализатора, распараллеливателя циклов, модуля оценки качества распараллеливания, генераторовпрограмм на параллельном ЯВУ или в машинных кодах.Схема преобразования программ методом гиперплоскостей.Метод гиперплоскостей применим только к многомерным циклам. В пространствеитераций ищется прямая (плоскость), на которой возможно параллельное асинхронноевыполнение тела цикла, причем в отличие от метода координат, эта прямая (плоскость)может иметь наклон по отношению к осям координат. Цикл вида:DO 5 I = 2,NDO 5 J = 2,M5 A(I,J) = ( A(I-1,J) + A(I,J-1) ) * 0.5методом координат не векторизуется.
Действительно, при фиксированном значениипеременной I (I = i) значение, вычисленное в точке (i,j) пространства итераций, зависитот результата вычислений в предыдущей точке (i,j-1) , так что параллельное выполнениетела цикла по переменной J невозможно. Аналогично нельзя проводить параллельныевычисления по переменной I.Однако можно заметить, что результат будет также правильным, если вычисленияпроводить в следующем порядке:на 1-м шаге - в точке (2,2),на 2-м шаге - в точках (3,2) и (2,3),на 3-м шаге - в точках (4,2), (3,3) и (2,4),на 4-м шаге - в точках (5,2), (4,3), (3,4) и (2,5)Вычисления в указанных точках для каждого шага, начиная со второго, можно проводитьпараллельно и асинхронно.
Перечисленные кортежи точек лежат на параллельныхпрямых вида I+J=K , а именно: на первом шаге - на прямой I+J=4 , на втором - I+J=5, натретьем шаге - I+J=6 и т.д., на последнем ((N-2)+(M-2)+1) - ом шаге - на прямойI+J=M+N.В общем случае для n-мерного тесногнездового цикла ищется семейство параллельныхгиперплоскостей в n-мерном пространстве итераций, таких что во всех точках каждой изэтих гиперплоскостей возможно параллельное выполнение тела цикла.Для приведенного примера множество точек, в которых возможно параллельноевыполнение, является однопараметрическим (прямая) и определяется из решенияуравнения 1I+J=K 0.
Цикл (5) может быть преобразован к виду:DO 5 K = 4,M+NTн = MMAX(2,K-N)Tк = MMIN(M,K-2)DO 5 T = Tн,Tк 1: PARI =T162J =K-T5 A(I,J) = ( A(I-1,J) + A(I,J-1) ) * 0.5Функция MMAX(X,Y) выбирает ближайшее целое, большее или равное максимуму изчисел X и Y , а функция MMIN(X,Y) - ближайшее целое, меньшее или равное минимумуиз X и Y .Внутренний цикл по переменной T может выполняться параллельно для всех значенийT . Границы изменения переменной цикла T меняются при переходе с одной прямой(гиперплоскости) на другую, поэтому их необходимо перевычислять во внешнем цикле.Число итераций внутреннего цикла, то есть потенциальная длина векторной операции,меняется с изменением K .
Для приведенного примера диапазон изменения T сначалавозрастает, а потом убывает, причем для начального и конечного значения K он равенединице. В некоторых случаях для отдельных значений K накладные расходы наорганизацию векторного вычисления могут превысить эффект ускорения от векторноговыполнения.Вопрос оценки целесообразности проведения векторизации данным методом долженрассматриваться для каждого конкретного случая отдельно.Метод параллелепипедов.Идея метода заключается в выявлении зависимых итераций цикла и объединении их впоследовательности - ветви, которые могут быть выполнены независимо друг от друга.При этом в пространстве итераций определяются области (параллелепипеды), все точкикоторых принадлежат разным ветвям. Задача максимального распараллеливаниязаключается в поиске параллелепипеда наибольшего объема; тогда исходный циклвыполняется наибольшим числом параллельных ветвей, каждая из которых представляетсобой исходный цикл, но с другим шагом изменения индекса.Для исходного цикла:DO 7 I = 1,7DO 7 J = 1,37 X(I,J) = X(I-2,J-1)параллельное представление в виде:DO 7 (K,L) = (1,1) (P1,P2) 1: PARDO 7 I = K,7,P1DO 7 J = L,3,P27 X(I,J) = X(I-2,J-1)допускается для различных разбиений пространства итераций: пара (P1,P2) можетиметь, например, значения (2,1), (2,3) или (7,1).
Таким образом, исходный цикл (7)преобразуется в последовательность параллельных ветвей, имеющих циклический вид.В общем виде задача, рассматриваемая методом параллелепипедов, для одномерныхциклов состоит в определении возможности представления цикла:DO L I = 1,rL T(I)(где T(i) - тело цикла) в виде следующей языковой конструкции:DO L K = 1,p 1: PARDO L I = K,r,p163L T(I)Оценить возможность параллельного выполнения цикла:DO i = 2,NA(i) = (B(i) + C(i))/A(i+CONST)ENDDOПараллельное выполнение цикла видаDO i=2,N A(I) =(B(i)+C(i))/A(i+const) ENDDO.Если const = 0, то все итерации цикла независимы и токой цикл может быть выполнен налюбой многопроцессорной ЭВМ, влючая Иллиак-4. (каждый виток цикла выполняется наотдельном процессоре)Если const > 0 (пусть =1) то при параллельное выполнение цикла на ЭВМ класса МКМД бездополнительных мер по синхронизации работы процессоров невозможно.
Например, пустьN=3 и два процессора вычисляют параллельно эти итерации, тогда, первый процессорвычисляет А2 по В2, С2, А3, а второй, А3 по В2, С2, А4 . При отсутствии синхронизацииможет случиться ситуация, при которой второй процессор завершит свою работу до началаработы первого. Тогда первый процессор для вычислений будет использовать А3, котороеобновил второй процессор, что неверно, ибо здесь нужно “старое” значение А3.
Однако,этот цикл выполняется параллельно на ЭВМ ОКМД (SIMD) так как там этот цикл можетбыть выполнен такими командами:1. Считать Вi в сумматоры каждого из n АЛУ.2. Сложить Сi со своим содержимом сумматора.3. Разделить содержимое каждого i-сумматора на Аi+1.4. Записать содержимое i- сумматоров в Аi.Из за того, что выборка из памяти и запись в память производится синхронно(одновременно), то работа цикла – корректна.Если const < 0 то параллельное выполнение цикла невозможно, ибо для выполненияочередной итерации цикла необходимы результаты работы предыдущей (рекурсия). Однакоизвестны приемы преобразования такого рода циклов к виду, допускающие параллельноевыполнение.Языки параллельного программированияСтандарты OpenMP.1. Введение. Что такое OpenMP?Интерфейс OpenMP задуман как стандарт для программирования на масштабируемых SMPсистемах (SSMP,ccNUMA, etc.) в модели общей памяти (shared memory model).
В стандартOpenMP входят спецификации набора директив компилятора, процедур и переменныхсреды.Кто разрабатывает стандарт?Разработкой стандарта занимается организация OpenMP ARB (ARchitecture Board), вкоторую вошли представители крупнейших компаний - разработчиков SMP-архитектур ипрограммного обеспечения. Спецификации для языков Fortran и C/C++ появилисьсоответственно в октябре 1997 года и октябре 1998 года. Открыт список рассылки дляпубличного обсуждения OpenMP (omp@openmp.org).Зачем нужен новый стандарт?До появления OpenMP не былопрограммирования на SMP-системах.подходящего164стандартадляэффективногоНаиболее гибким, переносимым и общепринятым интерфейсом параллельногопрограммирования является MPI (интерфейс передачи сообщений).
Однако модельпередачи сообщений 1) недостаточно эффективна на SMP-системах; 2) относительносложна в освоении, так как требует мышления в "невычислительных" терминах.POSIX-интерфейс для организации нитей (Pthreads) поддерживается широко (практическина всех UNIX-системах), однако по многим причинам не подходит для практическогопараллельного программирования:нет поддержки Fortran-а,слишком низкий уровень,нет поддержки параллелизма по данным,механизм нитей изначально разрабатывался не для целей организации параллелизма.OpenMP можно рассматривать как высокоуровневую надстройку над Pthreads (илианалогичными библиотеками нитей).Многие поставщики SMP-архитектур (Sun,HP,SGI) в своих компиляторах поддерживаютспецдирективы для распараллеливания циклов. Однако эти наборы директив, как правило,1) весьма ограничены; 2) несовместимы между собой; в результате чего разработчикамприходится распараллеливать приложение отдельно для каждой платформы.
OpenMPявляется во многом обобщением и расширением упомянутых наборов директив.Какие преимущества OpenMP дает разработчику?1. За счет идеи "инкрементального распараллеливания" OpenMP идеально подходит дляразработчиков, желающих быстро распараллелить свои вычислительные программы сбольшими параллельными циклами. Разработчик не создает новую параллельнуюпрограмму, а просто последовательно добавляет в текст последовательной программыOpenMP-директивы.2.
При этом, OpenMP - достаточно гибкий механизм, предоставляющий разработчикубольшие возможности контроля над поведением параллельного приложения.3. Предполагается, что OpenMP-программа на однопроцессорной платформе может бытьиспользована в качестве последовательной программы, т.е. нет необходимостиподдерживать последовательную и параллельную версии. Директивы OpenMP простоигнорируются последовательным компилятором, а для вызова процедур OpenMP могутбыть подставлены заглушки (stubs), текст которых приведен в спецификациях.4. Одним из достоинств OpenMP его разработчики считают поддержку так называемых"orphan" (оторванных) директив, то есть директивы синхронизации и распределения работымогут не входить непосредственно в лексический контекст параллельной области.Как это работает?Согласно терминологии POSIX threads, любой UNIX-процесс состоит несколько нитейуправления, которые имеют общее адресное пространство, но разные потоки команд ираздельные стэки.
В простейшем случае, процесс состоит из одной нити. Нити иногданазывают также потоками, легковесными процессами, LWP (light-weight processes).В OpenMP используется терминология и модель программирования, близкая к Pthreads(динамически порождаемые нити, общие и разделяемые данные, механизм "замков" для165синхронизации). Предполагается наиболее вероятным, что OpenMP будет реализован набазе Pthreads.Как это выглядит?Простой пример: вычисление числа "Пи".
В последовательную программу вставлены двестрочки, и она распараллелена!program compute_piparameter (n = 1000)integer idouble precision w,x,sum,pi,f,af(a) = 4.d0/(1.d0+a*a)w = 1.0d0/nsum = 0.0d0;!$OMP PARALLEL DO PRIVATE(x), SHARED(w)!$OMP& REDUCTION(+:sum)do i=1,nx = w*(i-0.5d0)sum = sum + f(x)enddopi = w*sumprint *,'pi = ',pistopend2. ДирективыДирективы OpenMP с точки зрения Фортрана являются комментариями и начинаются скомбинации символов "!$OMP". Директивы можно разделить на 3 категории: определениепараллельной секции, разделение работы, синхронизация.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
