Название представления	На каком шаге создается	Что содержит	Зачем нужно
Первое внутреннее	1 шаг	1. Информация обо всех операторах программы 2. Информация о локализации программы "по умолчанию"	Базовое представление, на основании которого производится последующий анализ
Второе внутреннее	2-3 шаг	Схема распараллеливания, которая считается наилучшей	Для формирования комментариев (содержит информацию по распараллеливанию)
Список параллельных регионов	2 шаг	Все параллельные регионы программы	Для формирования комментариев (содержит информацию по локализации)
Программный список локализаций переменных	3 шаг	Список переменных, для каждой из которых ведется список локализаций в параллельных регионах программы	Для простановки комментария threadprivate

Таблица 1. Внутренние представления "Эксперта".

Первое внутреннее представление содержит информацию о локализации переменных.

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

Пометки проставляются для всех переменных, используемых внутри данного оператора. Все возможные пометки представлены в Таблице 2.

1-е значение 1-й пары (вид приватной)	2-е значение 1-й пары - пометка приватной
private (по умолчанию) firstprivate lastprivate reduction	Ind - индекс Set - Необходимо указать в комментариях Redtype() - тип редукции (только для редукционных) Pos (по умолчанию) - возможно объявить приватной, но не обязательно No - невозможно объявить приватной
1-е значение 2-й пары (общая)	2-е значение 2-й пары (пометка общей)
Shared (по умолчанию)	Def (по умолчанию) - общая по умолчанию Set - необходимо указать в директивах No - невозможно объявить общей

Таблица 2. Пометки по локализации переменных.

Как пометки соответствуют директивам OpenMP:

Если 2-е значение 1-й пары = Set, переменную необходимо объявить PRIVATE.

Если 2-е значение 2-й пары = Set, переменную необходимо объявить SHARED.

Если 1-е значение 1-й пары = reduction, необходима директива REDUCTION(2-е значение 1-й пары: имя переменной).

Если 1-е значение 1-й пары = lastprivate, необходима директива LASTPRIVATE(имя переменной).

Если 1-е значение 1-й пары = firstprivate, необходима директива FIRSTPRIVATE(имя переменной).

4.3 Оценочные функции

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

Стоимость параллельного исполнения = (стоимость последовательного исполнения / число нитей + стоимость ordered) * число итераций + стоимость создания и удаления параллельной области стоимость последовательного исполнения

Это стоимость одной итерации цикла (предоставлена анализатором) без учета стоимости выражений, окруженных директивами Ordered/End Ordered число нитей - количество "полезных" процессоров. Для цикла это значение равно минимуму из общего количества процессоров и количества итераций цикла.

стоимость ordered = стоимость последовательного исполнения выражений, окруженных директивами Ordered/End Ordered.

стоимость создания и удаления параллельной области = const + стоимость создания m приватных переменных + стоимость синхронизации. Константа зависит от архитектуры системы и берется из базы данных или определяется пользователем. Это время, необходимое для создания (инициализации) и удаления параллельного региона.

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

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

2) Оценочная функция стоимости вычисляется по следующей формуле:

Стоимость конвейера = стоимость действий внутри конвейера * количество действий конвейера + инициализация конвейера + синхронизация конвейера.

стоимость действий внутри конвейера = стоимость последовательного исполнения внутреннего цикла (конвейер возможен лишь для тесно вложенных циклов).

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

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

синхронизация конвейера = количество директив FLUSH, BARRIER и ENDDO * количество локальных переменных * количество действий конвейера.

3) Оценочная функция региона равна сумме всех оценочных функций членов региона.

5. Пошаговая реализация "Эксперта"
5.1 Шаг 1. Предварительный анализ
Данные на входе: База Данных с результатами статического анализа.

Данные на выходе: 1-е внутреннее представление.

Как проходит преобразование входных данных в выходные:

Циклы разделяем на ППЦ и ЦНР, параллельно рассчитывая локализацию по умолчанию. Линейные фрагменты и условные операторы просто переносим. Проход по дереву осуществляется "сверху-вниз".

Алгоритм преобразования входных данных в выходные:

Проходим по дереву циклов из Базы Данных, в зависимости от вершины делаем соответствующие действия.

Если вершина - цикл, неподдающийся распараллеливанию переносим его в первое внутреннее представление с пометкой ЦНР.

Если вершина - ППЦ, проводим следующую последовательность действий:

1) В текущую версию комментариев к вершине в первом внутреннем представлении записать ППЦ.

2) Пометить уровень вложенности (исходя из того, что "тело" программы имеет уровень 0).

3) Для всех переменных, используемых в данном цикле во временном представлении сделать пометки:

· Для индекса: private, ind, shared, no

· Для остальных: private, pos, shared, def

4) Если есть редукция в цикле: для всех редукционных переменных сделать пометки: reduction, "операция редукции", shared, no

5) Если в цикле присутствует скалярная зависимость по данным: для всех переменных со скалярной зависимостью сделать пометки: private (lastprivate), set, shared, no

6) Если цикл содержит зависимость по данным в массиве: проставить для данного цикла пометку ordered и для оператора, соответствующего первому использованию массива, имеющего зависимость, в теле цикла пометку "первое использование ordered", для оператора, соответствующего последнему использованию массива, имеющему зависимость, в теле цикла поставить пометку "последнее использование ordered". Массивы, вызвавшие зависимость занести в список "массивов с зависимостями".

Если вершина - линейный фрагмент или ветвление - просто переносим вершину из Базы Данных в 1-е внутреннее представление.

