Professor: Lær de studerende at kode til 1000 kerner

Man kan lige så godt lære de programmørstuderende at kode til 1000 processorkerner eller mere nu, så de er klar til at programmere morgendagens multicore-processorer, mener dansk professor.

Selvom der formentligt snakkes mere om multicore-processorerne, end der rent faktisk skrives kode til dem i de danske udviklingshuse, er der ingen tvivl om, at vi fremover vil se stadigt flere kerner i processorerne.

Og derfor kan man lige så godt gå i gang med at lære programmørerne at skrive kode, der kan køre på flere hundrede gange så mange kerner, end vi er vant til fra dagens processorer med to eller fire kerner.

Det mener den danske professor og ekspert i parallel programmering ved Datalogisk Institut på Københavns Universitet, Brian Vinter.

Lige nu er der ifølge Brian Vinter en del af programmørskaren, der ikke har brug for den ekstra performance, nutidens multicore-processorer kan tilbyde, og en anden del af skaren, der rent faktisk har brug for tonsvis af performance, men ikke får behovene opfyldt af dagens multicore-processorer.

»Det sjove med multicore-processorer er, at der lige nu er et gab, hvor deres ydelse både er for meget og for lidt. Langt de fleste mennesker skal slet ikke forsøge sig med at skrive parallelle programmer, for det kan de ikke finde ud af, og dem, der kan finde ud af det og skal foretage kraftige beregninger, har måske typisk brug for 128 kerner,« siger Brian Vinter.

Situationen gør, at programmørerne lige nu tøver med for alvor at springe på vognen med multicore-processorer.

Men om få år vil situationen være anderledes, og derfor kan man lige så godt udnytte ventetiden, mens gabet lukkes, til at lære folk at skrive programmer, der snildt kan fordele sig ud over 1000 processorkerner, mener Brian Vinter.

Skriv koden til mange kerner fra begyndelsen
»Den rigtige måde at skrive kode på til multicore-processorerne er at sikre fra begyndelsen, at den kan køre på 1000 kerner og derefter er skalerbart, hvis endnu flere kerner bliver aktuelt. Hvis du gør det, varer det et stykke tid, for din software bliver overhalet af hardwaren,« siger Brian Vinter.

Brian Vinter peger på det formelle sprog Communicating Sequential Processes (CSP) som et eksempel på en parallelt sprog, der kan understøtte den tankegang.

Sproget blev oprindeligt bragt til torvs i 1978 af C.A.R. Hoare, manden bag en af verdens mest udbredte sorteringsalgoritmer, Quicksort, og på University of Canterbury i Kent, England har man forsøgt sig med at undervise de førsteårs?datalogistuderende i CSP.

Brian Vinter påpeger, at det i praksis er nemmere at lære at programmere til 1000 kerner, end man kunne frygte.

»Det er faktisk ikke så svært, hvis man lærer det på den rigtige måde fra begyndelsen. I England har man netop prøvet at undervise førsteårsstuderende i at programmere til 1000 processorkerner med CSP, og de klarer sig lige så godt som dem, der lærer at kode almindeligt i for eksempel Java,« siger Brian Vinter.

Tips og korrekturforslag til denne historie sendes til tip@version2.dk
Kommentarer (35)
sortSortér kommentarer
  • Ældste først
  • Nyeste først
  • Bedste først
Poul-Henning Kamp Blogger

Jeg glæder mig meget til at se nogen skrive en database der kan lave noget fornuftigt fordelt ud over 1000 kerner.

Hvid hærs problem med den blå bliver nu udvidet til også at omfatte "aliceblue army", "antiquewhite army", "aquamarine army" [994 andre farver] "yellowgreen army".

Velkommen til programmørenes helvede...

For mange år siden havde HP og NCR et vandvidsprojekt der hed "NewWave" der handlede om en eller anden sindsyg maskine med op til 1024 i486 processorer.

Dengang og den dag idag, er der ikke andet end numeriske simulationer og andre brute-force applikationer der kan udnytte den slags maskiner.

Er der slet ikke nogen der kan huske et firma der hed Inmos og en chip der hed "transputer" ?

Eller er der bare ikke nogen der har lært noget af det ?

Bare fordi hardware-producenterne er løbet tør for ideer, betyder det ikke, at deres marketingafdelingers hjerneblødninger får indflydelse på hvordan vi bruger computere i fremtiden.

Poul-Henning

  • 0
  • 0
Brian Vinter

Pointen med CSP er faktisk at programmøren*) skal skrive små overskuelige processer som man kan vise (eller overbevise sig selv om) er korrekte, CSP klarer så at vise at systemet er deadlock fri etc.

Men at der ikke er behov for 1000 kerner er dog en fantastisk nyhed for mig, det bliver en række folk meget glade for at høre, altså dem der i dag bruger millioner på supercomputere for at løse deres problemer fx:
• Finans sektoren (USAs største tæthed af regnekraft er på Wall-Street - eller var - efter 9/11 er de flyttet fysisk, men Wall Street er stadigt #1 kunden for HPC.)
• Bio-sektoren bliver helt klart også glade for at høre at molekylær dokning kan klares på en håndfuld kerner.
• Analyse af CT og MR scanninger bliver vel nok let hvis vi kan gøre det på en PC.
• Den strøm vi sparer på at olie-branchen ikke behøver 10.000'er af kerner til at analysere undergrunden vil alene begrænse den globale opvarmning mere end noget selvstændigt dansk initiativ.
• Vi kan så også begynde at modellere vores drikkevands resurser på en PC - DHI bliver enormt glade for at høre det!
• Mærsk og andre shipping firmaer kommer til at spare kassen når pakningsproblemer kan håndteres med få kerner.
• Men bedst af alt er at alle på problemer med at modellere kvante-mekaniske effekter ikke længere er et problem. Lidt surt for en af mine PhD stud som parallelisere sådan en kode og er kommet op på 16.384 kerner og har 128K som sit mål - men han må så finde sig noget andet at lave:)

Ude i virkeligheden peger alle rapporter så godt nok på det modsatte og siger at regnekraft er den største konkurrenceparameter i videnskabelig udvikling. Se fx:
http://research.microsoft.com/en-us/um/cambridge/projects/towards2020sci...

Og omkring Inmos og Transputer – jo det er sørme en historie vi husker. Dem af os der så husker hele historien ved at grunden til at Transputeren forsvandt var at Inmos blev købt af Thomson der i en klassisk ”slipse-manøvre” besluttede at ændre implementeringen af Transputeren fra Occam (CPUen var skrevet i Occam og Occam var også den primære sprog til dens programmering) til VHDL, den beslutning kostede 3 års forsinkelse på T9000 og da den endeligt kom ud kørte den ved ½ hastighed af det planlagte (25MHz ikke 50MHz), det koblet med at konkurrenterne var kørt fra den dræbte projektet. Det var altså single CPU performance der var problemet, ikke parallelitetsbegrebet!

Men et enkelt spm: ”Folk uden begreb...” – hvem er folk og hvad er det de (vi?) ikke har begreb om?

*) Hvad mener vi egentligt med programmører? Tidligere havde vi en egentlig uddannelse af dem, jeg ved ikke om der findes nogen i dag eller om det hele er "IT". Dem jeg siger skal lære CSP er professionelle dataloger for hvem kode bare er den endelige specifikation på problemet, ikke IT-folk eller autodidakte hackere!

  • 0
  • 0
