Анализ зависимостей цикла - это процесс, который можно использовать для поиска зависимостей в пределах итераций цикла с целью определения различных отношений между операторами. Эти зависимые отношения привязаны к порядку, в котором различные операторы обращаются к ячейкам памяти. Используя анализ этих взаимосвязей, можно организовать выполнение цикла, чтобы позволить нескольким процессорам работать над разными частями цикла параллельно. Это называется параллельной обработкой . Как правило, циклы могут занимать много времени обработки при выполнении в виде последовательного кода . Благодаря параллельной обработке можно сократить общее время выполнения программы за счет распределения нагрузки обработки между несколькими процессорами.
Процесс организации операторов, позволяющий нескольким процессорам работать с разными частями цикла, часто называют распараллеливанием . Чтобы увидеть, как мы можем использовать распараллеливание, мы должны сначала проанализировать зависимости внутри отдельных циклов. Эти зависимости помогут определить, какие операторы в цикле должны быть выполнены, прежде чем другие операторы могут начаться, и какие операторы в цикле могут выполняться параллельно с другими операторами в цикле. Две общие категории зависимостей, которые будут анализироваться в цикле, - это зависимости данных и зависимости управления.
Описание
Анализ петлевой зависимости выполняется на нормализованном цикле вида:
для i 1 до U 1 делать для i 2 до U 2 делать ... для г п до U п сделать тело Выполнено ... ВыполненоВыполнено
где тело может содержать:
S1 a [f 1 (i 1 , ..., i n ), ..., f m (i 1 , ..., i n )]: = ... ...S2 ...: = a [h 1 (i 1 , ..., i n ), ..., h m (i 1 , ..., i n )]
Где a - m-мерный массив иf n, ч пи т. д. - это функции, отображающие все итерационные индексы (i n ) на доступ к памяти в конкретном измерении массива.
Например, в C:
for ( i = 0 ; i < U1 ; i ++ ) for ( j = 0 ; j < U2 ; j ++ ) a [ i + 4 - j ] = b [ 2 * i - j ] + i * j ;
f 1 будетя + 4-j, управление записью в первом измерении a и h 2 будет2 * ij, контролируя чтение по первому измерению b .
Задача состоит в том, чтобы найти все возможные зависимости между S1 и S2 . Чтобы быть консервативным, любая зависимость, ложность которой не может быть доказана, должна считаться истинной.
Независимость демонстрируется путем демонстрации того, что никакие два экземпляра S1 и S2 не обращаются или не изменяют одно и то же место в массиве.а. Когда возможная зависимость обнаружена, анализ зависимости цикла обычно делает все возможное, чтобы охарактеризовать отношения между зависимыми экземплярами, поскольку некоторые оптимизации все еще возможны. Также можно преобразовать цикл, чтобы удалить или изменить зависимость.
В ходе доказательства или опровержения таких зависимостей оператор S может быть разложен в зависимости от того, на какой итерации он исходит. Например, S [1,3,5] относится к итерации, гдеi1 = 1, i2 = 3 а также i3 = 5. Конечно, ссылки на абстрактные итерации, такие как S [ d1 +1, d2 , d3 ], разрешены и распространены.
Зависимость от данных
Зависимости данных показывают отношения между переменными в коде. Есть три разных типа зависимостей данных:
- Истинная зависимость (иногда называемая зависимостью от потока)
- Анти-зависимость
- Выходная зависимость
Истинная зависимость
Истинная зависимость возникает , когда место в памяти записывается перед его читать. [1] [2] [3] Это представляет опасность чтения после записи (RAW), потому что инструкция, которая читает из места в памяти, должна ждать, пока она не будет записана предыдущей инструкцией, иначе инструкция чтения прочитает Неверное значение. [2] Пример истинной зависимости:
S1 : а = 5 ; S2 : b = а ;
В этом примере существует истинная зависимость между S1 и S2, поскольку переменная a сначала записывается в операторе S1, а затем переменная a читается оператором S2. Эта истинная зависимость может быть представлена как S1 → T S2.
Истинная зависимость также может быть замечена при чтении и записи между разными итерациями в цикле. В следующем примере показана истинная зависимость между разными итерациями.
для ( j = 1 ; j < n ; j ++ ) S1 : a [ j ] = a [ j -1 ];
В этом примере существует истинная зависимость между оператором S1 на j-й итерации и S1 на j + 1-й итерации. Существует истинная зависимость, потому что значение будет записано в [j] в одной итерации, а затем будет выполнено чтение [j-1] в следующей итерации. Эта истинная зависимость может быть представлена как S1 [j] → T S1 [j + 1].
Анти-зависимость
Анти зависимость возникает , когда место в памяти считывается до того, что же место записывается. [1] [2] [3] Это представляет опасность записи после чтения (WAR), потому что инструкция, которая записывает данные в ячейку памяти, должна ждать, пока эта ячейка памяти не будет прочитана предыдущей инструкцией или же инструкцией чтения прочитал бы неправильное значение. [2] Пример антизависимости:
S1 : а = b ; S2 : b = 5 ;
В этом примере существует противоположная зависимость между операторами S1 и S2. Это антизависимость, потому что переменная b сначала считывается в операторе S1, а затем переменная b записывается в операторе S2. Это может быть представлено как S1 → A S2. Анти-зависимость можно увидеть в разных итерациях цикла. В следующем примере показан пример этого случая:
для ( j = 0 ; j < n ; j ++ ) S1 : b [ j ] = b [ j + 1 ];
В этом примере существует анти-зависимость между j-й итерацией S1 и j + 1-м элементом S1. Здесь j + 1-й элемент считывается до того, как этот же элемент будет записан на следующей итерации j. Эту антизависимость можно представить как S1 [j] → A S1 [j + 1].
Выходная зависимость
Выход зависимость возникает , когда место в памяти записывается до этого же место записываются снова в другом заявлении. [1] [2] [3] Это представляет опасность записи после записи (WAW), потому что вторая инструкция для записи значения в ячейку памяти должна ждать, пока первая инструкция закончит запись данных в ту же ячейку памяти, или когда ячейка памяти читается позже, она будет содержать неправильное значение. [2] Пример выходной зависимости:
S1 : c = 8 ; S2 : c = 15 ;
В этом примере есть выходная зависимость между операторами S1 и S2. Здесь переменная c сначала записывается в S1, а затем переменная c снова записывается в операторе S2. Эта выходная зависимость может быть представлена как S1 → O S2. Выходную зависимость можно увидеть на разных итерациях цикла. В следующем фрагменте кода показан пример этого случая:
для ( j = 0 ; j < n ; j ++ ) S1 : c [ j ] = j ; S2 : c [ j + 1 ] = 5 ;
В этом примере существует выходная зависимость между j-м элементом в S1 и j + 1-м элементом в S2. Здесь c [j + 1] в операторе S2 записывается за одну итерацию. В следующей итерации c [j] в операторе S2, который является той же ячейкой памяти, что и c [j + 1] в предыдущей итерации, записывается снова. Эта выходная зависимость может быть представлена как S1 [j] → O S2 [j + 1].
Зависимость управления
Зависимости управления также необходимо учитывать при анализе зависимостей между различными операторами в цикле. Зависимости управления - это зависимости, вводимые кодом или самим алгоритмом программирования. Они контролируют порядок, в котором инструкции выполняются при выполнении кода. [4] Одним из распространенных примеров является оператор «если». Операторы "if" создают ветки в программе. Часть «then» в выражении «if» явно направляет или контролирует действия, которые необходимо предпринять. [3]
// Блок кода 1 (ПРАВИЛЬНО) // Блок кода 2 (НЕПРАВИЛЬНО) // Блок кода 3 (НЕПРАВИЛЬНО) if ( a == b ) then { if ( a == b ) then { if ( a == b ) then { c = "контролируемый" ; } c = "контролируемый" ; } c = "контролируемый" ; d = "не контролируется" ; d = "не контролируется" ; d = "не контролируется" ; }
В этом примере проиллюстрированы ограничения на поток управления. Блок кода 1 показывает правильный порядок при использовании оператора if на языке программирования C. Блок кода 2 иллюстрирует проблему, когда оператор, который должен управляться оператором if, больше не управляется им. Блок кода 3 иллюстрирует проблему, когда оператор, который не должен контролироваться оператором «if», теперь перемещен под его управление. Обе эти возможности могут привести к неправильному выполнению программы и должны учитываться при распараллеливании этих операторов в цикле.
Циклическая зависимость против петлевой независимой зависимости
Зависимости, переносимые с помощью цикла, и зависимости, не зависящие от цикла, определяются отношениями между операторами в итерациях цикла. Когда оператор в одной итерации цикла каким-то образом зависит от оператора в другой итерации того же цикла, существует переносимая циклом зависимость. [1] [2] [3] Однако, если оператор в одной итерации цикла зависит только от оператора в той же итерации цикла, это создает независимую от цикла зависимость. [1] [2] [3]
// Кодовый блок 1 // Кодовый блок 2 для ( i = 1 ; i <= 4 ; i ++ ) for ( i = 0 ; i < 4 ; i ++ ) S1 : b [ i ] = 8 ; S1 : b [ i ] = 8 ; S2 : a [ i ] = b [ i -1 ] + 10 ; S2 : a [ i ] = b [ i ] + 10 ;
В этом примере кодовый блок 1 показывает зависящую от цикла зависимость между итерацией i-го оператора S2 и итерацией i-1 оператора S1. Это означает, что оператор S2 не может выполняться, пока не завершится оператор S1 в предыдущей итерации. Кодовый блок 2 показывает независимую от цикла зависимость между операторами S1 и S2 в одной итерации.
Графики циклических зависимостей и обхода итерационного пространства
Графики обхода пространства итераций (ITG) показывают путь, по которому проходит код при обходе итераций цикла. [1] Каждая итерация представлена узлом. Графики зависимостей с циклическим переносом (LDG) дают визуальное представление всех истинных зависимостей, антизависимостей и выходных зависимостей, которые существуют между различными итерациями в цикле. [1] Каждая итерация представлена узлом.
Разницу между двумя графиками легче показать с помощью вложенного цикла for.
for ( i = 0 ; i < 4 ; i ++ ) for ( j = 0 ; j < 4 ; j ++ ) S1 : a [ i ] [ j ] = a [ i ] [ j -1 ] * x ;
В этом примере существует истинная зависимость между j-й итерацией оператора S1 и j + 1-м оператором S1. Это может быть представлено как S1 [i, j] → T S1 [i, j + 1] Граф обхода итерационного пространства и граф зависимостей с переносом цикла: График обхода пространства итераций: График зависимостей с переносом цикла:
Смотрите также
Рекомендации
- ^ Б с д е е г Solihin, Ян (2016). Основы параллельной компьютерной архитектуры: многокристальные и многоядерные системы . [Соединенные Штаты?]: Паб Солихин. ISBN 978-1-4822-1118-4.
- ^ Б с д е е г ч Деван, Прадип; Камат, РК (2014). «Обзор - Анализ зависимостей LOOP для распараллеливающего компилятора». Международный журнал компьютерных наук и информационных технологий . 5 .
- ^ а б в г д е Джон, Хеннесси; Паттерсон, Дэвид (2012). Компьютерная архитектура - количественный подход . 225 Wyman Street, Waltham, MA 02451, США: Morgan Kaufmann Publishers. С. 152–156. DOI : 10.1016 / B978-0-12-383872-8.00003-3 (неактивен 31 мая 2021 г.). ISBN 978-0-12-383872-8.CS1 maint: location ( ссылка ) CS1 maint: DOI неактивен с мая 2021 года ( ссылка )
- ^ Аллен, младший; Кеннеди, Кен; Портерфилд, Кэрри; Уоррен, Джо (1983-01-01). «Преобразование зависимости управления в зависимость от данных». Материалы 10-го симпозиума ACM SIGACT-SIGPLAN по принципам языков программирования . ПОПЛ '83. Нью-Йорк, Нью-Йорк, США: ACM: 177–189. DOI : 10.1145 / 567067.567085 . ISBN 0897910907. S2CID 39279813 .