5.2 Шаг 2. Выбор варианта распараллеливания

Данные на входе: База Данных с результатами статического анализа, 1-е внутреннее представление.

Данные на выходе: незаконченное 2-е внутреннее представление.

Как проходит преобразование входных данных в выходные:

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

На этом шаге обходим дерево из 1-ого внутреннего представления и выбираем наилучшую схему распараллеливания для вложенных ППЦ и объединяем в параллельные регионы "соседние" ППЦ. Для параллельных регионов перебираем все возможные варианты комментариев с фиксированием наилучшего из них во 2-м внутреннем представлении.

Алгоритм преобразования входных данных в выходные:

Проходим вершины дерева из 1-го внутреннего представления. Изначально все ППЦ помечаются как не пройденные. Продолжаем действия, пока не останется не пройденных ППЦ.

Основные действия шага 2:

1) Находим ППЦ наибольшего уровня (т.е. самый "низший" по вложенности) и делаем уровень найденного цикла текущим.

2) Для всех циклов текущего уровня сравниваем 3 оценочных функции:

a) оценочная функция для последовательного варианта,

b) оценочная функция при распараллеливании данного цикла,

c) оценочная функция при распараллеливании вложенных циклов, при том, что данный цикл остается последовательным (этот вариант оценивается только, если существуют вложенные ППЦ).

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

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

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, то в вершину с описанием переменных заносится !$OMP THREADPRIVATE (список переменных).

2) Если цикл первый в параллельном регионе и цикл выгодный для распараллеливания !$OMP PARALLEL <список необходимых к обозначению PRIVATE и SHARED переменных> <COPYIN (список переменных)>

<список необходимых к обозначению PRIVATE и SHARED переменных> - перечисление директив (клауз) вида PRIVATE (имя переменной) или SHARED (имя переменной). В одном списке может быть несколько и PRIVATE, и SHARED.

<COPYIN (список переменных)> - указывается, если в цикле используются переменные с пометкой threadprivate, причем все они должны быть перечислены через запятую в списке переменных.

3) Если цикл последний в параллельном регионе - !$OMP END PARALLEL, как директива после цикла.

4) Если цикл выгодный для распараллеливания - !$OMP DO <ORDERED> <список REDUCTION, LASTPRIVATE, FIRSTPRIVATE>

<ORDERED> - директива ORDERED. Указывается, если при распараллеливании цикла используется ORDERED.

<список REDUCTION, LASTPRIVATE, FIRSTPRIVATE> - перечисление директив (клауз) вида REDUCTION (имя переменной), или LASTPRIVATE (имя переменной), или FIRSTPRIVATE (имя переменной). В одном списке может быть несколько и REDUCTION, LASTPRIVATE, FIRSTPRIVATE.

5) Если цикл выгодный для распараллеливания - !$OMP END DO, как директива после цикла.

6) Если у цикла пометка Ordered, перед первой вершиной с пометкой "первое использование ORDERED" вносится !$OMP ORDERED.

7) Если у цикла пометка Ordered, в конец последней вершины с пометкой "последнее использование ORDERED" вносится, !$OMP END ORDERED.

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

!$OMP BARRIER

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

!$ 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 внешнего цикла - синхронизация:

!$OMP BARRIER

Таким образом, все нити входят в параллельный регион. Отрабатывает 1-я нить со своей частью витков внутреннего цикла. Вступает в работу 2-я нить, работают обе нити, причем 1-я со 2-м значением итератора, а 2-я с первым и т.д. Пример функционирования конвейера показан на Рис. 10.

Рис. 10. Вычисление цикла с конвейерной зависимостью для 2-х мерного случая. Квадраты - области элементов массива; цифра - № нити, которая вычислит эту область; цифра в скобках - шаг работы конвейера, на котором вычислится область.

5.5 Примеры работы алгоритма
5.5.1 Программа "Якоби"
1) Листинг последовательной программы
PROGRAM JAC
PARAMETER (L=8, ITMAX=20)
REAL A(L,L), EPS, MAXEPS, B(L,L)
PRINT *, '********** TEST_JACOBI **********'
MAXEPS = 0.5E - 7
DO 1 J = 1, L(1)
DO 1 I = 1, L(2)
A(I, J) = 0. IF(I.EQ.1 .OR. J.EQ.1 .OR. I.EQ.L .OR. J.EQ.L) THEN
B(I, J) = 0.
ELSE
B(I, J) = ( 1. + I + J ) ENDIF
1 CONTINUE
DO 2 IT = 1, ITMAX(3)
EPS = 0.
DO 21 J = 2, L-1(4)
DO 21 I = 2, L-1(5)
EPS = MAX ( EPS, ABS( B( I, J) - A( I, J)))
A(I, J) = B(I, J)
21 CONTINUE
DO 22 J = 2, L-1(6)
DO 22 I = 2, L-1(7)
B(I, J) = (A( I-1, J ) + A( I, J-1 ) + A( I+1, J)+ A( I, J+1 )) / 4
22 CONTINUE
PRINT 200, IT, EPS
200 FORMAT(' IT = ',I4, ' EPS = ', E14.7)
IF ( EPS . LT . MAXEPS ) GO TO 3
2 CONTINUE
3 OPEN (3, FILE='JAC.DAT', FORM='FORMATTED', STATUS='UNKNOWN')
WRITE (3,*) B CLOSE (3) END
2) Первое внутреннее представление для циклов

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

(1) Тип:ППЦ,уровень = 0, число итераций = 8

