Language Cafe followup: Parallel Extensions

 
31 mei 2008

Afgelopen maandag organiseerde Sogyo Academy weer een Language Café. Tijdens deze avond werd er gekeken naar verschillende ontwikkelingen op het gebied van ontwikkeltalen. Rob Vens heeft de avond geopend door de evolutie van ontwikkeltalen laten zien. Daarna zijn we in tracks dieper op de materie ingegaan en gekeken hoe talen als Erlang de huidige problemen als parallelisering op proberen te lossen. Naast Erlang was er een Smalltalk, Java en C# track. Waarbij ik als C# MVP de laatste track heb gevuld.

C# Track

Tijdens het café heb ik proberen te laten zien hoe we in C# onder anderen het probleem van parallellisering oplossen. Voor de mensen die er niet bij waren, hier mijn verhaal nogmaals maar dan in tekstuele vorm. Een verhaal over Spec# zal later volgen.

Multi core toekomst

Intel's 80 core CPUIn de afgelopen jaren is de kloksnelheid van processoren enorm gestegen. De 1.02MHz die ik op mijn Commodore 64 tot mijn beschikking had stelt niets meer voor als we dit vergelijken met de 2.4GHz in mijn huidige machine. Alleen, als ik kijk naar de machine die ik een paar jaar geleden gebruikte had deze ook zo’n 2.4GHz. Het verschil zit hem in het aantal cores. Mijn huidige machine heeft twee cores tot zijn beschikking terwijl mijn machine van een paar jaar geleden er nog maar een had.

Het limiet van het aantal hertz in een core zijn door het niet sneller af kunnen voeren van warmte bereikt en in de toekomst zullen we enorme een toename van het aantal cores in een processor zien. Zo presenteerde Intel begin 2007 nog een 80-core processor en als we Justin Ratner mogen geloven zal dit binnen 10 jaar als standaard worden gezien. Dit is een beweging die veel invloed heeft. Omdat we dingen niet sneller meer kunnen uitvoeren gaan we meerdere dingen tegelijk doen om de snelheid te verhogen. Veel van de huidige software is hier niet op voorbereid. Deze softeware is single threaded en sequentieel waardoor ze geen gebruik maken van de multi core omgeving. Bij een quad-core processor gebruikt single threaded software maximaal maar 25% van de rekenkracht.

Het grote aanbod van single threaded software is goed te verklaren: multi core is een vrij nieuw begrip en om deze cores te benutten moeten processen geparallelliseerd worden. Het parallelliseren van een process introduceert problemen als concurency en maakt het ontwikkelen van software ‘nog’ complexer.

Voordat software de voordelen van de een multi core omgeving optimaal zal benutten zullen eerst de talen en tools waarmee de software wordt gebouwd aangepast moeten worden aan deze nieuwe behoefte.

Parallellisering nowadays

Als we in een .NET omgeving een process willen paralelliseren kunnen we gebruik maken van de classes in de System.Threading namespace. Hier vinden we onder andere de Thread, monitor, ManualResetEvent en de ThreadPool.

Met de huidige threading API kunnen we threads niet hergebruiken, moeten we weten wat de verschillen zijn tussen een Pulse en een Signal en zullen we onder andere zelf optimalisatie omtrent de beschikbaren hardware toepassen.

Als we kijken naar de code van voorbeeld 1 dan zien we dat er bij het creëren van het resultaat geen side-effects te vinden zijn.

We praten van een side effect als een functie of een statement invloed heeft op de huidige state. Bijvoorbeeld als een functie een variable buiten zijn eigen private scope aanpast, een bestand uitleest. Het tegenovergestelde van een side effect noemen we safe.

Voorbeeld 1

public void MultiplyMatrices(int size, double[,] m1, double[,] m2, double[,] result)
{
    for (int i = 0; i < size; i++)
    {
        for (int j = 0; j < size; j++)
        {

            result[i, j] = 0;
            for (int k = 0; k < size; k++)
            {
                result[i, j] += m1[i, k] * m2[k, j];
            }
        }
    }
}

Als we de operatie optimaal willen parallelliseren zullen we het statement waarin de cell inhoud van m1 met m2 word vermenigvuldigd moeten verdelen over meerderen threads. Waarbij het aantal thread gelijk is aan het totaal aantal cores waarover we beschikken. We zullen de threads op een aantal plekken moeten synchroniseren en voordat we een return uitvoeren aan het einde van de methode zullen we moeten wachten totdat alle thread klaar zijn met hun werk. Het resultaat van het parallelliseren van de code uit voorbeeld1 zien we in voorbeeld 2.

Voorbeeld 2

int N = size;
int P = 2 * Environment.ProcessorCount;
int Chunk = N / P;                      // size of a work chunk
ManualResetEvent signal = new ManualResetEvent(false);
int counter = P;                        // use counter to reduce kernel transitions
for (int c = 0; c < P; c++)
{
    // for each chunk
    ThreadPool.QueueUserWorkItem(o =>
    {
        int lc = (int)o;
        for (int i = lc * Chunk;                 // process one chunk
             i < (lc + 1 == P ? N : lc * Chunk); // respect upper bound
             i++)
        {
            // original loop body
            for (int j = 0; j < size; j++)
            {
                result[i, j] = 0;
                for (int k = 0; k < size; k++)
                {
                    result[i, j] += m1[i, k] * m2[k, j];
                }
            }
        }
        if (Interlocked.Decrement(ref counter) == 0)
        {   // efficient interlocked ops
            signal.Set();  // and kernel transition only when done
        }
    }, c);
}
signal.WaitOne();

