Hvorfor er det så vanskelig å programmere for flerkjerne?

[Isbilen]

Trådtittel er nok et dumt spørsmål. Jeg vet at det er vanskelig. Men jeg er interessert i å vite hva slags problemer man må hanskes med for å lage effektive programmer for flere kjerner. Jeg har ikke programmert selv mer enn et par linjer i IT valgfag, men lurer på dette med tanke på vår egen hjerne. Tidligere forsøkte man nemlig å forstå tankeprosesser som lineære, men forsto kjapt at dette ikke kunne forklare alle tingene vi i hverdagslivet utfører parallellt og med enorm hurtighet og presisjon absolutt hele tiden. Derfor begynte man å se for seg hjernen som en mengde prosesser, men den siste artikkelen jeg har lest om temaet stammet fra før det var noe som het flerkjerneprosessor, og nevnte bare i forbifarten et "lovende prosjekt" som kunne kjøre flere prosesser samtidig. Det var tydelig at man på dette området ikke hadde kommet så langt.

 

Spørsmålet er altså hva slags utfordringer man i dag støter på når man skal få programvare til å utnytte flere prosessorer på en måte som gjør det å ha flere prosessorer en fordel.

[JAPCU]

1. Hvis problemet du prøver å løse er lineært av natur kan det ikke splittes opp i ulike oppgaver. Et steg er avhengig av resultatet til det forrige.

 

2. Det er vanskelig å programmere tråder som kommuniserer. En må passe på at såkalte "deadlocks" ikke oppstår. Ved deadlock låser programmet seg fordi trådene ikke sammarbeider. De har begge en ressurs hver som hver trenger for å fortsette, men vil ikke gi den fra seg. Programmereren har ikke tatt hensyn til at dette kunne oppstå.

 

3. Det blir mer kode. Mer å sette seg inn i. Vanskelig å designe, mange "hva om" tilfeller.

 

Noen flere?

 

Jeg leste for en tid tilbake en intr. artikkel om Valves erfaringer med implementasjon av flertrådstøtte i Half-Life 2 motoren:

http://techreport.com/articles.x/11237/1

 

De prøvde å kjøre spillets subsystemer til å kjøre flertrådet. Grovt sagt grafikk på en kjerne, AI og spill-logikk på en annen. Dette er såkalt coarse-threading (grov). På vanlige baner økte dette ytelsen med bare 20%. Det måtte lages kunstige baner (krevende AI) for å få full effekt, dvs. dobbel ytelse ifht. en kjerne.

 

Et annet problem Valve oppdaget med coarse-threading at det kanskje er flere cpu-kjerner enn subsystemer som kan kjøres på disse kjernene. Grafikk, lyd, AI, input, fysikk, logikk er kanskje mer en 4 subsystemer, men vi vil i fremtiden få prosessorer med veldig mange kjerner.

 

Valve gikk kikket så på "fine-threading". Det går ut på å dele en oppgave opp i mange små tråder (noen kaller dette fibre ^^). Dette går bra hvis oppgavene alltid tar like lang tid å utføre. Skalering blir vanskelig om oppgavne tar en variabelt mengde tid.

 

Valve valgte å lage et hybrid-system som utføres enten på grove- eller fine-tråder avhengig av oppgavens natur. Dette fordeles dynamiskt slik jeg oppfattet det.

 

Får å unngå at tråder må vente på at såkalte "locks" bruker Valve helst "lås-frie"-algoritmer.

 

Edit: Dette har vært diskutert mye

 

Sjekk einaros sitt innlegg her:

https://www.diskusjon.no/index.php?showtopic=717433

 

Anders Jensens innlegg her:

https://www.diskusjon.no/index.php?showtopic=854110

 

Kommentarer til artikkelen "Dagens programvare er gammeldags":

https://www.diskusjon.no/index.php?showtopic=1068174

Endret 10. mars 2009 av JAPCU

[Jann - Ove]

Vel. Om man skal forklare det uten å bli for teknisk så kan man f.eks sammenligne det med jobbing.

 

Se for deg at du har en jobb der du skal formatere 10 datamaskiner av forskjellige sorter, med forskjellig hardware. Som kjent innebærer dette mye venting, og av og til litt leting etter rett drivere.

 

Først se for deg at du sitter med en skjerm og tar en maskin av gangen. Mye dødtid med venting, ja?

 

Deretter se for deg at hver maskin har en egen skjerm, og at du starter formateringen på alle samtidig, og bytter imellom dem for å unngå dødtid. Mye mer effektivt når det gjelder tidsbruk, ja?

 

Tenk deg da at du i nevnte jobb ikke bestandig har mulighet til å gjøre dette, fordi maskinene ikke kommer inn til formatering samtidig. Det er ikke bestandig lett å gjøre flere ting samtidig.

[Isbilen]

Takk, nice svar. Så "fine threading" er en form for pseudo-flertrådet på en kjerne?

[Giddion]

Noen flere?

 

Det å kunne dele opp oppgaver slik at de passer bra til flere kjerner er ikke alltid så lett så det er et problem.

 

Det kan være ekstremt vanskelig å finne feil i et program med mange tråder. Er det verdt bryet er det lett å tenke.

 