Использование переменных:

Имя: i. Пометки: PRIVATE, SET, SHARED, NO

Имя: j. Пометки: PRIVATE, IND, SHARED, NO

Имя: a. Пометки: PRIVATE, POS, SHARED, DEF

Имя: b. Пометки: PRIVATE, POS, SHARED, DEF

(2) Тип:ППЦ,уровень = 1, число итераций = 8

Использование переменных:

Имя: i. Пометки: PRIVATE, IND, SHARED, NO

Имя: j. Пометки: PRIVATE, POS, SHARED, DEF

Имя: a. Пометки: PRIVATE, POS, SHARED, DEF

Имя: b. Пометки: PRIVATE, POS, SHARED, DEF

(3) Тип:ЦНР,уровень = 0, число итераций = 20

Использование переменных:

Имя: eps. Пометки: PRIVATE, SET, SHARED, NO

Имя: j. Пометки: PRIVATE, SET, SHARED, NO

Имя: i. Пометки: PRIVATE, SET, SHARED, NO

Имя: b. Пометки: PRIVATE, NO, SHARED, SET ORDERED!

Имя: a. Пометки: PRIVATE, NO, SHARED, SET ORDERED!

(4) Тип:ППЦ,уровень = 1, число итераций = 6

Использование переменных:

Имя: i. Пометки: PRIVATE, SET, SHARED, NO

Имя: eps. Пометки: REDUCTION, MAX, SHARED, NO

Имя: b. Пометки: PRIVATE, POS, SHARED, DEF

Имя: j. Пометки: PRIVATE, IND, SHARED, NO

Имя: a. Пометки: PRIVATE, POS, SHARED, DEF

(5) Тип:ППЦ,уровень = 2, число итераций = 6

Использование переменных:

Имя: eps. Пометки: REDUCTION, MAX, SHARED, NO

Имя: b. Пометки: PRIVATE, POS, SHARED, DEF

Имя: i. Пометки: PRIVATE, IND, SHARED, NO

Имя: j. Пометки: PRIVATE, POS, SHARED, DEF

Имя: a. Пометки: PRIVATE, POS, SHARED, DEF

(6) Тип:ППЦ,уровень = 1, число итераций = 6

Использование переменных:

Имя: i. Пометки: PRIVATE, SET, SHARED, NO

Имя: a. Пометки: PRIVATE, POS, SHARED, DEF

Имя: j. Пометки: PRIVATE, IND, SHARED, NO

Имя: b. Пометки: PRIVATE, POS, SHARED, DEF

(7) Тип:ППЦ,уровень = 2, число итераций = 6

Использование переменных:

Имя: a. Пометки: PRIVATE, POS, SHARED, DEF

Имя: i. Пометки: PRIVATE, IND, SHARED, NO

Имя: j. Пометки: PRIVATE, POS, SHARED, DEF

Имя: b. Пометки: PRIVATE, POS, SHARED, DEF

3) Второй шаг

На этом шаге будет устроен перебор различных вариантов распараллеливания. Рассмотрим их, группируя по регионам. Все варианты будем рассматривать при числе процессоров=4. 1-й регион: циклы (1) и (2). Здесь будет рассмотрено 3 варианта, время исполнения 1 витка внутреннего цикла =6, L=8.

!$OMP PARALLEL PRIVATE (I)

!$OMP DO

DO 1 J = 1, L

DO 1 I = 1, L

A(I, J) = 0.

IF(I.EQ.1 .OR. J.EQ.1 .OR. I.EQ.L .OR. J.EQ.L) THEN

B(I, J) = 0.

ELSE

B(I, J) = ( 1. + I + J )

ENDIF

ENDDO

!$OMP END DO

!$OMP END PARALLEL

DO 1 J = 1, L

!$OMP PARALLEL

!$OMP DO

DO 1 I = 1, L

A(I, J) = 0.

IF(I.EQ.1 .OR. J.EQ.1 .OR. I.EQ.L .OR. J.EQ.L) THEN

B(I, J) = 0.

ELSE

B(I, J) = ( 1. + I + J )

ENDIF

ENDDO

!$OMP END DO

ENDDO

!$OMP END PARALLEL

Стоимость = 6*8*8/4 + 14 = 110

Количество приватных = 2

Время инициализации = 5

Время синхронизации переменных и удаления региона = 7

Итого: 14

Стоимость = 8*(6*8/4 + 12) = 192

Количество приватных = 1

Время инициализации = 5

Время синхронизации переменных и удаления региона = 6

Итого: 12

Рис. 11. Сравнение вариантов распараллеливания в 1-м регионе программы "Якоби".

На Рис. 11 показаны возможные рассматриваемые варианты распараллеливания: цикла по J в левой части и цикла по I в левой части. Пункт "Стоимость" отражает подсчет оценочной функции. Она берется, как сумма "параллельного" вычисления цикла и "дополнительных" расходов, подсчитанных в пункте "Итого". Так как стоимость последовательная = 6*8*8 = 384, будет выбран вариант, показанный в левой части.

2-й регион: циклы (4) и (5). Время исполнения 1 витка внутреннего цикла =5.

!$OMP PARALLEL PRIVATE (I)

!$OMP DO REDUCTION(EPS,MAX)

DO 21 J = 2, L-1

DO 21 I = 2, L-1

EPS = MAX ( EPS, ABS( B( I, J) - A( I, J)))

A(I, J) = B(I, J)

21 CONTINUE

!$OMP END DO

!$OMP END PARALLEL