De essentie is bijna niet meer terug te vinden en er is meer code nodig om te parallelliseren dan eerste instantie nodig was voor de operatie. Ook is het lastig geworden om aanpassingen te doen in deze code en spreekt de code niet meer voor zichzelf. We kunnen concluderen dat het huidige .NET framework niet klaar is voor het parallelliseren van operaties. Niet alleen ik trek die conclusie, maar Microsoft zelf ook. Microsoft wil dit probleem oplossen met de introductie van de Parallel Extensions.

Parallel Extensions

Met de komst van de Parallel Extensions introduceert Microsoft een toevoeging aan de .NET omgeving Deze toevoeging stelt de .NET ontwikkelaar in staat om af te stappen van sequentiële operaties naar operaties waar werk verdeeld wordt over verschillende threads. Dit alles zonder dat de ontwikkelaar veel extra kennis nodig heeft van de techniek en threading. Wel is het noodzakelijk dat een ontwikkelaar op de hoogte is van concurency problemen en zal er bij het ontwikkelen rekening moeten worden gehouden met de beperkingen die gesteld worden aan broncode.

Een belangrijke class binnen de Parallel Extensions is Parallel. Deze class kunnen we gebruiken voor het parallelliseren van veel voorkomende code als: een lijst van taken, for-loop en een foreach-loop. Met deze class kunnen we de code uit voorbeeld 1 met een kleine aanpassingen parallelliseren zoals te zien is in voorbeeld 3.

Voorbeeld 3

public void MultiplyMatrices(int size, double[,] m1, double[,] m2, double[,] result)
{
    Parallel.For(0, size, i => {
        for (int j = 0; j < size; j++)
        {
            result[i, j] = 0;
            for (int k = 0; k < size; k++)
            {
                result[i, j] += m1[i, k] * m2[k, j];
            }
        }
    });
}

De Parallel.For methode zal van 0 tot en met de waarde van Size het gespecificeerde code block uitvoeren. Voor het uitvoeren zal de Parallel class taken aanmaken die bestaan uit instanties van de Task class en zal de TaskManager class gebruiken voor het uitvoeren van deze taken. De TaskManager heeft weet van de hardware en kan vertellen wat het ideaal aantal threads is om onze for-loop mee uit te voeren. Bij het verdelen van taken word er rekening gehouden met de cache op de processor, threads die beschikbaar zijn en volgordelijkheid van de taken. Default is er altijd een instantie van de TaskManager aanwezig die gebruikt word als er geen een gespecificeerd word. De API stelt je dus wel in staat om zelf een TaskManager aan te maken en het minimaal, ideale en maximale aantal thread te specificeren hoe er geparallelliseerd kan worden wordt door de Parallel Extension bepaald. Het enige wat je nog hoeft te declareren is wat er parallel uitgevoerd kan worden. Wel geeft de API je de vrijheid om dingen zelf te bepalen. Zo zijn er overloads beschikbaar binnen de Parallel class waarin je zelf een op kunt geven waarin je zelf de Thread selecteert die een Task gaat uitvoeren.

Parallel LINQ

Met de introductie van het .NET Framework 3.0 hebben wij als .NET ontwikkelaars LINQ tot onze beschikking. De parallel extensions voegen ook een parallelle versie van LINQ toe genaamd PLINQ (Parallel LINQ). Deze LINQ provider geeft ons de mogelijkheid om een LINQ query parallel uit te voeren. Dit is vooral handig als je in je query veel berekeningen of vergelijkingen doet. Als je een query wilt parallelliseren dan hoef je dit alleen maar te specificeren. De Parallel Extensions voegen namelijk een extensions method AsParallel toe aan de IEnumerable<T> interface zoals te zien in code voorbeeld 4. Door deze extentie method kunnen we een LINQ query gemakkelijk parallelliseren. In code voorbeeld 5 vermenigvuldigen we alle integers en stoppen het resultaat in een array. In code voorbeeld 6 doen we hetzelfde maar dan parallel.

Code voorbeeld 4

public static IParallelEnumerable<T> AsParallel<T>(this IEnumerable<T> source)
{
    ...
}

Voorbeeld 5

public static int[] MultiplyAllSeq(int[] source)
{
    return (from num in source
            select (int)Math.Pow(num, 2)).ToArray();
}

Voorbeeld 6

public static int[] MultiplyAllPar(int[] source)
{
    var options = ParallelQueryOptions.PreserveOrdering;
    var parallelSource = source.AsParallel(options); 

    return (from num in parallelSource
            select (int)Math.Pow(num, 2)).ToArray();
}

Conclusie

De Parallel Extensions is het antwoord van Microsoft op de multi-core toekomst. Het stelt de .NET ontwikkelaar in staat op met minimale kennis en code processes en operaties te parallelliseren. De API kent een gemakt waarmee het mogelijk wordt om te declareren en niet te hoeven specificeren; in tegen stelling tot de huidige threading classes van het .NET Framework.

Wel zullen ontwikkelaars concurrency problemen als deadlocks en raceconditions moeten kennen en zullen ontwikkelaars vaker moet nadenken over threadsafe code zonder side effects.

Resources


Werken met ?
Kijk dan bij onze mogelijkheden voor zowel starters als ervaren engineers.


Categorieën: Development, .Net

Tags: , , , , , , ,


Reactie

  • slibbe schreef:

    Een vraag meer over de problematiek dan over deze oplossing:
    Waarom zijn de oplossingen die al bestaan voor systemen met twee of meer processoren niet toepasbaar bij meerdere cores?
    Waarin verschilt de uitdaging van de meerdere cores van het programmeren voor meerdere processoren?

    Geplaatst op 01 maart 2009 om 1:13 Permalink