Анализ зависимости цикла

В информатике с анализ зависимостей цикла — это процесс, который можно использовать для поиска зависимостей внутри итераций цикла целью определения различных отношений между операторами. Эти зависимые отношения связаны с порядком, в котором различные операторы обращаются к областям памяти. Используя анализ этих взаимосвязей, можно организовать выполнение цикла так, чтобы несколько процессоров могли работать над разными частями цикла параллельно. Это известно как параллельная обработка . В общем, циклы могут занимать много времени обработки при выполнении в виде последовательного кода . Благодаря параллельной обработке можно сократить общее время выполнения программы за счет распределения вычислительной нагрузки между несколькими процессорами.

Процесс организации операторов, позволяющий нескольким процессорам работать над разными частями цикла, часто называют распараллеливанием . Чтобы увидеть, как мы можем использовать распараллеливание, нам нужно сначала проанализировать зависимости внутри отдельных циклов. Эти зависимости помогут определить, какие инструкции в цикле необходимо выполнить, прежде чем смогут начаться другие инструкции, и какие инструкции в цикле могут выполняться параллельно по отношению к другим инструкциям в цикле. Две общие категории зависимостей, которые будут анализироваться в цикле, — это зависимости данных и зависимости управления .

Описание

Анализ зависимости цикла происходит на нормализованном цикле вида:

for i₁ until U₁ do
  for i₂ until U₂ do
    ...
    for i_n until U_n do
      body
    done
    ...
  done
done

где тело может содержать:

S1  a[f₁(i₁, ..., i_n), ..., f_m(i₁, ..., i_n)] := ...
    ...
S2  ... := a[h₁(i₁, ..., i_n), ..., h_m(i₁, ..., i_n)]

Где a — m-мерный массив и ж _н, час _ни т. д. — это функции, отображающие все индексы итерации (i _n ) на доступ к памяти в определенном измерении массива.

Например, в С:

for (i = 0; i < U1; i++)
  for (j = 0; j < U2; j++)
    a[i+4-j] = b[2*i-j] + i*j;

f ₁ будет я+4-дж , управление записью в первом измерении a и h ₂ будет 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: a = 5;
S2: b = a;

В этом примере существует истинная зависимость между S1 и S2, поскольку переменная a сначала записывается в операторе S1, а затем переменная a считывается оператором S2. Эту истинную зависимость можно представить как S1 →T S2. Истинную зависимость также можно увидеть при чтении и записи между различными итерациями в цикле. Следующий пример показывает истинную зависимость между различными итерациями.

for (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: a = b;
S2: b = 5;

В этом примере существует антизависимость между утверждениями S1 и S2. Это антизависимость, поскольку переменная b сначала считывается в операторе S1, а затем в переменную b записывается в операторе S2. Это можно представить как S1 →A S2. Антизависимость можно увидеть по различным итерациям цикла. В следующем примере показан пример этого случая:

for (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. Выходную зависимость можно увидеть по различным итерациям цикла. В следующем фрагменте кода показан пример этого случая:

for (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]

// Code block 1 (CORRECT)
if (a == b) {
   c = "controlled";
}
d = "uncontrolled";

// Code block 2 (INCORRECT)
if (a == b) {
}
c = "controlled";
d = "uncontrolled";

// Code block 3 (INCORRECT)
if (a == b) {
   c = "controlled";
   d = "uncontrolled";
}

В этом примере проиллюстрированы ограничения на поток управления. Блок кода 1 показывает правильный порядок использования оператора if в языке программирования C. Блок кода 2 иллюстрирует проблему, когда оператор, который должен управляться оператором if, больше не контролируется им. Блок кода 3 иллюстрирует проблему, когда оператор, который не должен контролироваться оператором «if», теперь перешел под его контроль. Обе эти две возможности могут привести к неправильному выполнению программы и их следует учитывать при распараллеливании этих операторов внутри цикла.

Зависимость, переносимая в цикле, и зависимость, независимая от цикла

Зависимости, переносимые циклом, и зависимости, независимые от цикла, определяются отношениями между операторами в итерациях цикла. Когда оператор в одной итерации цикла каким-то образом зависит от оператора в другой итерации того же цикла, существует зависимость, переносимая циклом. ^[1]^[2]^[3] Однако если оператор в одной итерации цикла зависит только от оператора в той же итерации цикла, это создает независимую от цикла зависимость. ^[1]^[2]^[3]

// Code block 1
for (i = 1; i <= 4; i++) {
   S1: b[i] = 8;
   S2: a[i] = b[i-1] + 10;
}

// Code block 2
for (i = 0; i < 4; i++) {
   S1: b[i] = 8;
   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] Граф обхода итерационного пространства и график зависимости, переносимый циклом: Граф обхода итерационного пространства: График зависимости, переносимый циклом:

График зависимости с циклическим переносом (LDG)

Граф обхода итерационного пространства (ITG)

См. также

Ссылки

^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г Солихин, Ян (2016). Основы параллельной компьютерной архитектуры: многокристальные и многоядерные системы . [США?]: Солихин Паб. ISBN 978-1-4822-1118-4 .
^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час Деван, Прадип; Камат, РК (2014). «Обзор — анализ зависимостей LOOP для распараллеливающего компилятора». Международный журнал компьютерных наук и информационных технологий . 5 .
^ Jump up to: ^а ^б ^с ^д ^и ^ж Джон, Хеннесси; Паттерсон, Дэвид (2012). «Глава третья, параллелизм на уровне инструкций и его использование». Архитектура компьютера. Количественный подход . Издательство Морган Кауфманн. стр. 152–156. ISBN 978-0-12-383872-8 .
^ Аллен-младший; Кеннеди, Кен; Портерфилд, Кэрри; Уоррен, Джо (1 января 1983 г.). «Преобразование зависимости управления в зависимость данных». Материалы 10-го симпозиума ACM SIGACT-SIGPLAN по принципам языков программирования - POPL '83 . ПОПЛ '83. Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 177–189. дои : 10.1145/567067.567085 . ISBN 0897910907 . S2CID 39279813 .

[Solihin_Parallel_Computer_Book-1] Jump up to: ^а ^б ^с ^д ^и ^ж ^г Солихин, Ян (2016). Основы параллельной компьютерной архитектуры: многокристальные и многоядерные системы . [США?]: Солихин Паб. ISBN 978-1-4822-1118-4 .

[Loop_dependence_journal-2] Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час Деван, Прадип; Камат, РК (2014). «Обзор — анализ зависимостей LOOP для распараллеливающего компилятора». Международный журнал компьютерных наук и информационных технологий . 5 .

[:0-3] Jump up to: ^а ^б ^с ^д ^и ^ж Джон, Хеннесси; Паттерсон, Дэвид (2012). «Глава третья, параллелизм на уровне инструкций и его использование». Архитектура компьютера. Количественный подход . Издательство Морган Кауфманн. стр. 152–156. ISBN 978-0-12-383872-8 .

[4] Аллен-младший; Кеннеди, Кен; Портерфилд, Кэрри; Уоррен, Джо (1 января 1983 г.). «Преобразование зависимости управления в зависимость данных». Материалы 10-го симпозиума ACM SIGACT-SIGPLAN по принципам языков программирования - POPL '83 . ПОПЛ '83. Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 177–189. дои : 10.1145/567067.567085 . ISBN 0897910907 . S2CID 39279813 .

[1]

[2]

[3]

[4]