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