Optimering av loopbo
Inom datavetenskap och i synnerhet inom kompilatordesign är loop nest optimization (LNO) en optimeringsteknik som tillämpar en uppsättning slingtransformationer för lokalitetsoptimering eller parallellisering eller annan loop-overhead - reduktion av slingbon. ( Inkapslade loopar uppstår när en loop är inne i en annan loop.) En klassisk användning är att minska minnesåtkomstfördröjningen eller cachebandbredden som krävs på grund av cacheåteranvändning för vissa vanliga linjära algebraalgoritmer .
Tekniken som används för att producera denna optimering kallas loop tiling , även känd som loop blocking eller strip min and interchange .
Översikt
Loop-tiling delar upp en loops iterationsutrymme i mindre bitar eller block, för att säkerställa att data som används i en loop stannar i cachen tills den återanvänds. Partitioneringen av loop-iterationsutrymme leder till uppdelning av en stor array i mindre block, vilket gör att åtkomliga arrayelement anpassas till cachestorlek, vilket förbättrar cacheåteranvändning och eliminerar kraven på cachestorlek.
En vanlig slinga
0
för ( i = ; i < N ; ++ i ) { ... }
kan blockeras med ett block storlek B genom att ersätta det med
0
för ( j = ; j < N ; j += B ) { för ( i = j ; i < min ( N , j + B ); ++ i ) { .... } }
där min() är en funktion som returnerar minimum av dess argument.
Exempel: matris-vektor multiplikation
Följande är ett exempel på matrisvektormultiplikation. Det finns tre arrayer, var och en med 100 element. Koden delar inte upp arrayerna i mindre storlekar.
0
0
0
int i , j , a [ 100 ][ 100 ], b [ 100 ], c [ 100 ]; int n = 100 ; för ( i = ; i < n ; i ++ ) { c [ i ] = ; för ( j = ; j < n ; j ++ ) { c [ i ] = c [ i ] + a [ i ][ j ] * b [ j ]; } }
Efter att slingbeläggning har applicerats med 2 * 2 block ser koden ut så här:
0
0
0
0
int i , j , x , y , a [ 100 ][ 100 ], b [ 100 ], c [ 100 ]; int n = 100 ; för ( i = ; i < n ; i += 2 ) { c [ i ] = ; c [ i + 1 ] = ; för ( j = ; j < n ; j += 2 ) { för ( x = i ; x < min ( i + 2 , n ); x ++ ) { för ( y = j ; y < min ( j + 2 ) , n ); y ++ ) { c [ x ] = c [ x ] + a [ x ][ y ] * b [ y ]; } } } }
Det ursprungliga loop-iterationsutrymmet är n gånger n . Den åtkomliga biten av array a[i, j] är också n med n . När n är för stort och maskinens cachestorlek är för liten, kan de åtkomliga arrayelementen i en loopiteration (till exempel i = 1 , j = 1 till n ) korsa cache-linjer, vilket orsakar cachemissar.
Plattstorlek
Det är inte alltid lätt att avgöra vilket värde av tiling-storlek som är optimal för en slinga eftersom det kräver en exakt uppskattning av åtkomliga arrayregioner i slingan och cachestorleken för målmaskinen. Ordningen på loop-bon ( loop interchange ) spelar också en viktig roll för att uppnå bättre cacheprestanda. Explicit blockering kräver att du väljer en brickstorlek baserat på dessa faktorer. Däremot cache-omedvetna algoritmer designade för att effektivt använda cache utan explicit blockering.
Exempel: matrismultiplikation
Många stora matematiska operationer på datorer ägnar mycket av sin tid åt matrismultiplikation . Operationen är:
- C = A×B
där A, B och C är N×N arrayer. Subskriptioner, för följande beskrivning, är i form C[rad][kolumn] .
Grundslingan är:
0
0
0
0
int i , j , k ; för ( i = ; i < N ; ++ i ) { för ( j = ; j < N ; ++ j ) { C [ i ][ j ] = ; för ( k = ; k < N ; ++ k ) C [ i ][ j ] += A [ i ][ k ] * B [ k ][ j ]; } }
Det finns tre problem att lösa:
- Flyttalstillägg tar ett antal cykler att slutföra. För att hålla en adderare med flera cyklers latens upptagen måste koden uppdatera flera ackumulatorer parallellt.
- Maskiner kan vanligtvis bara göra en minnesoperation per multiplicerad add , så värden som laddas måste återanvändas minst två gånger.
- Typiska PC-minnessystem kan bara upprätthålla ett 8-byte dubbelord per 10–30 dubbelprecisionsmultiplikationer, så värden som laddas in i cachen måste återanvändas många gånger.
Den ursprungliga loopen beräknar resultatet för en post i resultatmatrisen åt gången. Genom att beräkna ett litet block med poster samtidigt, återanvänder följande loop varje laddat värde två gånger, så att den inre slingan har fyra belastningar och fyra multiplicerar-lägger, vilket löser problem #2. Genom att bära fyra ackumulatorer samtidigt kan denna kod hålla en enda flyttalsadderare med en latens på 4 upptagen nästan hela tiden (problem #1). Koden tar dock inte upp det tredje problemet. (Det tar inte heller upp det nödvändiga saneringsarbetet när N är udda. Sådana detaljer kommer att utelämnas i följande diskussion.)
0
0
0
0
0 0
0
0
0 0
0
0
för ( i = ; i < N ; i += 2 ) { för ( j = ; j < N ; j += 2 ) { acc00 = acc01 = acc10 = accll = ; för ( k = ; k < N ; k ++ ) { acc00 += B [ k ][ j + ] * A [ i + ][ k ]; acc01 += B [ k ][ j + 1 ] * A [ i + ][ k ]; acc10 += B [ k ][ j + ] * A [ i + 1 ][ k ]; accll += B [ k ][ j + 1 ] * A [ i + 1 ][ k ]; } C [ i + ][ j + ] = acc00 ; C [ i + ][ j + 1 ] = acc01 ; C [ i + 1 ][ j + ] = acc10 ; C [ i + 1 ][ j + 1 ] = accll ; } }
Den här koden har haft både i- och j -iterationerna blockerade med en faktor två och hade båda de resulterande två-iterations inre slingorna helt utrullade.
Den här koden skulle köras helt acceptabelt på en Cray Y-MP (byggd i början av 1980-talet), som kan upprätthålla 0,8 multiplicering – tillägg per minnesoperation till huvudminnet. En maskin som en 2,8 GHz Pentium 4, byggd 2003, har något mindre minnesbandbredd och mycket bättre flyttal, så att den kan upprätthålla 16,5 multiplikationer per minnesoperation. Som ett resultat kommer koden ovan att köras långsammare på 2,8 GHz Pentium 4 än på 166 MHz Y-MP!
En maskin med en längre tilläggslatens med flyttal eller med flera adderare skulle kräva att fler ackumulatorer körs parallellt. Det är lätt att ändra slingan ovan för att beräkna ett 3x3-block istället för ett 2x2-block, men den resulterande koden är inte alltid snabbare. Slingan kräver register för att hålla både ackumulatorerna och de laddade och återanvända A- och B-värdena. Ett 2x2 block kräver 7 register. Ett 3x3-block kräver 13, vilket inte fungerar på en maskin med bara 8 flyttalsregister i ISA . Om CPU:n inte har tillräckligt med register, kommer kompilatorn att schemalägga extra laddningar och lagrar för att spilla registren i stackplatser, vilket gör att loopen går långsammare än en mindre blockerad loop.
Matrismultiplikation är som många andra koder genom att den kan begränsas av minnesbandbredd, och att fler register kan hjälpa kompilatorn och programmeraren att minska behovet av minnesbandbredd. Detta registertryck är anledningen till att leverantörer av RISC- processorer, som hade för avsikt att bygga maskiner mer parallella än de generella x86- och 68000 -processorerna, antog 32-ingångars flyttalsregisterfiler .
Koden ovan använder inte cachen särskilt bra. Under beräkningen av en horisontell remsa av C-resultat, laddas en horisontell remsa av A, och hela matrisen B laddas. För hela beräkningen lagras C en gång (det är bra), A laddas in i cachen en gång (förutsatt att en remsa av A passar i cachen med en remsa av B), men B laddas N/ib gånger, där ib är storleken på remsan i C-matrisen, för totalt N 3 /ib dubbelordsladdningar från huvudminnet. I koden ovan är ib 2.
Nästa steg för att minska minnestrafiken är att göra ib så stort som möjligt. Det måste vara större än "balans"-talet som rapporteras av strömmar. I fallet med ett speciellt 2,8 GHz Pentium 4-system som används i detta exempel är saldotalet 16,5. Det andra kodexemplet ovan kan inte utökas direkt, eftersom det skulle kräva många fler ackumulatorregister. blockeras slingan över i. (Tekniskt sett är detta faktiskt andra gången jag blockeras, eftersom första gången var faktorn 2.)
0
0
0
0
0 0
0
0
0 0
0
0
for ( ii = ; ii < N ; ii += ib ) { for ( j = ; j < N ; j += 2 ) { for ( i = ii ; i < ii + ib ; i += 2 ) { acc00 = acc01 = acc10 = acc11 = ; för ( k = ; k < N ; k ++ ) { acc00 += B [ k ][ j + ] * A [ i + ][ k ]; acc01 += B [ k ][ j + 1 ] * A [ i + ][ k ]; acc10 += B [ k ][ j + ] * A [ i + 1 ][ k ]; accll += B [ k ][ j + 1 ] * A [ i + 1 ][ k ]; } C [ i + ][ j + ] = acc00 ; C [ i + ][ j + 1 ] = acc01 ; C [ i + 1 ][ j + ] = acc10 ; C [ i + 1 ][ j + 1 ] = accll ; } } }
Med denna kod kan ib ställas in på vilken parameter som helst, och antalet belastningar av B-matrisen kommer att reduceras med den faktorn. Denna frihet har en kostnad: N×ib-skivor av A-matrisen hålls i cachen. Så länge det passar kommer denna kod inte att begränsas av minnessystemet.
Så vilken storlek matris passar? Exempelsystemet, en 2,8 GHz Pentium 4, har en 16KB primär datacache. Med ib=20 kommer delen av A-matrisen i denna kod att vara större än den primära cachen när N > 100. För problem som är större än så behövs ett annat trick.
Det tricket är att minska storleken på remsan i B-matrisen genom att blockera k-slingan så att remsan blir av storleken ib × kb. Blockering av k-loopen innebär att C-matrisen kommer att laddas och lagras N/kb gånger, totalt minnesöverföringar. B överförs fortfarande N/ib gånger, för överföringar. Så länge som
- 2*N/kb + N/ib < N/balans
maskinens minnessystem kommer att hålla jämna steg med flyttalsenheten och koden kommer att köras med maximal prestanda. 16KB-cachen för Pentium 4 är inte riktigt stor nog: om ib=24 och kb=64 valdes istället, skulle 12KB av cachen användas – för att undvika att helt fylla den, vilket är önskvärt så C- och B-arrayerna måste ha lite utrymme att flöda igenom. Dessa siffror ligger inom 20 % av processorns maximala flyttalshastighet.
Här är koden med loop k blockerad.
0
0
0
0
0
0 0
0
0
0 0
0
0
0 0
0
0
for ( ii = ; ii < N ; ii += ib ) { for ( kk = ; kk < N ; kk += kb ) { for ( j = ; j < N ; j += 2 ) { for ( i = ii i < ii + ib ; i + = 2 ) { if ( kk == ) acc00 = acc01 = acc10 = acc11 = ; annars { acc00 = C [ i + ][ j + ]; acc01 = C [ i + ][ j + 1 ]; acc10 = C [ i + 1 ][ j + ]; accll = C [ i + 1 ][ j + 1 ]; } för ( k = kk ; k < kk + kb ; k ++ ) { acc00 += B [ k ][ j + ] * A [ i + ][ k ]; acc01 += B [ k ][ j + 1 ] * A [ i + ][ k ]; acc10 += B [ k ][ j + ] * A [ i + 1 ][ k ]; accll += B [ k ][ j + 1 ] * A [ i + 1 ][ k ]; } C [ i + ][ j + ] = acc00 ; C [ i + ][ j + 1 ] = acc01 ; C [ i + 1 ][ j + ] = acc10 ; C [ i + 1 ][ j + 1 ] = accll ; } } } }
Ovanstående kodexempel visar inte detaljerna för att hantera värden på N som inte är multiplar av blockeringsfaktorerna. Kompilatorer som gör loop-nest-optimering sänder ut kod för att rensa upp kanterna på beräkningen. Till exempel skulle de flesta LNO-kompilatorer troligen dela upp kk == 0 iterationen från resten av kk iterationerna, för att ta bort if-satsen från i- loopen. Detta är ett av värdena för en sådan kompilator: även om det är enkelt att koda de enkla fallen av denna optimering, är det en felbenägen process att hålla alla detaljer korrekta när koden replikeras och transformeras.
Ovanstående loop kommer endast att uppnå 80 % av toppflopsarna på exempelsystemet när den är blockerad för 16KB L1-cachestorlek. Det kommer att bli sämre på system med ännu mer obalanserade minnessystem. Lyckligtvis har Pentium 4 256KB (eller mer, beroende på modell) nivå-2-cache med hög bandbredd samt nivå-1-cache. Det finns ett val:
- Justera blockstorlekarna för nivå-2-cachen. Detta kommer att betona processorns förmåga att hålla många instruktioner under flygning samtidigt, och det finns en god chans att den inte kommer att kunna uppnå full bandbredd från nivå-2-cachen.
- Blockera slingorna igen, igen för nivå 2-cachestorlekarna. Med totalt tre nivåer av blockering (för registerfilen, för L1-cachen och L2-cachen), kommer koden att minimera den erforderliga bandbredden på varje nivå i minneshierarkin . Tyvärr kommer de extra nivåerna av blockering att medföra ännu mer loop-overhead, vilket för vissa problemstorlekar på viss hårdvara kan vara mer tidskrävande än eventuella brister i hårdvarans förmåga att strömma data från L2-cachen.
Istället för att specifikt ställa in en viss cachestorlek, som i det första exemplet, är en cache-omedveten algoritm utformad för att dra fördel av alla tillgängliga cache, oavsett storleken. Detta drar automatiskt fördel av två eller flera nivåer av minneshierarki, om tillgängligt. Cache-omedvetna algoritmer för matrismultiplikation är kända.
Se även
Vidare läsning
- Wolfe, M. Mer Iteration Space Plating . Supercomputing'89, sidorna 655–664, 1989.
- Wolf, ME och Lam, M. A Data Locality Optimizing Algorithm . PLDI '91, sidorna 30–44, 1991.
- Irigoin, F. och Triolet, R. Supernode Partitioning . POPL '88, sid 319–329, 1988.
- Xue, J. Loop Tiling for Parallelism . Kluwer Academic Publishers. 2000.
- MS Lam, EE Rothberg och ME Wolf. Cacheprestanda och optimeringar av blockerade algoritmer . I Proceedings of the 4th International Conference on Architectural Support for Programming Languages and Operating Systems, sidorna 63–74, april 1991.
externa länkar
- Streamar benchmarkresultat som visar den övergripande balansen mellan flyttalsoperationer och minnesoperationer för många olika datorer
- "CHiLL: Composable High-Level Loop Transformation Framework" [ permanent död länk ]
| Myndighetskontroll : Nationella bibliotek |
|---|
