Залежність даних

Залежність даних в інформатиці є ситуація, в якій програмна заява (інструкція) відноситься до даних в попередній заяві. У теорії компіляції, метод використовується для виявлення залежностей даних між висловлюваннями (або інструкції) називається Аналіз залежностей.

Є три типи залежностей: дані, ім'я, та контроль.

Залежність даних ред.

Припускаючи твердження S1 і S2, S2, залежить від того, S1, якщо: [I(S1) ∩ O(S2)] ∪ [O(S1) ∩ I(S2)] ∪ [O(S1) ∩ O(S2)] ≠ Ø

де:

I (см) являє собою набір елементів пам'яті зчитується і Si
O (S) є безліч осередків пам'яті, написана Sj
i існує допустимий час виконання шляху виконання від S1 до S2

Цей стан називається Bernstein стан, названий А. Бернштейном.

Три випадки існують:

Flow (дані) залежність: O (S1) ∩ I (S2), S1 → S2 і S1 пише після того, як щось прочитаної S2
Антизалежність: I (S1) ∩ O (S2), S1 → S2 і S1 читає щось, перш ніж S2 переписує його
Вихідна залежність: O (S1) ∩ O (S2), S1 → S2 і обидва написати ту ж комірку пам'яті.

Потокова залежність ред.

Залежність потоку, також відомий як залежність даних або істинної залежності або читання після запису (RAW), відбувається, коли інструкція залежить від результату попередньої інструкції:

1. A = 3 2. B = A 3. C = B

Інструкція 3 дійсно залежить від інструкції 2, оскільки кінцеве значення C залежить від інструкції оновлюючи B. Інструкція 2 дійсно залежить від інструкції 1, бо остаточне значення B залежить від поновлення інструкції A. Через те, що інструкція 3 дійсно залежить Інструкція по 2 і 2 інструкції дійсно залежить від інструкції 1, 3 інструкція також дійсно залежить від інструкції 1. паралелізм на рівні команд тому не варіант в даному прикладі.

Антизалежність ред.

Антизалежність, також відомий як від запису після читання (WAR), має місце, коли інструкція вимагає значення, який пізніше був оновлений. У наступному прикладі, команда 2 антизалежить від інструкції 3 — впорядкування цих інструкцій не можуть бути змінені, вони також не можуть бути виконані паралельно (можлива зміна упорядкування команд), позаяк це може вплинути на кінцеве значення А.

1. B = 3
2. A = B + 1
3. B = 7

Антизалежність є прикладом імені залежності. Тобто, перейменування змінних можна було видалити залежність, як в наступному прикладі:

1. B = 3
N. B2 = B
2. A = B2 + 1
3. B = 7

Нова змінна, B2, був оголошений як копія B в новій інструкції, інструкції N. антизалежність між 2 і 3 був видалений, а це означає, що ці інструкції можуть бути в цей час виконуються паралельно. Проте, модифікація представила нову залежність: інструкція 2 тепер дійсно залежить від інструкції N, який дійсно залежить від інструкції 1. Залежно потоку, ці нові залежності неможливо безпечно видалити.

Вихідна залежність ред.

Вихідна залежність, також відома як записи після запису (WAW), має місце, коли впорядкованість інструкцій впливатиме на кінцеве вихідне значення змінної. У прикладі, наведеному нижче, є вихід залежність між командами 3 і 1 — зміна порядку інструкцій в цьому прикладі буде змінюватися кінцеве значення A, таким чином, ці інструкції не можуть бути виконані паралельно.

1. B = 3
2. A = B + 1
3. B = 7

Як і з антизалежностей, залежностей вихідних є залежностями імен. Тобто, вони можуть бути видалені за допомогою перейменування змінних, як в наведеному нижче модифікації наведеного вище прикладу:

1. B2 = 3
2. A = B2 + 1
3. B = 7

