Spår utfordringer for multikjerne

[Simen1]

Nja, nå har jeg ikke sykkel, men det kunne likevel være fristende å si ja siden det er presedens for at veddemål her på forumet om sykkelturer er uforpliktende 

5122131[/snapback]

Nåja, jeg vil ikke si det. Øivind Dahle ligger i hardtreninga og det kom raskt frem at sykkelturen er utsatt til sommeren 2006 på grunn av form og opptrening etter en operasjon. Øivind har hele tiden sagt at det skal gjennomføres og har begynt planleggingen allerede. Øivind har til og med skiftet brukernavn til Sykler'n for å minne oss på veddemålet. Så dette blir nok noe av skal du se

[Anders Jensen]

Syklende eller ikke. Dagens programmerere skal få en seriøst vanskelig jobb med å lage programmvare som utnytter mer enn to kjerner på et standard desktop eller laptop system. TLP er uten tvil den vanskeligste formen for parallellitet å utnytte generelt sett, men det kan i enkelte tilfeller være ekstremt mye å hente på det. I andre tilfeller kan selv en 100% optimal flertrådet løsning faktisk være tregere enn en entrådet løsning.

Endret 8. november 2005 av Anders Jensen

[DargarWhiteFang]

Når det gjelder 2 kjerner vs. 4 kjerner osv. så tror jeg 2 kjerner vil være nok i mange år fremover på desktop, men at behovet for 4 kjerner utvilsomt kommer for en del bruksområder for tjenere og arbeidsstasjoner. 2 kjerner vil trolig være nok i massevis for oss desktop-brukere i kanskje 5-8 år fremover.

 

.... 640k should be enough for everyone....

 

skjønner jo litt resonemanget ditt her, men 5 - 8 år er BRA lenge i dataverden. Tror at innen 4 år så vil de fleste av Gamere å sånnt ha døtt av kjedsomhet dersom de ikke har fått 2<kjerne CPU'er..

[DargarWhiteFang]

[edit]

usedvanlig dårlige settninger og språk, selv til meg å være... må bare beklage... men orker ikke rette, det ble for mye..

[/edit]

Med begrennset erfaring fra multi-tråd programmer så kan jeg si et par ting om hva som skiller.

 

* Er det nok å enndre kompilatoren? -nei er det korte svaret.

 

Grunnen til dette, og en del av svaret om hvorfor det vil ta tid og energi å utnytte 2 cores og paralellitet kan beskrives på flere måter. Om jeg prøver å være litt overgripende så kan man si noe slikt som at:

 

En utvikler har et program, si ett veldig enkelt spill.. I spillet vil han ha AI i en tråd og "alt" annet i en annen tråd..

 

Problem: hvordan skal disse to trådene kommunisere med hverandre? -Dersom AI er litt kjappt ute i løypa, må AI tråden vente på at den andre tråden skal få kommet ikapp igjen før den kan fortsette. Hvordan skal det håndteres?

 

Videre får man problemer med ressurser (som delte variabler) da den ene tråden kan være i ferd med å enndre (skrive) til ressursen når den andre tråden begynner å lese fra den.

 

Dette er jo såklart bare et par av de problem-stillingene som man får når man skal kode for fler-tråds-prossesser...

 

Selvsagt så finnes det metoder og systemer for å håndtere disse problemene, f.eks. så har man noe man kaller semaforer og slikt, men det blir straks mye mer "spennende" og ikke "rett fram" å kode slik.

 

og som nevnt tidligere her, ikke ALLT vil tjene på å bli skrevet som multi-tråd programmer.

 

 

Som en side-notis kan jeg nevne att all kode skrevet med LabVIEW (et grafisk programmerings-språk av www.ni.com) støtter multi-kjerne og paralell prossesering, og har gjort det lenge. Der skapes det en "tråd" for hver oppgave som ligger i paralell med en anne, og mye av de stygge tingene, som synkronisering av trådene (der trådene konvergerer må man vente på hverandre) er sjult for brukeren.. Det har blitt laget en del "spill" i LabVIEW, men dette er mer entusiast prosjekter da LabVIEW er mer ett industrielt prossess og kontroll programerings system.

