W poprzednim poście pisałem  o statycznej dekompozycji tablicy na kilka wątków. Główną wadą podejścia było przypuszczenie, że wszystkie iteracje są tak samo skomplikowane.

W niektórych algorytmach należy znaleźć element spełniający podane wymagania. Wyobraźmy sobie, że mamy 100 elementową tablicę i dzielimy ją na 10 wątków. Ponadto element szukany znajduje się pod indeksem 9. Wniosek taki, że NIC nie zyskamy ze zrównoleglenia. Dziewięć wątków będzie szukało w złym miejscu, a pierwszy z nich będzie wykonywał prace jak w podejściu sekwencyjnym.

Powyższe problemy można łatwo ominąć. Zamiast statycznie przydzielać wątki do iteracji, możemy wykonać to w sposób bardziej dynamiczny. Wystarczy, że iteracje będą przetwarzane na zmianę przez różne wątki.

Załóżmy, że tablica ma 10 elementów a mamy do dyspozycji 3 wątki. Możemy zatem do T1 przydzielić elementy 1,4,7,10, do T2 2,5,8 a do T3 3,6,9. Innymi słowy wątek wykonuje swoją porcję a następnie pomija wszystkie elementy, które przydzielone są do innego wątku. Oczywiście wspomniane porcję danych nie muszą być równe jednej iteracji. Może być, że pierwsze 5 elementów jest przydzielonych do T1, następne 5 do T2 itd.

Mała zmiana a zlikwiduje problemy wspomniane na początku wpisu. Implementacja jest również prosta:

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)
{
  const int chunkSize = 4;

  var countdownEvent = new CountdownEvent(threadsNumber);

  for (int i = 0; i < threadsNumber; i++)
  {
      Task.Factory.StartNew(delegate(object threadIndexState)
      {
          int start = startIndex + (int)threadIndexState * chunkSize;

          for (int j = start; j < endIndex; j += chunkSize * threadsNumber)
          {
              for (int k = 0; k < chunkSize && j + k < endIndex; k++)
              {
                  iteration(j + k);
              }
          }
          countdownEvent.Signal();
      }, i);
  }
  countdownEvent.Wait();
}

Kod jest podobny do tego z poprzedniego wpisu. Tak naprawdę wciąż jest to statyczna dekompozycja. Każdy wątek ma z góry określone iteracje do przetworzenia ale nie są one przylegające do siebie – co niweluje wiele problemów. Wciąż jednak musimy znać rozmiary tablicy – dla IEnumerable podejście nie sprawdzi się ponieważ nie mamy tam do dyspozycji indeksów.