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

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

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

Залежність данихРедагувати

Припускаючи твердження 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 (2003). Computer Architecture: a quantitative approach (3rd ed.). Morgan Kaufmann. 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.