Endret 8. november 2005 av Dargar

[Anders Jensen]

Når det gjelder 2 kjerner vs. 4 kjerner osv. så tror jeg 2 kjerner vil være nok i mange år fremover på desktop, men at behovet for 4 kjerner utvilsomt kommer for en del bruksområder for tjenere og arbeidsstasjoner. 2 kjerner vil trolig være nok i massevis for oss desktop-brukere i kanskje 5-8 år fremover.

 

.... 640k should be enough for everyone....

 

skjønner jo litt resonemanget ditt her, men 5 - 8 år er BRA lenge i dataverden. Tror at innen 4 år så vil de fleste av Gamere å sånnt ha døtt av kjedsomhet dersom de ikke har fått 2<kjerne CPU'er..

5123410[/snapback]

Dette handler jo minst like mye om hvor mange kjerner det vil være praktisk mulig å utnytte som det handler om hvor mye som er "enough for everyone" (Et sitat som jeg forstår er bare oppspinn. BG skal vistnok ikke ha uttalt dette.)

 

Men joda det kan åpne seg muligheter. Blandt annet er det mulig at general purpose CPU kjerner gradvis begynner å ta over jobben til special purpose kjerner som GPU og foreslåtte PPU. Det vil åpne for bruk av ekstremt mange general purpose kjerner. Gevinsten er at utviklerne står langt friere til å velge hvordan de vil utvikle regnekraften. Medaljens bakside er at en vil slite med å oppnå høy nok ytelse de første par åra, men deretter vil det stort sett bare være en gevinst i form av lavere effektforbruk. En må imidlertid forutsette at behovet for regnekraft begynner å stagnere om det skal være realistisk å gå over til en ren general purpose modell i fremtiden.

[DargarWhiteFang]

... om man drar en liten paralell så blir det kanskje ikke så veldig lenge før vi får fres på nye spill og programmer som utnytter flere kjerner!

 

 

Når 3D-kort kom på banen, så oppsto det plutselig et behov for 3D-code-monkeys... disse mystiske apekattene forstod den nye teknikken og hvordan man skulle skrive kode for å utnytte den. Med tiden så ble det mer og mer vanlig, og nå har det i flere år funnets bra "open-GL" tutorials og liknende der ute på internet.

 

Det som er verd å få med seg her, er at før 3D kort kom på banen så fantes nesten ikke den typen programmerere, da koden for å vise graffikk på "ikke-3d-akkselerert kort" ikke er så veldig lik den som er tilpasset og skrevet for 3d kort.

 

Om vi da drar paralellen, så har fler-tråds programmer vært en viktig og stor del i flere industrielle sammenhenger. Det finnes en mengde språk som støtter utvikling av slike programmer, det finnes systemer og metoder for å utnytte teknikken og ikke minnst har det funnets på universitet i laaange tider (årevis). Det finnes masse av teori. Så da blir det jo litt rart om det ikke blir litt som når 3d kort kom... det tar bitte-litt tid mens man gjør omstillingen, og så, vrrooom, tar det av igjen... og denne gangen finnes det faktisk bøker og eksperter fra før, imotsettning(?) til når 3D-kort kom på banen.

 

[Del]

Bør ikke operativssystemet sørge for (være skrevet slik) at programvaren kan utnytte multi-core CPU'er?

 

EDIT: Hva kreves for å lage flertrådskompatibel programvare? Hvis du har en kompilator som lager kode tilpasset flertrådskjerner er det bra nok da, eller må programvareutvikleren lære seg ekstra grep for å håndtere slik koding?

 

Kunne vært greit om noen kunne sette ting i perspektiv slik at sammenhengene kommer tydelig fram.

5122750[/snapback]

Det er ikke gjort i en håndvending å svare på dine spørsmål, men jeg regner med mange lurer på det samme, så jeg kan prøve å gi mitt bidrag til svaret.

 

