Система автоматизации распараллеливания отображения на мультипроцессор (стр. 6 из 9)
5) Далее, цикл помечается, как пройденный. Если на уровне не осталось не пройденных циклов, текущий уровень становится на единицу меньше, и продолжаются действия 2). Если же текущий уровень принял значение 0, то после того, как не останется не пройденных ППЦ формируется второе внутреннее представление, отражающее все циклы, эффективные для распараллеливания.
Как происходит установка NOWAIT для подряд стоящих параллельных циклов:
Условие проверяется для подряд идущих циклов при добавлении нового цикла в параллельный регион.
· Если у последнего цикла в параллельном регионе есть пометка NowaitIn (означает, что перед предыдущим циклом уже установлена директива NOWAIT), то проверить условие Nowait для пар (новый цикл, последний цикл в параллельном регионе). Если условие истинно проверять условие для пар всех (новый цикл, цикл с пометкой NowaitOut), причем начиная с предпоследнего и в обратном порядке, до первой неудачной проверки или до первого цикла без пометки NowaitOut. Если не было неудачных проверок, поставить у нового цикла пометку NowaitIn, а у последнего в параллельном регионе NowaitOut (означает, что после цикла установлена директива NOWAIT).
· Если же у последнего цикла в параллельном регионе нет пометки пометка NowaitIn, то проверить условие Nowait для пар (новый цикл, последний цикл в параллельном регионе). Если условие истинно, поставить у нового цикла пометку NowaitIn, а у последнего в параллельном регионе NowaitOut.
Проверка условия Nowait между двумя циклами:
· Если множество переменных/массивов для 2 подряд идущих циклов не пересекается (за исключением индексов - они могут быть одинаковыми), то проверка удачна.
· Иначе, сравнить индексы массивов. Для каждого обращения к неприватизованному массиву в левой части одного цикла и для каждого обращения к этому же массиву в другом цикле сравнить индексы. Если докажем для измерения, по которому идет распараллеливание, что индексы во всех обращениях различны и количество итераций в циклах равны, то проверка удачна. Иначе проверка неудачна.
Фактически проверенное условие представляет собой проверку, будет ли нить, выполняющая набор инструкций из первого цикла записывать/считывать данные, которые считаны/записаны другой нитью, выполняющей инструкции из другого цикла. Для каждого неприватизованного массива мы проверяем, что множество мест в памяти для записи у одной нити и множество мест чтения/записи другой не пересекаются.
Для параллельных циклов с зависимостью по данным в массиве происходит проверка на возможность установки конвейера.
Для распараллеливания циклов с зависимостью используется алгоритм, который был применен в тестах NASA. Этот алгоритм накладывает ряд ограничений, которые проверяются экспертом. Вариант конвейерной работы тестируется только, если цикл с конвейерной зависимостью является вложенным внутренним. В зависимости не участвуют "угловые" элементы. На Рис. 9 слева изображена зависимость без участия "угловых" элементов. То есть значение массива зависит от значения элементов при изменении лишь 1 измерения. В правой части Рис. 9 описан вариант зависимости, при котором установка конвейера невозможна из-за "угловых" элементов.
Рис. 9. Возможность установки конвейера.
Для такого цикла оценочная функция при распараллеливании цикла считается, как минимум оценочной функции:
a) для работы цикла с директивами ORDERED,
b) конвейерным распараллеливанием.
В случае если на основном шаге цикл был помечен, как эффективный для распараллеливания, то если минимальна функция a), то цикл помечается ORDERED, иначе PIPELINE.
5.3 Шаг 3. Выбор варианта локализации
Данные на входе: База Данных с результатами статического анализа, 1-е внутреннее представление, незаконченное 2-е внутреннее представление.
Данные на выходе: 2-е внутреннее представление.
Как проходит преобразование входных данных в выходные:
Последний шаг по распараллеливанию: пытаемся выбрать наилучшую локализацию для текущего распараллеливания. Пробуем склеить соседние параллельные регионы за счет выбора подходящей локализации. Параллельно для массивов, у которых есть возможность установки threadprivate, создаем альтернативные локализации.
Алгоритм преобразования входных данных в выходные:
Для соседних параллельных регионов, находящихся на одном уровне пробуем альтернативные локализации. Если для какой—либо локализации регионы можно склеить, сравниваем оценочную функцию при склейке регионов и без склейки регионов. Если функция при склейке меньше, то превращаем 2 региона в один, помечаем для него локализацию.
После того, как не останется регионов, которые возможно склеить, внутри каждого региона проверяем все альтернативные локализации. Если оценочная функция для какой-либо альтернативной локализации меньше, чем оценочная функция для текущего варианта локализации, то эта альтернативная локализация заносится в текущий вариант локализации. Как только пройдены все регионы, информация из текущего варианта локализации заносится во 2-е внутреннее представление.
Если в Программном списке локализации переменных, какой-либо переменная во всех параллельных регионах становится приватным, то в программном списке локализаций переменных данный массив помечается как threadprivate. Для следующих параллельных регионов, использующих данный массив, он объявляется в списке copyin. Установка данных директив дает ускорение за счет отсутствия инициализации private переменных.
Для всех массивов, для которых не проставлены комментарии threadprivate, рассчитываем альтернативную локализации для всей программы, считая переменную приватной, но вычитая стоимость инициализации и синхронизации для массива. Если оценочная функция альтернативной локализации лучше оценочной функции для 2-го внутреннего представления, альтернативная локализация заносится во 2-е внутреннее представление, переменная во всех параллельных регионах становится: private, def, shared, noи помечается какthreadprivate.
5.4 Шаг 4. Внесение конечных комментариев в Базу Данных и подсчет ускорения
Данные на входе: База Данных, незаконченное 2-е внутреннее представление.
Данные на выходе: База Данных с комментариями.
Как проходит преобразование входных данных в выходные:
Из 2-го внутреннего представления комментарии переносятся в Базу Данных, соблюдая синтаксис OpenMP. Оценивается общее ускорение.
Алгоритм преобразования входных данных в выходные:
Проходим все вершины в Базе Данных. Каждую вершину пытаемся найти во 2-м внутреннем представлении, в случае успеха проставляем соответствующие комментарии следующим образом:
1) Если есть массивы с пометкой threadprivate, то в вершину с описанием переменных заносится !$OMPTHREADPRIVATE (список переменных).
2) Если цикл первый в параллельном регионе и цикл выгодный для распараллеливания !$OMPPARALLEL <список необходимых к обозначению PRIVATE и SHARED переменных> <COPYIN (список переменных)>
<список необходимых к обозначению PRIVATE и SHARED переменных> - перечисление директив (клауз) вида PRIVATE (имя переменной) или SHARED(имя переменной). В одном списке может быть несколько и PRIVATE, и SHARED.
<COPYIN (список переменных)> - указывается, если в цикле используются переменныес пометкойthreadprivate, причем все они должны быть перечислены через запятую в списке переменных.
3) Если цикл последний в параллельном регионе - !$OMPENDPARALLEL, как директива после цикла.
4) Если цикл выгодный для распараллеливания - !$OMPDO <ORDERED> <список REDUCTION, LASTPRIVATE, FIRSTPRIVATE>
<ORDERED> - директива ORDERED. Указывается, если при распараллеливании цикла используется ORDERED.
<список REDUCTION, LASTPRIVATE, FIRSTPRIVATE> - перечисление директив (клауз) вида REDUCTION (имя переменной), или LASTPRIVATE(имя переменной), или FIRSTPRIVATE (имя переменной). В одном списке может быть несколько и REDUCTION, LASTPRIVATE, FIRSTPRIVATE.
5) Если цикл выгодный для распараллеливания - !$OMPENDDO, как директива после цикла.
6) Если у цикла пометка Ordered, перед первой вершиной с пометкой "первое использование ORDERED" вносится !$OMPORDERED.
7) Если у цикла пометка Ordered, в конец последней вершины с пометкой "последнее использование ORDERED" вносится, !$OMPENDORDERED.
8) Если у цикла пометка pipeline– вставляются следующие директивы:
В области инициализации переменных, проверяется уникальность и происходит объявление функций и переменных, необходимых для функционирования конвейера:
!$ INTEGER OMP_GET_NUM_THREADS, OMP_GET_THREAD_NUM
!$ INTEGER IAM, NUMT, ISYNC("количество процессоров")
При инициализации параллельного региона, в который входит цикл с конвейером:
!$OMP PARALLEL PRIVATE (IAM,NUMT,ILIMIT)
Перед do внешнего цикла - инициализация нитей и синхронизационного массива ISYNC:
!$ iam = omp_get_thread_num ()
!$ numt = omp_get_num_threads ()
!$ ILIMIT=MIN(NUMT-1,Число витков внешнего цикла)
!$ ISYNC (IAM) = 0
!$OMPBARRIER
До цикла с конвейерной зависимостью - инициализация конвейера, допуск к циклу для нитей только после того, как предыдущая нить сделала одну итерацию внешнего цикла и распараллеливание витков внутреннего цикла между нитями:
!$ IF (IAM .GT. 0 .AND. IAM .LE. ILIMIT) THEN
!$ DO WHILE (ISYNC (IAM-1) .EQ. 0)
!$OMP FLUSH (ISYNC)
!$ ENDDO
!$ ISYNC (IAM-1)=0
!$OMP FLUSH(ISYNC)
!$ ENDIF
!$OMP DO
Перед enddo внешнего цикла – дождаться, пока следующая нить запустится, и продолжать выполнение цикла:
!$OMP ENDDO NOWAIT
!$ IF (IAM .LT. ILIMIT) THEN
!$ DO WHILE (ISYNC (IAM) .EQ. 1)
!$OMP FLUSH (ISYNC)
!$ ENDDO
!$ ISYNC (IAM)=1
!$OMP FLUSH(ISYNC)
!$ ENDIF
Послеenddo внешнегоцикла – синхронизация: