Subsections

5 Forelesning 9/2-12(2 timer). Cahce, multitasking og hyperthreading 


Avsnitt fra Tanenbaum: 1.3-1.6

5.1 Sist

5.1.1 CPU-intensiv prosess på Mac med to CPU'er

Mac OS X sin operativsystemkjerne heter Darwin og bygger blant annent på FreeBSD-kjernen som er en Unix-kjerne bygd på den opprinnelig BSD Unix-versjonen. Dermed følger det som standard også med mye som er kjent fra Linux. For eksempel kan får man opp et bash-shell når man starter opp et Mac OS X-terminalvindu: 

harek-haugeruds-macbook:~ hh$ uname -a
Darwin dhcp-202-136.wlan.hio.no 9.5.1 Darwin Kernel Version 9.5.1: Fri Sep 19 16:19:24 PDT 2008; root:xnu-1228.8.30~1/RELEASE_I386 i386
Som vi ser er dette kjerneversjon 9.5.1 av Darwin og denne har en enda mer rettferdig måte å dele to CPU'er mellom tre prosesser på. Når man kjører det samme regn-scriptet, får man følgende resultat: 

$ top -o cpu
Processes:  48 total, 5 running, 43 sleeping... 176 threads             21:43:01
Load Avg:  3.16,  1.85,  0.83    CPU usage: 89.27% user, 10.73% sys,  0.00% idle

  PID COMMAND      %CPU   TIME   #TH #PRTS #MREGS RPRVT  RSHRD  RSIZE  VSIZE
  170 bash        63.9%  2:33.80   1    13     19  192K   704K   692K    18M 
  168 bash        63.8%  2:56.34   1    13     19  192K   704K   692K    18M 
  169 bash        62.1%  2:35.43   1    13     19  192K   704K   692K    18M
Man ser at tiden deles praktisk talt likt mellom de tre prosessene.

5.2 Internminne og Cache

Vi har sett at CPU'en kan lese og utføre maskininstruksjoner og disse blir hentet inn til registerne fra internminnet. Dette minnet blir også kalt RAM, forkortelse for Random Access Memory, fordi enhver random byte kan leses ut like raskt som enhver annen. Maskinkoden for operativsystemet og andre programmer som skal kjøres må først lastes inn i internminnet fra disk. Deler av programmene kan hentes senere ved behov. Selvom det går omtrent hundre tusen ganger raskere å hente data fra internminne enn å hente data fra harddisken, tar det alt for lang tid i forhold til hvor fort moderne CPU'er kan behandle data. De raskeste prosessorene yter mer enn 1000 MIPS (Million Instructions Per Second), det vil si mer enn en milliard ($10^{9}$) instruksjoner i sekundet. Hvis CPU'en måtte vente på data fra RAM for hver instruksjon den skulle gjøre, ville mange prosesser gått ti ganger så sakte som de gjør nå. For å kunne fore en hurtig prosessor med instruksjoner og data raskt nok, bruker man flere nivåer av mellomlagring av data, såkalt cache-minne. Det går vesentlig raskere å hente minne fra cache-minnet enn fra internminnet. I tillegg har det vist seg at de fleste programmer i 90% av tiden utfører instruksjoner innenfor 10% av det totale minnet. Når CPU ber om en instruksjon som ligger et bestemt sted i minnet, hentes derfor ikke bare denne instruksjonen, men for eksempel 32 KByte av minnet. Alt dette lagres i cache og når CPU ber om neste instruksjon, ligger den ofte i cache, slik at den ikke må hentes fra internminnet. Fig. 12 viser noen typiske størrelser og aksesstider for de sentrale lagringsmedien som finnes i en datamaskin, fra registere til harddisk. Legg spesielt merke til den store forskjellen i aksesstid mellom internminne og harddisk.

