Obkládání smyčky (obkládání [1] , rozdělení smyčky na bloky ) je optimalizační transformace navržená tak, aby zefektivnila provádění určitých typů smyček.
Tato optimalizační metoda spočívá v rozdělení iteračního prostoru původní smyčky (která může být provedena přes několik proměnných) na malé bloky menší velikosti, což umožňuje uložit data použitá v těchto malých blocích do mezipaměti zcela pro jejich opakované použití během provádění bloku. Rozdělení iteračního prostoru smyčky způsobí, že se pole rozdělí na menší bloky, které se vejdou do mezipaměti, což vede k lepšímu využití mezipaměti, nižším chybám a menším požadavkům na velikost mezipaměti.
Po rozdělení smyčky na 2 × 2 bloky
pro ( i = 0 ; i < N ; i += 2 ) pro ( j = 0 ; j < N ; j + = 2 ) pro ( 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 ];Zpočátku má iterační prostor velikost N × N. Blok pole a[i, j], ke kterému je třeba přistupovat, má také velikost N × N. , pak prvky, které se používají v rámci jedné iterace (například když i = 1, j se změní z 1 na N), pak dochází k chybám mezipaměti, různé části pole se musí uvolnit, což výrazně snižuje výkon.
Dalším příkladem použití této optimalizační transformace je násobení matic.
Zdroj:
pro ( i = 0 ; i < N ; i ++ ) pro ( k = 0 ; k < N ; k ++ ) pro ( j = 0 ; j < N ; j ++ ) z [ i , j ] = z [ i , j ] + x [ i , k ] * y [ k , j ]Po rozdělení na bloky B × B:
pro ( k2 = 0 ; k2 < N ; i += B ) pro ( j2 = 0 ; j2 < N ; j + = B ) pro ( i = 0 ; i < N ; i ++ ) pro ( 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 ];Není vždy snadné určit, jaká velikost bloku je optimální pro konkrétní smyčku, protože to závisí na přesnosti výpočtu oblastí polí, ke kterým se přistupuje. Pořadí vnoření smyček také hraje důležitou roli při dosahování lepšího výkonu.