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.