DO 21 J = 2, L-1

!$OMP PARALLEL

!$OMP DO REDUCTION(EPS,MAX)

DO 21 I = 2, L-1

EPS = MAX ( EPS, ABS( B( I, J) - A( I, J)))

A(I, J) = B(I, J)

!$OMP END DO

!$OMP END PARALLEL

21 CONTINUE

Стоимость = 5*6*6/4+16=61

Количество приватных = 3

Время инициализации = 5

Время синхронизации переменных и удаления региона = 8

Итого: 16

Стоимость = 6*(5*6/4+14)=129

Количество приватных = 2

Время инициализации = 5

Время синхронизации переменных и удаления региона = 7

Итого: 14

Рис. 12. Сравнение вариантов распараллеливания в 2-м регионе программы "Якоби".

На Рис. 12 показаны возможные рассматриваемые варианты распараллеливания: цикла по J в левой части и цикла по I в левой части. Стоимость последовательная = 6*6*5=180, следовательно, будет выбран вариант, описанный в левой части Рис. 12. Редукционная переменная считается как приватная.

3-й регион: циклы (6) и (7). Время исполнения 1 витка внутреннего цикла =9.

!$OMP PARALLEL PRIVATE (I)

!$OMP DO

DO 22 J = 2, L-1

DO 22 I = 2, L-1

B(I, J) = (A( I-1, J ) + A( I, J-1 ) + A( I+1, J)+ A( I, J+1 )) / 4

22 CONTINUE

!$OMP END DO

!$OMP END PARALLEL

DO 21 J = 2, L-1

!$OMP PARALLEL

!$OMP DO SHARED(J), REDUCTION(EPS,MAX)

DO 21 I = 2, L-1

EPS = MAX ( EPS, ABS( B( I, J) - A( I, J)))

A(I, J) = B(I, J)

!$OMP END DO

!$OMP END PARALLEL

21 CONTINUE

Стоимость = 9*6*6/4+14=95

Количество приватных = 2

Время инициализации = 5

Время синхронизации переменных и удаления региона = 7

Итого: 14

Стоимость = 6*(9*6/4+12)=153

Количество приватных = 1

Время инициализации = 5

Время синхронизации переменных и удаления региона = 7

Итого: 12

Рис. 13. Сравнение вариантов распараллеливания в 3-м регионе программы "Якоби".

На Рис. 13 показаны возможные рассматриваемые варианты распараллеливания: цикла по J в левой части и цикла по I в левой части. Стоимость последовательная = 9*6*6=324, следовательно, будет выбран 1-й вариант из Рис. 13.

2-й и 3-й параллельные регионы объединятся в один регион, т.к. нет противоречий по локализации переменных. Проверка на NOWAIT не будет успешна: для обращения A(I, J) = B(I, J) есть обращение B(I, J) = (A( I-1, J ) + A( I, J-1 ) + A( I+1, J)+ A( I, J+1 )) / 4 (может возникнуть ситуация, когда одной нити придется использовать "старое" значение массива A во втором цикле).

3) Шаг 3 и Шаг 4

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

На шаге 4 получим выходную программу:

program jac

parameter (l = 8,itmax = 20)

real a(l,l),eps,maxeps,b(l,l)

! arrays A and B with block distribution

print *, '********** TEST_JACOBI **********'

maxeps = 5.000000e-008

!nest of two parallel loops, iteration (i,j) will be executed on

!processor, which is owner of element A(i,j)

!OMP PARALLEL PRIVATE(i)

!OMP DO

do j = 1,l

do i = 1,l

a(i,j) = 0.

if (i .eq. 1 .or. j .eq. 1 .or. i .eq. l .or. j .eq. l) then

b(i,j) = 0.

else

b(i,j) = 1. + i + j

endif

enddo

!OMP ENDDO

!OMP END PARALLEL

do it = 1,itmax

eps = 0

!variable EPS is used for calculation of maximum value

!OMP PARALLEL PRIVATE(i)

!OMP DO REDUCTION(MAX:eps)

do j = 2,l - 1

do i = 2,l - 1

eps = max (eps,abs (b(i,j) - a(i,j)))

a(i,j) = b(i,j)

enddo

!Copying shadow elements of array A from

!neighbouring processors before loop execution

!OMP ENDDO

!OMP DO

do j = 2,l - 1

do i = 2,l - 1

b(i,j) = (a(i - 1,j) + a(i,j - 1) + a(i + 1,j) + a(i,j +

&1)) / 4

enddo

!OMP ENDDO

!OMP END PARALLEL

print 200, it,eps

200 FORMAT(' IT = ',I4, ' EPS = ', E14.7)

if (eps .lt. 5.000000e-008) goto 3

enddo

3 open (unit = 3,file = 'JAC.DAT',form = 'FORMATTED',status = 'UNKNO

&WN')

write (unit = 3,fmt = *) b

close (unit = 3)

end

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

Общее время последовательного выполнения: 10547 у.е.

Общее время параллельного выполнения (4 нити): 3231 у.е

Суммарное ускорение: в 3,26 раза

5.5.2 Программа "Sor"

1) Листинг последовательной программы

PROGRAM SOR

PARAMETER ( N = 10 )

REAL A( N, N ), EPS, MAXEPS, W

INTEGER ITMAX

PRINT *, '********** TEST_SOR **********'

ITMAX=20

MAXEPS = 0.5E - 5

W = 0.5

DO 1 J = 1, N

DO 1 I = 1, N

IF ( I .EQ.J) THEN

A( I, J ) = N + 2

