Az idei PDC-n elég sok szó esett a párhuzamos programozásról, legfőképpent a Microsoft új libraryjéről, a concurrency run-time-ról, vagyis a ConCRT-ről. Ezért úgy gondoltam végzek egy kis tesztet ezzel a még meg sem jelent libraryvel, valamint a piacon lévő egyéb ingyenes megoldásokkal. A teszt magja az a prímszámkeresés, amit a PDC-n is használtak. Sajnos azonban az gépemben nincs 4 magos CPU, csak 2 magos, így a gyorsulás is ennek megfelelően 2 alatti. De nem csak a CPU-n teszteltem a párhuzamos libraryk teljesítményét, hanem az nVidia CUDA-jával a videókártyámon is. Ez utóbbi 14 multiprocesszort tartalmaz, azaz egyszerre 112 hardverthreadet tud futtatni. A konfiguráció: Intel Core2 Duo E8400 3.0 GHz, memória: DDR2 1 GHz, videókártya: 8800GT core clock: 600 MHz, Memória: 900 MHz, shader: 1500 MHz. Lássuk hát az eredményeket:

Mind release-ben futott default beállításokkal. GCC-nél bekapcsoltam a sebességoptimalizációt, ami MSVC-nél alapból be van kapcsolva, de ez sem segített rajta. A mérés egy 30000000-s egésztömbön zajlott, amibe meghatározott sorrendbe 1 és 50000 közötti számokat tettem. Majd ezt 10-szer lefuttattam. Először egszer lefuttattam a párhuzamos verziót, hogy az esetleges indulási jelenségek, mint például a library inicializálása, ne számítson bele a mérésbe. Majd lefuttattam egy sima 1 threades verziót a CPU-n. És végül a párhuzamos verziót. A gyorsulás egyszerűen a két idő hányadosa.

Amint látható a gyorsulás az Intel Threading Building Blocks és az OpenMP esetén 80% körüli, ami igen jó. Ellentétben a ConCrt-vel, ahol csak 40% körüli gyorsulást sikerült elérni. Jól látható még, hogy a GCC eleve hátrányból indul, egyszerűen gyengébben optimalizálja a kódot. De még így sikerül beérnie a ConCrt-t alig egy másodpercre. Ez olyan, mint amikor a Forma 1-ben két pilóta eszeveszett küzdelmet folytat az utolsó pontszerző helyért. Kemény verseny, de a két pilótán kívül senkit nem érdekel. Az is jól látszik, hogy a CUDA tetemes előnyre tett szert, jóval gyorsabb, mint a CPU-n futó tesztek. Azért engebb nem nyűgözött le, általában azt szokták mondani, hogy a GPU-k teljesítménye egy nagyságrenddel nagyobb a CPU-knál. Hát itt ez most nem áll meg. Ez úgy 56% 40%-kal gyorsabb csak a leggyorsabb CPU-s tesztnél. (A nagyobb értékek túlhúzott GPU-nál jelentkeztek. A túlhúzott GPU sebessége ez volt: core: 700 MHz, RAM: 1010 MHz, Shader: 1750 MHz) Kétféle CUDA teszt van, az első módszerben egyszerűen párhuzamosítottam a kódot: minden thread egy-egy számot tesztel. Mivel 32-esével kötegelve vannak a threadek, ez azt jelenti, hogy ha egy számot hosszú ideig tesztel, az 31 másik threadet visszafog. Ezért azt csináltam a második módszerben, hogy 32 threadenként tesztel egy számot. Így csak az utolsó menetben lehet némi üresjárat. Láthatóan gyorsabb is.

Nos, a ConCRT nem győzött meg. Először is lassú (legalábbis alapbeállítások mellett), másodszor is kizárólag Visual Studioval lehet használni. Ez pedig azt jelenti, hogyha a távoli jövőben a programunkat szeretnénk esetleg más platformokra is átültetni, nem célszerű használni. Olyan egyszerű eseteknél mint ez is, ahol csak pár threadre van szükség, nem lehet gond az átírás, de amikor már taszkokat kezdünk készíteni, aszinkron ágensek küldözgetnek jobbra-balra üzeneteket, akkor már komoly gondban leszünk. Tehát jól meg kell fontolni a használatát. Mármint akkor, ha release-re sikerül begyorsítaniuk. (Bár persze az is lehet, hogy az express verzió miatt volt lassítva, ki tudja.)

Gondolom többeket érdekel a kód is. Nos, itt jönnek.

Először is egy prím tesztelése a CPU-n így történt:

bool isPrime(int x)
{
    if (x <= 2) return x == 2;
    if (x % 2 == 0) return false;
    int sqrtx = static_cast<int>(ceil(sqrt(static_cast<double>(x))));
    for (int i = 3; i <= sqrtx; i += 2)
        if (x % i == 0) return false;
    return true;
}Ez gyakorlatilag megegyezik a PDC-n látott kóddal. Ezután a VS2008-as Intel TBB kód:

class PrimeTestFunctor
{
private:
    int *src;
    bool *result;
public:
    PrimeTestFunctor(int *p_src, bool *p_result):
      src(p_src), result(p_result)
      {
      }

    void operator()(const blocked_range<size_t>& r) const
    {
        for (size_t i = r.begin(); i != r.end(); ++i)
            result[i] = isPrime(src[i]);
    }
};

void parallelPrimeTest(int *src, bool *result, size_t length)
{
    parallel_for(blocked_range<size_t>(0, length), PrimeTestFunctor(src, result));
}


A 2008-as Visual Studioban még functort kellett alkalmazni a TBB használatához. De a 2010-esben már lehet lambdafüggvényt is. Voilà:

void parallelPrimeTest(int *src, bool *result, size_t length)
{
    parallel_for(blocked_range<size_t>(0, length),
        [&] (const blocked_range<size_t>& r)
        {
            for (size_t i = r.begin(); i != r.end(); ++i)
                result[i] = isPrime(src[i]);
        });
}
Ugye mennyivel rövidebb? És végül a concurrency runtime-mal így néz ki a kód:

void parallelPrimeTest2(int *src, bool *result, size_t length)
{
    parallel_for(static_cast<size_t>(0), length,
        [&] (size_t i)
        {
            result[i] = isPrime(src[i]);
        });
}
Az 1. CUDA módszer:

__device__ bool isPrime(int x)
{
    if (x <= 2) return x == 2;
    if (x % 2 == 0) return false;
    int sqrtx = static_cast<int>(ceilf(sqrtf(x))); // int sqrtx = static_cast<int>(__fsqrt_ru(x));
    for (int i = 3; i <= sqrtx; i += 2)
        if (x % i == 0) return false;
    return true;
}

__global__ void checkPrime(int* source, int* destination)
{
    int index = threadIdx.x + blockIdx.x * blockDim.x;
    destination[index] = isPrime(source[index]);
}
Ebből a checkPrime függvény hívható a CPU-ról, a másik belső függvény, ami nagy valószínűséggel inline-osodik. A 2. CUDA módszer kicsit bonyolultabb:

const int numbersPerBlock = 16;
const int blockSize = numbersPerBlock * 32;
__shared__ volatile int values[numbersPerBlock];
__shared__ volatile int numbers[numbersPerBlock];

__global__ void checkPrime2(int* source, int* destination)
{
    // Kiszamitjuk az offszeteket.
    int sharedOffset = threadIdx.x / 32;
    int globalOffset = blockIdx.x * numbersPerBlock + sharedOffset;

    // Beolvassuk a szamot.
    int thread = threadIdx.x % 32;
    if (thread == 0)
        values[sharedOffset] = source[globalOffset];
    int x = values[sharedOffset];

    // Jelezzuk, hogy a szamrol meg lehet, hogy prim.
    if (thread == 0)
        numbers[sharedOffset] = 1;

    // Vegigmegyunk a lehetseges osztokon.
    if (x <= 2)
    {
        if (thread == 0)
            destination[globalOffset] = x == 2 ? 1 : 0;
        return;
    }
    if (x % 2 == 0)
    {
        if (thread == 0)
            destination[globalOffset] = 0;
        return;
    }

    int sqrtx = static_cast<int>(ceilf(sqrtf(x))); // int sqrtx = static_cast<int>(__fsqrt_ru(x));
    for (int i = 3; i <= sqrtx; i += 64)
    {
        if (((i + thread * 2) > sqrtx) || (numbers[sharedOffset] == 0))
            break;
        else if ((x % (i + thread * 2)) == 0)
            numbers[sharedOffset] = 0;
    }

    // Kiirjuk az eredmenyt.
    if (thread == 0)
        destination[globalOffset] = numbers[sharedOffset];
}
Itt jól látható, hogy a shared memóriát aktívan használja, hogy egy warpon belül a threadek jelezzenek egymásnak. A volatile azért szükséges, hogy mindig a memóriához férjen hozza, ne optimalizálja ki regiszterekbe a változót.

A jövőben fogok még egy mérést végezni. Az a Conway-féle életjáték sebességét fogja tesztelni. Remélhetőleg az már jobban áll a GPU-nak. De ott bejön az SSE2 is konkurrenciának.