Figure: Minne-pyramiden. Størrelsen og tiden det tar å hente data øker nedover pyramiden.
\includegraphics[width=18cm]{fig/osaCache.eps}
Både CPU-registere og cache er vanligvis laget av SRAM (Static RAM). Aksess er meget hurtig og SRAM er statisk i den betydning at det ikke trenger å oppfriskes, slik DRAM (Dynamic RAM) må. Mer en 10 ganger i sekundet må DRAM opplades, ellers forsvinner informasjonen. SRAM består av 6 transistorer for hver bit som lagres, til sammenligning består en NOT-port av to transistorer og AND og OR-porter av 4. Men DRAM trenger bare en transistor og en kapasitator(lagrer elektrisk ladning) for å lagre en bit. Derfor er DRAM billigere, mindre og bruker mindre effekt og kan derfor lages i større enheter. Internminne består derfor av DRAM eller forbedrede varianter av DRAM. DDR3 SDRAM (Double-Data Rate type 3 Synchronus Dynamic RAM) er et av de foreløpig siste leddene av kjedene av forbedrede utgaver av DRAM.
Figure: Level 1 cache (L1) ligger nærmest CPU. L2 er større, men har lengre aksesstid. Større deler av instruksjoner og data blir hentet av gangen fordi det ofte blir brukt for dette senere.
\includegraphics[width=22cm]{fig/osaCache1.eps}
Cache inneholder både data og instruksjoner og deler av MMUs (Memory Management Unit) page-tables i TLB (Translation Lookaside Buffer). I L1 cache er ofte disse separert i egne enheter, mens L2 cache pleier å være en enhet. I de senere årene har man klart å få plass til L2 på selve prosessorchip'en (den lille brikken som utgjør mikroprosessoren, bare noen kvadratcentimeter stor).

Arkitekturen til en moderne prosessor kan da i grove trekk se ut som i Fig. 40.

Figure: Level 1 cache (L1) bestående av tre deler. I AMD Athlon 64 er TLB i tillegg delt i to deler, en for adresser til instruksjoner og en for adresser til data.
\includegraphics[width=18cm]{fig/osaCache2.eps}

Noen arkitekturer har i tillegg enda et lag i minnehierarkiet, en offchip L3 cache som sitter mellom mikroprosessoren og RAM.

5.3 Multitasking og Multiprocessing

Figure: Single og dual prosessor og dual core prosessorer. Den tykke linjen markerer grensen for brikken/chip'en
\includegraphics[width=24cm]{fig/dualcore.eps}

5.4 Multitasking og hyperthreading

Flere av Intels prosessorer som Pentium 4 og Xeon har såkalt hyperthreading teknologi. Det vil si at deler av CPU'en er duplisert, men for eksempel ikke ALU'en. Det gjør at en CPU kan inneholde to prosesser samtidig, slik at hvis den ene prosessen for eksempel bruker tid på å hente noe fra minne, kan CPUen ekstremt raskt switche over og la den andre prosessen bruke ALU'en. En slik overgang skjer i løpet av et nanosekund eller to. En normal context switch utført av OS tar flere tusen ganger så lang tid, flere mikrosekunder. Det å utføre instruksjoner for en prosess kalles en thread eller tråd. Det er basert på bildet av den linjen(tråden) som følges når et program utføres ved å hoppe i mellom instruksjonene som programmet består av. Mer om threads senere. I en CPU med hyperthreading er ikke fullstendig delt i to enheter, slik som kjernene i en dobbel core prosessorer hvor de er helt separate enheter. Et operativsystem oppfatter en hyperthreading CPU på samme måte som en duo core, som to CPU'er. Det kan derfor være vanskelig å se forskjellen, men det vil kunne sees av ytelsen.

IU-serveren huldra har to Intel Xeon prosessorer (på hver sin brikke, ikke multicore) som begge er hyperthreading. Som før bruker vi følgende CPU-slukende program: 


#! /bin/bash

(( max = 150000 ))
(( i = 0  ))
(( sum = 0  ))

echo $0 : regner....
while (($i < $max))
do
        (( i += 1 ))
	(( sum += i  ))
done
echo $0, resultat: $sum

Slik ser det ut på huldra om man starter 6 CPU-intensive regnejobber: 


top - 08:31:21 up 114 days, 23:25,  2 users,  load average: 6.04, 3.77, 1.62
Tasks: 221 total,   7 running, 214 sleeping,   0 stopped,   0 zombie
Cpu0  : 96.6% us,  3.4% sy,  0.0% ni,  0.0% id,  0.0% wa,  0.0% hi,  0.0% si
Cpu1  : 98.7% us,  1.3% sy,  0.0% ni,  0.0% id,  0.0% wa,  0.0% hi,  0.0% si
Cpu2  : 99.3% us,  0.7% sy,  0.0% ni,  0.0% id,  0.0% wa,  0.0% hi,  0.0% si
Cpu3  : 98.0% us,  2.0% sy,  0.0% ni,  0.0% id,  0.0% wa,  0.0% hi,  0.0% si

  PID   USER      PR  NI  VIRT  RES  SHR S %CPU %MEM    TIME+  P COMMAND
  27550 haugerud  25   0  3644 1340 1020 R   99  0.3   4:50.35 1 regn2
  27549 haugerud  25   0  3648 1344 1020 R   97  0.3   4:46.08 0 regn2
  27547 haugerud  25   0  3644 1340 1020 R   50  0.3   2:34.50 3 regn2
  27548 haugerud  25   0  3644 1340 1020 R   50  0.3   2:31.34 2 regn2
  27551 haugerud  25   0  3648 1344 1020 R   50  0.3   2:25.52 2 regn2
  27552 haugerud  25   0  3648 1344 1020 R   50  0.3   2:23.75 3 regn2


