Skalbar ort

Datorprogramvara sägs uppvisa skalbar lokalitet om den kan fortsätta att använda processorer som överstiger deras minnessystem , för att lösa allt större problem. Denna term är en högpresterande enprocessoranalog av användningen av skalbar parallellism för att hänvisa till programvara för vilken ett ökande antal processorer kan användas för större problem.

Översikt

Tänk på minnesanvändningsmönstren för följande loopnest (en iterativ tvådimensionell stencilberäkning ):

   0   
          
              
                        
        
    

          
              
              
        
     för  t  :=  till  T  gör  för  i  :=  1  till  N  -  1  gör  för  j  :=  1  till  N  -  1  gör  nytt  (  i  ,  j  )  :=  (  A  (  i  -  1  ,  j  )  +  A  (  i  ,  j )  -1  )  +  A  (  i  ,  j  )  +  A  (  i  ,  j  +  1  )  +  A  (  i  +  1  ,  j  )  )  *  .  2  ändslut  för  i  :  =  1  till  N  -  1  gör  för  j  :  =  1  till  N  -  1  gör  A  (  i  ,  j  )  :=  ny  (  i  ,  j  )  ändände  slut 

Hela loopnest berör cirka 2*N**2 arrayelement och utför cirka 5*T*N**2 flyttalsoperationer. Således är den totala beräkningsbalansen (förhållandet mellan flyttalsberäkningar och flyttalsminnesceller som används) för hela detta slingbo omkring 5T/2. När beräkningsbalansen är en funktion av problemstorlek, som den är här, sägs koden ha skalbar beräkningsbalans . Här kan vi uppnå vilken beräkningsbalans vi önskar genom att helt enkelt välja ett tillräckligt stort T .

Men när N är stort, kommer den här koden fortfarande inte att uppvisa bra cacheåteranvändning, på grund av dålig referenslokalitet : när new(1,1) behövs i den andra tilldelningen, eller det andra tidsstegets exekvering av den första tilldelningen , kommer cacheraden som innehåller new(1,1) att ha skrivits över med någon annan del av en av arrayerna.

Beläggning av det första i/j-loopboet kan förbättra cacheprestandan, men endast med en begränsad faktor, eftersom det boet har en beräkningsbalans på cirka 5/2. För att producera en mycket hög grad av lokalitet, till exempel 500 (för att köra den här koden effektivt med en array som inte passar i RAM-minne och förpassas till virtuellt minne), måste vi återanvända värden över tidssteg.

Optimering över tidssteg har undersökts i ett antal forskningskompilatorer; se verk av Wonnacott, av Song och Li, eller av Sadayappan et al. för detaljer om några metoder för tidsbeläggning . Wonnacott visade att tidsutjämning kunde användas för att optimera för datauppsättningar utanför kärnan; i princip bör vilken som helst av dessa tillvägagångssätt kunna uppnå godtyckligt hög minneslokalitet utan att kräva att hela arrayen passar i cache (cachekravet växer dock med den nödvändiga lokaliteten). Multiprocessorteknikerna som citeras ovan bör i princip samtidigt producera skalbar lokalitet och skalbar parallellism .