Først tror jeg det er veldig nyttig å ha nivåene av parallellitet klart for seg. Det mest grunnleggende er ILP, parallellitet på instruksjonsnivå, få prosessoren til å gjøre flere enn en operasjon pr. klokkesyklus. SGI sine MIPS prosessorer var kjent for at de kunne gjøre multiplyadd, dvs. regne ut ax+b i en klokkesyklus. I dag er alle x86 superskalare, og kan utføre tre instruksjoner pr. klokkesyklus. Den arkitekturen som kanskje har dratt dette lengst er Itanium, som kan utføre seks instruksjoner pr. klokke syklus. ILP kan tilrettelegges i koden, men det er opp til kompilatoren å utnytte dette, f.eks. med kompilator opsjonen "unrolloops", evt. bruke biblioteker som er speielt designet for å optimalisere ILP.

 

Det neste nivået er TLP, flertråding, og brukes primært på en SMP maskin, dvs. en maskin hvor alle kjerner har tilgang til alt minnet. Dagens ledende kompilatorer kan gjøre koden din flertrådet ved å sette antall tråder som kompilator opsjon. Igjen kan du legge opp koden din slik at du til en viss grad legger til rette for kompilatoren her, men du har i tillegg muligheten til å bruke openMP, og fortelle kompilatoren nøyaktig hvor den skal lage flere tråder. Dette gjelder spesielt på løkker. OpenMP gir likevel begrensede muligheter for å fortelle kompilatoren nøyaktig hva hver tråd skal gjøre.

 

Det siste nivået er parallellisering av prosesser, har ikke sett forkortelsen PLP før, men den ville vel passet godt her. PLP blir typisk brukt for klynger, hvor koden skal distribueres via noder som kun kommuniserer med hverandre gjennom en NIC, eller evt. noe kjappere interface som Myrinet eller Infiniband. Industristandarden for å implementere PLP er MPI (message passing interface), flere varianter fins, du kan f.eks. sjekke ut LamMPI som er en av de vanligste. Med MPI kan du i detalj styre hvilken prosessor som skal gjøre hva, så det gir deg veldig stor fleksibilitet. Å programmere i MPI er krevende, og debugging kan være ganske slitsomt, men til gjengjeld kan du virkelig optimalisere koden din.

 

Så hva betyr dette for oss og flerkjerne prosessorer. Her tror jeg nøkkelen ligger i å se på hva som er CPU intensivt. Selv om MS nylig demonstrerte sitt klyngeprodukt for å kjøre sinnsykt fort med Excel, er det vel neppe her de fleste av oss trenger datakraft. I farten kommer jeg på konvertering av media filer, videoredigering, spill, (ut)pakking av filer, tunge beregninger. Det er sikkert flere, men poenget her er at det er ikke alt det er interessant å utnytte flere kjerner til. For svært mange oppgaver er datakraften vi har i dag nok, og for de oppgavene hvor vi ønsker å bruke den ekstra CPU-kraften er ikke veien så lang. Det eneste av det jeg kom på som ikke allerede i dag blir flertrådet med stort hell, er spill, og det tror jeg kommer til å endre seg ganske raskt. Å utnytte en SMP arkitektur til å flertråde CPU-intensive oppgaver med nær lineær skalering opp til fire kjerner er ofte ikke noe hokus pokus. Når man kommer over åtte kjerner begynner det å bli vesentlig mer krevende, men selvfølgelig helt avhengig av hva det er du ønsker å parallellisere.

 

EDIT: lett korrektur

Endret 9. november 2005 av Del

[Codename_Paragon]

Nå er et meste av diskusjonen her relatert til spill, men en bør ikke glemme at tunge servere har stor nytte av flere prosessorer. En middels Linux-server har flere titalls prosesser igang (Apache (mange), FTP, NNTP, NTP osv).

 

Så til spill (det er vel det som opptar flertallet her):

I gamle dager var spill rått optimalisert i assembly. De dagene er over, akkurat som for mer administrative datasystemer benytter mange seg av innkjøpte ferdige middleware-løsninger, f.eks. for

