Рассмотрим более детально алгоритм работы Блока поиска DVM/OpenMP-вариантов. Его работу можно разбить на несколько этапов.

Этап 1. Подготовительная работа

Шаг 1.1. Переход от DVM-вариантов к DVM/OpenMP-вариантам.

Прежде всего, DVM-варианты следует перенести из внутреннего представления DVM-эксперта во внутреннее представление DVM/OpenMP-варианта. Внутреннее представление каждого DVM/OpenMP-варианта - это ассоциативный массив. Ключами ассоциативного массива являются номера строк программы, а значением - список DVM- и OpenMP-директив, которые следует вставить перед данной строкой. Соответственно, по окончанию данного этапа списки директив будут содержать только DVM-директивы.

Таким образом, из DVM-варианта мы получили DVM/OpenMP-вариант, в котором циклы распараллелены только на DVM. В дальнейшем мы будем добавлять в этот DVM/OpenMP-вариант директивы языка OpenMP.

Шаг 1.2. Добавление приватных особенностей для индексных переменных

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

Во Внутреннем представлении DVM-эксперта информация об этих особенностях не отражена. Добавляем в описание каждого цикла private-особенность для индексных переменных этих циклов, а также всех вложенных циклов.

Шаг 1.3 Добавление приватных особенностей для скаляров

Предположим, в теле цикла в некоторую скалярную переменную происходит запись, и между витками цикла отсутствуют зависимости по данным. Если оставить эту переменную общей для всех нитей, мы получим условие гонок (race-condition). Чтобы избежать этой ситуации, в описание цикла следует добавить private-особенность для данной переменной.

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

Подытожим: если в теле цикла в какую-нибудь скалярную переменную происходит запись, для неё в описание цикла следует добавить private-особенность.

Шаг 1.4 Добавление all_private особенностей

Из Базы данных может поступить информация о том, что какая-либо переменная является приватной на протяжении всей работы программы. Для отражения этого факта существует специальный комментарий all_private (см. раздел Специальные комментарии).

Чтобы добавить эту информацию в описания циклов, нужно сделать следующее:

· На этапе считывания особенностей из Базы данных запомнить список all_private переменных

· Добавить private-особенности для полученного списка переменных в описание всех циклов программы.

Этап 2. Распараллеливание DVM-вариантов на OpenMP

Теперь мы будем поочередно обрабатывать каждый DVM/OpenMP-вариант, который пока что распараллелен только на DVM, и пытаться распараллелить его на OpenMP. Мы будем распараллеливать только те гнезда циклов, которые распараллелены на DVM.

Итак, для каждого гнезда циклов, распараллеленного на DVM в DVM/OpenMP-варианте, выполняем следующие шаги:

Шаг 2.1. Сбор информации о циклах в гнезде.

Просматриваем дерево циклов программы. Нас будут интересовать только те циклы, которые распараллелены в DVM-варианте. Для формирования DVM/OpenMP-варианта распараллеливания программы, необходимо собрать следующую информацию о гнезде циклов:

· Список циклов, принадлежащих гнезду. Первый элемент цикла - внешний цикл.

· Количество итераций каждого цикла из гнезда (если точное значение вычислить невозможно, выбирается значение по умолчанию).

· Время выполнения одной итерации каждого цикла из гнезда.

· Проанализировать DVM-директиву CDVM$ PARALLEL ON и определить

o Как отображаются измерения массива на циклы из гнезда.

o На какие циклы из гнезда не распределены измерения массива.

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

Примечание:

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

Этот метод не может дать точного результата. Например, если все измерение массива распределено на узел, то ни клауза ACROSS, ни клауза SHADOW_RENEW не смогут сообщить о наличии регулярной зависимости.

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

Шаг 2.2. Формирование вариантов распараллеливания гнезда.

Этот шаг следует выполнить для каждого гнезда циклов, которое распараллелено в DVM-варианте.

Пробегаемся по списку циклов гнезда, и пытаемся поочередно распараллелить их на OpenMP. Пусть наше гнездо содержит M циклов. Пронумеруем циклы от 1 до M. Цикл с номером 1 - внешний. Первый вариант распараллеливания гнезда у нас уже есть - распараллелить внешний цикл на DVM, и не распараллеливать на OpenMP. Формируем еще M вариантов следующего вида: внешний цикл распараллелен на DVM, а i-й цикл гнезда распараллелен на OpenMP, где i принимает значения от 1 до М.

Возможны два способа для распараллеливания i-го цикла в гнезде:

Способ 1. Распараллеливание с использованием конвейера.

Если цикл соответствует измерению массива с регулярной зависимостью, для него невозможно независимое выполнение витков. Мы можем организовать конвейерное выполнение цикла при условии, что для него есть тесно-вложенный цикл (см. варианты 4.1 и 5.2). В противном случае, мы не будем распараллеливать этот цикл. Также, мы не сможем распараллелить цикл конвейером, если для записи этих двух циклов используется одна и та же метка.

