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 ¨C 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 ÑDz©ÓéÀÖ¹ÙÍø_ÑDz©ptÊÖ»ú¿Í»§¶ËµÇ¼er 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).