Pętla wykonywana równolegle–statyczne przydzielanie wątków

W .NET istnieje metoda do wykonywania pętli równolegle. Pisałem ogólne o niej kilka miesięcy temu. Temat jest jednak dużo bardziej skomplikowany i z pewnością należy zrozumieć różne podejścia do problemu.

Przed zrównolegleniem pętli, należy zastanowić się czy na prawdę przyniesie to pozytywne efekty. Złe rozpoznanie przypadku spowoduje znaczącą degradację wydajności. Zastanówmy się na co należy zwracać uwagę:

  1. Czy poszczególne elementy tablicy można przetwarzać w sposób bezpieczny (thread-safe). Jeśli nie, wtedy musielibyśmy użyć elementów synchronizacyjnych co mija się z celem.
  2. Czy kolejność z jaką przetwarzamy elementy ma znaczenie? Jeśli drugi element tablicy musi zostać koniecznie wykonany po pierwszym, zrównoleglenie nie ma sensu.
  3. Jakie są relacje między poszczególnymi iteracjami? W przypadku, gdy kolejne iteracje muszą operować na danych z poprzednich, nie będziemy mieli żadnych korzyści z optymalizacji.

Zadanie to wykonanie pętli przez wszystkie elementy w kolekcji z użyciem wątków. Pierwsze pytanie jakie nasuwa się to ile wątków chcemy stworzyć? W jaki sposób je przydzielić do zadań?

Istnieje wiele rozwiązań, ale zacznijmy od najprostszego. Podzielmy tablicę na kilka równych części, w zależności od liczby dostępnych wątków. Jeśli mamy 5 wątków, to każdy z nich będzie przetwarzał 20 elementów dla tablicy 100 elementowej.

Powstały kod wygląda prosto, a mianowicie:

private static void Main(string[] args)
{
  For(Console.WriteLine,1,10,3);
  Console.WriteLine("Koniec");
}

private static void For(Action<int> iteration, int startIndex, int endIndex, int threadsNumber)
{
  int chunkSize = (endIndex - startIndex)/threadsNumber;

  var countdownEvent = new CountdownEvent(threadsNumber);

  for (int i = 0; i < threadsNumber; i++)
  {
      Task.Factory.StartNew(delegate(object threadIndexState)
      {
          int threadIndex = (int)threadIndexState;
          int threadStartIndex = threadIndex * chunkSize + startIndex;
          int threadEndIndex = threadIndex == threadsNumber - 1 ? endIndex : threadStartIndex + chunkSize;

          for (int j = threadStartIndex; j < threadEndIndex; j++)
          {
              iteration(j);
          }
          countdownEvent.Signal();
      }, i);
  }
  countdownEvent.Wait();
}

CountdownEvent używamy w celu blokowania funkcji, aż wszystkie iteracje zostaną wykonane. Kod jest bardzo prosty ale w niektórych przypadkach stanowi optymalne rozwiązanie. Zastanówmy się, kiedy powyższe, statyczne rozwiązanie nie sprawdzi się:

  1. Nie znamy rozmiaru kolekcji. W przypadku tablic, zawsze wiemy jaki jest całkowity rozmiar kolekcji. Wiele źródeł danych to jednak IEnumerable, który może być np. nieskończony. W takiej sytuacji nie jesteśmy w stanie dokonać statycznej dekompozycji, jak to zostało powyżej pokazane.
  2. Powyższa dekompozycja zakłada, że wszystkie iteracje mają taką samą liczbę operacji. A co jeśli iteracja zależy np. od indeksu? Mam ma myśli, że niektóre iteracje mogą mieć złożoność obliczeniową dużo wyższą niż pozostałe. W takim scenariuszu, statyczne przydzielenie wątków do iteracji nie jest optymalne. Co jeśli 5 pierwszych iteracji wykonają się po jednej sekundzie, a ostatnie 5 zajmą po kilka godzin?

Kolejnym problemem jest dobranie optymalnej liczby wątków wykonującej operacje. Jeśli mamy do dyspozycji 4 procesory wtedy nie ma sensu tworzyć 20 wątków ponieważ zmarnujemy czas na zmianę kontekstu a operacje  i tak będą mogły być wykonywane wyłącznie na 4 CPU.

Czy to znaczy, że dla 4 rdzeniowego procesora, 4 wątki wykonujące pętle są optymalne? Niestety nie… System Windows jak wiemy może wywłaszczyć wątki i jest to zjawisko bardzo częste. W OS jest masa wątków, które mają dużo wyższy priorytet np. te  wykonujące GC. Jeśli zatem stworzyliśmy 4 wątki i jeden lub więcej zostały zablokowane to marnujemy trochę zasoby.  Inny scenariusz to sytuacja gdzie wykorzystujemy zdarzenia do blokowania wątków. Jeśli każda iteracja musi czekać na jakieś dane wtedy zdecydowanie lepiej stworzyć więcej wątków, ponieważ część z nich i tak będzie zablokowana na jakiś czas. Zjawisko blokowania wątków jest powszechne i odbywa się niezależnie od nas (system decyduje o tym).

Ze względu na możliwość blokowania, rozsądnym podejściem jest przekazanie Environment.ProcessorCount*2 jako liczby wątków. Wtedy zwiększamy szansę, że w przypadku blokowania któryś z wątków, duża cześć danych jest wciąż przetwarzana.

Ponadto powyższy kod można lekko zoptymalizować ale o tym pisałem już tutaj:

http://www.pzielinski.com/?p=1738

2 thoughts on “Pętla wykonywana równolegle–statyczne przydzielanie wątków”

  1. @agares:
    O Parallel.For pisałem juz – w tym i kolejnych postach bede wyjasnial internals, aby pokazac, ze sprawa nie jest tak prosta I oczywista jak moze wydawac sie.

Leave a Reply

Your email address will not be published.