Linux-kjernen betrakter dette som fire uavhengige CPU'er. Av kolonnen P kan vi se at OS fordeler jobbene på de fire prosessorene, en på CPU 0 og 1 og to hver på CPU 2 og 3. Prosessene på CPU 2 og 3 må dele på CPU'en og får derfor i gjennomsnitt bare 50% CPU-tid som %CPU kolonnen viser. Prosessene på CPU 0 og 1 trenger ikke å konkurrere med andre CPU-krevende jobber og får dermed nesten 100% CPU-tid (Når man kjører top må man taste 1 for å se 4 øverste CPU-linjene og f fulgt av p og return for å se hvilke prosessorer som brukes).

5.4.1 Kjører en CPU med hyperthreading to prosesser reelt sett samtidig?

Men regner disse prosessene reelt sett samtidig? Hvis man setter igang fire regnejobber viser jo top at de jobber på hver sin CPU og at de hver får 100% CPU-tid. Men hvordan kan man finne ut om de virkelig gjør det?

På samme måte som om man ønsker å finne ut om fire potetskrellere man har ansatt for å skrelle poteter virkelig jobber samtidig. Man tar tiden på dem. Fire personer bør bruke like lang tid på å skrelle fire sekker poteter som to stykker bruker på to sekker poteter. Så vi setter igang to regnejobber som skreller ivei på hver sin av de to CPU'ene: 


huldra:~/hh/task# for i in $(seq 1 2); do time ./regn1& done
./regn1, resultat: 11250075000
real	0m4.971s
user	0m4.820s
sys	0m0.140s

./regn1, resultat: 11250075000
real	0m5.054s
user	0m4.928s
sys	0m0.124s

Jobben går unna på fem sekunder og det bør ikke ta lenger tid for fire prosesser hvis de reelt sett jobber samtidig: 


huldra:~/hh/task# for i in $(seq 1 4); do time ./regn1& done
./regn1, resultat: 11250075000
real	0m10.462s
user	0m10.189s
sys	0m0.276s

./regn1, resultat: 11250075000
real	0m10.472s
user	0m10.189s
sys	0m0.244s

./regn1, resultat: 11250075000
real	0m10.481s
user	0m10.137s
sys	0m0.304s

./regn1, resultat: 11250075000
real	0m10.479s
user	0m10.233s
sys	0m0.208s

Men det tar ganske nøyaktig dobbelt så lang tid. Som beskrevet tidligere, CPU'en har lastet inn to prosesser samtidig, men internt må de bytte på å bruke ALU'en og for slike prosesser som hele tiden bruker CPU har hyperthreading liten effekt.

5.5 Intel Core og AMD K10

Vi skal se litt på Intel Core i7 og AMD Opteron K10. De har mange likheter, begge er quad core, det vil si har 4 kjerner og har opptil 3.2 GHz klokkefrekvens. Cache-arkitekturen ligner også på hverandre, begge ser ut som i figuren:
Figure: Intel Core i7 og AMD Opteron K10. K10 kjernen har 512KB L2 cache og i7 kjernene har hyperthreading, ellers er de i store trekke relativt like.
\includegraphics[width=14cm]{fig/quadcore.eps}
En forskjell er at Intel Core i7 har hyperthreading i motsetning til de foregående Intel Core 2 prosessorene. Dermed kan den kjøre åtte prosesser samtidig. Men som vist i forrige avsnitt, for svært CPU-krevende prosesser har ikke dette så stor betydning, de må dele på beregnings .

Merk forøvrig: 30 MHz var maks klokkefrekvens for Intel i 1992 og den ble mer enn tredvedoblet pp åtte år fram til 2000 hvor de første GHz prosessorene kom. Men på de neste åtte årene ble frekvensen bare tredoblet. Det at det er vanskelig å øke klokkefrekvensen har gjort at man istedet har økt kapasiteten med multi core og hyperthreading.

5.6 Hvorfor kan ikke en prosess bruke to CPU'er?

