Výměna smyčky - Loop interchange

v teorie překladače, výměna smyčky je proces výměny pořadí dvou iteračních proměnných použitých vnořeným smyčka. Proměnná použitá ve vnitřní smyčce se přepne na vnější smyčku a naopak. Často se provádí, aby se zajistilo, že prvky vícerozměrného pole se přistupuje v pořadí, v jakém jsou přítomny v paměti, což se zlepšuje referenční lokalita.

Například ve fragmentu kódu:

pro i od 0 do 10 pro j od 0 do 20 a [i, j] = i + j

výměna smyčky by vedla k:

pro j od 0 do 20 pro i od 0 do 10 a [i, j] = i + j

Příležitostně může taková transformace vytvořit příležitosti k další optimalizaci, například automatická vektorizace přiřazení pole.

Užitečnost výměny smyčky

Ilustrace řádkové a sloupcové hlavní objednávky

Hlavním účelem výměny smyček je využít výhod Mezipaměť CPU při přístupu k prvkům pole. Když procesor přistupuje k prvku pole poprvé, načte celý blok dat z paměti do mezipaměti. Tento blok pravděpodobně bude mít po prvním mnohem více po sobě jdoucích prvků, takže při dalším přístupu k prvkům pole bude přiveden přímo z mezipaměti (což je rychlejší než získání z pomalé hlavní paměti). Cache chybí nastat, pokud souvisle přistupované prvky pole ve smyčce pocházejí z jiného bloku mezipaměti a výměna smyčky tomu může zabránit. Efektivita výměny smyčky závisí na a musí být brána v úvahu ve světle modelu mezipaměti používaného základním hardwarem a modelu pole použitého kompilátorem.

v Programovací jazyk C., prvky pole ve stejném řádku jsou ukládány postupně do paměti (a [1,1], a [1,2], a [1,3]) - v řádková hlavní objednávka. Na druhou stranu, FORTRAN programy ukládají prvky pole ze stejného sloupce dohromady (a [1,1], a [2,1], a [3,1]) pomocí hlavní sloupec. Pořadí dvou iteračních proměnných v prvním příkladu je tedy vhodné pro program C, zatímco druhý příklad je lepší pro FORTRAN.[1] Optimalizace překladačů dokáže detekovat nesprávné řazení programátory a vyměnit pořadí, aby bylo dosaženo lepšího výkonu mezipaměti.

Upozornění

Jako každý optimalizace kompilátoru, výměna smyčky může vést k horšímu výkonu, protože výkon mezipaměti je pouze částí příběhu. Vezměte následující příklad:

 dělat i = 1, 10000   dělat j = 1, 1000     A[i] = A[i] + b[j,i] * C[i]   konec udělej konec udělej

Výměna smyčky v tomto příkladu může zlepšit výkon mezipaměti při přístupu k b (j, i), ale zničí opětovné použití a (i) a c (i) ve vnitřní smyčce, protože zavádí dvě další zátěže (pro ( i) a pro c (i)) a jeden obchod navíc (pro a (i)) během každé iterace. V důsledku toho může být celkový výkon po výměně smyčky snížen.

Bezpečnost

Není vždy bezpečné vyměňovat iterační proměnné kvůli závislostem mezi příkazy v pořadí, ve kterém se musí provést. Chcete-li zjistit, zda kompilátor může bezpečně vyměňovat smyčky, analýza závislosti je požadováno.

Viz také

Reference

  1. ^ „Výměna smyčky“ (PDF). Průvodce paralelním programováním pro systémy HP-UX. HP. Srpna 2003.

Další čtení