ELSE

A( I, J ) = -1.0

ENDIF

1CONTINUE

DO 2 IT = 1, ITMAX

EPS = 0.

DO 21 J = 2, N-1

DO 21 I = 2, N-1

S = A( I, J )

A( I, J ) = (W / 4) * (A( I-1, J ) + A( I+1, J ) + A( I, J-1 ) +

*A( I, J+1 )) + ( 1-W ) * A( I, J)

EPS = MAX ( EPS, ABS( S - A( I, J )))

21CONTINUE PRINT 200, IT, EPS

200 FORMAT(' IT = ',I4, ' EPS = ', E14.7)

IF (EPS .LT. MAXEPS ) GO TO 4

2CONTINUE

4 OPEN (3, FILE='SOR.DAT', FORM='FORMATTED',STATUS='UNKNOWN')

WRITE (3,*) A CLOSE (3) END

2) Первое внутреннее представление для циклов

(1) Тип:ППЦ,уровень = 0, число итераций = 8

Использование переменных:

Имя: i. Пометки: PRIVATE, SET, SHARED, NO

Имя: j. Пометки: PRIVATE, IND, SHARED, NO

Имя: a. Пометки: PRIVATE, POS, SHARED, DEF

(2) Тип:ППЦ,уровень = 1, число итераций = 8

Использование переменных:

Имя: i. Пометки: PRIVATE, IND, SHARED, NO

Имя: j. Пометки: PRIVATE, POS, SHARED, DEF

Имя: a. Пометки: PRIVATE, POS, SHARED, DEF

(3) Тип:ЦНР,уровень = 0, число итераций = 20

Использование переменных:

Имя: eps. Пометки: PRIVATE, SET, SHARED, NO

Имя: j. Пометки: PRIVATE, SET, SHARED, NO

Имя: i. Пометки: PRIVATE, SET, SHARED, NO

Имя: a. Пометки: PRIVATE, NO, SHARED, SET ORDERED! PIPELINE!

Имя: s. Пометки: PRIVATE, SET, SHARED, NO

(4) Тип:ППЦ,уровень = 1, число итераций = 6

Использование переменных:

Имя: i. Пометки: PRIVATE, SET, SHARED, NO

Имя: eps. Пометки: REDUCTION, MAX, SHARED, NO

Имя: j. Пометки: PRIVATE, IND, SHARED, NO

Имя: a. Пометки: PRIVATE, NO, SHARED, SET, rw= 2 ORDERED! PIPELINE!

Имя: s. Пометки: PRIVATE, SET, SHARED, NO

(5) Тип:ППЦ,уровень = 2, число итераций = 6

Использование переменных:

Имя: i. Пометки: PRIVATE, IND, SHARED, NO

Имя: j. Пометки: PRIVATE, POS, SHARED, DEF

Имя: eps. Пометки: REDUCTION, MAX, SHARED, NO

Имя: a. Пометки: PRIVATE, NO, SHARED, SET, rw= 2 ORDERED! PIPELINE!

Имя: s. Пометки: PRIVATE, SET, SHARED, NO

3) Второй шаг

На этом шаге будет устроен перебор различных вариантов распараллеливания. Рассмотрим их, группируя по регионам. Все варианты будем рассматривать при числе процессоров=4.

1-й регион: циклы (1) и (2). Здесь будет рассмотрено 3 варианта, время последовательного исполнения 1 витка = 1.

!$OMP PARALLEL PRIVATE(I)

!$OMP DO

DO 1 J = 1, N

DO 1 I = 1, N

IF ( I .EQ.J) THEN

A( I, J ) = N + 2

ELSE

A( I, J ) = -1.0

ENDIF

1CONTINUE

!$OMP END DO

!$OMP END PARALLEL

DO 1 J = 1, N

!$OMP PARALLEL

!$OMP DO

DO 1 I = 1, N

IF ( I .EQ.J) THEN

A( I, J ) = N + 2

ELSE

A( I, J ) = -1.0

ENDIF

!$OMP END DO

!$OMP END PARALLEL

1 CONTINUE

Стоимость = 1*10*10/4 + 14 = 39

Количество приватных = 2

Время инициализации = 5

Время синхронизации переменных и удаления региона = 7

Итого: 14

Стоимость = 10 * (1*10/ 4 + 12) = 145

Количество приватных = 1

Время инициализации = 5

Время синхронизации переменных и удаления региона = 6

Итого: 12

Рис. 14. Сравнение вариантов распараллеливания в 1-м регионе программы "SOR".

На Рис. 14 показаны возможные рассматриваемые варианты распараллеливания: цикла по J в левой части и цикла по I в левой части. Стоимость последовательная = 10*10=100, следовательно, будет выбран вариант, показанный в левой части Рис. 14.

2-й регион: циклы (4) и (5). Здесь будет рассмотрено 4 варианта, время последовательного исполнения 1 витка = 22.

!$OMP PARALLEL PRIVATE(S) PRIVATE(I)

!$OMP DO REDUCTION(EPS,MAX)

DO 21 J = 2, N-1

DO 21 I = 2, N-1

!$OMP ORDERED

S = A( I, J )

A( I, J ) = (W / 4) * (A( I-1, J ) + A( I+1, J ) + A( I, J-1 ) +

*A( I, J+1 )) + ( 1-W ) * A( I, J)

EPS = MAX ( EPS, ABS( S - A( I, J )))

!$OMP END ORDERED

21CONTINUE

!$OMP END DO

!$OMP END PARALLEL

