Зависност података

Зависност података, у рачунарству, је ситуација у којој исказ програма (инструкција) упућује на податак претходног исказа. У теорији компајлера, техника која се користи да се открију зависности података међу исказима (или инструкцијама) се зове анализа зависности.

Постоје три типа зависности:

Зависност података
Зависност назива и
Зависност контроле

Зависност података

Ако имамо исказе $S_{1}$ и $S_{2}$ , $S_{2}$ зависи од $S_{1}$ ако:

[I(S_{1})\cap O(S_{2})]\cup [O(S_{1})\cap I(S_{2})]\cup [O(S_{1})\cap O(S_{2})]\neq \varnothing

где:

$I(S_{i})$ представља скуп меморијских локација прочитане од стране $S_{i}$
$O(S_{j})$ је скуп меморијских локација које је $S_{j}$ уписао
постоје изводљиве путање (у run-time извршавању програма) од $S_{1}$ до $S_{2}$

Ово стање се зове Бернштајн стање (енгл. Bernstein Condition, по A. J. Bernstein).

Постоје три случаја:

Зависност тока (података) : O(S1) ∩ I (S2), S1 → S2; и S1 пише нешто што чита S2
Анти-зависност: I(S1) ∩ O(S2), S1 → S2; и S1 чита нешто пре него што га S2 измени
Зависност излазних података: O(S1) ∩ O(S2), S1 → S2; и оба пишу на исту меморијску локацију

Зависност тока

Зависност тока (још познато и као завиност података или као "суштинска" (енгл. true) завиност или као "читај после писања" (RAW)), се догађа када нека инструкција зависи од резултата претходне инструкције:

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

Инструкција 3 "суштински" зависи од инструкције 2, јер закључна вредност C зависи од инструкција које ажурирају B. Инструкција 2 "суштински" зависи од иструкције 1, јер закључна вредност B зависи од инструкција које ажурирају А. Пошто инструкција 3 "суштински" зависи од инструкције 2 и пошто инструкција 2 "суштински" зависи од инструкције 1, инструкција 3 такође "суштински" зависи од инструкције 1. Паралелизам на нивоу наредбе због тога не може бити опција у овом примеру.^[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. Као зависности тока, ове нове зависности је немогуће безбедно уклонити.^[1]

Зависност излазних података

Зависност излазних података (још позната и као "пиши после писања" (WAW)) се догађа када ће позивање инструкција утицати на коначану вредност излазне променљиве. У примеру испод, постоји зависност излазних података између инструкција 3 и 1. Промена редоследа инструкција, у овом примеру, ће променити коначну вредност B, чиме се ове инструкције неће моћи извршити паралелно.

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

Као и код анти-зависности, зависност излазних података је у ствари зависност назива. Тиме би ова зависност могла бити уклоњена преименовањем променљивих, као у примеру испод:

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

Често коришћена конвенција имена за зависност података је следећа: "читај после писања" или RAW (зависност тока), "пиши после писања" или WAW (зависност излазних података) и "пиши после читања" или WAR (анти-зависност).^[1]

Зависност контроле

Нека инструкција је контролно зависна од претходне инструкције ако каснији исход утврди да ли претходни треба да се изврши или не. У примеру доле, инструкција S2 је контролно зависна од инструкције S1. Међутим, S3 није контролно зависан од S1 зато што се S3 увек извршава без обзира на исход S1.

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

Интуитивно, постоји зависност контроле између два исказа S1 и S2 ако би:

S1 било могуће извршити пре S2
исход извршавања S1 одлучио да ли ће се извршити S2

Типичан пример је када постоји завиност контроле између услова if исказа и исказа "тачног" или "нетачног" тела.

Формална дефиниција зависности контроле се може презентовати овако:

За исказ S2 се каже да је контролно зависан у односу на исказ S1 ако и само ако:

постоји пут P од S1 до S2 такав да би сваки исказ Si ≠ S1 у P био праћен са S2 у сваком могућем путу до краја програма; и
S1 неће обавезно бити праћено S2 тј. постоји пут извршавања од S1 до краја програма који не иде кроз S2.

Изражено уз помоћ (пост)доминације, два услова су еквивалентни са:

S2 пост-доминира свим Si
S2 не пост-доминира S1

Пример 2: контролно независни:

for (i=0;i<n;i++)
{
a[i] = c[i];
if (a[i] < 0) a[i] = 1;
}

контролно зависни:

for (i=1;i<n;i++) 
{		
if (a[i-1] < 0) a[i] = 1;                                
}

Импликације

Конвенционални програми су писани узимајући у обзир модел секвенцијалног извршавања. Под овим моделом, инструкције се извршавају једна за другом, атомично (тј. у сваком трнутку времена само се једна инструкција извршава) и у редоследу који одређује програм.

Међутим, зависности међу изјавама или инструкцијама могу ометати паралелизам, било паралелизовањем компајлера или процесоровим искоришћавањем паралелизма на нивоу бита. Безобзирно извршавање више инструкција без разматрања зависности може изазвати опасност добијања погрешних резултата, наиме конфликте проточне обраде.

Референце

^ ^а ^б ^в Hennessy & Patterson 2003

Литература

Hennessy, John L.; Patterson, David A. (2003). Computer Architecture: a quantitative approach (3rd ed.). Morgan Kaufmann. ISBN 978-1-55860-724-8.

[architecture-1] а ^б ^в Hennessy & Patterson 2003

[1]