Det ville vært ønskelig om et vilkårlig program kjøres fire ganger så raskt på en maskin med en quadcore prosessor(4 CPU'er på en brikke) som på en maskin med en enkelt CPU av samme type. Men det gjør generelt et program ikke, det bruker like lang tid om det har fire prosessorer, for det klarer bare å utnytte en prosessor av gangen. Slik at man bare får en gevinst av de fire prosessorene om man har flere programmer som kjører samtidig.

For å undersøke hvorfor det er slik, ser vi på assemblerkoden for et program som regner ut Fibonacci-rekken, 1 1 2 3 5 8 13 21 34 55 ..... I denne rekken er neste tall summen av de to foregående. Assemblerkode ligger tett opp til maskinkode, det er en litt mer lesbar utgave av maskininstruksjoner og kan sees på som den koden som CPU'en utfører en for en: 


1. MOV ax, 1   # ax = 1
2. MOV bx, 1   # bx = 1
3. ADD bx, ax  # bx = bx + ax
4. ADD ax, bx  # ax = ax + bx
5. JMP 3

Etter hver runde i denne evige løkken, vil ax og bx være siste og nest siste ledd i Fibonacci-rekken som er regnet ut. I instruksjon 3 settes bx lik summen av de to og i nummer 4 settes ax lik summen av de to og dermed har vi kommet to stepp videre i beregningen. Vi ser at det ikke er mulig for et operativsystem å fordele bergningene i en slik algoritme på flere CPU'er. Neste ledd i beregningen avhenger av det forrige og det tar uforholdsmessig lang tid å flytte verdier av registere fra en CPU til en annen. I dette tilfellet lar ikke algoritmen seg naturlig dele opp i separate bergningsdeler og da vil det også være vanskelig for en programmerer å dele opp beregningen i flere prosesser for å utnytte flere prosessorer. Følgende eksempel som regner ut summen

\begin{displaymath} S = 1 + 2 + 3 + 4 + \cdots + 2000 = \sum_{i=1}^{2000}i \end{displaymath}

er det i prinsippet letter å dele opp eller parallellisere som det kalles: 


1. MOV ax, 2001
2. MOV bx, 1
3. MOV cx, 0
3. ADD cx, bx   # cx += bx
4. INC bx          # bx++
5. CMP bx ax    
6. JNE 3            # Hopp til linje 3 hvis bx ikke er lik 2001

Etter dette programmet er avsluttet vil registereret cx være lik $S = \sum_{i=1}^{2000}i$. Det er lett å se at denne algoritmen i prinsippet kan deles i to. En CPU kan regne ut $\sum_{i=1}^{1000}i$ og en annen CPU kan regne ut $\sum_{i=1001}^{2000}i$ og så legger man sammen svarene til slutt. Men poenget er at operativsystemet ikke har noen anelse om hva som foregår i et vilkårlig program. Det bare sørger for at prosessene får utført sine instruksjoner. Derfor er det programmereren som eksplisitt må skrive programmet slik at det kjøres som to uavhengige prosesser for at det skal kunne utnytte flere CPU'er. En annen løsning er at programmet inneholder flere tråder(threads) som kan kjøres på hver sin CPU, dette kommer vi tilbake til senere. Threads i denne sammenhengen har ikke noe med hyperthreads å gjøre, disse threads styres av OS og ikke av prosessoren. Det har også blitt utviklet kompilatorer som til en viss grad klarer å parallelisere kode. Men operativsystemet kan ikke gjette seg til hva programmet gjør og kan derfor ikke på egenhånd få en enkelt prosess til å utnytte flere prosessorer.

Moderne spillkonsoller inneholder ofte mange CPU'er, XBOX 360 har tre og Playstation 3 har åtte CPU'er. For å kunne utnytte disse må spill-programmen som kjøres på dem skrives slik at de kan utnytte alle prosessorene. Programmererne deler da opp oppgavene i uavhengige deler slik at de kan beregnes hver for seg. Dette kalles å parallellisere koden. Tidligere var dette bare viktig i såkalte clustere satt sammen av mange datamaskiner, men med dagens utvikling hvor etterhvert alle datamakiner har flere CPU'er er dette viktig for alle programmer.

5.7 Multitasking eksempel

Bare rene regneprosesser bruker CPU hele tiden. Vanlige prosesser venter mye på I/O (Input/Output fra disk, nettverk etc.) og multitasking gir da mer effektiv utnyttelse av CPU.
Figure: Prosessene A og B kjørt med single og multitasking
\includegraphics[width=18cm]{fig/multitasking.eps}

5.8 Linux multitasking eksempler

Når to prosesser kjøres på en Linux-maskin samtidig, deler de på CPU'en. Her skal vi vise hvordan CPU'en effektivt utnyttes med multitasking når prosesser som ikke nødvendigvis bruker CPU'en hele tiden kjører. De fleste vanlige programmer som webbrowsere, teksteditorer, regneark etc bruker stort sett lite CPU. Det meste av tiden går med til å vente på I/O, input fra brukere, nettverkskort eller disk. Tidligere brukte vi følgende program til å illustrere et program som ikke bruker mye CPU:

io1 (bruker lite CPU): 

#! /bin/bash

echo "start" > fileio1
(( max = 600 ))

echo $0 : skriver til fileio1....
(( i = 0 ))
while (( $i < $max )) 
do
        echo $i >> fileio1
        (( i += 1 ))
done

Men en stor effektivisering av hvordan bash utfører dette har gjort at filskrivingen blir så effektiv at CPU brukes nærmest 100%. For å illustrere effekten av et program som bruker tid fordi det venter på en prosess som ikke CPU'en har kontroll over, bruker vi istedet følgende kode

io1: 

#! /bin/bash

echo $0 : laster ned....

wget http://download.intel.com/products/processor/corei7/prod_brief.pdf

Kjøring av de følgende programmer viser hvordan multitasking virker i praksis.

5.8.1 CPU-intensive prosess regn1 alene

Vi bruker som CPU-intensiv jobb samme program som tidligere, men hvor løkken bare går til 100.000: 


$ TIMEFORMAT="Real:%R User:%U System:%S %P%%"
group11@ubuntu:~/task$ time regn1
./regn1 : regner....
./regn1, resultat: 5000050000
Real:3.303 User:2.916 System:0.336 98.45%

Her angir 3.303 antall sekunder totaltid, 2.916 bruker-CPUtid, 0.336 OS-overhead og 98.45% andel av CPU'en prosessen har hatt tilgang til.

5.8.2 CPU-intensive prosesser regn1 og regn2 samtidig

$ time regn1 $ time regn2
./regn1 : regner.... ./regn2 : regner....
./regn1, resultat: 50005000 ./regn2, resultat: 50005000
Real:6.962 User:2.992 System:0.160 45.27% Real:7.399 User:3.112 System:0.180 44.49%


De to prosessene deler på CPU-tiden og det hele tar da naturlig nok dobbelt så lang tid som en prosess bruker alene. Av output ser vi også direkte at de bruker i underkant av 50% hver av CPU'en.

5.8.3 I/O intensiv prosess io1 


$ time io1
./io1 : laster ned....
Real:3.738 User:0.000 System:0.008 0.21%

Hvis man kjører io1 og regn1 samtidig

$ time io1 $ time regn1
./io1 : laster ned.... ./regn1 : regner....
  ./regn1, resultat: 50005000
Real:3.837 User:0.012 System:0.000 0.31% Real:3.302 User:2.920 System:0.308 97.77%



er det stort sett regn1 som bruker CPU'en, så det går omtrent like fort som når de kjører hver for seg.

5.8.4 CPU-bruk og I/O annenhver gang

For å demonstrere eksempelet i Fig. 17 i praksis, lager vi to script som bruker CPU og I/O om hverandre, men i motsatt rekkefølge:

task1: 

#! /bin/bash
regn1
io1
regn2
io2

task2: 

#! /bin/bash
io1
regn1
io2
regn2

Når vi kjører task1 alene får vi føgende resultat: 


$ time task1
./regn1 : regner....
./regn1, resultat: 50005000
./io1 : laster ned....
./regn2 : regner....
./regn2, resultat: 50005000
./io2 : laster ned....
Real:13.460 User:5.924 System:0.556 48.14%

Man ville kanskje ventet at jobbene task1 og task2 til sammen ville bruke det dobbelte av det task1 bruker alene, ca. 27 sekunder.

$ time task1 $ time task2
./regn1 : regner.... ./io1 : laster ned....
./io1 : laster ned.... ./regn1 : regner....
./regn2 : regner.... ./io2 : laster ned....
./io2 : laster ned.... ./regn2 : regner....
Real:15.605 User:6.048 System:0.496 41.93% Real:14.624 User:5.900 System:0.556 44.14%



Men siden de sjelden bruker CPU'en samtidig, går det i praksis nesten like raskt som å kjøre task1 alene. Konklusjon: multitasking utnytter generelt ressursene bedre.


haugerud 2012-05-10