Parallella summor

Här följer några parallella varianter av summationsprogrammet. Det torde knappast löna sig att parallellisera ett så kort program, så detta är mest för att visa några av de hjälpmedel som finns när man arbetar med parallella numeriska koder.

Det finns väsentligen två sätt att parallellisera (numeriska) program. Om stora delar av ett program kan köras parallellt ("large (eller coarse) grain parallelism") kan man kanske klara sig med meddelandeskickning. Dvs. olika processer går på olika CPUer och kommunicerar, med explicita proceduranrop, via ett nätverk. Det finns flera paket som tillhandahåller denna funktionalitet. Det två vanligaste i numeriska sammanhang är PVM och MPI.

Om processerna är beräkningsintensiva och ej kommunicerar med varandra i någon större utsträckning är denna form av parallellisering mycket effektiv. I detta fall ställs mindre krav på parallelldatorn, en uppsättning av arbetsstationer/PC som kommunicerar via Ethernet är en budgetvariant. Ju mer processerna kommunicerar med varandra desto större krav ställs på nätverket (för att få goda prestanda). En nackdel med att använda PVM och MPI är att parallelliseringen ofta är mycket arbetskrävande (och medför en hel del avlusning; om t.ex. en process väntar på data och programmeraren har glömt att lägga in motsvarande Send-anrop så hänger programmet tills det dödas).

Ett mycket bekvämt sätt att parallellisera enkla loopar (fine grain parallelism) är att använda system som genererar trådad kod; man brukar köra en tråd på varje CPU. De olika trådarna arbetar på olika delar (olika iterationer) av loopen parallellt. Så för att kunna parallellisera en sådan loop får inte ordningsföljden mellan iterationerna spela någon roll. Resultatet av en iteration får inte bero på resultat av en annan. Den stora nackdelen med denna typ av parallellisering är att det krävs en "shared memory"-dator. I en sådan dator sköts meddelandeskickningen av operativsystem och hårdvara och programmeraren behöver inte själv (i någon större utsträckning) tänka på hur detta går till.

Om man är datalog kanske man skriver trådad kod direkt i C eller Java, vi numeriker använder dock normalt OpenMP som finns för både Fortran och C/C++. OpenMP, som är en standard, består av en uppsättning procedurer och direktiv som styr parallellisering. Ett typiskt direktiv säger "kör denna loop parallellt". Direktiven läses av en preprocessor eller av kompilatorn som automatiskt genererar den trådade koden.

Här följer en parallellt summationsprogram i Fortran90. Utropstecken markerar normalt en kommentar i Fortran90, men när jag kompilerar säger jag åt kompilatorn att tolka alla rader med !$omp som OpenMP-direktiv. Detta är en annan fördel med att använda OpenMP. Jag behöver inte göra så stora förändringar av källkoden. Om jag inte vill köra parallellt så använder jag inte den speciella kompilatorflaggan. 

program OpenMP_example
  integer :: k
  real    :: s


  call omp_set_num_threads(5)   ! sätt antalet trådar till 5

  s = 0.0
!$omp parallel do private(k) reduction(+:s) ! en parallell loop
  do k = 1, 1000000
    s = s + 1.0 / k
  end do

  print*, 's = ', s
end program OpenMP_example

% f90 -openmp omp.f90           kompilera
% a.out                         exekvera

private(k) betyder att varje tråd får en privat loopvariabel. Det går ju inte att ha en gemensam eftersom de olika trådarna arbetar på olika delar av loopen. En variabel som uppdateras av flera trådar ("många till en")  kallar vi reduktionsvariabel. En sådan variabel måste hanteras på ett speciellt sätt så att vi kan garantera att uppdateringen av summan görs på rätt sätt. reduction(+:s) ser till att s skyddas på detta sätt (+ är operationen i detta fall, s = s + ...). Ett effektivt sätt att lösa detta problem är att varje tråd får sin egen summationsvariabel, där tråden beräknar sin partialsumma. Efter loopen adderas så partialsummorna på ett säkert sätt (inom en sk "critical section", endast en tråd i taget får uppdatera summationsvariabeln, s). Så här ser motsvarande C-program ut: 

#include <stdio.h>

int main()
{
  int k;
  float s;

  omp_set_num_threads(5);

  s = 0.0;
#pragma omp parallel for private(k) reduction(+:s)
  for(k = 1; k <= 1000000; k++)
    s += 1.0 / k;

  printf("s = %f\n", s);
  return 0;
}

Om man inte har tillgång till en preprocessor eller kompilator som hanterar OpenMP så finns det flera gratisvarianter. Omni OpenMP Compiler Project  i Japan och OdinMP från KTH.

Observera att flera OpenMP-system kräver att man inkluderar headerfilen omp.h först i programmet (för att få tillgång till funktionsprototyper och konstanter).

Back