Зазвичай використовується для іменування залежностей даних є наступне: для читання після запису або RAW (залежність потоку), запис після запису або WAW (вихід залежностей) і Write-Після читання або WAR (антизалежність).

Контроль залежностей ред.

Інструкція B має залежність управління від попередньої команди А якщо результат А визначає, чи слід виконувати B чи ні. У наступному прикладі, S2 інструкція має залежність управління по інструкції S1. Проте, S3 не залежить від S1 S3, тому що завжди виконується незалежно від результату S1.

S1. if (a == b)
S2.     a = a + b
S3. b = a + b

Інтуїтивно зрозуміло, що існує контроль залежність між двома твердженнями А і В, якщо

B може бути, можливо, після того, як виконується А
Підсумки виконання визначатиме, чи буде виконуватися B чи ні.

Типовим прикладом є те, що існують керуючі залежності між станом частині, якщо заяву і заяви в його справжніх / помилкових тел.

Формальне визначення залежності управління може бути представлена наступним чином: Заява S2 називається управління залежить від іншого заяву S1 тоді і тільки тоді

існує шлях P від S1 до S2 таким чином, що кожне твердження Si ≠ S1 в P буде супроводжуватися S2 в кожному можливому шляху до кінця програми та
S1 не обов'язково повинні слідувати S2, тобто є шлях до виконуваних від S1 до кінця програми, яка не проходить через S2.

Виражений за допомогою (пост-) домінування дві умови еквівалентні

S2 постдомінує все Si
S2 НЕ пост-S1 домінувати над

Побудова управління залежностями ред.

Залежно управління, по суті, домінування кордону у зворотному графіку графа потоку управління (CFG). [2] Таким чином, один зі способів їх побудови, було б побудувати постдомінантності кордон КТГ, а потім заднім ходом його отримання контроль граф залежностей.

Нижче наведено псевдокод для побудови постдомінантності кордону: for each X in a bottom-up traversal of the dominator tree do:

 PostDominanceFrontier(X) ← ∅
 for each Y ∈ Predecessors(X) do:
   if immediatePostDominator(Y) ≠ X:
     then PostDominanceFrontier(X) ← PostDominanceFrontier(X) ∪ {Y}
 done
 for each Z ∈ Children(X) do:
   for each Y ∈ PostDominanceFrontier(Z) do:
     if immediatePostDominator(Y) ≠ X:
       then PostDominanceFrontier(X) ← PostDominanceFrontier(X) ∪ {Y}
   done
 done

Тут діти (X) є безліч вузлів у CFG, які після домінують X і Попередники (X) є набором вузлів у CFG, які безпосередньо передують X у CFG.

Після того, як постдомінантність кордону карти обчислюється, звертає його призведе до карти від вузлів у CFG до вузлів, які мають залежність управління від них.

Наслідки ред.

Звичайні програми написані в припущенні моделі послідовного виконання. В рамках цієї моделі інструкції виконуються один за іншим, атомарному (тобто в будь-який даний момент часу тільки одна команда виконується) і в порядку, зазначеному в програмі.

Однак залежності між заяв або інструкцій може перешкоджати паралелізм — паралельне виконання декількох інструкцій, або за допомогою розпаралелювати компілятора або процесором експлуататорського на рівні інструкцій паралелізм. Нерозважливо виконання кількох команд без урахування пов'язаних залежностей може привести до небезпеки отримання неправильних результатів, а саме небезпеки.

Див. також ред.

Граф залежностей

Література ред.

John L. Hennessy, David A. Patterson (). Computer Architecture: a quantitative approach (3rd ed.). Morgan Kaufmann, 2003. — ISBN 1-55860-724-2. (англ.)
Cytron R. Ferrante J., Rosen B. K., Wegman M. N., Zadeck F. K. (1989-01-01). «An Efficient Method of Computing Static Single Assignment Form». Proceedings of the 16th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. POPL '89 (New York, NY, USA: ACM): 25–35. doi:10.1145/75277.75280. — ISBN 0897912942. (англ.)