29. mars: Den vanskelige maskinen - hvordan programmerer vi den?

Kort om foredraget:

Datamaskinen har utviklet seg mye de siste 10-årene, men dette har også gjort det vesentlig vanskeligere å lage raske programmer.

I gamle dager var programmering 'enkelt' - en beregningsenhet (CPU) med ett lager/hukommelse hvor program og data lå. Foredraget vil fortelle hvordan og hvorfor dagens maskiner er helt annerledes. For nå å lage effektive programmer må man sette igang en rekke parallelle beregninger. Vi vil se på både riktige og håpløst feilaktige måter å lage parallelle beregninger i en moderne PC. Men fortvil ikke, følger man visse regler, er det fortsatt mulig å lage riktige og raske programmer!

Se også Arnes notater til presentasjonen (pdf) og nytt kapittel 19 i "Rett på Java" (pdf) der dette er beskrevet i mer detalj.

Oppsummering skrevet av Morten Dæhlen:

Før 1980 besto kjernen av datamaskinen av en CPU (regneenhet) og hukommelse. Regneenheten var rask, mens det å skrive og lese til hukommelsen var (og er) en tregere prosess. For å bøte på dette ble det utviklet mellomlagre eller såkalte “cache” for mer effektiv lagring av de data man brukte ofte. Det ble videre utviklet to eller flere nivåer med “cache” slik at data kunne graderes ut mot hovedhukommelsen. Slik så prosessoren  i en datamaskin ut i mange år!

CPUer med 2 eller flere “cache” ble stadig kraftigere i den forstand at stadig flere transistorer kunne plasseres på en databrikke (integrert krets). Når strøm kjøres gjennom transistorene i den integrerte kretsen utvikles varme og etter hvert som CPUene ble kraftigere og kraftigere ble de for varme. For å bøte på dette fant man ut at en databrikke kunne inneholde flere CPUer (CPU ble heretter kalt prosessor og hver beregningsenhet ble kalt en kjerne). Hver kjerne hadde da sine egne mellomlagre, men slik at begge kjernene  hadde en felles hukommelse. Vi fikk parallelle maskiner. Dette skjedd omkring år 2005. En annen form for parallelle enheter er grafikkprosessorer (GPUer) drevet fram av spillindustrien. I dag har de fleste datamaskiner en kjerne bestående av minst 2 kjerner, og det blir stadig mer vanlig med både 4, 8 og 16 kjerner i datamaskinens prosessor. Hvordan utnytte denne kraften?

Svaret er å kjøre programmet som flere tråder i parallell og da utføre såkalte parallelle beregninger. Her oppstår imidlertid noen utfordringer som Arne Maus snakket om i sitt foredrag, og det er særlig to forutsetninger som må være oppfylt før man kan utnytte flere kjerner i parallell:

1. Det må eksistere en naturlig oppdeling av den oppgaven man skal løse slik at hver deloppgave kan løses  for seg. Anta at vi har en prosessor med 8 kjerner og et bilde på 1024 x 1024 punkter (pixler) med gråtoneverdier mellom 0(sort) og 255(hvitt). Finne alle punkter i bildet med gråtoneverdier i intervallet [0-9]. Da kan bildet deles i 8 bilder hver på 512 x 256 punkter og hver av de 8 kjernene kan behandle hvert sitt bilde, dvs finne gråtoneverdier i intervallet [0-9]. Denne type problemstillinger kan parallellisering med tilnærmet full effekt, dvs. at 8 kjerner tilnærmet går 8 ganger så hurtig som én kjerne.
2. Oppgaven må være stor nok, dvs. at man ikke får effekt av en parallellisering før problemet har en viss størrelse. Et klassisk eksempel er sortering av tall – et eksempel Arne Maus gikk gjennom i detalj. Anta at vi har en prosessor med 8 kjerner og N usorterte tall. Da finnes det en algoritme/metode som heter kvikksort for å sortere disse tallene i stigende rekkefølge. Denne algoritmen kan parallelliseres over 8 kjerner, men den vil ikke være raskere enn en sekvensiell prosessering (dvs. sortering på én kjerne) før N er omkring 1 million. Skal man sortere 10 millioner eller flere tall vil en parallellisering over 8 kjerner gå 3-4 ganger raskere enn på én kjerne. I motsetning til bildeeksemplet over er kvikksort en mer sammensatt problemstilling, og effekten er derfor mindre. Det er til og med slik at effekten er negativ dersom problemet ikke er stort nok.

I tillegg til de to forutsetningen som må være tilstede for at parallellisering gir effekt er det en særlig utfordring å synkronisere prosessene på de ulike kjernene slik at 1) de samarbeider i de tilfeller en kjerne er avhengig av resultater fra andre kjerner for å gjøre en jobb og 2) slik at de ikke arbeider på de samme dataene i hukommelsen samtidig. Dette finnes det mekanismer for i de fleste programmeringsspråk i dag, f.eks. i Java.

Arne Maus snakket mye om “tråder”, som er en betegnelse på én beregningsprosess i et program som gjør en sekvensiell jobb på en kjerne. En tråd kan starte nye tråder og disse vil av operativsystemet bli sendt til andre kjerner. Et klassisk eksempel har vi foran oss når vi spiller dataspill der all tastingen på tastaturet eller signalene fra en “joystick” håndteres i én tråd på én kjerne som igjen gir signaler til figurene som beveger seg og tegnes ut på skjermen ved hjelp en eller flere andre tråder på andre kjerner eller en GPU (som i seg selv er en parallell datamaskin spesiallaget for å tegne bilder på en dataskjerm).