Parallelitet i Java

Samtidighed (engelsk concurrency) er når noget sker samtidigt. Parallitet er når noget sker på samme tid. For at man kan have parallelitet er man nødt til at have flere beregningsenheder, altså processorer. Parallelitet går ud på at udnytte den kraft.

Lad os sige du vil lægge en masse tal i en array sammen. Du kan lave en løkke som går gennem alle tallene og lægger dem sammen. Men hvis du har 8 kerner i din computer udnytter du kun en af dem.

 long sum = 0;
 for(int i=low; i < high; ++i) 
     sum += array[i];
 return sum;

Spørgsmålet er så, i stedet for at én kerne beregner alt, kan vi bruge de 7 andre kerner til det også? I dette tilfælde og andre er svaret ja, men det er ikke altid tilfældet. Specielt dette eksempel er nemt at parallelisere. Vi tager en liste af tal og beregner en sum. Hvis vi nu delte arbejdet op i 8 dele, får vi 8 mindre lister. Hver kerne kan beregne summen af en af listerne. Til sidst står vi tilbage med 8 summer, for at få den endelige sum skal de 8 tal bare lægges sammen.

Så i stedet for at gøre dette

// [#1, #2, ...] array med tal, #1 er det første tal.

Kerne #1:   [#1, #2, ..., #8000]   ->   Sum
Kerne #2 laver ingenting
Kerne #3 laver ingenting
Kerne #4 laver ingenting
Kerne #5 laver ingenting
Kerne #6 laver ingenting
Kerne #7 laver ingenting
Kerne #8 laver ingenting

Gør vi dette:

Kerne #1:   [#1,       #2, ..., #1000]   ->   Sum #1
Kerne #2:   [#1001, #1002, ..., #2000]   ->   Sum #2
Kerne #3:   [#2001, #2002, ..., #3000]   ->   Sum #3
Kerne #4:   [#3001, #3002, ..., #4000]   ->   Sum #4
Kerne #5:   [#4001, #4002, ..., #5000]   ->   Sum #5
Kerne #6:   [#5001, #5002, ..., #6000]   ->   Sum #6
Kerne #7:   [#6001, #6002, ..., #7000]   ->   Sum #7
Kerne #8:   [#7001, #7002, ..., #8000]   ->   Sum #8

Også til sidst lægges de 8 summer sammen.

Kerne #1:   Sum = Sum #1 +  Sum #2 + ... + Sum #8

På den måde skal hver kerne kun lægge 1000 tal sammen, i stedet for at en enkelt lægger alle 8000 tal sammen.

Dette er den basale tilgang. Der er nogle ting som ikke er så gode ved denne løsning dog. F.eks. er den lavet specifik til 8 kerner. Så hvis man kører den hos en med 16 kerner udnytter man ikke alt computerkraften. På den kører man den på en computer med kun én kerne vil det køre lidt langsommere fordi processen skal skifte mellem 8 tråde, og det ville være bedre hvis der bare var en enkelt tråd. En sidste ting er at selv med den rigtige antal tråde kan det være en tråd er færdig hurtigere end de andre og så laver ingenting mens de andre arbejder, hvilket også er spild.

Nu spørger du bestemt om Java. En måde er manuelt at oprette tråde og fordele arbejdet ud blandt dem. Men dette er en ret primitiv måde at gøre tingene på. Over tiden er der kommet framework til for at gøre arbejdet nemmere. En populær tilgang, som nu er med i Java 7, som også håndterer ovenstående problemer, er Fork-Join tilgangen.

Fork betyder at man deler en opgave i mindre bidder. F.eks. i stedet for løse SUM(8000 tal), kan man dele det op i 2 x SUM(4000 tal) - (eller 8 x SUM(1000 tal) som vidst før ). Læg mærke til at du kan gentage denne opdeling, f.eks. kan man yderlige opdele SUM(4000 tal) til 2 x SUM(2000 tal).

Join betyder at man samler delresultaterne. I dette tilfælde vil det være at lægge summerne sammen. Andre problemer kunne være at man havde en lang tekst og ville tælle antallet af punktummer. Fork (opdel) teksten i to dele, og find hvor mange punktummer der i hver del. Join dem ved at lægge hvor mange punktummer der var i hver del sammen.



Jeg har fundet et eksempel fra http://homes.cs.washington.edu/~djg/teachingMaterials/grossmanSPAC_forkJoinFramework.html , vidst nedenunder som lige præcis lægger tal sammen via. Java's fork join framework.

En opgave er Sum som her er arver fra en RecursiveTask som beregner en long, altså et tal. RecursiveTask er fra Fork/join frameworket. Der sættes en bagetelgrænse på 5000 tal, dvs. når der er færre end 5000 tal i en delopgave gider vi ikke at splitte mere. Den bruges i linje 22 som siger at hvis vi har under 5000 tal i denne opgave så bare beregn resultatet.

Det mere interessante er hvis der stadig er mere end 5000 tal. Så opdeles problemet i to dele på linje 28-30. Den venstre del bliver forket, som en helt ny opgave, og ellers fortsættes der med at beregne den højre del. Efter den højre del er færdig med summen, er vi nødt til at vente på den venstre del er også er færdig. Når den er det kan de to tal lægges sammen som resultatet.

 import java.util.concurrent.ForkJoinPool;
 import java.util.concurrent.RecursiveTask;
 
 class Globals {
     static ForkJoinPool fjPool = new ForkJoinPool();
 }
 
 class Sum extends RecursiveTask<Long> {
     static final int SEQUENTIAL_THRESHOLD = 5000;
 
     int low;
     int high;
     int[] array;
 
     Sum(int[] arr, int lo, int hi) {
         array = arr;
         low   = lo;
         high  = hi;
     }
 
     protected Long compute() {
         if(high - low <= SEQUENTIAL_THRESHOLD) {
             long sum = 0;
             for(int i=low; i < high; ++i) 
                 sum += array[i];
             return sum;
          } else {
             int mid = low + (high - low) / 2;
             Sum left  = new Sum(array, low, mid);
             Sum right = new Sum(array, mid, high);
             left.fork();
             long rightAns = right.compute();
             long leftAns  = left.join();
             return leftAns + rightAns;
          }
      }
 
      static long sumArray(int[] array) {
          return Globals.fjPool.invoke(new Sum(array,0,array.length));
      }
 }

Det Fork-Join frameworket så gør er automatisk at tildele opgaver til kerner. Læg mærke til vi kan sagtens lave flere "opgaver" end der er kerner. Så en kerne kan få flere opgaver at løse. På den måde kan vi altid udnytte den computerkraft der er tilgængelig, selv hvis det kun er en 1 kerne. Hvis en kerne bliver færdig med alle sine opgaver før de andre, er der yderlige en feature kaldet "works stealing". Det indebærer at den færdige kerne stjæler noget arbejde fra en anden kerne og begynder på det. Det undgår problemet nævnt tidligere med at man står med en kerne der ikke laver noget.

Takkker

Super seriøst svar Søren. Respekt!