Poul-Henning Kamp Blogger

Men at der ikke er behov for 1000 kerner er dog en fantastisk nyhed for mig, det bliver en række folk meget glade for at høre, altså dem der i dag bruger millioner på supercomputere for at løse deres problemer fx:

Lagde du mærke til at jeg skrev:

Dengang og den dag idag, er der ikke andet end numeriske simulationer og andre brute-force applikationer der kan udnytte den slags maskiner.

Alle dine eksempler tilhører disse to kategorier, fælles for hvilke er, at de netop er paralleliserbare.

(Og om du har 1000 kerner eller 1000 maskiner i dit cluster til den slags applikationer er egentlig kun et optimeringsspørgsmål)

Min protest skyldes denne manglende kvalificering af artiklens definitionsmængde.

For jeg antager at vi er helt enige om, at intet at det du udtaler sig om, har nogen relevans i forbindelse med implementeringen af almindelig forretningslogik ?

Og ja, måske burde vi helt afskaffe begrebet programmører, for ingen kan blive enige om hvem de er, hvad de laver eller hvad de kan eller ikke kan.

Poul-Henning

  • 0
  • 0
Jens Madsen

Efter min opfattelse, er det ikke væsentligt, at lære programmører at programmere mange kerner. Det, som er væsentligt, er at de kan mestre parallelisme.

Det vil sige, at de skal vide, hvordan de koder pålideligt, når det er parallelt - hvordan at de sikrer sig, at koden har en deterministisk funktion.

De skal kunne oversætte fra sekventiel kode, til parallel kode i hånden, for at opnå forståelse for, hvordan det gøres, og hvordan en eventuel automatisk oversætter gør det, samt opnå forståelse for, hvordan sammenhængen er mellem sekventiel og parallel skrevet kode.

De skal lære, hvordan en oversætter, kan dynamisk oversætte fra sekventiel kode, til parallel kode, således at paralleliseringsgraden udvides, når koden eksekveres.

Ved parallel programmering, mistes i nogen tilfælde overblikket - og det kan faktisk være en fordel, at holde koden sekventiel, hvis overblikket skal være optimalt. Min opfattelse er, at vi nemt kan lave automatiske værktøjer, der omsætter sekventiel kode til parallelt, og at der ikke er grund til, at tvinge programmørerne til at gøre dette job i hånden, samtidigt med at overblik forsvinder. I nogle tilfælde, kan en parallel beskrivelse, dog øge overblikket - fordi opgaven ganske enkelt er parallel i sin natur. Og så er bedst, at beskrive opgaven parallelt. En opgave, skal kodes, så det er så overskueligt som muligt - og datalogernes job er så, at udvikle kompilere, der kan bruge programmørernes inputs (kode), til at generere et effektivt output til processorene. Datalogernes opgave er ikke, at springe over hvor gærdet er lavest og sige, at dette oversætterarbejde kan programmørerne "få lov til". Og måske uden, at kende den teoretiske baggrund for, hvordan der manuelt ovesættes fra sekventiel kode, til parallel. Mangles denne baggrund, arbejder de måske hårdt på, at gøre noget i hånden, uden at de reelt ved hvordan - og opnår alligevel et dårligere resultat, end kunne være opnået automatisk.

Men, skal programmørerne kunne bruge værktøjerne korrekt, er vigtigt, at de har forståelse for, hvordan automatisk oversættelse mellem sekventiel kode, og parallel kode fungerer, og hvilke problemer det kan indebære - samt lære, om problemerne kan løses teoretisk, og det kun er et spørgsmål om tid, før compilere vil kunne fås.

Når man koder, er det væsentlige ikke, om det er parallelt eller sekventielt. Det væsentlige er, at det er kodet overskueligt. Det er så computerens opgave (operativsystem og compiler), at henholdsvis øge, eller mindske paralleliseringen, i forhold til den i koden angivne, således processorens faciliteter bruges bedst muligt. Normalt, vil kode, der gør dette, være under operativsystemet, fordi den derved har flest mulige processer at arbejde med, og derfor kan opnå bedre schedulering. Operativsystemet, kan også have kendskab til processorens arkitektur, og bruge at der er flere tråde, til at sikre der er kode, og data, til rådighed, så cachen bruges optimalt. Flere tråde, som processoren har adgang til, kan ofte øge effektiviteten af cachen. Årsagen er, at den ganske enkelt har nogle ekstra "tråde" den kan skifte til, og umiddelbart udføre, hvis cachen staller - og processoren er derfor altid i gang med at udføre en process uden den "hænger". Det kræver kun, at der er tråde nok. Normalt vil koden paralleliseres til mange processer automatisk, og kode, der kan udføres lidt senere, vil opskrives som en særskildt process, der måske kun kører i kort tid. Det kan i princippet, være ganske simple opgaver, som at initialisere nogle positioner i ram lager ol. der kun tager få indstruktioner, og så "nedlægges" tråden. Når det laves som en separat process, vil det kunne udføres tidligere, og "elastisk", så tiden kan fyldes op med det.

Skal man manuelt kode disse ting, bliver koden hurtigt totalt uoverskueligt. Så det bedste er, at lade compileren gøre arbejdet, og dele det op i indstruktioner der kan udføres uafhængigt, og parallelt. Kun, hvor det er fornuft, skal det kodes parallelt i hånden.

  • 0
  • 0
Brian Vinter

"For jeg antager at vi er helt enige om, at intet at det du udtaler sig om, har nogen relevans i forbindelse med implementeringen af almindelig forretningslogik ?"

Ja og nej....

Den forretningslogik du ser idag: Ja

Den der er på vej med Mapreduce på dokumenter, budgetter og lignende der bliver der behov for seiøs regnekraft - til gengæld er det relativt let at parallelisere

  • 0
  • 0
Lasse Lasse

Hej PHK,

Du lyder lidt som "nobody would ever need more than 64K of memory" i forbindelse med desktop-applikationer og standardservere. Men lad os tage et par forudsigelser om fremtiden, som er så sikre, at vi næsten kan regne dem for facts:

1) Billedkvaliteten for digitalkameraer og skærme vil først standse, når den har nået samme niveau som det biologiske øje, 360 grader rundt i højde og bredderetning. Vi taler gigapixels med 128 bit/pixel med HDR.
Men Moster Olga skal selvfølgelig kunne bruge lidt billedfiltre, inkludere dem i dokumenter og generelt kunne håndtere dem akkurat som i dag.

2) Computerspil opnår samme billedkvalitet hvilket øger regnekraften der skal bruges til at gengive fysikken korrekt (eksplosioner, bilsammenstød, ting, som vælter, etc). Udviklingen i computerspil standser først, når man med alle sine sanser ikke kan skelne spillet fra virkelighed. For ikke at tale om øgede krav til AI.

Alene de to forudsigelser garanterer et uudtømmeligt behov for regnekraft. Dertil kommer spekulationer om, hvor udbredt AI bliver med fx genkendelse af ansigter og objekter i fotos, stavekontrol, oversættelser mellem sprog i tekst og tale, osv.

Det kan altså være svært at se, hvordan dekstop-opgaver, som i dag kan klares fint af en enkelt kerne på en 2 GHz maskine nogen sinde skulle få behov for mere regnekraft, men det hjælper at træde nogle skridt tilbage og se på samfundets behov :-)

