Używanie Parallel Extensions z .NET 4.0

W trakcie rozwijania algorytmów na potrzeby pracy magisterskiej pojawiło się zapotrzebowanie na zdecydowane przyspieszenie jednego z nich. Algorytm polegał na liczeniu pewnych własności dla każdego punktu regularnej siatki. Zrównoleglenie było naturalnym rozwiązaniem, ponieważ elementy nie zależały od siebie nawzajem. Zdecydowałem się na użycie Parallel Extensions (Wiki, MSDN) ze względu na prostotę.

Przedstawię szkielet rozwiązania, które może zostać zastosowane praktycznie dla dowolnego problemu o podobnej charakterystyce, może zostać łatwo rozszerzone dla wyższych wymiarów.

Problem

Policzyć pewną właściwość (niech będzie to rezultat wywołania funkcji
int ComputeSmth(int x, int y, int z)) dla każdego elementu trójwymiarowej tablicy
int[,,] tab. Rozmiary tablicy są znane i wynoszą odpowiednio [SizeX, SizeY, SizeZ].

Wersja liniowa

Zamieszczam dla kompletu, żeby było wszystko Puszczam oczko

for (int i = 0; i < SizeX; ++i)
    for (int j = 0; j < SizeY; ++j)
        for (int k = 0; k &lt; SizeZ; ++k)
            tab[i, j, k] = ComputeSmth(i, j, k);

Zrównoleglanie – krok pierwszy

Użycie Parallel.For wymaga podania trzech argumentów: zakresu przedziału pętli [fromInclusive, toExclusive), czyli pętla wykona się dla (powiedzmy)
i = fromInclusive; i > toExclusive. Trzecim argumentem jest delegat wykonywany w każdej iteracji, który jest obiektem Action. Na początku wprowadzimy potrójną pętlę równoległą, oto kod:

Parallel.For(0, SizeX, i =>
{
    Parallel.For(0, SizeY, j =>
    {
        Parallel.For(0, SizeZ, k =>
        {
            tab[i, j, k] = ComputeSmth(i, j, k);
        });
    });
});

Taki kod wydał mi się jednak brzydki, więc postanowiłem pójść o krok dalej.

Zrównoleglenie – krok drugi

Skorzystałem z własności, że każdą tablicę trójwymiarową można traktować jak jednowymiarową, wystarczy odpowiednio przeliczyć indeksy (działa również dla wyższych wymiarów, ale akurat potrzebowałem wersji 3D). Na szybko powstały dwie metody:

private static int Calculate3Dto1D(int x, int y, int z, int sizeX, int sizeY, int sizeZ)
{
    return z * (sizeX * sizeY) + y * sizeX + x;
}

private static void Calculate1Dto3D(int k, int sizeX, int sizeY, int sizeZ, out int x, out int y, out int z)
{
    z = k / (sizeX * sizeY);
    int tmp = k % (sizeX * sizeY);
    y = tmp / sizeX;
    x = tmp % sizeX;
}

Kod jest raczej prosty, przeliczanie indeksu jednowymiarowego na trójwymiarowy najlepiej rozrysować sobie na kartce – to mój najlepszy (w parze z ołówkiem) doradca ds. algorytmów Puszczam oczko Obie metody są symetryczne – jedna służy do przeliczania współrzędnych z 3D do 1D, druga odwrotnie (nazwy są samoopisujące się), w dalszej części będziemy używać tylko jednej z nich, ale obie lepiej oddają ideę tej metody. Poza tym zdziwić może nieużywanie w ciele metod parametru sizeZ. Tak naprawdę do przeliczania potrzebne są nam tylko dwa pierwsze wymiary kostki, ale dla jasności kodu (w wersji produkcyjnej można spokojnie usunąć ten parametr) zostawiłem go w obu metodach.

Kiedy wiemy już jak przeliczać indeksy, można uzyskać pożądany efekt przy użyciu tylko jednego wywołania metody Parallel.For. Kod źródłowy:

const int n = SizeX * SizeY * SizeZ;
Parallel.For(0, n, i =>
{
    int x, y, z;
    Calculate1Dto3D(i, SizeX, SizeY, SizeZ, out x, out y, out z);
    tab[x, y, z] = ComputeSmth(x, y, z);
});

Podsumowanie

Nie zagłębiałem się jeszcze we właściwości tych klas i nie wiem jak w teorii wypada wydajność i rozłożenie wątków przy zagnieżdżonych wywołaniach Parallel.For, jednak testy pokazują, że najlepiej radzi sobie wersja ostatnia (czasy w formacie Min:Sec:Milisec).

test

Poza samą różnicą w czasie działania wersji równoległych, najbardziej cieszy mnie przyspieszenie osiągnięte w stosunku do wersji początkowej.

Mam nadzieję, że zachęciłem do zapoznania się z możliwościami nowego C# i korzyściami z tego płynącymi.

Be Sociable, Share!
czoper opublikowano dnia 2010-11-22 Kategoria: Programowanie | Tagi:, ,

Jedna odpowiedź Zostaw komentarz

  1. #1Łukasz Bartczak @ 2010-11-22 15:40

    Bardzo ciekawy post! Praktycznie widać zalety wykorzystania Parallel 😉 Na pewno skorzystam!

Zostaw odpowiedź

(Ctrl + Enter)