Analiza zależności pętli

W informatyce analiza zależności pętli jest procesem, który można wykorzystać do znalezienia zależności w iteracjach pętli w celu określenia różnych relacji między instrukcjami. Te zależne relacje są powiązane z kolejnością, w jakiej różne instrukcje uzyskują dostęp do lokalizacji w pamięci. Korzystając z analizy tych zależności, wykonanie pętli można zorganizować w taki sposób, aby umożliwić wielu procesorom równoległą pracę nad różnymi częściami pętli. Nazywa się to przetwarzaniem równoległym . Ogólnie rzecz biorąc, pętle mogą zużywać dużo czas przetwarzania , gdy jest wykonywany jako kod seryjny . Dzięki przetwarzaniu równoległemu możliwe jest skrócenie całkowitego czasu wykonywania programu poprzez podział obciążenia przetwarzania między wiele procesorów.

Proces organizowania instrukcji w celu umożliwienia wielu procesorom pracy nad różnymi częściami pętli jest często nazywany równoległością . Aby zobaczyć, jak możemy wykorzystać równoległość, musimy najpierw przeanalizować zależności w poszczególnych pętlach. Zależności te pomogą określić, które instrukcje w pętli muszą zostać zakończone, zanim inne instrukcje będą mogły zostać uruchomione, a które instrukcje w pętli mogą być wykonywane równolegle w odniesieniu do innych instrukcji w pętli. Dwie ogólne kategorie zależności, które będą analizowane w pętli, to zależności danych i zależności sterowania.

Opis

Analiza zależności pętli odbywa się na znormalizowanej pętli postaci:

 dla i ₁ do U ₁ do i ₂ do U ₂ do ... do i _n do U _n do  ciało  gotowe ... gotowe gotowe

gdzie ciało może zawierać:

 S1 a[f ₁ (ja ₁ , ..., ja _n ), ..., f _m (ja ₁ , ..., ja _n )] := ... ... S2 ... := a [h ₁ (ja ₁ , ..., ja _n ), ..., hm ₍ ja ₁ , ..., ja _n )]