Spørgsmålet er så, om det bliver parallel-paradigmet, som vinder, eller om hardwareindustrien pludselig skulle opfinde nye hurtige serielle proessorer. Men sådan har trends jo altid skiftet frem og tilbage med tiden.

Jeg ville som udvikler i øvrigt helt klart foretrække, at det blev løst ved at opdage/opfinde hurtigere sekventielle processorer.

  • 0
  • 0
Poul-Henning Kamp Blogger

@Lasse:

Alene de to forudsigelser garanterer et uudtømmeligt behov for regnekraft.

Et "uudtømmeligt behov" har ingen sammenhæng med om der existerer teknologier, hardware eller software, der kan opfylde hele eller dele af dette behov.

@Brian:

Så vi er altså enige, hvad du har udtalt dig om har relevans for (visse) teknisk videnskabelige opgaver, men ingen relevans for 90+ procent af de folk der opfatter sig selv som, eller bliver ansat/omtalt som programmører.

Jeg tror det var sætningen:

Og derfor kan man lige så godt gå i gang med at lære programmørerne at skrive kode[...]

Hvis der her havde stået "ph.d'erne" istedet for programmørene, havde jeg ikke haft nogen indvendinger.

Hvis jeg skal forholde mig til substansen i dine udtalelser har jeg måske temmelig svært ved at få hænderne op i klappehøjde.

CSP er muligvis fra 1978 men det er basalt set Conways coroutiner fra 1958 vi taler om.

Bevares, Conways er klart en af de største og mindst kendte indsigter i computer science og jeg skal være den første der klapper højt hvis han igen kommer med i pensum.

Problemet er, groft sagt, at vi ikke er kommet et hak videre i de mellemliggende 50 år...

Poul-Henning

  • 0
  • 0
Brian Vinter

Da jeg udtalte mig om ”studerende” var det i konteksten ”datalogi studerende” jeg er ikke på nogen måde fortaler for at alle der sidder ved en computer skal have samme uddannelse. Så at det kun skulle være PhD’ere er jeg ikke enig i – men jeg promovere ikke CSP udenfor datalogi.
Men at co-routiner og CSP skulle være det samme er ganske simpelt noget vrøvl!!! Med CSP får man en algebra hvormed man kan udtale sig om ting som indenfor samtidighed (eg: concurrency) race-conditions, deadlocks, livelocks, etc… co-routiner er en programmeringsteknik (for resten er co-routiner først gjort praktisk anvendelige af danske Brinch-Hansen).
Et meget simpelt eksempel på forskellen på at bruge CSP og ikke gøre det:
Da Mercedes lavede ABS bremser fik de deres SW verificeret formelt med CSP
Da Peugeot lavede deres var det bare et hack… kan nogen huske de brændte Peugeot’s pga. live-lock i bremserne? 
Og så ellers god weekend herfra!

  • 0
  • 0
Poul-Henning Kamp Blogger

@Torben:

Min pointe er, at SAGE systemet løste det fundamentalt set triville "problem" med at distribuere read-only data, (med, så vidt jeg husker, reference til hvordan Library of Congress leverede trykte kataloger/index til andre biblioteker.) den eneste udfordring de sidste 50 år har været optimering og nye varianter af det dybe vand og den varme tallerken.

Det er når man skal kunne forandre data at multi-programmering bliver langhåret.

Og der er til mit kendskab ingen gennembrud i computer science der har gjort det nemt, man har alene kastet og møvet det svære aspekt rundt imellem koderen, sproget, compileren og hardwaren.

@Brian: Jamen så er vi tæt på at være enige, men det var ikke sådan dit budskab blev formidlet ovenfor. Jeg vil ikke blandes ind i om skylden er din eller Mikkels.

Jeg vil stædigt fastholde at CSP bare er Conway med syntaktisk sukker og ekstra pynt.

Men jeg er villig til at lade khan@diku være opmand på spørgsmålet, for så vidt jeg ved, implementerede han den mest fuldstændige version af Conways Coroutines, nogen sinde, til RC7000/DOMUS.

Poul-Henning

PS: @Torben: Jeg ville bryde mig om at skulle overbevise Datatilsynet om, at jeg havde styr på de meget personfølsomme oplysninger i et EPJ, hvis jeg havde dem i Sawzall...

  • 0
  • 0
Steen Christensen

Hr. Kamp

Jeg er selv programmør, og til hr. Vinter... der findes stadig nogle af os gamle EDB-assistener der er uddannet programmør.

Jeg underes over Deres kategoriske afvisning af multicore/paraelle programmering i erp systemer.

Dette må nødvendigt skyldes Deres manglende viden og/eller erfaring med store datamængder, der behandles på gl. hardware.

Jeg har selv implementeret en paraell Nettobehovsberegning i et ERP system hvor vi ganske enkelt ikke havde tid nok til at gennemføre beregningen på den normale liniær programmering.

I min verden findes der opgaver som godt kan gennemføres med "brute force" men hvor tiden gør at vi ikke kan vente på at den bliver færdig... igen primært fordi vi har gl. hardware.

m.v.h.

Steen Christensen

  • 0
  • 0
Steen Christensen

Hej Brian

Det ved jeg også godt og jeg kan ligeså godt indrømme at jeg prøvede at drille lidt.

Jeg har i en årrække selv undervist i programmering... om end kun i mit specifikke ERP system, men det er dog OO og udvikler sig i retningen af C#.

Når jeg ser på den "masse" af elever så kan jeg godt se at der mangler en entlig >programmør< uddannelse.

De nyudd. datamatikere kan "for meget" andet også... ikke at det er en kritik... men min udd. var 1½ år og på den tid lærte jeg 5 forskellige sprog... og evenen til at tilegne mig nye....

Idag kan de c# og noget java.

Mit sidste eksempel... var for 14 dage siden hvor vi skulle finde en fejl i et gammelt produkt som ikke har debugger... og jeg spurgte en af vores yngre folk hvordan han ville gøre det.

Han var tæt at være handlingslammet... og det tog næsten 3 kvarters snak inden han kom på "at man jo kunne indsætte printsætninger der udskriver de variable vi har brug for".

Man nå nu skal denne diskution ikke løbe i retningen af manglende uddanelser, men vel kvaliteten af de udd. vi har :)

btw så er jeg medlem af Odense .net user group, hvor sidste møde var om parell programmering i c# - eller intruduktion til det... og et senere møde vil være den praktiske udførsel... vi har en gut som er meget habil.

Steen
<En edb-dinosaur>

  • 0
  • 0
Peter Valdemar Mørch

jeg skriver ofte "for" løkker som i deres natur sagtens kunne paralleliseres. Hvorfor kan jeg ikke få paralleliseret disse automatisk:

[code="C"]
// In many languages
ResultHash result;

for (element in collection) {
// do something with element
}
//or
for (i = 0; i < nrElements; i++) {
// do something with array[i]
}
nextOperation();
[/code]

Hvis jeg som programmør ved (og garanterer), at rækkefølgen er ligegyldig, at én beregning ikke afhænger af resultatet af en anden og at dette kun ændrer i "ResultHash result" og evt. i element/array[i], ville jeg elske, hvis alle nrElements beregningerne kunne blive paralleliseret automatisk uden at jeg skulle gøre andet. Hvis man nu indførte "pfor" som parallel-for, så skulle nextOperation først udføres når pfor er færdig med den sidste parallelle beregning. (Måske med behørig syntaks til at at bekendtgøre at pfor løkken ændrer præcis "result" og ikke andet.)

