Первое внутреннее представление содержит информацию о локализации переменных.
Эта информация представляет собой 2 пары значений, по которым однозначно можно определить директиву OpenMP, с помощью которой переменная будет локализована в программе нужным способом.
Пометки проставляются для всех переменных, используемых внутри данного оператора. Все возможные пометки представлены в Таблице 2.
| 1-е значение 1-й пары (вид приватной) | 2-е значение 1-й пары - пометка приватной |
| private (поумолчанию)firstprivatelastprivatereduction | 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(имя переменной).
1) Оценочная функция стоимости параллельного региона вычисляется по следующей формуле:
Стоимость параллельного исполнения = (стоимость последовательного исполнения / число нитей + стоимость ordered) * число итераций + стоимость создания и удаления параллельной области стоимость последовательного исполнения
Это стоимость одной итерации цикла (предоставлена анализатором) без учета стоимости выражений, окруженных директивами Ordered/EndOrderedчисло нитей – количество "полезных" процессоров. Для цикла это значение равно минимуму из общего количества процессоров и количества итераций цикла.
стоимость ordered = стоимость последовательного исполнения выражений, окруженных директивами Ordered/EndOrdered.
стоимость создания и удаления параллельной области = const + стоимость создания m приватных переменных + стоимость синхронизации. Константа зависит от архитектуры системы и берется из базы данных или определяется пользователем. Это время, необходимое для создания (инициализации) и удаления параллельного региона.
стоимость создания mприватных переменных = m, где m это количество приватных переменных в данном параллельном регионе. Так как известно, что единица стоимости последовательного исполнения программы эквивалентна единичной записи в память, то для создания m локальных переменных возьмем время равное m"условных единиц". Это связано с тем, что для каждой нити необходимо инициализировать m переменных.
стоимость синхронизации = количество приватных переменных. Синхронизация происходит при закрытии параллельного цикла. При этом необходимо синхронизировать все локальные копии переменных. Стоимость барьерной синхронизации, зависящей от аппаратуры, учитывается в стоимости удаления параллельной области.
2) Оценочная функция стоимости вычисляется по следующей формуле:
Стоимость конвейера = стоимость действий внутри конвейера * количество действий конвейера + инициализация конвейера + синхронизация конвейера.
стоимость действий внутри конвейера = стоимость последовательного исполнения внутреннего цикла (конвейер возможен лишь для тесно вложенных циклов).
количество действий конвейера, количество действий, когда в работу задействована хотя бы 1 нить.
инициализация конвейера = const, зависит от архитектуры системы и берется из базы данных или определяется пользователем.
синхронизация конвейера = количество директив FLUSH, BARRIER и ENDDO * количество локальных переменных * количество действий конвейера.
3) Оценочная функция региона равна сумме всех оценочных функций членов региона.
Данные на входе: База Данных с результатами статического анализа.
Данные на выходе: 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-е внутреннее представление.
Данные на входе: База Данных с результатами статического анализа, 1-е внутреннее представление.
Данные на выходе: незаконченное 2-е внутреннее представление.
Как проходит преобразование входных данных в выходные:
Для ППЦ выбираем наилучший вариант комментариев. Одновременно создается 2-е внутреннее представление, отражающее наилучшую схему распараллеливания: перебором всех возможных вариантов распараллеливания и альтернативных локализаций. Поиск наилучшего распараллеливания происходит "снизу-вверх": сначала спускаемся на самый нижний уровень, находим распараллеливание для него, затем поднимаемся на 1 уровень выше и находим наилучшее представление для данного уровня и т.д. При нахождении наилучшего варианта распараллеливания на уровне пытаемся объединить подряд стоящие эффективные для распараллеливания циклы в параллельный регион. Если возникает конфликт локализации в регионе, он делится на регионы, в которых не будет конфликта.
На этом шаге обходим дерево из 1-ого внутреннего представления и выбираем наилучшую схему распараллеливания для вложенных ППЦ и объединяем в параллельные регионы "соседние" ППЦ. Для параллельных регионов перебираем все возможные варианты комментариев с фиксированием наилучшего из них во 2-м внутреннем представлении.
Алгоритм преобразования входных данных в выходные:
Проходим вершины дерева из 1-го внутреннего представления. Изначально все ППЦ помечаются как не пройденные. Продолжаем действия, пока не останется не пройденных ППЦ.
Основные действия шага 2:
1) Находим ППЦ наибольшего уровня (т.е. самый "низший" по вложенности) и делаем уровень найденного цикла текущим.
2) Для всех циклов текущего уровня сравниваем 3 оценочных функции:
a) оценочная функция для последовательного варианта,
b) оценочная функция при распараллеливании данного цикла,
c) оценочная функция при распараллеливании вложенных циклов, при том, что данный цикл остается последовательным (этот вариант оценивается только, если существуют вложенные ППЦ).
3) Если минимальна функция a), то цикл помечается как неэффективный для распараллеливания. Если минимальна функция b), то цикл помечается как эффективный для распараллеливания и добавляется в параллельный регион. Вложенные циклы, признанные эффективными для распараллеливания становятся неэффективными для распараллеливания. Если минимальна функция с), то никаких действий не происходит.
4) Циклы, для которых распараллеливание эффективно (минимальна функция b) добавляются в параллельный регион. Если на текущем уровне уже есть параллельный регион, причем последний пройденный цикл соседствует с текущим, то производится проверка на отсутствие конфликтов локализаций, если текущий цикл будет добавлен в параллельный регион. В случае отсутствия конфликтов, текущий цикл добавляется в регион. Если найдены конфликты локализации, или предыдущий цикл на уровне не соседствует с текущим, или текущий цикл первый на уровне, то для цикла создается новый параллельный регион. Если в параллельный регион добавляется цикл, то происходит проверка на установку Nowait.