- grafikkmotor (selv om GPU-er avhjelper noe)

- nettverkshåndtering (statefull situasjonsbilde fra enkeltpakker, samt kompresjon)

- lyd (effekter, musikk, 3D-effekter)

- AI (disse blir stadig mer avanserte)

- fysikk (her er det snakk om egne fysikkmotorer, som nevt tidligere i tråden)

- kamera i third person shooters (optimal vinkling av kamera)

Siden alt dette er moduler, er dette også egnet for å fordele utover flere prosessorer.

 

På mange måter vil dette gjøre spillindustrien mer lik resten av dataindustrien, der en heller velge å sette på mer datakraft og abstrahering enn å kode smart, alt for å spare utviklings- og vedlikeholdskostnader.

[enden]

Nå er et meste av diskusjonen her relatert til spill, men en bør ikke glemme at tunge servere har stor nytte av flere prosessorer.

5124041[/snapback]

Nå må heller ikke du glemme at tunge servere som oftest har flere prosessorer. Vi snakker tross alt om dekstop-markedet her

[martiol]

Nå er et meste av diskusjonen her relatert til spill, men en bør ikke glemme at tunge servere har stor nytte av flere prosessorer. En middels Linux-server har flere titalls prosesser igang (Apache (mange), FTP, NNTP, NTP osv).

 

Så til spill (det er vel det som opptar flertallet her):

I gamle dager var spill rått optimalisert i assembly. De dagene er over, akkurat som for mer administrative datasystemer benytter mange seg av innkjøpte ferdige middleware-løsninger, f.eks. for

- grafikkmotor (selv om GPU-er avhjelper noe)

- nettverkshåndtering (statefull situasjonsbilde fra enkeltpakker, samt kompresjon)

- lyd (effekter, musikk, 3D-effekter)

- AI (disse blir stadig mer avanserte)

- fysikk (her er det snakk om egne fysikkmotorer, som nevt tidligere i tråden)

- kamera i third person shooters (optimal vinkling av kamera)

Siden alt dette er moduler, er dette også egnet for å fordele utover flere prosessorer.

 

På mange måter vil dette gjøre spillindustrien mer lik resten av dataindustrien, der en heller velge å sette på mer datakraft og abstrahering enn å kode smart, alt for å  spare utviklings- og vedlikeholdskostnader.

5124041[/snapback]

 

 

Det er sant at alle disse oppgavene kan kjøres i forskjellige tråder. Men det er ikke det som er problemet med paralelle tråder. Man må synkronisere ressursjer (for at ikke to tråder skriver til en variabel eller lign. samtidig). Synronisering gjør ting mye tregere siden det er en overordnet "sjef" som må overvåke (som OS), det er en grunn alene til å unngå fler tråder. Når man synkroniserer flere tråder er det fare for dead-lock, som det igjen er ressursjkrevende å overvåke og forhindre.

 

Det mål i programmererens verden har alltid vert å bruke så få tråder som mulig. Unngå synkroniserings problematikken osv. Det har blitt forsket mye på hvordan man unngår å bruke tråder. En stor nyhet i Java (1.5?) var mulighet for ikke-blokkerende IO. Dette for at utviklere skulle slippe å bruke tråder i nettverksprogrammer og lign. Det har blitt utviklet ftp-servere og webservere som har fungert i en tråd, selv om det er typisk paralelle applikasjoner. Altså å dele ett program opp i tråder er noe man har gjort fordi man må og det er (nesten) siste utvei.

 

I dag satt jeg på skolen og diskuterte hvordan vi kunne dele systemet vi skal delei hovedoppgaven opp i flere tråder. Vi skal teste det på en Athlon X2. Den store tekniske utfordringen blir å holde ytelsen oppe, forhindre bugs (dobbelt så vanskelig) og i det hele tatt bli ferdig. Prisen på det vi utvikler hopper fra 3 til 4 millioner pga. flertrådproblematikken.

Endret 8. november 2005 av martiol

[Solarstone]