Jeg ved jo godt det sagtens kan være mere kompliceret end dette, men ofte synes jeg dette er det hele.

Inde i løkken kan der så blive kaldt endnu en pfor løkke, og compileren eller OS skal så holde styr på hvor meget det giver mening at parallelisere så der ikke bliver 100'000 parallelle beregninger på én gang. Og i de simpleste implementeringer (eller til debug formål) udføres pfor med en simpel sekventiel for.

Hvad har jeg overset? Hvorfor findes "pfor"-varianter ikke i alle moderne sprog?

  • 0
  • 0
Brian Vinter

Bare for lige at være perfid vil jeg lige bemærke at der er temmelig stor forskel på samtidighed (concurrency) og parallelitet - det jeg promoverer med CSP er samtidighed.

Når det er sagt så er det sandt at hvis man har triviel parallelitet som dine for-loops (nu er det jo kun trivielt parallelt hvis der ikke er afhængigheder i loopet) så bør man bare bruge en parallel for konstuktion.

Til C og Fortran har de fleste compilere OpenMP udvidelser der kan gøre det for dig (OpenMP er kun til den mest banale parallelitet men der er den også let at bruge).

Til sprog der ikke har OpenMP kan jeg anbefale fx Jibu som nævnt ovenfor eller en af de mange CSP varianter; C++CSP, JCSP, PyCSP,...

Brian

  • 0
  • 0
Jens Madsen

Når det er sagt så er det sandt at hvis man har triviel parallelitet som dine for-loops (nu er det jo kun trivielt parallelt hvis der ikke er afhængigheder i loopet) så bør man bare bruge en parallel for konstuktion.

Nej - netop når du har triviel parallelitet, er der ingen grund til, at compileren ikke selv gør det. Du behøver her ikke, at skulle angive det. Det væsentlige er, at gøre din kode så overskueligt, og sikker som muligt. Selvom en processor, måske har 200 kerner, kan godt ske at de alle er optaget - brugeren kører måske andre programmer samtidigt end dit program. Du kan ikke vide, om dit program, eller "løkke" reelt, er hensigtsmæssigt at parallelisere. Måske er det netop løkken, der ikke bør paralleliseres, i forhold til andre processer. Et øjeblik senere, er måske lukket nogle af de andre tråde, og der er kerner til rådighed - nu er der behov for, at din løkke gøres parallel. Det er operativsystem, og compilere, der afgør dette, og gør det dynamisk meddens systemet kører - de kan såvel øge, som sænke parallelismen, og gør det så det kører så effektivt som muligt.

Programmørens opgave, er aldrig, at angive "triviel parallelitet". Der, hvor programmøren skal angive parallelitet, er hvor det er hensigtsmæssigt - fordi at opgaven måske ellers skulle løses af en tilstandsmaskine, og blive særdeles uoverskueligt.

Parallelitet, kan i nogen grad, gøres til en naturlig del, af sekventielle sprog. Fordi, at "åbenbar" parallelisme, jo nemt kan parallelisers automatisk, så behøver vi reelt ikke konstruktioner, for at opnå parallelisme. Vi angiver blot flere "programmer", der ikke direkte har berøringsflade mellem hinanden, eller kun har det på en måde, der ikke forbyder parallelisme. Det kan f.eks. være i form af køer mellem koden.

  • 0
  • 0
Jens Madsen

Med hensyn til løkken, der kan udføres som mange processer - så er den ikke helt så oplagt, at parallelisere automatisk. Det kræver, at opgaven klares dynamisk, meddens programmet kører. En compiler, der compilerer til et fast antal kerner, vil ikke umiddelbart kunne klare opgaven. Løkken, hvor du angiver processerne, går fra 0 til nrElements, men nrElements, er ikke kendt på kompileringstidspunktet. Først, når nrElements har fået en værdi, kan processerne begynde at blive oprettet. I nogle tilfælde, vil de ikke kunne udføres, fordi der stadigt mangler værdier at blive fyldt ind, som du bruger i de oprettede processer. Men så snart, at processerne har fået de opsætninger, som er nødvendige, og nrElements er initialiseret, kan udførslen starte. At se, om der er afhængigheder mellem processerne besværliggøres af anvendelsen af array[i], hvis alle processer, har adgang til samme array. Det skal så gennemskues - for alle i - at der ikke er afhængigheder. Også dette, kan først ske, når løkken kan gennemløbes. Indexerede arrays, kan være svært at gennemskue med hensyn til afhængighed, før at index kendes - og her kendes index i princippet ikke, før at løkken kan gennemløbes (altså nrElements har fået gyldig værdi). Specielt, når array[n] bruges senere, betyder det noget - da array for n, som er mindre end nrElements, vil være påvirket af konstruktionen, meddens for n større end nrElements, vil være upåvirket, og i princippet kan køre parallelt.

Som koder, er svært at holde styr på dette. Koden bliver meget nem uoverskueligt. Men for en compiler, er det meget nemt at gøre. (Nu kan nemt jo diskuteres, men det er nemt på et kvalificeret niveau).

  • 0
  • 0
Brian Vinter

Desværre er det sådan at såsnart man har pointere i et sprog så er det faktisk meget hurtigt IKKE afgørbart for compileren om der er afhængigheder i koden - compiler detekteret parallelitet har optaget nogle meget dygtige folk meget længe og vi har ærlig talt ikke så meget at vise for det.

Nyere sprog (Fortress fx) gør et indhug ved at lave sproglige konstruktioner der gør det muligt et stykke hen af vejen. Desværre er de fleste "programmørere" ikke professionelle nok til at vælge det rigtige sprog til opgaven men vælger oftere at specialisere sig i et sprog og så bruge det til alle formål - derfor har de nye sprog lidt svært ved at vinde fodfeste:(

@PHK om Convex:
Jeg ved ikke hvad der skete med koden - men den var jo også meget Convex specifik og havde nogle meget arkitektur afhængige udvidelser der ikke lige kunne migreres. Folkene derimod cyclede/cycler rundt i miljøet stadigvæk, Cray var selvfølgeligt hurtigt ude og samle nogen op men også SUN og SGI trak nogen, mange endte dog hos Digital, så HP og tilsidst Intel - jeg snakkede med en enkelt fyr der havde skiftet 3 gange på 3 år uden at bytte kontor:)

  • 0
  • 0
Lars Lundin

"ved du hvad der blev af Convex' compilere fra deres supercomputere ?"

Jeg brugte sådan een på Convex´ nok mest succesfulde maskine, 3880 (8 CPUer, 2GB RAM, knapt 1.92GFLOP/s teoretisk peak).

Paralleliseringen var, som ovenfor skrevet, meget effektiv. Den virkede via compiler-direktiver, som blev omsat til tråd-parallisme.

Så selve princippet er ført videre i f.eks. OpenMP.

Fra min egen erfaring med et multi-tusind-processor system vil jeg give PHK ret: Visse numeriske simuleringer (f.eks. baseret på numerisk linær algebra) specielt skrevet til en given hardware-type giver god mening, men det er meget begrænset hvad der egner sig til massiv parallelisme.

Tænk på Amdahls lov:

Hvis så meget som 1/1000 del af koden ikke paralleliseres, så er fordelen ved at benytte mere end 1000 processorer stærkt aftagende.

Og hvis man ønsker at parallelisere via tråde (eller processorer, der deler adgangen til samme hukommelse), så har man et endnu mindre set af programmer, der kan køre effektivt uden at totalt overbelaste adgangen til den delte hukommelse.

