Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
| Ця стаття є сирим з англійської мови. Можливо, вона створена за допомогою машинного перекладу або перекладачем, який недостатньо володіє обома мовами. (серпень 2019) |
| Ця стаття може містити помилки з англійської мови. |
Залежність даних в інформатиці є ситуація, в якій програмна заява (інструкція) відноситься до даних в попередній заяві. У теорії компіляції, метод використовується для виявлення залежностей даних між висловлюваннями (або інструкції) називається Аналіз залежностей.
Є три типи залежностей: дані, ім'я, та контроль.
Залежність даних
Припускаючи твердження 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. — . (англ.)
- 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. — . (англ.)
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Cya stattya ye sirim perekladom z anglijskoyi movi Mozhlivo vona stvorena za dopomogoyu mashinnogo perekladu abo perekladachem yakij nedostatno volodiye oboma movami Bud laska dopomozhit polipshiti pereklad serpen 2019 Cya stattya mozhe mistiti pomilki perekladu z anglijskoyi movi Bud laska dopomozhit polipshiti pereklad perevirivshi jogo yakist i pogodivshi vmist zi stilistichnimi pravilami Vikipediyi Original anglijskoyu movoyu Data dependency Zalezhnist danih v informatici ye situaciya v yakij programna zayava instrukciya vidnositsya do danih v poperednij zayavi U teoriyi kompilyaciyi metod vikoristovuyetsya dlya viyavlennya zalezhnostej danih mizh vislovlyuvannyami abo instrukciyi nazivayetsya Analiz zalezhnostej Ye tri tipi zalezhnostej dani im ya ta kontrol Zalezhnist danihPripuskayuchi tverdzhennya S1 i S2 S2 zalezhit vid togo S1 yaksho I S1 O S2 O S1 I S2 O S1 O S2 O de I sm yavlyaye soboyu nabir elementiv pam yati zchituyetsya i Si O S ye bezlich oseredkiv pam yati napisana Sj i isnuye dopustimij chas vikonannya shlyahu vikonannya vid S1 do S2 Cej stan nazivayetsya Bernstein stan nazvanij A Bernshtejnom Tri vipadki isnuyut Flow dani zalezhnist O S1 I S2 S1 S2 i S1 pishe pislya togo yak shos prochitanoyi S2 Antizalezhnist I S1 O S2 S1 S2 i S1 chitaye shos persh nizh S2 perepisuye jogo Vihidna zalezhnist O S1 O S2 S1 S2 i obidva napisati tu zh komirku pam yati Potokova zalezhnist Zalezhnist potoku takozh vidomij yak zalezhnist danih abo istinnoyi zalezhnosti abo chitannya pislya zapisu RAW vidbuvayetsya koli instrukciya zalezhit vid rezultatu poperednoyi instrukciyi 1 A 3 2 B A 3 C B Instrukciya 3 dijsno zalezhit vid instrukciyi 2 oskilki kinceve znachennya C zalezhit vid instrukciyi onovlyuyuchi B Instrukciya 2 dijsno zalezhit vid instrukciyi 1 bo ostatochne znachennya B zalezhit vid ponovlennya instrukciyi A Cherez te sho instrukciya 3 dijsno zalezhit Instrukciya po 2 i 2 instrukciyi dijsno zalezhit vid instrukciyi 1 3 instrukciya takozh dijsno zalezhit vid instrukciyi 1 paralelizm na rivni komand tomu ne variant v danomu prikladi Antizalezhnist Antizalezhnist takozh vidomij yak vid zapisu pislya chitannya WAR maye misce koli instrukciya vimagaye znachennya yakij piznishe buv onovlenij U nastupnomu prikladi komanda 2 antizalezhit vid instrukciyi 3 vporyadkuvannya cih instrukcij ne mozhut buti zmineni voni takozh ne mozhut buti vikonani paralelno mozhliva zmina uporyadkuvannya komand pozayak ce mozhe vplinuti na kinceve znachennya A 1 B 3 2 A B 1 3 B 7 Antizalezhnist ye prikladom imeni zalezhnosti Tobto perejmenuvannya zminnih mozhna bulo vidaliti zalezhnist yak v nastupnomu prikladi 1 B 3 N B2 B 2 A B2 1 3 B 7 Nova zminna B2 buv ogoloshenij yak kopiya B v novij instrukciyi instrukciyi N antizalezhnist mizh 2 i 3 buv vidalenij a ce oznachaye sho ci instrukciyi mozhut buti v cej chas vikonuyutsya paralelno Prote modifikaciya predstavila novu zalezhnist instrukciya 2 teper dijsno zalezhit vid instrukciyi N yakij dijsno zalezhit vid instrukciyi 1 Zalezhno potoku ci novi zalezhnosti nemozhlivo bezpechno vidaliti Vihidna zalezhnist Vihidna zalezhnist takozh vidoma yak zapisi pislya zapisu WAW maye misce koli vporyadkovanist instrukcij vplivatime na kinceve vihidne znachennya zminnoyi U prikladi navedenomu nizhche ye vihid zalezhnist mizh komandami 3 i 1 zmina poryadku instrukcij v comu prikladi bude zminyuvatisya kinceve znachennya A takim chinom ci instrukciyi ne mozhut buti vikonani paralelno 1 B 3 2 A B 1 3 B 7 Yak i z antizalezhnostej zalezhnostej vihidnih ye zalezhnostyami imen Tobto voni mozhut buti vidaleni za dopomogoyu perejmenuvannya zminnih yak v navedenomu nizhche modifikaciyi navedenogo vishe prikladu 1 B2 3 2 A B2 1 3 B 7 Zazvichaj vikoristovuyetsya dlya imenuvannya zalezhnostej danih ye nastupne dlya chitannya pislya zapisu abo RAW zalezhnist potoku zapis pislya zapisu abo WAW vihid zalezhnostej i Write Pislya chitannya abo WAR antizalezhnist Kontrol zalezhnostejInstrukciya B maye zalezhnist upravlinnya vid poperednoyi komandi A yaksho rezultat A viznachaye chi slid vikonuvati B chi ni U nastupnomu prikladi S2 instrukciya maye zalezhnist upravlinnya po instrukciyi S1 Prote S3 ne zalezhit vid S1 S3 tomu sho zavzhdi vikonuyetsya nezalezhno vid rezultatu S1 S1 if a b S2 a a b S3 b a b Intuyitivno zrozumilo sho isnuye kontrol zalezhnist mizh dvoma tverdzhennyami A i V yaksho B mozhe buti mozhlivo pislya togo yak vikonuyetsya A Pidsumki vikonannya viznachatime chi bude vikonuvatisya B chi ni Tipovim prikladom ye te sho isnuyut keruyuchi zalezhnosti mizh stanom chastini yaksho zayavu i zayavi v jogo spravzhnih pomilkovih tel Formalne viznachennya zalezhnosti upravlinnya mozhe buti predstavlena nastupnim chinom Zayava S2 nazivayetsya upravlinnya zalezhit vid inshogo zayavu S1 todi i tilki todi isnuye shlyah P vid S1 do S2 takim chinom sho kozhne tverdzhennya Si S1 v P bude suprovodzhuvatisya S2 v kozhnomu mozhlivomu shlyahu do kincya programi ta S1 ne obov yazkovo povinni sliduvati S2 tobto ye shlyah do vikonuvanih vid S1 do kincya programi yaka ne prohodit cherez S2 Virazhenij za dopomogoyu post dominuvannya dvi umovi ekvivalentni S2 postdominuye vse Si S2 NE post S1 dominuvati nad Pobudova upravlinnya zalezhnostyami Zalezhno upravlinnya po suti dominuvannya kordonu u zvorotnomu grafiku grafa potoku upravlinnya CFG 2 Takim chinom odin zi sposobiv yih pobudovi bulo b pobuduvati postdominantnosti kordon KTG a potim zadnim hodom jogo otrimannya kontrol graf zalezhnostej Nizhche navedeno psevdokod dlya pobudovi postdominantnosti kordonu 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 Tut diti X ye bezlich vuzliv u CFG yaki pislya dominuyut X i Poperedniki X ye naborom vuzliv u CFG yaki bezposeredno pereduyut X u CFG Pislya togo yak postdominantnist kordonu karti obchislyuyetsya zvertaye jogo prizvede do karti vid vuzliv u CFG do vuzliv yaki mayut zalezhnist upravlinnya vid nih NaslidkiZvichajni programi napisani v pripushenni modeli poslidovnogo vikonannya V ramkah ciyeyi modeli instrukciyi vikonuyutsya odin za inshim atomarnomu tobto v bud yakij danij moment chasu tilki odna komanda vikonuyetsya i v poryadku zaznachenomu v programi Odnak zalezhnosti mizh zayav abo instrukcij mozhe pereshkodzhati paralelizm paralelne vikonannya dekilkoh instrukcij abo za dopomogoyu rozparalelyuvati kompilyatora abo procesorom ekspluatatorskogo na rivni instrukcij paralelizm Nerozvazhlivo vikonannya kilkoh komand bez urahuvannya pov yazanih zalezhnostej mozhe privesti do nebezpeki otrimannya nepravilnih rezultativ a same nebezpeki Div takozhGraf zalezhnostejLiteraturaJohn L Hennessy David A Patterson Computer Architecture a quantitative approach 3rd ed Morgan Kaufmann 2003 ISBN 1 55860 724 2 angl 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 angl