Такой эффект вызван особенностью используемого алгоритма распараллеливания конвейером.

Итак, если цикл соответствует измерению массива с регулярной зависимостью, имеет тесно-вложенный цикл и для записи этих циклов не используется одна и та же метка, мы ставим для этого цикла метку "Распараллелен конвейером".

Способ 2. Распараллеливание без конвейера.

Если цикл не соответствует измерению массива с регулярной зависимостью, этот цикл распараллеливается без конвейера (см. варианты 1.1, 1.2, 3.1, 3.2, 5.1 и 5.3). Ставим для этого цикла метку "Распараллелен без конвейера".

Если ни один из способов не подошел, i-й цикл мы распараллеливать не будем. Также, если количество итераций i-го цикла достаточно мало (каждому узлу достанется не более одного витка цикла, то есть работать на узле будет не более одного ядра), цикл признается неэффективным для распараллеливания на OpenMP, и соответствующий вариант отбрасывается.

Шаг 2.3. Поиск наилучшего варианта распараллеливания гнезда.

С помощью оценочной функции (о ней мы поговорим далее), мы вычисляем приближенное время выполнения каждого варианта на SMP-кластере с заданным количеством узлов и ядер. Располагая прогнозируемым временем выполнения каждого варианта распараллеливания гнезда циклов, мы выбираем вариант с наименьшим временем. При оценке учитываем, каким способом мы распараллеливаем цикл - с использованием конвейера, или без.

Шаг 2.4. Вставка OpenMP-директив в DVM/OpenMP-вариант.

Итак, мы выбрали, как лучше всего распараллелить гнездо циклов: либо распараллеливаем на OpenMP один из циклов гнезда, либо не распараллеливаем ни один из них. Если мы приняли решение распараллелить i-й цикл в гнезде, нам нужно вставить OpenMP-директивы в DVM/OpenMP-вариант. Возможны два случая:

Случай 1. i-й цикл имеет метку "Распараллелен с конвейером".

Выполняем следующие действия:

1. Если это первый цикл, распараллеленный конвейером в DVM/OpenMP-варианте, в начало программы добавляем описание служебных переменных. Если имена служебных переменных уже заняты, генерируем для уникальные имена. Перед первым оператором в программе вставляем:

!$ INTEGER omp_get_num_threads, omp_get_thread_num

!$ INTEGER IAM, NUMT, ISYNC(<количество нитей>), ILIMIT

2. Добавляем в описание i-го цикла три особенности приватного типа - для переменных IAM, NUMT и ILIMIT.

3. Формируем директиву !$OMP PARALLEL. Для распараллеливания на OpenMP цикла с особенностями после директивы требуется вставить клаузы. Пробегаемся по списку особенностей.

3.1. Если особенность имеет тип private, first_private или last_private, для нее формируем клаузу PRIVATE (<список переменных>), FIRSTPRIVATE (<список переменных>) или LASTPRIVATE (<список переменных>). Отметим, что в списке особенностей одна и та же переменная может иметь одновременно две разных особенности - private и first_private (private и last_private). В этом случае переменную следует занести только в клаузу FIRSTPRIVATE (LASTPRIVATE).

3.2. Если особенность имеет тип reduction, для нее формируем клаузу REDUCTION(<операция>: <список переменных>). Для разных операций создается отдельная клауза REDUCTION.

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

5. Сразу после !$OMP PARALLEL <список клауз> добавляем инициализацию служебных переменных и барьерную синхронизацию нитей:

!$ iam = omp_get_thread_num ()

!$ numt = omp_get_num_threads ()

!$ ILIMIT=MIN(NUMT-1,<число витков i-го цикла>)

!$ ISYNC (IAM) = 0

!$OMP BARRIER

6. Перед заголовком i+1-го цикла добавляем инициализацию конвейера: ядро дожидается, пока предыдущее ядро выполнит очередную итерацию i-го цикла, и только после этого

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

7. Перед ENDDO i-го цикла добавляем операции по синхронизации работы ядер

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

8. После ENDDO i-го цикла обозначаем завершение параллельной области.

!$OMP END PARALLEL

Случай 2. i-й цикл имеет метку "Распараллелен без конвейера".

1. Формируем директиву !$OMP PARALLEL. Выполняем действия, описанные в пункте 3 предыдущего случая.

2. Обозначаем начало параллельной области и распределение витков цикла между ядрами. Вставляем сформированную директиву !$OMP PARALLEL с клаузами, а также директиву !$OMP DO SCHEDULE(STAITC), перед заголовком i-го цикла.

Страницы: 1, 2, 3, 4, 5, 6