Men kendskab til paralliserbare algoritmer, samt almindelig fornuft, såsom at skrive thread-safe (tråd-sikker?) kode, kan hjælpe til at et program kan udnytte et mindre antal kerner - og det vil da allerede være en forbedring.

  • 0
  • 0
Jens Madsen

Desværre er det sådan at såsnart man har pointere i et sprog så er det faktisk meget hurtigt IKKE afgørbart for compileren om der er afhængigheder i koden - compiler detekteret parallelitet har optaget nogle meget dygtige folk meget længe og vi har ærlig talt ikke så meget at vise for det.

Pointere, er i det store hele noget rod - og programmeringssprog med pointere burde forbydes. I mange tilfælde, vil man kunne finde andre konstruktioner, der giver anledning til bedre kode, og mere optimal kodning. Og ikke mindst - større analyserbarhed overfor parallelisme.

Pointere, har en lighed med indexerbare arrays. Hvis du som pointer, anvender en konstant, er den analyserbar. Men, det er meget svært gennerelt at vide, om du eksempelvis kan parallelisere. I nogle tilfælde, kan du være heldig, og kan udregne nogle "grænser" som pointeren må være imellem, og derfor være i stand til at parallelisere. Hvis operativsystemet står for paralleliseringen - og det er bedst da denne kender alle samtidige processer - så skal koden derfor ikke overleveres i form af maskinkode, hvor alt er pointerbaseret - men man skal overholde arraystrukturer, hvor det så vidt muligt vides, hvilke områder variable, og arrays holder sig indenfor - fordi det deffineres i sproget. Sædvanlig "maskinkode" egner sig ikke som maskinkode, til computere der kører under et operativssystem, og hvor operativssystemet står for paralleliseringen ud på kerner. Det kan - teoretisk - hjælpe lidt, at slå "range check" til, fordi at man så bedre teoretisk kan afgøre områder. Af samme årsag, er det egentligt hellerikke godt, at compileren indsætter kode til range check, men i stedet skal programmet overleveres til operativsystemet i en grad, så det faktisk er dens opgave. Range check, vil så hellerikke fylde ekstra i koden. Og - i fremtiden - vil man måske vælge, at lave CPU'er, der har indbygget faciliteter til range checking, og hvis koden så overleveres til operativsystemet, vil den kunne oversætte automatisk til fremtidige processorer, via dens oversætter, og bruge de nye faciliteter, uden brugeren skal foretage genkompilering.

Selvom pointere, og indexerbare arrays, giver problemer med paralleliseringen, og specielt forplumrer en statisk parallelisering, så er det ikke ensbetydende med, at det totalt udelukker parallelisering. Hvis du eksempelvis ikke har nogle skrivninger (tildelinger) med pointere, er fuld parallelisering muligt - men naturligvis er det jo totalt urealistisk. Dog, er ikke urealistisk, at kunne opdele et program i læsning, og skrivning, og der sker så en trådning - men ved læsningen, har du mulighed for, at have parallelisme.

Det bedste er dog, at udvikle et sprog, der ikke indeholder problemer som pointere - pointere, og brugen af dynamisk hukommelse, er i det store hele ustruktureret og uovervejet i mange programmeringssprog. Det viser sig, at denne mangel på struktur, også fører til kodefejl, og pointere er i meget høj grad årsag til uoverskuelighed - ikke kun for analysering - men også for programmører. Selvom vi måske kan udvikle metoder, der håndterer pointere i maskinkode - specielt hvis eksempelvis range check slås til - så er langt bedre, at udvikle nye sprog, der håndterer problemet på en god måde.

Et sådant sprog, må gerne være lavet til, at koden udføres i rækkefølge. Ofte er nemmere, at gennemskue et program, når det udføres i rækkefølge - og programmørerne er mest vandt til det.

Det, at et sprog udvikles til, at køre i rækkefølge, er ikke problemet ved paralleliseringen. Det, som er problemet, er mangel på struktur, så compileren ikke kan gennemskue i hvilket interval at en variabel arbejder, og i hvilket interval, at et array bruges.

En af grundene til, at jeg er meget modstander af sprog som C og C++ - i forhold til f.eks. pascal - er at disse sprog, har begreber som "int", og at "int" er standard deffineret interval. Dette er totalt urelevant for koden, og en programmør bør i princippet ikke bruge "bare" en int, med mindre, at de virkeligt har brug for en integervariabel, der er uendelig i dens område, og kan fylde et vilkårligt antal bits i lageret. Ellers, skal man angive explicit hvad man har behov for, på samme måde som i pascal. Derved er ikke nogen grænser sat af en eventuel underlæggende defination, og integer har ikke teoretisk nogen minimum og maximum i pascal. Det er altid en fordel, at compileren har så meget viden om koden som mulig - og hvis vi lægger range check ind i koden, så mister compileren dens viden omkring kode, og kan ikke bruge det f.eks. ved parallelisering. At angive intervallet, skal derfor være del af sproget.

Efter min opfattelse, er det helt forfejlet, at nu skulle "lære" programmører, at lave uoverskuelige programmer, hvor selv enkle algorithmer angives som tusinder af tråde - hvis ikke, at denne parallelisering giver den simpleste, overskueligste, mest forståelige, og mest bevisbare kode.

Det bedste er, at udvikle nye sprog, som er designet til at koden skrives i rækkefølge som sædvanligt - men også er designet til, at koden skal kunne paralleliseres automatisk, evt. dynamisk meddens den udføres, hvis paralleliseringen først kan indsés på dette tidspunkt. Det betyder selvsagt, at programmeringssproget gerne må være så overskueligt, at pointere ikke eksisterer, og at de problemer, vi i dag håndterer med pointere, alle kan håndteres på anden måde.

Der vil altid være "lidt" pointere i et sprog - ligesom vi har arrays, med variabelt index som parameter. Disse giver dog langtfra samme blokering som pointere.

I visse tilfælde, såsom del og sort algorithmer - vil man måske gerne kunne angive, at to dele af samme array, kan udføres parallelt i koden - dette kan være forholdsvis svært at analysere sig til. Har vi derimod to delarrays, der hver er halvt så store, og kun har adgang til sin del af lageret, så vil to processer, der arbejder på disse delarrays, nemt kunne udføres samtidigt. Laves en procedure, hvor de to delarrays overføres, og hvor disse har et range, der er halvt så stort som det samlede array, og hvis sproget laves så dette er muligt, så vil compileren ved sekventiel udførsel sikre, at de to halvdele ikke kan få adgang til hinanden, og ved parallel kode, vil der sikres, at koden kan udføres samtidigt.

I koden, med eksemplet, hvor mange processer startes op, og bruger hver sit element i array[i], svarer problemet lidt til pointere, og er svært at gennemskue. Det er bedre, hvis man kan opstarte n processer, der har hvert sit lokale lager, f.eks. ved at opstarte n procedurer/funktioner, med lokale variable. På den anden side, mener jeg, at i det simple eksempel med i, er det så simpelt, at vi kan antage at en compiler kan gennemskue det. Men laver vi nogle beregninger på i, så vi eksempelvis laver access til 2*i+3, eller andet, der også er "disjunkt", så kan vores compiler, måske ikke gennemskue opgaven. I nogle tilfælde, kan en opgave gennemskues, når paralleliseringen sker meddens koden udføres, fordi den så "opdager" at den pågældende opgave er disjunkt med eksisterende - men det er meget mere kompliceret.

