В информатике анализ зависимостей цикла — это процесс, который можно использовать для поиска зависимостей внутри итераций цикла с целью определения различных отношений между операторами. Эти зависимые отношения связаны с порядком, в котором различные операторы обращаются к областям памяти. Используя анализ этих взаимосвязей, выполнение цикла можно организовать так, чтобы несколько процессоров могли работать над разными частями цикла параллельно. Это известно как параллельная обработка . В общем, циклы могут занимать много времени обработки при выполнении в виде последовательного кода . Благодаря параллельной обработке можно сократить общее время выполнения программы за счет распределения вычислительной нагрузки между несколькими процессорами.
Процесс организации операторов, позволяющий нескольким процессорам работать над разными частями цикла, часто называют распараллеливанием . Чтобы увидеть, как мы можем использовать распараллеливание, нам нужно сначала проанализировать зависимости внутри отдельных циклов. Эти зависимости помогут определить, какие инструкции в цикле необходимо выполнить, прежде чем смогут начаться другие инструкции, и какие инструкции в цикле могут выполняться параллельно по отношению к другим инструкциям в цикле. Две общие категории зависимостей, которые будут анализироваться в цикле, — это зависимости данных и зависимости управления .
Анализ зависимости цикла происходит на нормализованном цикле вида:
для меня 1 , пока ты 1 не сделаешь ибо я 2 , пока U 2 не сделаю ... пока я не сделаю тело сделанный ... сделанныйсделанный
гдетеломожет содержать:
S1 a[f 1 (i 1 , ..., я n ), ..., f m (i 1 , ..., я n )] := ... ...S2 ... := a[h 1 (i 1 , ..., я n ), ..., h m (i 1 , ..., я n )]
Где a — m-мерный массив иж н,час ни т. д. — это функции, отображающие все индексы итерации (i n ) на доступ к памяти в определенном измерении массива.
Например, в С:
для ( я знак равно 0 ; я < U1 ; я ++ ) для ( j знак равно 0 ; j < U2 ; j ++ ) а [ я + 4 - j ] = б [ 2 * я - j ] + я * j ; f 1 будетя+4-дж, управление записью в первом измерении a и h 2 будет2*идж, управляя чтением по первому измерению b .
Задача состоит в том, чтобы найти все возможные зависимости между S1 и S2 . Чтобы быть консервативным, любая зависимость, ложность которой не может быть доказана, должна считаться истинной.
Независимость демонстрируется путем демонстрации того, что никакие два экземпляра S1 и S2 не получают доступ к одному и тому же месту в массиве и не изменяют его.а. Когда обнаруживается возможная зависимость, анализ циклической зависимости обычно делает все возможное, чтобы охарактеризовать отношения между зависимыми экземплярами, поскольку некоторые оптимизации все еще могут быть возможны. Также возможно преобразовать цикл, чтобы удалить или изменить зависимость.
В ходе доказательства или опровержения таких зависимостей утверждение S может быть разложено в зависимости от того, из какой итерации оно получено. Например, S [1,3,5] относится к итерации, гдея1 = 1,я2 = 3ия3 = 5. Конечно, ссылки на абстрактные итерации, такие как S [ d1 +1, d2 , d3 ], разрешены и распространены.
Зависимости данных показывают отношения между переменными в коде. Существует три различных типа зависимостей данных:
Настоящая зависимость возникает, когда ячейка памяти записывается до того, как она будет прочитана. [1] [2] [3] Это создает опасность чтения после записи (RAW), поскольку инструкция, которая читает из ячейки памяти, должна ждать, пока она не будет записана предыдущей инструкцией, иначе инструкция чтения прочитает Неверное значение. [2] Пример истинной зависимости:
S1 : а = 5 ; S2 : б = а ; В этом примере существует истинная зависимость между S1 и S2, поскольку переменная a сначала записывается в операторе S1, а затем переменная a считывается оператором S2. Эту истинную зависимость можно представить как S1 →T S2. Истинную зависимость также можно увидеть при чтении и записи между различными итерациями в цикле. Следующий пример показывает истинную зависимость между различными итерациями.
для ( j знак равно 1 ; j < n ; j ++ ) S1 : а [ j ] = а [ j -1 ]; В этом примере существует истинная зависимость между утверждением S1 на j-й итерации и S1 на j+1-й итерации. Существует истинная зависимость, поскольку значение будет записано в a[j] на одной итерации, а затем произойдет чтение с помощью a[j-1] на следующей итерации. Эту истинную зависимость можно представить как S1[j] →T S1[j+1].
Антизависимость возникает, когда ячейка памяти считывается до того , как в нее записывается. [1] [2] [3] Это приводит к возникновению опасности записи после чтения (WAR), поскольку инструкция, записывающая данные в ячейку памяти, должна ждать, пока эта ячейка памяти не будет прочитана предыдущей инструкцией или же командой чтения. будет читать неправильное значение. [2] Примером антизависимости является:
S1 : а = б ; С2 : б = 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 : с = 8 ; S2 : с = 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». Операторы «if» создают ветки в программе. Часть «then» оператора «if» явно указывает или контролирует действия, которые необходимо предпринять. [3]
В этом примере проиллюстрированы ограничения на поток управления. Блок кода 1 показывает правильный порядок использования оператора if в языке программирования C. Блок кода 2 иллюстрирует проблему, когда оператор, который должен был контролироваться оператором if, больше не контролируется им. Блок кода 3 иллюстрирует проблему, когда оператор, который не должен контролироваться оператором «if», теперь перешел под его контроль. Обе эти две возможности могут привести к неправильному выполнению программы и их следует учитывать при распараллеливании этих операторов внутри цикла.
Зависимости, переносимые циклом, и зависимости, независимые от цикла, определяются отношениями между операторами в итерациях цикла. Когда оператор в одной итерации цикла каким-то образом зависит от оператора в другой итерации того же цикла, существует зависимость, переносимая циклом. [1] [2] [3] Однако, если оператор в одной итерации цикла зависит только от оператора в той же итерации цикла, это создает независимую от цикла зависимость. [1] [2] [3]
В этом примере блок кода 1 показывает зависимую от цикла зависимость между итерацией i оператора S2 и итерацией i-1 оператора S1. Это означает, что оператор S2 не может продолжаться до тех пор, пока не завершится оператор S1 на предыдущей итерации. Блок кода 2 показывает независимую от цикла зависимость между операторами S1 и S2 в одной итерации.
Графы обхода пространства итераций (ITG) показывают путь, который проходит код при прохождении итераций цикла. [1] Каждая итерация представлена узлом. Графы зависимостей, переносимые циклом (LDG), дают визуальное представление всех истинных зависимостей, антизависимостей и выходных зависимостей, которые существуют между различными итерациями в цикле. [1] Каждая итерация представлена узлом.
Разницу между двумя графиками проще показать с помощью вложенного цикла for.
для ( я знак равно 0 ; я < 4 ; я ++ ) для ( j знак равно 0 ; j < 4 ; j ++ ) S1 : а [ я ][ j ] = а [ я ][ j -1 ] * x ; В этом примере существует истинная зависимость между j-й итерацией оператора S1 и j+1-м оператором S1. Это можно представить как S1[i,j] →T S1[i,j+1] Граф обхода итерационного пространства и график зависимости, переносимый циклом: Граф обхода итерационного пространства: График зависимости, переносимый циклом:
