Hurok csempézés (csempézés [1] , a hurok blokkokra bontása ) egy optimalizáló átalakítás , amely bizonyos típusú hurkok végrehajtását hatékonyabbá teszi.
Ez az optimalizálási módszer abból áll, hogy az eredeti ciklus iterációs terét (amely több változón keresztül is végrehajtható) kisebb méretű kis blokkokra bontja, ami lehetővé teszi az ezekben a kis blokkokban használt adatok teljes tárolását a gyorsítótárban az ismétlődés céljából. blokk végrehajtása során használja. A hurok iterációs terének felosztása azt eredményezi, hogy a tömb kisebb, a gyorsítótárba illeszkedő blokkokra oszlik, ami jobb gyorsítótárkihasználást, kisebb kihagyásokat és alacsonyabb gyorsítótárméret-követelményeket eredményez.
Miután a hurkot 2 × 2 blokkra osztotta
for ( i = 0 ; i < N ; i += 2 ) for ( j = 0 ; j < N ; j + = 2 ) for ( ii = i ; ii < min ( i + 2 , N ); ii ++ ) for ( jj = j ; jj < min ( j + 2 , N ); jj ++ ) c [ ii ] = c [ ii ] + a [ ii , jj ] * b [ ii ];Kezdetben az iterációs tér N × N méretű. Az elérendő a[i, j] tömbblokk is N × N méretű. , majd az egy iteráción belül használt elemek (például amikor i = 1, j 1-ről N-re változik), akkor gyorsítótár-kihagyások lépnek fel, a tömb különböző részeit ki kell tölteni, ami nagymértékben csökkenti a teljesítményt.
Egy másik példa ennek az optimalizáló transzformációnak a használatára a mátrixszorzás.
Forrás:
for ( i = 0 ; i < N ; i ++ ) for ( k = 0 ; k < N ; k ++ ) for ( j = 0 ; j < N ; j ++ ) z [ i , j ] = z [ i , j ] + x [ i , k ] * y [ k , j ]B × B blokkra bontás után:
for ( k2 = 0 ; k2 < N ; i += B ) for ( j2 = 0 ; j2 < N ; j + = B ) for ( i = 0 ; i < N ; i ++ ) for ( k1 = k2 ; k1 < min ( k2 + B , N ); k1 ++ ) for ( j1 = j2 ; k2 < min ( j2 + B , N ); j1 ++ ) z [ i , j1 ] = z [ i , j1 ] + x [ i , k1 ] * y [ k1 , j1 ];Nem mindig könnyű meghatározni, hogy egy adott hurok számára melyik blokkméret az optimális, mivel ez az elért tömbök területeinek kiszámításának pontosságától függ. A hurkok egymásba ágyazási sorrendje is fontos szerepet játszik a jobb teljesítmény elérésében.