dependence analysis

dependence analysis (tsz. dependence analysises)

1. (informatika) A dependence analysis (függőségelemzés) a programanalízis egy fontos területe, amely azt vizsgálja, hogy a program utasításai vagy műveletei milyen viszonyban állnak egymással – különösen abból a szempontból, hogy végrehajthatók-e párhuzamosan, átrendezhetők-e vagy optimalizálhatók-e biztonságosan.

Ez a típusú analízis alapvető a fordítóoptimalizálás, loop transformation, párhuzamosítás, vectorizáció, és programverifikáció szempontjából.

Egy utasítás függ egy másiktól, ha annak kimenetétől vagy állapotától függ.

a = 3;
b = a + 1;

Itt a második sor adatfüggő az elsőtől, mert a értékére szükség van b kiszámításához.

Ez a leggyakoribb típus.

• True Dependence (Read after Write / RAW) → Egy utasítás használ egy értéket, amit egy korábbi utasítás írt. Példa:

  a = 5;       // ír
  b = a + 1;   // olvas
  

• Anti-Dependence (Write after Read / WAR) → Egy utasítás ír egy változóra, amit előtte olvasott egy másik. Példa:

  b = a + 1;   // olvas
  a = 7;       // ír
  

• Output Dependence (Write after Write / WAW) → Két utasítás ír ugyanarra a változóra. Példa:

  a = 5;
  a = 6;
  

Ez azt mutatja, hogy egy utasítás csak akkor hajtódik végre, ha egy előző feltétel igaz.

Példa:

if (x > 0) {
    y = 1;
}

A y = 1 utasítás végrehajtása függ az x > 0 kifejezés eredményétől.

Ez egy cikluson belüli adatfüggőség, ahol egy iteráció hatással van egy másikra.

Példa:

for (int i = 1; i < n; i++) {
    A = A + 1;
}

Itt A kiszámítása függ az A értékétől → nem vektorozható, nem futtatható egyszerre.

• Optimalizáció: Átrendezhető-e a kód? Eliminálható-e változó?
• Párhuzamosítás: Elindíthatók-e utasítások több szálon?
• Loop unrolling & fusion: Ciklusok átalakítása hatékonyabb végrehajtásra.
• Vectorization (SIMD): Ugyanazon művelet többszöri végrehajtása egy utasítással csak akkor lehetséges, ha nincs függés.

• DFG (Data Flow Graph): Csomópontok: utasítások, Élek: adatfüggés.
• PDG (Program Dependence Graph): Kombinálja az adat- és vezérlésfüggéseket.

Ez a reprezentáció hasznos az automatikus optimalizáláshoz és verifikációhoz.

• A program minden változóját csak egyszer írjuk fel, egyedi indexekkel.
• A függőségek könnyen követhetők → analízis egyszerűbbé válik.

int a = 1;
int b = a + 2;  // RAW: b függ a-tól
int c = b + 3;  // RAW: c függ b-től
a = 5;          // WAW: a értéke felülíródik

for (int i = 0; i < n; i++) {
    A = B + 1;      // Loop-independent
    B = A + 2;    // Loop-carried dependence
}

A B = A + 2 sor miatt az egyik iteráció függ az előző eredményétől → nem lehet párhuzamosítani az iterációkat.

• GCC / LLVM: loop unrolling, dead code elimination, strength reduction mind függőségelemzést használnak.
• Auto-vectorization: csak függésmentes ciklusokat vektoroz a fordító.

• Elemzik, hogy mely részek futhatnak egymástól függetlenül.
• #pragma omp parallel for csak akkor biztonságos, ha nincs loop-carried dependence.

A ciklus akkor párhuzamosítható, ha:

• Nincs loop-carried dependence a ciklusmagban.
• A memóriahozzáférések nem okoznak adatversenyt.

Példa (párhuzamosítható):

for (int i = 0; i < n; i++) {
    A = B + 1;
}

Példa:

x = 1;
y = x + 2;
z = y + 3;

Graph:

x → y → z

Az élek a függőségeket jelölik: y függ x-től, z függ y-től.

• Pointerek és aliasok: C/C++ kód esetén nehéz megmondani, hogy két mutató ugyanarra a memóriára mutat-e.
• Dinamikus viselkedés: Feltételek, elágazások megnehezítik a pontos elemzést.
• Függőség hamis pozitív/negatív: statikus elemzés túl óvatos lehet.

A dependence analysis azt vizsgálja, hogy a program különböző utasításai hogyan függnek egymástól – különösen, hogy végrehajthatók-e más sorrendben, párhuzamosan, vagy optimalizálhatóak-e. Az elemzés az adatfüggés (RAW, WAR, WAW), vezérlésfüggés, és ciklusfüggés felismerésére fókuszál. Ez kulcsfontosságú a fordítóoptimalizálás, párhuzamosítás, loop transformation és programverifikáció szempontjából.

• dependence analysis - Szótár.net (en-hu)
• dependence analysis - Sztaki (en-hu)
• dependence analysis - Merriam–Webster
• dependence analysis - Cambridge
• dependence analysis - WordNet
• dependence analysis - Яндекс (en-ru)
• dependence analysis - Google (en-hu)
• dependence analysis - Wikidata
• dependence analysis - Wikipédia (angol)