Gdzie a jest m-wymiarową tablicą, a _fn , hn itd ₎ . są funkcjami odwzorowującymi wszystkie indeksy iteracji (in _na dostęp do pamięci w określonym wymiarze tablicy.

Na przykład w C:

   0    
     0    
         dla  (  ja  =  ;  ja  <  U1  ;  ja  ++  )  dla  (  jot  =  ;  jot  <  U2  ;  jot  ++  )  za  [  ja  +  4  -  jot  ]  =  b  [  2  *  ja  -  jot  ]  +  ja  *  jot  ;

f ₁ byłoby i+4-j , kontrolując zapis w pierwszym wymiarze a i h ₂ byłoby 2*ij , kontrolując odczyt w pierwszym wymiarze b .

Zakres problemu polega na znalezieniu wszystkich możliwych zależności między S1 i S2 . Aby być konserwatywnym, należy założyć, że każda zależność, której nie można udowodnić, że jest fałszywa, jest prawdziwa.

Niezależność jest pokazana przez wykazanie, że żadne dwie instancje S1 i S2 nie mają dostępu ani nie modyfikują tego samego miejsca w tablicy a . Gdy zostanie znaleziona możliwa zależność, analiza zależności pętli zwykle podejmuje wszelkie próby scharakteryzowania relacji między zależnymi instancjami, ponieważ niektóre optymalizacje mogą być nadal możliwe. Może być również możliwe przekształcenie pętli w celu usunięcia lub zmodyfikowania zależności.

W trakcie udowadniania lub obalania takich zależności zdanie S można rozłożyć według iteracji, z której pochodzi. Na przykład S [1,3,5] odnosi się do iteracji, w której i1 = 1 , i2 = 3 i i3 = 5 . Oczywiście odniesienia do abstrakcyjnych iteracji, takie jak S [ d1 +1, d2 , d3 ], są zarówno dozwolone, jak i powszechne.

Zależność od danych

Zależności danych przedstawiają relacje między zmiennymi w kodzie. Istnieją trzy różne typy zależności danych:

Prawdziwa zależność (czasami określana jako zależność od przepływu)
Anty uzależnienie
Zależność wyjściowa

Prawdziwa zależność

Prawdziwa zależność występuje, gdy miejsce w pamięci jest zapisywane przed odczytaniem. Wprowadza zagrożenia odczytu po zapisie (RAW) , ponieważ instrukcja, która czyta z miejsca w pamięci, musi czekać, aż zostanie zapisana przez poprzednią instrukcję, w przeciwnym razie instrukcja odczytu odczyta niewłaściwą wartość. Przykładem prawdziwej zależności jest:

   
    S1  :  za  =  5  ;  S2  :  b  =  za  ;

W tym przykładzie istnieje prawdziwa zależność między S1 i S2, ponieważ zmienna a jest najpierw zapisywana w instrukcji S1, a następnie zmienna a jest odczytywana przez instrukcję S2. Ta prawdziwa zależność może być reprezentowana przez S1 →T S2. Prawdziwą zależność można również zaobserwować podczas odczytu i zapisu między różnymi iteracjami w pętli. Poniższy przykład pokazuje prawdziwą zależność między różnymi iteracjami.

       
        dla  (  jot  =  1  ;  jot  <  n  ;  jot  ++  )  S1  :  za  [  jot  ]  =  za  [  jot  -1  ];

W tym przykładzie istnieje prawdziwa zależność między instrukcją S1 w j-tej iteracji a S1 w j+1-ej iteracji. Istnieje prawdziwa zależność, ponieważ wartość zostanie zapisana do a[j] w jednej iteracji, a następnie nastąpi odczyt przez a[j-1] w następnej iteracji. Tę prawdziwą zależność można przedstawić jako S1[j] →T S1[j+1].

Przeciwnie uzależnieniu

Antyzależność występuje, gdy miejsce w pamięci jest odczytywane przed zapisem w tej samej lokalizacji . Wprowadza to zagrożenia zapisu po odczycie (WAR), ponieważ instrukcja, która zapisuje dane do komórki pamięci, musi czekać, aż ta lokalizacja pamięci zostanie odczytana przez poprzednią instrukcję, w przeciwnym razie instrukcja odczytu odczytałaby niewłaściwą wartość. Przykładem antyuzależnienia jest:

   
    S1  :  a  =  b  ;  S2  :  b  =  5  ;

W tym przykładzie istnieje antyzależność między instrukcjami S1 i S2. Jest to antyzależność, ponieważ zmienna b jest najpierw odczytywana w instrukcji S1, a następnie zapisywana do zmiennej b w instrukcji S2. Można to przedstawić jako S1 →A S2. Antyzależność można zobaczyć w różnych iteracjach w pętli. Poniższy przykład pokazuje przykład tego przypadku:

   0    
        dla  (  jot  =  ;  jot  <  n  ;  jot  ++  )  S1  :  b  [  jot  ]  =  b  [  jot  +  1  ];

W tym przykładzie istnieje antyzależność między j-tą iteracją S1 a j+1-tym elementem S1. Tutaj element j+1 jest odczytywany przed zapisaniem tego samego elementu w następnej iteracji j. Ta antyzależność może być reprezentowana przez S1[j] →A S1[j+1].

Zależność wyjściowa

Zależność wyjściowa występuje, gdy miejsce w pamięci jest zapisywane przed ponownym zapisaniem tego samego miejsca w innej instrukcji. Wprowadza to zagrożenia związane z zapisem po zapisie (WAW) , ponieważ druga instrukcja zapisania wartości w lokalizacji pamięci musi czekać, aż pierwsza instrukcja zakończy zapisywanie danych w tej samej lokalizacji pamięci lub gdy lokalizacja pamięci zostanie odczytana w późniejszym czasie będzie zawierał błędną wartość. Przykładem zależności wyjściowej jest:

    
    S1  :  do  =  8  ;  S2  :  do  =  15  ;

W tym przykładzie istnieje zależność wyjściowa między instrukcjami S1 i S2. Tutaj najpierw zapisywana jest zmienna c w S1, a następnie ponownie zapisywana jest zmienna c w instrukcji S2. Ta zależność wyjściowa może być reprezentowana przez S1 →O S2. Zależność wyjściową można zobaczyć na podstawie różnych iteracji w pętli. Poniższy fragment kodu pokazuje przykład tego przypadku:

   0    
         
        dla  (  jot  =  ;  jot  <  n  ;  jot  ++  )  S1  :  do  [  jot  ]  =  jot  ;  S2  :  do  [  j  +  1  ]  =  5  ;

W tym przykładzie istnieje zależność wyjściowa między j-tym elementem w S1 a j+1-tym elementem w S2. Tutaj c[j+1] w instrukcji S2 jest zapisywane w jednej iteracji. W następnej iteracji c[j] w instrukcji S2, która jest tą samą lokalizacją pamięci co c[j+1] w poprzedniej iteracji, jest ponownie zapisywana. Ta zależność wyjściowa może być przedstawiona jako S1[j] →O S2[j+1].

Zależność kontrolna

Zależności kontrolne należy również wziąć pod uwagę podczas analizowania zależności między różnymi instrukcjami w pętli. Zależności sterowania to zależności wprowadzone przez kod lub sam algorytm programowania. Kontrolują kolejność, w jakiej pojawiają się instrukcje w ramach wykonywania kodu. Typowym przykładem jest instrukcja „if”. Instrukcje „if” tworzą gałęzie w programie. Część „wtedy” instrukcji „if” wyraźnie kieruje lub kontroluje działania, które należy podjąć.


     
     

   // Blok kodu 1 (POPRAWNY)  if  (  a  ==  b  )  then  {  c  =  "kontrolowany"  ;  }  d  =  "niekontrolowany"  ;


     

  
   // Blok kodu 2 (NIEPOPRAWNY)  if  (  a  ==  b  )  then  {  }  c  =  "control"  ;  d  =  „niekontrolowany”  ;


     
     
     
 // Blok kodu 3 (NIEPOPRAWNY)  if  (  a  ==  b  )  then  {  c  =  "control"  ;  d  =  „niekontrolowany”  ;  }

W tym przykładzie zilustrowano ograniczenia przepływu sterowania. Blok kodu 1 pokazuje poprawną kolejność podczas używania instrukcji if w języku programowania C. Blok kodu 2 ilustruje problem polegający na tym, że instrukcja, która powinna być kontrolowana przez instrukcję if, nie jest już przez nią kontrolowana. Blok kodu 3 ilustruje problem polegający na tym, że instrukcja, która nie powinna być kontrolowana przez instrukcję „if”, została teraz przeniesiona pod jej kontrolę. Obie te możliwości mogą prowadzić do nieprawidłowego wykonania programu i należy je wziąć pod uwagę podczas zrównoleglania tych instrukcji w pętli.

Zależność przenoszona w pętli a zależność niezależna od pętli

Zależności przenoszone przez pętle i zależności niezależne od pętli są określane przez relacje między instrukcjami w iteracjach pętli. Kiedy instrukcja w jednej iteracji pętli zależy w jakiś sposób od instrukcji w innej iteracji tej samej pętli, istnieje zależność przenoszona przez pętlę. Jeśli jednak instrukcja w jednej iteracji pętli zależy tylko od instrukcji w tej samej iteracji pętli, tworzy to zależność niezależną od pętli.


       
      
         // Blok kodu 1  for  (  i  =  1  ;  i  <=  4  ;  i  ++  )  S1  :  b  [  i  ]  =  8  ;  S2  :  za  [  ja  ]  =  b  [  ja  -1  ]  +  10  ;


   0    
      
         // Blok kodu 2  for  (  i  =  ;  i  <  4  ;  i  ++  )  S1  :  b  [  i  ]  =  8  ;  S2  :  za  [  ja  ]  =  b  [  ja  ]  +  10  ;

W tym przykładzie blok kodu 1 pokazuje zależną od pętli zależność między iteracją instrukcji S2 i a iteracją instrukcji S1 i-1. Oznacza to, że instrukcja S2 nie może być kontynuowana, dopóki instrukcja S1 w poprzedniej iteracji nie zakończy się. Blok kodu 2 pokazuje niezależną od pętli zależność między instrukcjami S1 i S2 w tej samej iteracji.

Wykresy zależności i przechodzenia przez przestrzeń iteracji w pętli

Wykresy przechodzenia przez przestrzeń iteracji (ITG) pokazują ścieżkę, którą podąża kod podczas przechodzenia przez iteracje pętli. Każda iteracja jest reprezentowana przez węzeł. Wykresy zależności przenoszone w pętli (LDG) zapewniają wizualną reprezentację wszystkich prawdziwych zależności, antyzależności i zależności wyjściowych, które istnieją między różnymi iteracjami w pętli. Każda iteracja jest reprezentowana przez węzeł.

Łatwiej jest pokazać różnicę między dwoma wykresami za pomocą zagnieżdżonej pętli for.

    0    
       0    
             dla  (  ja  =  ;  ja  <  4  ;  ja  ++  )  dla  (  jot  =  ;  jot  <  4  ;  jot  ++  )  S1  :  za  [  ja  ][  jot  ]  =  za  [  ja  ][  jot  -1  ]  *  x  ;

W tym przykładzie istnieje prawdziwa zależność między iteracją instrukcji S1 a instrukcją j+1 instrukcji S1. Można to przedstawić jako S1[i,j] →T S1[i,j+1] Wykres przechodzenia w przestrzeni iteracji i wykres zależności przenoszonej przez pętlę to: Graf przechodzenia w przestrzeni iteracji: Wykres zależności przenoszonej w pętli:

Graf zależności przenoszony w pętli (LDG)

Graf przechodzenia w przestrzeni iteracyjnej (ITG)

Zobacz też