Efter min opfattelse, er sprog som C++ og Java ikke fremtiden - de skal "modificeres" så de egner sig til, at parallelisere sekventiel kode automatisk, og de må ikke bero på en underliggende "maskine" der definerer intervaller og nøjagtighed. Et sprog, skal være hardwareuafhængig, og må ikke løse problemet med hardwareuafhængighed, ved at definere en underliggende hardware, som koden defineres til at køre på. Ved udviklingen af sprog, skal tænkes på sådanne forhold, og der skal tænkes på, om en opgave er nemt at parallelisere. COMAL80, kan nemt vinde over sprog som pascal, og C++, når det drejer sig om parallelisering, på grund af dets manglende implementering af pointere. Men, naturligvis kan det gøres langt bedre end COMAL 80.

Det, at anvende "filer" i forbindelse med dynamisk hukommelse, således man har mulighed for at åbne, og lukke områder i hukommelsen dynamisk, og mulighed for at åbne dem, med kun læseadgang mv. er meget mere velovervejet, end den "rå" brug af hukommelse. Naturligvis, behøver det ikke at gå langsomt, da koden reelt implementeres som var det brugt ram direkte. Dette kan også ske, når der anvendes filer, ved at en fil associeres til et bestemt område i ram'en, i stedet for, at det er ram på området. Filer, er på mange måde mere egnet, til struktureret opbevaring af dynamiske data, end pointerstrukturer. I mange tilfælde, kan filer bruges, f.eks. til databaser mv. hvis man ophævede begrænsningerne, der gør at filer opbevares ineffektivt, sløvt, og langsomt tilgængeligt. I dag, er ofte lagt grænser ind, for hvor mange filer, der må være åben ol.

Håndteringen af ram, kan i nogle tilfælde, også gøres mere logisk, ved at tillade at normale strukturer har fleksibel størrelse. I dag, er f.eks. strenge, og arrays, af faste størrelser. Tillades fleksible størrelser, i et sprog, så vil måske kun indexes i arrays, der er optaget, optage plads. Måske kan vi have strukturer, der indlejrer sig selv, fordi at dette ikke fylder noget, så længe der ikke er indsat data - rekursive strukturer, giver mulighed for at have et teoretisk uendeligt forbrug af lager, men uden det fylder, fordi at data ikke er sat i. Vi kan, ved eksempelvis et træ, så slette dele af træet, og ned. Eller, vi kan bruge det, som et harddisk katalog, hvor strukturen er angivet på forhånd, og hvor vi kun har lovlig access til typer, der angives i strukturen.

Næsten uanset hvad vi gør, vil vi opnå mere gennemskuelig kode - og ikke mindst mere paralleliserbar kode - end hvis vi bruger pointere.

Det vi skal, er ikke at lære programmørerne at kode parallelt. De skal derimod have programmeringssprog, der gør at deres sekventielle kode, nemt lader sig parallelisere - eller parallel kode, nemt lader sig gøre sekventielt.

  • 0
  • 0
Brian Vinter

Jeg må desværre sige mig uenig i din konklusion:)

Det vi har behov for er sprog/miljøer der tillader programmøren at specificere potentiel samtidighed og afhængigheder. Simpel parallelisering er sjældent problemet fordi selv den simpleste paralelle algoritme render ind i hukommelses-flaskehalse (Von Neumann Bottleneck). Derfor hyperthreading/SMT og de andre triks for latency-hiding.

Når man så med CSP får en algebra der kan bevise egenskaber ved den endelige applikation og man kombinere det med en scheduler der dynamisk kan optimere til hardware så begynder det at virke, men statiske paralleliseringer er alt for følsomme overfor støj (=async hændelser) til at de kan skaleres til den hardware vi får i fremtiden.

Til distribuerede hukommelses-arkitekturer vil vi nok bruge klassisk parallelitet langt ud i fremtiden:)

  • 0
  • 0
Jens Madsen

Vi er enige i, at statisk parallelisering ikke giver nok. Det kan dog optimeres, ved at lave fornuftige sprog. Med gode sprog, og ved samtidigt at have forståelse for, hvordan det fungerer, vil du kunne opnå ligeså gode resultater, som med deciderede parallel programmeringssprog.

Programmører skal ikke programmere i assembler, eller have kendskab til busserne og problemer omkring dette - deres opgave er, at kode opgaven ind i et højnivausprog. Hardwarevidenskab, hører under embedded software. Ved embedded software, sættes ikke samme krav til generisk programmering, som på computere, og du kan derfor bedre acceptere at der tages hensyn til hardwarens opbygning. Ofte, er den endog skrædersyet, til at fungere sammen med koden.

På PC'er, er dette urelevant. Her, skriver du et program, og kender ikke processoren, eller flaskehalse. Det er operativsystemet, og compilerens opgave, at løse flaskehalsene og paralleliseringen. Dog, må du gerne overveje f.eks. store O funktioner, da dette har noget med softwarens kompleksitet at gøre, og er ikke en hardware parameter. Selve størrelsesordenen, afhænger ikke af hardwaren.

Bortset fra indenfor visse grafikberegninger, er det dog ikke computerkræfter der mangler på nutidens PC'er, men kopieringskræfter. PC'ere, står typisk og "kopiere" uafbrudt hele tiden. En stor del, af denne kopiering, kunne undgås ved fornuftigere software, eller ved at indbygge specielt elektronik der får hardwaren til at kopiere et op til ubegrænset antal bytes, på en endelig kort tid.

  • 0
  • 0
Torben Mogensen Blogger

PS: @Torben: Jeg ville bryde mig om at skulle overbevise Datatilsynet om, at jeg havde styr på de meget personfølsomme oplysninger i et EPJ, hvis jeg havde dem i Sawzall...

Nu har du ikke oplysninger i Sawzall, oplysningerne er i den distribuerede database, som tilgås af Sawzall.

Men jeg tror, at du vil have større problemer med at overbevise om sikkerhed i en distribuere applikation skrevet i C eller C++, end i en applikation skrevet i Sawzall.

  • 0
  • 0
Lasse Lasse

Hej Jens,

Pointere er næsten uunværlige når man arbejder med dataformater og protokoller (billeder, lyd, video, kryptering, kompression, kommunikation, osv).

Dataformater indeholder som regel dataelementer som er placeret på offsets som ikke er delelige med dataelementets størrelse. Fx en header på 23 bytea efterfulgt af en sekvens af floats á 4 bytes.

  • 0
  • 0
Jens Madsen

Pointere er næsten uunværlige når man arbejder med dataformater og protokoller (billeder, lyd, video, kryptering, kompression, kommunikation, osv).

Pointere er uundværlige - specielt, fordi at index'es til arrays, også kan betragtes som en form for pointere. Her peger du, med en peger, i en array, af en bestemt type. Analysemæssigt, er det svært at håndtere, hvis du har et kæmpe program, der kun anvender et array - hvis derimod, at du opdeler det i flere arrays, så kan du nemt afgøre, at disse er disjunkte, og kan bruges samtidigt.

Det er som sådan ikke et så stort problem at bruge pointere, hvis bare du kun anvender dem indenfor et så lille område som muligt - og ikke hele computerens hukommelse. Du opretter bare en array, eller hukommelsesdel, som du kan "pege" i.