Bruker selv Softimage XSI (3d design program) som har støtte for 8 cpuer har AMD X2 4400 og merker 70% forbedring i forhold til enkelt kjerne ved rendering. Noe som jeg er stor fornøyd med

[el-asso]

Johan DeGalas hos Anandteck har en interessant artikkel

 

The limits of TLP...

 

Hardware engineers do not believe in massive superscalar CPUs anymore. Increasing ILP a tiny bit requires exponentially bigger out-of-order hardware, which exponentially requires more power.

 

TLP and multi-core is hot and trendy. But the same problems that were true for squeezing ILP out of hardware are true about TLP in software. On the exception of naturally parallel applications such as rendering and database servers, getting more and more threads out of the majority of hardware will require exponentially more programming and debugging time. There are more high TLP designs such as Sun's Niagara that increase throughput, but also response time. And while the numbers of users that can update and read the database matters, the response time of the database can be important too. For example, while OLTP loads consist of many relatively simple SQL selects, Decision Support Systems (DSS or OLAP) fire off very complex queries with a high response time. To offer a good "data mining" experience, the single thread performance must not be neglected. The same can be said for some HPC and many typical workstation applications.

 

So, while designs that sacrifice ILP completely on the altar of TLP, such as Sun's Niagara, they may well be very popular in some markets such as webserving. Single thread performance is going to make the difference between the different multi-core solutions.

Og da er vi vel tilbake der hvor vi var før flerkjerneprosessorene ved at selv med flere kjerner vil fremtidig ytelsesøkning avhenge av den enkelte kjernes yteevne.

Altså tilbake til klokkefrekvens, alternativt ett helt annet ISA.

[G]

Hva når en selv multitask'er (kjører flere program samtidig), vil en multikjerne CPU da utnyttes bedre til oppgavene enn en singelkjerne CPU?

[Betroz]

Hva når en selv multitask'er (kjører flere program samtidig), vil en multikjerne CPU da utnyttes bedre til oppgavene enn en singelkjerne CPU?

5128733[/snapback]

Om prosessoren har 2 eller fler kjerner, så vil det gå bedre når du kjører flere programmer samtidig ja. Men hvert enkelt av programmene vil fortsatt være avhengig av at ytelsen til ên enkelt kjerne er bra.

[Del]

Hva når en selv multitask'er (kjører flere program samtidig), vil en multikjerne CPU da utnyttes bedre til oppgavene enn en singelkjerne CPU?

5128733[/snapback]

Absolutt, og her er den største gevinsten. Et OS svir av en hel masse klokkesykluser hver gang den må bytte mellom prosesser/programmer, noe den gjør stadig vekk når flere programmer kjører på en prosessor (for å gi deg inntrykk av at den gjør alt på en gang). Med flere kjerner vil denne switchingen bli drastisk redusert, så ved kjøring av flere CPU-intensive programmer kan du mer enn doble ytelsen ved å gå fra SC til DC. Dette kan forresten også være tilfellet ved parallellisering, men da gjerne grunnet færre cachemiss siden du har dobbelt opp med cache på DC.

[Del]

TLP er uten tvil den vanskeligste formen for parallellitet å utnytte generelt sett,

Dette er jeg ikke enig i, ref. prosessnivå, men du siktet antagelig at TLP er vanskeligere å utnytte enn ILP, hvilket jeg i utgangspunktet er enig i fra et teoretisk synspunkt. I praksis kan kanskje også den diskuteres.

[Anders Jensen]

TLP er uten tvil den vanskeligste formen for parallellitet å utnytte generelt sett,

Dette er jeg ikke enig i, ref. prosessnivå, men du siktet antagelig at TLP er vanskeligere å utnytte enn ILP, hvilket jeg i utgangspunktet er enig i fra et teoretisk synspunkt. I praksis kan kanskje også den diskuteres.

5129078[/snapback]