DO 21 J = 2, N-1

!$OMP PARALLEL PRIVATE(S)

!$OMP DO REDUCTION(EPS,MAX)

DO 21 I = 2, N-1

!$OMP ORDERED

S = A( I, J )

A( I, J ) = (W / 4) * (A( I-1, J ) + A( I+1, J ) + A( I, J-1 ) +

*A( I, J+1 )) + ( 1-W ) * A( I, J)

EPS = MAX ( EPS, ABS( S - A( I, J ))) !$OMP END ORDERED

!$OMP END DO

!$OMP END PARALLEL

21 CONTINUE

Стоимость = 22*8*8 + 18 = 1426

Количество приватных = 4

Время инициализации = 5

Время синхронизации переменных и удаления региона = 9

Итого: 18

Стоимость = 8*(22*8 + 16) = 1536

Количество приватных = 3

Время инициализации = 5

Время синхронизации переменных и удаления региона = 8

Итого: 16

Рис. 15. Сравнение вариантов распараллеливания в 2-м регионе программы "SOR" с директивой ORDERED.

!$OMP PARALLEL

!$ iam = omp_get_thread_num ()

!$ numt = omp_get_num_threads ()

!$ ISYNC (IAM) = 0

!$ ILIMIT=MIN(NUMT-1,N-1-2)

!$OMP BARRIER

DO 21 J = 2, N-1

!$OMP DO PRIVATE(S), REDUCTION(EPS,MAX)

!$ 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

DO 21 I = 2, N-1

S = A( I, J )

A( I, J ) = (W / 4) * (A( I-1, J ) + A( I+1, J ) + A( I, J-1 ) +

*A( I, J+1 )) + ( 1-W ) * A( I, J)

EPS = MAX ( EPS, ABS( S - A( I, J )))

!$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

!$OMP END DO

!$OMP BARRIER

!$OMP END PARALLEL

21 CONTINUE

Стоимость = 22*32+3+9+22 = 738

Количество действий конвейера = 32

Количество приватных = 3

Время инициализации конвейера без учета приватных = 5 + 4 = 9

Время синхронизации переменных и удаления региона = 3+5+4+3+3+4 = 22 (синхронизация приватных + инициализация региона + барьер до первого цикла + по барьеру во время инициализации каждой нити + по барьеру во время инициализации последующей нити + барьер в конце региона)

Рис. 16. Схема распараллеливания в 2-м регионе программы "SOR" при конвейерном варианте.

На Рис. 15 и Рис. 16 показаны варианты параллелизма, которые будут перебираться "Экспертом". Стоимость последовательная = 22*8*8=1408, следовательно, будет выбран вариант c конвейером.

4) Шаг 3 и Шаг 4

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

На шаге 4 получим выходную программу для варианта задачи с 4 процессорами:

program sor

parameter (n = 10)

real a(n,n),eps,maxeps,w

integer itmax

!$INTEGER OMP_GET_NUM_THREADS,OMP_GET_THREAD_NUM

!$INTEGER IAM, NUMT,ISYNC(4)

print *, '********** TEST_SOR **********'

itmax = 20

maxeps = 5.000000e-006

w = 5.000000e-001

!$OMP PARALLEL PRIVATE(i)

!$OMP DO

do j = 1,n

do i = 1,n

if (i .eq. j) then

a(i,j) = n + 2

else

a(i,j) = (-(1.0))

endif

enddo

!$OMP END DO

!$OMP END PARALLEL

do it = 1,20

eps = 0

!$OMP PARALLEL PRIVATE (IAM,NUMT,ILIMIT) PRIVATE(i) SHARED(a) PRIVATE(s) & &REDUCTION(MAX:eps)

!$ iam = omp_get_thread_num ()

!$ numt = omp_get_num_threads ()

!$ ISYNC (IAM) = 0

!$ ILIMIT=min(NUMT-1,n-1-2)

!$OMP BARRIER

do j = 2,n - 1

!$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

do i = 2,n - 1

s = a(i,j)

a(i,j) = 5.000000e-001 / 4 * (a(i - 1,j) + a(i + 1,j) + a

&(i,j - 1) + a(i,j + 1)) + (1 - 5.000000e-001) * a(i,j)

eps = max (eps,abs (s - a(i,j)))

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

!$OMP BARRIER

!$OMP END PARALLEL

print 200, it,eps

200 FORMAT(' IT = ',I4, ' EPS = ', E14.7)

if (eps .lt. 5.000000e-006) goto 4

enddo

4 open (unit = 3,file = 'SOR.DAT',form = 'FORMATTED',status = 'UNKNO

&WN')

write (unit = 3,fmt = *) a

close (unit = 3)

end

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

Общее время последовательного выполнения: 28343 у.е.

Общее время параллельного выполнения (4 нити): 14880 у.е.

Суммарное ускорение: в 1,9 раза

5.5.3 Программа "Модифицированный SOR"

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

1) Листинг последовательной программы

PROGRAM SOR

PARAMETER ( N = 10 )

REAL A( N, N ), B(N,N), EPS, MAXEPS, W

INTEGER ITMAX

PRINT *, '********** TEST_SOR **********'

ITMAX=20

MAXEPS = 0.5E - 5

W = 0.5

DO 1 J = 1, N

DO 1 I = 1, N

IF ( I .EQ.J) THEN

A( I, J ) = N + 2

ELSE

A( I, J ) = -1.0

ENDIF

1CONTINUE

DO 2 IT = 1, ITMAX

EPS = 0.

