Silmukan laatoitus (laatoitus [1] , silmukan jakaminen lohkoihin ) on optimoiva muunnos , joka on suunniteltu tehostamaan tietyntyyppisten silmukoiden suorittamista.
Tämä optimointimenetelmä koostuu alkuperäisen silmukan iteraatioavaruuden jakamisesta (joka voidaan suorittaa useilla muuttujilla) pieniksi, pienempikokoisiksi lohkoiksi, mikä mahdollistaa näissä pienissä lohkoissa käytetyn datan tallentamisen välimuistiin kokonaan niiden toistamista varten. käyttää lohkon suorittamisen aikana. Silmukan iteraatioavaruuden jakaminen saa matriisin jaettua pienempiin lohkoihin, jotka sopivat välimuistiin, mikä johtaa parempaan välimuistin hyödyntämiseen, pienempään hukkaan ja pienempiin välimuistin kokovaatimuksiin.
Silmukan jakamisen jälkeen 2 × 2 lohkoon
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 ];Aluksi iteraatioavaruus on kooltaan N × N. Matriisilohko a[i, j], johon on pääsy, on myös N × N kooltaan. , sitten elementit, joita käytetään yhdessä iteraatiossa (esim. kun i = 1, j muuttuu 1:stä N), jolloin tapahtuu välimuistihäiriöitä, taulukon eri osia on purettava, mikä heikentää suorituskykyä huomattavasti.
Toinen esimerkki tämän optimoivan muunnoksen käytöstä on matriisin kertominen.
Lähde:
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 ]Lohoihin B × B jakamisen jälkeen:
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 ];Aina ei ole helppoa määrittää, mikä lohkokoko on optimaalinen tietylle silmukalle, koska se riippuu käsiteltävien taulukoiden alueiden laskennan tarkkuudesta. Silmukoiden sisäkkäisjärjestys on myös tärkeä rooli paremman suorituskyvyn saavuttamisessa.