Alligevel, mener jeg, at vi skal udarbejde strukturer i programmeringssprog, så vi undgår pointere. Årsagen er mest, at jeg tror det vil give bedre programmering. Men, hvis det er en pointer vi har brug for - eller et index i et array - så har vi naturligvis brug for det, og skal bruge det.

Vi ser i visse tilfælde, at vi har arrays (eller dele af hukommelsen), som vi ønsker at kunne behandle samtidigt - f.eks. array[0..9] samtidigt med array[10..19] - og her kan det være praktisk, at kunne angive på en måde, at dette er muligt - altså at vi kan angive, at det i en del af programmet, er disjunkte områder, der samtidigt kan bruges.

I forbindelse med protokoller, ser vi ofte at der angives datastrukturer, hvor noget betsår af en byte, efterfulgt, af en integer/word osv, og måske indeholder disse strukturer også pointere, eller floats, der er angivet efter en bestemt standard. Efter min opfattelse, skal et programmeringssprog være abstrakt - det betyder, at compileren selv afgør hvor mange bits den bruger til en integer, udfra hvilket område at integeren dækker, og udfra hvad det er praktisk af hensyn til computerens struktur. En integer fra 0..99 vil måske fylde syv bit, eller 16 bits, fordi at computerens struktur gør det mest praktis, at den fylder 16 bits. Det er alene compilerens afgørelse, og der må ikke kunne laves kode, der kan "vise" hvad compileren har gjort. Programmets funktion, skal beskrive funktionen, og compilerens valg, skal være bagved, og ikke kunne lokkes ud.

Det ses, at denne teknik ikke arbejder godt med faste strukturer, hvor vi siger at vi har en byte, og en float efter en bestemt "standard". For vores compiler, har netop lov til at selv bestemme, hvordan den vil gemme vores integer, hvor mange bits den vil bruge, og hvilken standard den vil bruge. Dette må ikke kunne påvirke programmet. I forbindelse med protokoller, har vi behov for, at kunne angive at vi ønsker noget gemt i en bestemt integer form, efter en bestemt standard. Det kan være, at laveste bit angiver 1'ere, næste bit -2'ere, tredie bit +4'ere, og fjerde bit -8'ere osv. således at at fortegnet skifter på hver anden kvotient. Vi ved ikke, om vores compiler tilfældigvis gemmer en integer på samme måde, eller om den gemmer dem på en helt anden - måske gemmer den dem med fortegn først, og herefter det absolutte tal på normal binær form.

Moralen er, at compileren selv bestemmer - men at vi har behov for, at i visse tilfælde specificere eksakt hvordan noget skal gemmes af hensyn til typekompatibilitet. Dette skal defineres på to forskellige måder - når det gemmes "normalt" bestemmer compileren. Hvis vi har behov for, at gemme det på en speciel måde, så er der et navn for hver type (også vores specielle integer gemme metode), og vi kan så sammenstykke vores type, på samme måde som ved bit-unions i C++. Der må ikke være nogen "grænser" så vi ikke kan lave en struct der overstiger 42 bits eller noget i den retning. Det skal være muligt, at stykke vores typer sammen som vi har behov for, og vi skal i princippet have mulighed for at få adgang til "bit indholdet", eller "byte" indholdet af typerne, så vi kan sende det ud som en datastreng, eller gemme det på et eksternt medie. En sådan struktur, skal altid gemmes packed, og ikke pakket format giver i princippet ingen mening for bit-unions. For hvis to typer, f.eks. bit, eller byte, lægger på samme position som en float, så vil eventuelle indsatte tomrum få betydning for programmets udførsel - og det er ulovligt. Ligesom ved bit-unions i C++, er det vigtigt, at det er en helt seperat type, i forhold til compilerens måde at opbevare data på, fordi det ikke giver mening at "blande" de to metoder.

Når vi normalt koder, vil vi ikke anvende "bit unions", og strukturer hvor vi presser compileren til at bruge et helt specielt format for de gemte data, og at pakke dem tæt, så vi kan få det ud bitmæssigt og bytemæssigt korrekt rækkefølge. Det er ikke nødvendigt, og nedsætter kodens evne til at kunne analyseres.

Det er vigtigt, at supportere begge muligheder. Ved normale programmer, må vi ikke anvende bit-unions, og specificere eksakt hvordan at en byte, eller integer skal gemmes i lageret - eller en float. Vi må angive hvilket interval en byte, eller integer er - eller hvilket interval og nøjagtighed, en float skal kunne opfylde. Kun, hvis det direkte er typer vi definerer af hensyn til dataudveksling, så fratager vi compilerens dens mulighed for at tage bedste beslutning, og dirigerer den til, at gøre eksakt som vi beskriver, af hensyn til datakompatibiliteten.

Vi kan undlade "bit unions", og så skrive kode, der gør alt dette - men det bliver meget uoverskueligt, og på grund af at protokoller og datakompatibilitet med andet software og hardware er noget meget brugbart indenfor software, mener jeg at det bør med at kunne "sammensætte" en selvdefineret type, udfra indbyggede typer, og hvor at dataene gemmes præcis og eksakt efter definationerne, således vi kan give bit og bytemæssigt adgang til typen. Dog, er vigtigt at forstå, at det ikke er noget vi må anvende til programmets algorithmer - det må kun anvendes, hvor det er yderst nødvendigt, altså ved kommunikation med hardware eller dataformater på diskette, eller lign. og ikke ved programmets normale funktion - for vi udelukker i høj grad at compileren gør dens arbejde bedst muligt, ved at "overspecificere" hvad den skal. Det er altid bedst, at give en compiler dens frie muligheder for at lave en optimal oversættelse, og kun diktere, når det er yderst nødvendigt og praktisk. På den måde, opnås bedste oversatte og kompatible kode.

Det er også en fordel, hvis vi har en metode, så vi kan definere vores egen eksakte "integer" type, som vi kan bruge i vores sammensatte "bit union" type. F.eks. hvis den pågældende integer, hvor hver anden kvotient er negativ, ikke er implementeret i compileren - så skal vi gerne selv kunne definere en sådan type, til vor bit union. Det betyder, at vi kan lave et bibliotek, med sådanne specielle integer typer (måske kan de også have parametre, så vi kan angive det skal være fra -78..9) og der angives så en "metode" for hvordan den håndteres. Float, kan måske også defineres på flere forskellige typer måder, og vi kan have et bibliotek med "floats" for vor sammensatte bitunion. Men, for normal kode, har vi ingen indflydelse på typerne, og kan ikke selv definere eksakt hvordan bittene skal forstås.

Som man måske kan se, synes jeg at bit_union i C++, er et meget praktisk begreb - men det giver kun mening i pakket sammenhæng, og kun mening, hvis bittene er eksakt defineret. Samtidigt, giver det også kun mening, hvis der ikke er "grænser" så det skal holde sig indenfor en byte, eller word. Der kan være behov for at specificere integer på en bestemt måde, eller måske om bittene skal gemmes med mindst betydende først, eller lavest betydende først osv. Formålet, er alene datakompatibilitet, og vi må ikke forvente så høj ydelse, som når vi lader compileren afgøre hvordan bits skal opbevares. Compileren tager hensyn til vor hardware, og vi har måske fået en helt ny hardware, der gemmer data på en ny måde - stadigt, vil programmet angive den samme funktion, og virke identisk. Der, hvor vi har angivet hvordan vores type skal gemmes, kan den måske ikke mere håndtere opgaven i hardware, man skal implementere det som "kode" der emulerer typen. Derfor, kan vi ikke forvente, at data der specificeres på denne måde, går hurtigt. Ved typer, hvor vi selv angiver "kode" for hvordan de forstås, vil de altid være emuleret. Kun indbyggede typer, er måske muligt, at de går hurtigt, fordi at computeren tilfældigvis håndterer typen i hardwaren. Dette er et tilfælde, og behøver ikke at gælde næste generation - men koden vil altid fungere ens, da det er et krav at compileren håndtere de typer som er indbygget for de sammensatte "bit unions" typer. Måske, vil det med tiden gå sådan, at alle typer der anvendes i "bit unions" emuleres, og tager lang tid, uanset de håndteres af hardware.