DO 21 J = 2, N-1

DO 21 I = 2, N-1

S = A(I,J)

A( I, J ) = (W / 4) * (A( I-1, J ) + A( I+1, J ) + A( I, J-1 ) +

*A( I, J+1 )) + ( 1-W ) * A( I+1, J+1)

B(I,J) = A(I,J)

EPS = MAX ( EPS, ABS( S - B( I, J )))

21CONTINUE

PRINT 200, IT, EPS

200 FORMAT(' IT = ',I4, ' EPS = ', E14.7)

IF (EPS .LT. MAXEPS ) GO TO 4

2CONTINUE

4 OPEN (3, FILE='SOR.DAT', FORM='FORMATTED',STATUS='UNKNOWN')

WRITE (3,*) A

CLOSE (3)

END

2) Работа "Эксперта"

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

2-й регион: циклы (4) и (5). Здесь будет рассмотрено 3 варианта, время последовательного исполнения первых 3 директив = 19, 4-й директивы = 4:

!$OMP PARALLEL PRIVATE(S) PRIVATE(I)

!$OMP DO REDUCTION(EPS,MAX)

DO 21 J = 2, N-1

DO 21 I = 2, N-1

!$OMP ORDERED

S = A(I,J)

A( I, J ) = (W / 4) * (A( I-1, J ) + A( I+1, J ) + A( I, J-1 ) +

*A( I, J+1 )) + ( 1-W ) * A( I+1, J+1)

B(I,J) = A(I,J)

!$OMP END ORDERED

EPS = MAX ( EPS, ABS( S - B( I, J )))

21CONTINUE

!$OMP END DO

!$OMP END PARALLEL

DO 21 J = 2, N-1

!$OMP PARALLEL PRIVATE(S)

!$OMP DO REDUCTION(EPS,MAX)

DO 21 I = 2, N-1

!$OMP ORDERED

S = A(I,J)

A( I, J ) = (W / 4) * (A( I-1, J ) + A( I+1, J ) + A( I, J-1 ) +

*A( I, J+1 )) + ( 1-W ) * A( I+1, J+1)

B(I,J) = A(I,J)

!$OMP END ORDERED

EPS = MAX ( EPS, ABS( S - B( I, J )))

!$OMP END DO

!$OMP END PARALLEL

21 CONTINUE

Стоимость = 19*8*8 + 4*8*8/4 + 18 = 1298

Количество приватных = 4

Время инициализации = 5

Время синхронизации переменных и удаления региона = 9

Итого: 18

Стоимость = 8*(19*8 + 4*8/4 + 16) = 1408

Количество приватных = 3

Время инициализации = 5

Время синхронизации переменных и удаления региона = 8

Итого: 16

Рис. 17. Сравнение вариантов распараллеливания в 2-м регионе программы "модифицированный SOR".

На Рис. 17 показаны возможные варианты параллелизма для данного региона. Как видно, случай с конвейером не будет рассмотрен, из-за того, что элемент A(I,J) зависит от "бокового" элемента A(I+1,J+1). Стоимость последовательная = 23*8*8=1472, следовательно, будет выбран 1-й вариант.

На выходе получим следующую программу:

program sor

parameter (n = 10)

real a(n,n),b(n,n),eps,maxeps,w

integer itmax

print *, '********** TEST_SOR **********'

itmax = 20

maxeps = 5.000000e-006

w = 5.000000e-001

!$OMP PARALLEL PRIVATE(i)

!$OMP DO

do j = 1,n

do i = 1,n

if (i .eq. j) then

a(i,j) = n + 2

else

a(i,j) = (-(1.0))

endif

enddo

!$OMP END DO

!$OMP END PARALLEL

do it = 1,20

eps = 0

!$OMP PARALLEL PRIVATE(i) SHARED(a) PRIVATE(s)

!$OMP DO ORDERED REDUCTION(MAX:eps)

do j = 2,n - 1

do i = 2,n - 1

!$OMP ORDERED

s = a(i,j)

a(i,j) = 5.000000e-001 / 4 * (a(i - 1,j) + a(i + 1,j) + a

&(i,j - 1) + a(i,j + 1)) + (1 - 5.000000e-001) * a(i + 1,j + 1)

b(i,j) = a(i,j)

!$OMP END ORDERED

eps = max (eps,abs (s - b(i,j)))

enddo

!$OMP END DO

!$OMP END PARALLEL

print 200, it,eps

200 FORMAT(' IT = ',I4, ' EPS = ', E14.7)

if (eps .lt. 5.000000e-006) goto 4

enddo

4 open (unit = 3,file = 'SOR.DAT',form = 'FORMATTED',status = 'UNKNO

&WN')

write (unit = 3,fmt = *) a

close (unit = 3)

end

Общее время последовательного выполнения: 29623 у.е.

Общее время параллельного выполнения (4 нити): 26143 у.е.

Суммарное ускорение: в 1,13 раза

5.5.4 Программа "Модифицированный Якоби"

Данный пример приведен для того, чтобы показать работу "Эксперта", при установке директивы NOWAIT. Исходная программа "Якоби" была изменена, чтобы проверка установки NOWAIT была успешна. Работа "Эксперта" на этом примере повторяет действия из пункта 5.5.1 за исключением того, что проверка установки NOWAIT даст положительный результат.

1) Листинг последовательной программы

PROGRAM JAC

PARAMETER (L=8, ITMAX=20)

REAL A(L,L), EPS, MAXEPS, B(L,L), C(L,L)

C arrays A and B with block distribution