Fra mitt ståsted som er litt nærmere hw enn sw så er trådnivå og prosessnivå bare to mildt forskjellige måter å løse det samme problemet på. Sammenligner du på tvers av OS f.eks Linux prosess mot Solaris tråd så tror jeg du vil se at det ikke nødvendigvis er noen prinsippiell forskjell når det gjelder selve parallellitets problematikken. Det går mer på nyanser i forhold til kommunikasjonsmetoder og privilegier. Begrensningene på å parallellisere en gitt algoritme er nesten identiske enten du velger tråd eller prosess, og når tråd og prosess ikke er det samme på forskjellige OS så blir dette mest kverrulerings materiale enn noe fornuftig vel?

[Del]

Jeg siktet i grunnen til kombinasjonen av hw og sw, hva som er lettest å få til i praksis. Følgende er sitat fra "man threads" i Solaris:

Differences

    POSIX pthreads and Solaris threads differ in  the  following

    ways:

 

        o  POSIX threads are more portable.

 

        o  POSIX  threads  establish  characteristics  for  each

          thread according to configurable attribute objects.

 

        o  POSIX pthreads implement thread cancellation.

 

        o  POSIX pthreads enforce scheduling algorithms.

 

        o  POSIX pthreads allow for clean-up handlers for fork(2)

Så jeg vet ikke helt om det er så spesielt under Solaris. Men uansett, jeg feiltolket deg. Du siktet kanskje til ILP kontra TLP v.h.a. SMT (evt. inkludert med skalerings problematikk ved flere kjerner), man prøver jo gjerne å bruke den siste for å avhjelpe den første. ILP ser for meg ut til også å være en meget stor utfordring å utnytte på hw/kompilator nivå.

 

Fra mitt praktiske ståsted er TLP nærmest trivielt å utnytte siden det bare er å benytte en kommandolinje opsjon i kompilatoren, mens på prosessnivå slipper man gjerne ikke så billig. Grov forenkling selvfølgelig, optimal TLP kan være langt fra det kompilatoren utnytter. I mitt hode kobler jeg tråder med shared memory og prosesser med distributed memory, selv om prosesser selvfølgelig kan kjøres på en shared memory arkitektur uten problemer.

[Anders Jensen]

Vel tråd og prosess er oppkonstruerte konsepter og en er ikke nødvendigvis avhengig av noen av de, en kan jo bare definere seg et annet konsept. Det jeg siktet til med Linux og Solaris er at en Solaris tråd er nesten like kompleks som en linux prosess. Dermed tullet rundt å definere TLP og PLP som to forskjellige ting når en diskuterer parallellitet. Jeg ser imidlertid at det har praktiske hensikter for hver enkelt implementasjon, men det var ikke på dette abstraksjonsnivået jeg ønsket å legge meg nå. Kanskje det er noe av grunnen bak missforståelsene. Det er uansett et sidespor. Poenget er at parallelliteten for instruksjoner faller inn under et av to prinsipper. Det er parallellitet innad i en instruksjonsstrøm (ILP) og og parallellitet mellom individuelle instruksjonsstrømmer (TLP samt din egen definisjon PLP som jeg må si å aldri ha hørt om før og det skyldes nok at det egentlig er det samme problemet som TLP, bare med litt andre metoder).

 

Av disse to (TLP og ILP) påstår jeg at TLP er vanskeligst å utnytte. Det skyldes først og fremst at en får ikke-deterministisk utførelse. Et problem en ikke har med utnyttelse av ILP. Det kan derfor prinsippielt sett ta uendelig lang tid å bevise at en TLP optimalisering faktisk er korrekt og det skjer da også ofte at en ikke finner feil som oppsto pga TLP optimaliseringer før det har gått galt hos kunden x antall ganger. Noen ganger finner en ikke feien heller, bare symptomene.

Endret 9. november 2005 av Anders Jensen

[Del]

Mitt skille mellom tråd og prosess mhp. parallelliseringsproblematikk er ikke næret av eget bryst, jeg foreslår et oppslag i egnet litteratur angående HPC.

 

Debugging av parallellisert kode kan være meget krevende, men hvis du lar kompilatoren ta seg av flertrådingen snakker vi vel primært om kompilatorbugs, nok et viktig skille mellom OpenMP og MPI.