I dag, er compilerne noget snask, hvor man aldrig har taget stilling til, om compileren skal afgøre hvordan data gemmes, eller ikke. Det betyder, at vi selv skal angive det, ved hjælp af packed, eller ikke packed ordre. Og det er muligt, at angive bit-unions, hvor strukturer der overlejre hinanden, og giver forskellige resultater afhængigt af om det er packed, eller ikke packed, og koden derfor "måske" virker, hvis den tilfældigvis koder det korrekt. I princippet, er bit unions udeffinerbare, hvis de ikke er i packed format, fordi vi tillader forskellige typer overlejrer hinanden, eksempelvis bit arrays, og byte arrays, der kan overlejre integers og floats.

Idéen med bit unions er god, og det er den, som du skal bruge her, hvor du eksakt vil definere din type, og måske bruge "pointers", eller måske en selvdefineret type, du helt selv har defineret ved hjælp af emuleringskode.

Typisk, vil dine pointers her, være "index'es" i en byte array, der overlejrer nogle andre datatyper vil jeg tro. Det vil ikke være pointers, der relaterer til den fysiske ram (med mindre du bruger den til dataudvekslingen). Problemet med låsning af hukommelsen globalt, eksisterer derfor ikke.

  • 0
  • 0
Brian Vinter

For de fleste koder vi bruger idag kommer grænsen lang før de 8 kerner - faktisk er rigtigt mange programmer ikke i stand til at bruge bare en kerne uden at hukommelsen er en flaskehals.

Klassisk 'flere kerner cache løser problemerne' virker ikke, så lige nu er de konkurrende løsninger:
*Flere HW tråde der skjuler latens (SMT - SUN fører her)
*Program styret "cache" med end DMA motor (IBM fører her)

Hvem der vinder ved jeg ikke- men det er sjovt at lege med:)

  • 0
  • 0
Steen Christensen

hmm

Undskyld men sådanne udtagelser får de små nakkehår (og guderne skal vide der er ikke for meget) til at stritte :)

Det er vel ikke tilfældigvis de samme mennesker som udtalte at "der er et markeded for 5 computere på verdensplan" - Thomas Watson, IBM, 1943 eller "640K ought to be enough for anybody" - Bill Gates 1981.

Nu er det jo ikke helt nye udtagelser, men det beviser at noget af det sværeste at spå om er fremtiden.

Kan vi ikke blive enig om at det er muligt at med den arkitektur og de programmeringsværktøjer vi bruger lige nu, så er det måske nok vanskelig at udnytte ressourcerne optimalt.

Kan i have en god dag.

Steen

  • 0
  • 0
Jens Madsen

Hvis du kan opnå 32 CPU kerner, får hurtig adgang til samme registre (evt. øger antal registre) og lager, samt lader dem få direkte adgang til hinandens data (forwarder imellem dem med en hurtig forbindelse), og optimerer dem efter at give så lidt forsinkelse som muligt, i operationsretingen (her betyder menteretninge ikke meget), så kan du opnå, at de dels fungerer godt sammen, selvom der er data afhængigheder, og kan anvende samme hukommelse. Det har vist sig, i dette tilfælde, at der er tendens til en "dybde" i indstruktionerne, som er logaritmisk afhængig af antallet af kerner - det betyder at ved 32 kerner, vil være en gennemsnitslig forsinkelse på tiden 5, hvis alle indstruktionerne udføres i huk. Der udføres, altså 32 indstruktioner, på samme tid, som 5 indstruktioner tager. Øges det til 64 indstruktioner samtidigt, så er forsinkelsen typisk svarende til 6 indstruktioner - og dermed er omtrent en linær vækst i hastighed, som funktion af antal kerner.

I praksis, er det altså hardwaren så sænker grænsen, da det på et tidspunkt, bliver næsten umuligt, at opnå ligeligt og hurtig adgang, til samme hukommelse, for mange kerner. Dertil kommer, at index addresseringer, giver "problemer", og ikke altid kan gøres hurtigt. I nogle tilfælde, kan man hente flere data på éen gang, og så håbe på, at de tilfældigvis er der - og det er muligt at forprocesssere koden, så den kan indsætte direkte et offset i forhold til index, hvis der læses flere addresser samtidigt - det kan dels gøres i compiler, og det kan gøres i CPU.

Det er derfor primært hardware problemer, i form af en ligelig tildelt hurtig adgang til samme ram, der gør at det går sløvt. Hvis rammen laves intern på chippen, er det i praksis intet problem at opnå op til 32 kerner idag, som får ligeligt adgang til samme ram, og derfor bliver omtrent 6 gange hurtigere på grund af de mange kerner, end en enkelt kerne vil have opnået. Kan proppes 64 kerner ind, er gevindsten endnu hurtigere - ca. 8-9 gange højere, end en enkelt kerne. Men hardwarens overhead er også større, på grund af de mange ligeligt fordelte adgange.

I nogle tilfælde, kan data processeres først, så der opnås bedre ydelse. Og i nogle tilfælde, kan adgangen til ram'en simplificeres, så der kun samtidigt haves ligeligt adgang til nogle samtidigt brugte blokke. Sekventiel kode, har det med at kun bruge hukommelsen, i nogle samtidigt brugte blokke. Dog, vil altid være et problem med dataoverførslen fra ekstern ram, og til processor - specielt, ved indekserede data, hvor næste data er svært at udregne på forhånd, kan det medføre en access tid.

Sådanne problemer, gøres på mange måder mere simple, hvis der anvendes automatiske metoder, til at gøre programmet parallelt. Typisk, vil en løkke, der styrer index til ram lageret, måske også styre andet - men vi kan adskille de to løkker i to, så der bliver éen til styring af index, og en anden til styring af index for de andre dele - og denne parallelisering, gør at de også kan forløbe med forskellig hastighed. Processen, der styrer index, kan derfor automatisk separeres, og levere index i god tid, så de kan hentes ind, og anbringes i processoren, når det er hensigtsmæssigt.

Parallel programmering - eller automatisk omsættelse til mange tasks, har derfor store fordele, fremfor normal sekventiel kodning. Sekventiel kodning, har også fordele, fordi det her er nemmere at analysere databrugen, ofte vil programmet bruge samme data, hvis koden står tæt. Det bedste, er derfor normal sekventiel kodning, men hvor automatikken gør det parallelt - for så ved processoren og compileren mest om koden - både hvordan data naturligt hører sammen fordi det står sekventielt, og den kan adskille det i så mange processer, som den ønsker, for at lette afviklingen, og eventuelt bruge mange kerner.

  • 0
  • 0
Log ind eller Opret konto for at kommentere
IT Company Rank
maximize minimize