PRINT *, '********** TEST_JACOBI **********'

MAXEPS = 0.5E - 7

Cnest of two parallel loops, iteration (i,j) will be executed on

Cprocessor, which is owner of element A(i,j)

DO 1 J = 1, L

DO 1 I = 1, L

A(I, J) = 0.

IF(I.EQ.1 .OR. J.EQ.1 .OR. I.EQ.L .OR. J.EQ.L) THEN

B(I, J) = 0.

ELSE

B(I, J) = ( 1. + I + J )

ENDIF

1 CONTINUE

DO 2 IT = 1, ITMAX

EPS = 0.

Cvariable EPS is used for calculation of maximum value

DO 21 J = 2, L-1

DO 21 I = 2, L-1

A(I, J) = B(I, J)

21 CONTINUE

CCopying shadow elements of array A from

Cneighbouring processors before loop execution

DO 22 J = 2, L-1

DO 22 I = 2, L-1

A(I, J) = (C( I-1, J ) + C( I, J-1 ) + C( I+1, J)+

* C( I, J+1 )) / 4

22 CONTINUE

PRINT 200, IT, EPS

200 FORMAT(' IT = ',I4, ' EPS = ', E14.7)

IF ( EPS . LT . MAXEPS ) GO TO 3

2 CONTINUE

3 OPEN (3, FILE='JAC.DAT', FORM='FORMATTED', STATUS='UNKNOWN')

WRITE (3,*) B

CLOSE (3)

END

2) Выходная программа

program jac

parameter (l = 8,itmax = 20)

real a(l,l),eps,maxeps,b(l,l),c(l,l)

! arrays A and B with block distribution

print *, '********** TEST_JACOBI **********'

maxeps = 5.000000e-008

!nest of two parallel loops, iteration (i,j) will be executed on

!processor, which is owner of element A(i,j)

!$OMP PARALLEL PRIVATE(i)

!$OMP DO

do j = 1,l

do i = 1,l

a(i,j) = 0.

if (i .eq. 1 .or. j .eq. 1 .or. i .eq. l .or. j .eq. l) then

b(i,j) = 0.

else

b(i,j) = 1. + i + j

endif

enddo

!$OMP END DO

!$OMP END PARALLEL

do it = 1,itmax

eps = 0

!variable EPS is used for calculation of maximum value

!$OMP PARALLEL PRIVATE(i)

!$OMP DO

do j = 2,l - 1

do i = 2,l - 1

a(i,j) = b(i,j)

enddo

!Copying shadow elements of array A from

!neighbouring processors before loop execution

!$OMP END DO NOWAIT

!$OMP DO

do j = 2,l - 1

do i = 2,l - 1

a(i,j) = (c(i - 1,j) + c(i,j - 1) + c(i + 1,j) + c(i,j +

&1)) / 4

enddo

!$OMP END DO

!$OMP END PARALLEL

print 200, it,0

200 FORMAT(' IT = ',I4, ' EPS = ', E14.7)

if (0 .lt. 5.000000e-008) goto 3

enddo

3 open (unit = 3,file = 'JAC.DAT',form = 'FORMATTED',status = 'UNKNO

&WN')

write (unit = 3,fmt = *) b

close (unit = 3)

end

Общее время последовательного выполнения: 7667 у.е.

Общее время параллельного выполнения (4 нити): 2471 у.е.

Суммарное ускорение: в 3,1 раза

6. Заключение

В рамках дипломной работы был реализован "Эксперт по распараллеливанию на мультипроцессор", как компонент "Системы автоматизации распараллеливания".

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

Проект реализован в программе Visual Studio .NET на языке C++. Общий объем программного кода, реализующего "Эксперт"- свыше 1800 строк.

Перечень принятых терминов
Потенциально Параллельный Цикл (ППЦ) - цикл, который можно распараллелить средствами OpenMP, не обязательно эффективно.

Цикл Неподдающийся Распараллеливанию (ЦНР) - циклы с зависимостями следующих видов:

1) содержащие ввод/вывод,

2) содержащие вызовы процедур,

3) содержащие выход из цикла,

4) содержащие неизвестные анализатору зависимости,

5) циклы, с которыми не справился анализатор.

Параллельный регион - последовательность циклов, линейных фрагментов, ветвлений, которая будет заключена в рамки !$OMP PARALLEL - !$OMP END PARALLEL.

Вариант параллелизма программы (Вариант параллелизма) - вариант директив OpenMP, описывающих параллельные области и параллельные циклы (без директив локализации переменных).

Вариант локализации переменных (Вариант локализации) - вариант директив локализации переменных. Для каждого варианта параллелизма может существовать несколько вариантов локализации.

Схема распараллеливания - фиксация одного варианта параллелизма и одного варианта локализации.

1-е внутреннее представление - дерево, по структуре схожее с деревом из Базы Данных, в котором помечены все ППЦ и для каждого ППЦ обозначены пометки для локализации. Является результатом работы 1-го шага.

2-е внутреннее представление - дерево, по структуре схожее с деревом из Базы Данных, в котором расставлены пометки, по которым в базу данных можно занести комментарии по распараллеливанию (Распараллеливание и Локализацию). Является результатом работы 3-го шага.

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

Проверка Альтернативного Распараллеливания - нахождения минимума оценочной функции между текущим 2-м внутренним представлением и неким другим (альтернативным) распараллеливанием, с фиксацией распараллеливания с минимальной оценочной функцией во 2-м внутреннем представлении.

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

Страницы: 1, 2