Jeg husker jeg så en presentasjon på netten om hvordan animasjonen i Id tech 5 (rage) fungerte, men jeg finner den ikke igjen . Den viste ganske detaljert hvordan de hadde tenkt og hvordan programmering for flere kjerner vil utvikle seg i årene fremover.

[JAPCU]

En kjerne kan jobbe med mange tråder. Ikke bare en.

 

"Fine threading" går ut på å dele opp en oppgave så mye som mulig. Dvs. i så mange tråder som mulig. Trådene behøver ikke nødvendigvis alle samles på en kjerne. Dette er helt opp til "scheduler-en", ("sjefen") som bestemmer hvilken kjerne skal jobbe med hvilken tråd. Poenget med "fine threading" er å utnytte alle kjernene fullt ut. Istedet for at programmet deles i 4 tråder, hvor en kunne trenge mer kraft en 1 kjerne og resten ikke bruker kjernene sine fult ut, deles programmet opp i mange flere tråder.

[Isbilen]

Kan en kjerne egentlig gjøre mer enn en binær operasjon parallellt? Er det ikke snakk om at den veksler mellom tråder veldig fort?

[JAPCU]

Isbilen: Nå snakker du om hardware, CPU-ens oppbygning.

 

Veldig grovt sagt:

Gamle CPU-er kunne bare gjøre 1 ting ad gangen, dagens CPU-er tar inn mange operasjoner i en buffer, finner de den kan gjøre uten å måtte bruke svaret på en annen utregning, sender disse "utførbare" instruksjonene til eksekveringsenheter. Så samles resultatet i et nytt buffer (reordering) som sender svarene ut i riktig rekkefølge.

 

Edit: Det kan være mange ulike eksekveringsenheter som jobber i parallell. Eksekveringsenhetene er gjerne spesialisert til å utføre en eller noen få instruksjoner (f.eks binær addisjon).

 

En støter på mange av de samme problemene på hardware-nivå som på tråd/programvare nivå.

 

 

Dette kalles instruction level parallelism (IPC)

http://en.wikipedia.org/wiki/Cpu#Instructi...vel_parallelism

Endret 10. mars 2009 av JAPCU

[Isbilen]

Er det sånn at "kjerne" i denne forstand ikke er fysisk, men mer noe som oppstår mellom cache og cpu?

[JAPCU]

Hva mener du? Eksekveringsenhetene er en del av CPU-en. En kjerne er alltid en fysisk komplett CPU. Det å ha flere kjerner er så å si det samme som å ha flere enkelte CPU-er på et hovedkort som med flere sockets, som støtter flere CPU-er.

[Isbilen]

Jeg trodde jeg hadde misforstått betydningen av en "kjerne", at det egentlig var noe som oppsto i samspill mellom CPU og cache. Men da er det likevel sånn at en kjerne kan utføre flere prosesser virkelig samtidig?

[Jann - Ove]

Ja.

 

Problemet er problemer som ikke lar seg utføre effektivt samtidig.

[JAPCU]

quote Simen1:

Et program kan gjerne bestå av tusenvis av tråder med mye eller lite interaksjon mellom trådene. Trådene i programmet trenger ikke å ha samtidig skrivetilgang til en bestemt minneadresse på nøyaktig samme tidspunkt for å bli kalt flertrådet. Tråder utveksler informasjon ved å lese fra og skrive til de samme minneadressene, men det er en del begrensninger angående samtidighet. Likevel beskrives slike programmer som ekte flertrådede programmer. Skaleringen er ofte ikke 100% pga blant annet forsinkelser og koherens, men det er fortsatt ekte flertrådede programmer. Trådene kan kjøre samtidig på samme kjerne (SMT) eller samtidig på hver sine kjerner (SMP) eller begge deler. I tillegg til dette utføres hver enkelt tråd med en viss grad av parallellitet der det er mulig. Ofte regner man med 2-2,5 instruksjoner per tråd per klokkesyklus. Altså et gjennomsnitt på 2-2,5 parallelle instruksjoner for hver tråd. Dette skjer automatisk i prosessoren ved at avhengigheter sjekkes og instruksjoner stokkes slik at de kan utføres mest mulig parallelt. Kompilatorer bruker ulike taktikker for å maksimalisere denne effekten.

 

Hentet fra:

https://www.diskusjon.no/index.php?session=...&p=13134718

Endret 10. mars 2009 av JAPCU

[sygard]

Ja.

 

Problemet er problemer som ikke lar seg utføre effektivt samtidig.

 

øh? Hva er det du sier? En fysisk kjærne kan aldri utføre mer enn en regneoperasjon om gangen. Nå har selvfølgelig Intel gjort et forsøk da de tok i bruk HT (HyperThreading), men det var slik jeg forstår det, det bare en algoritme for å pipeline instruksjoner mer effektivt.

 

Har du derimot flere CPU'er eller flere kjærner pr. CPU, kan vi begynne å snakke om parallell-prosessering.

[Jann - Ove]

Se bort ifra fysiske kjerner, siden dette også gjelder for virtuelle kjerner ala HT osv.

 

Det store problemet med å programere parallellt er problemer som er sekvensielle av natur, altså vanskelige å kjøre samtidig med ytelsesgevinst.