Torben Mogensen header

Fremtidens programmering

I en nylig artikel, citeres Bruce Eckel for nogle forudsigelser om fremtidens programmering. Som jeg nævnte i en kommentar til artiklen, synes jeg det er en gang luftig øregas, specielt i lys af den forholdsvis korte tidshorisont på 25 år.

Hvis man ser på de foregående 50 år, så er der faktisk ikke sket meget inden for egentlig programmering: Den største forskel er, at nutidens programmører har meget større biblioteker af eksisterende kode at tage af, og at de har værktøjer, der allerede mens, man skriver sit program, kan finde de mest almindelige fejl, hvor tidligere tiders programmører ofte skulle vente i minutter eller sågar timer på at få oversat sit program, og dermed få checket for typefejl og lignende. Men den egentlige programmeringsproces: At klarificere og konkretisere sine ideer, er ikke væsentligt anderledes nu end i 1960.

Og denne proces slipper man ikke for: En computer kan ikke gætte, hvad det er, du vil – du bliver nødt til at forklare det entydigt og i detaljer. Allerhøjest kan ubetydelige detaljer overlades til computeren, og man kan specificere en kontekst, som betyder at andre detaljer kan være underforstået ud fra konteksten.

En sådan kontekst kan være specificeret i form at et domænespecifikt programmeringssprog, som netop er et sprog, der er designet til en bestemt type problemer, og hvor det er underforstået i ethvert program, at det er denne type problemer, der arbejdes med. Jo mere indskrænket problemområdet er, jo mere kontekst er underforstået, og jo færre detaljer skal programmøren specificere. Prisen er selvfølgelig, at sproget er ganske uanvendeligt til ting udenfor problemområdet. Men det er lidt ligesom forskellen på en schweizerkniv og en skruetrækker: Schweizerkniven kan bruges til flere forskellige ting, inklusive at skrue skruer i, men når man skal skrue en skrue i, så er det klart nemmere at bruge en skruetrækker.

Så min første forudsigelse er, at en gennemsnitlig programmør vil bruge flere, men mere specialiserede programmeringssprog. Denne tendens er allerede i gang: Hvor en gennemsnitsprogrammør for 50 år siden typisk brugte et eller to sprog, og en programmør for 25 år siden måske brugte tre-fire sprog, bruger en typisk programmør i dag ofte en halv snes forskellige sprog til forskellige typer af opgaver.

En elefant i stuen er selvfølgelig parallelisme: Processorfrekvenserne, der i løbet af firserne og halvfemserne fordobledes hvert andet år, er i løbet af de sidste fem år slet ikke steget. I stedet er der kommet flere kerner i processorerne. Som det ser ud nu, bliver de forskellige kerner typisk brugt til at køre forskellige jobs – det er de færreste applikationer, der bruger mere end en processor, og når det sker er det som regel til deljob, der er skarpt adskilte, såsom at tegne flere websider samtidigt. Men hvis man ønsker at bevare tendensen til, at computere bliver hurtigere og hurtigere til alting, så må man meget mere effektivt fordele jobs mellem det hastigt stigende antal processorer.

Det er naivt at tro, at man kan blive ved med at programmere i samme stil som siden 1960, hvor man beskriver et program som en sekvens af operationer på lageret (repræsenteret som variable, objekter, og andre datastrukturer), og forvente, at computeren (repræsenteret ved oversætter og operativsystem) selv kan finde ud af at fordele arbejdet effektivt. Modsat Eckel tror jeg heller ikke, at dynamiske sprog, skyer og sværme uden videre vil løse alle problemer. Man bliver ganske enkelt nødt til at programmere på måder, hvor det kræver en indsats fra programmøren at pålægge en rækkefølge på sine operationer, modsat nu, hvor det kræver en indsats at udtrykke, at der ikke er nogen foretrukket rækkefølge. Men det alene er ikke nok, man bliver nødt til at hjælpe computeren med at fordele arbejdet, for programmøren ved bedre end computeren, hvad det er for et problem, der skal løses, og dermed, hvordan problemet bedst deles op i underproblemer. Igen kan noget af dette gøres nemmere ved at have en kontekst, der underforstår et problemområde og dermed indirekte en del af løsningen – f.eks. hvordan man bedst fordeler arbejdet.

Men alt det tager tid: Der er en voksende korpus af software, som man ikke har ressourcer til at skrive om, men som man alligevel forventer vil køre hurtigere ved skift til nyere hardware. Det sætter et pres på hardwareproducenterne for at udskyde det uundgåelige skift af software, og så længe det lykkes for hardwareproducenterne at levere dette, er der ikke så stort behov for den enkelte softwareudvikler for at ændre sine vaner – de gamle metoder virker stadig, og hvorfor skifte, når det ikke er absolut nødvendigt.

Dertil kommer, at den almindelige forbrugers behov for regnekraft primært er indenfor medieteknologi: Bedre filmkvalitet, lækrere grafik i spil, bedre lydkvalitet, osv. Den slags beregninger kan i stort omfang lægges ud på grafikprocessorerne via standardbliblioteker, så den almindelige applikationsprogrammør ikke behøver at tænke på parallelitet. Så det bliver kun en håndfuld meget specialiserede biblioteksudviklere, der skal lave udvikling specifikt mod højparallelle systemer. Med det holder kun et stykke hen af vejen: På et eller andet tidspunkt bliver det nødvendigt selv for "almindelige" applikationsprogrammører at programmere parallelle systemer. Og det er ikke trivielt med nutidens værktøj: De er ofte specialiserede til en bestemt type hardware, så programmer udviklet til den ene maskine slet ikke kan køre på andre (eller i hvert fald ikke specielt effektivt). Det ses blandt andet i de problemer Sony har med at få spiludviklere til at udnytte Cell-processorens fulde potentiale: Programmer, der kan gøre dette, kan ikke køre på andet end PS3, og da de fleste spiludviklere udvikler spil, der kan køre på flere forskellige konsoller (f.eks. både Xbox 360 og PS3), er det ikke umagen værd at gøre forsøget.

Så, hvis det virkelig skal batte, så må man kunne skrive effektiv parallelprogrammering uden at skulle have en bestemt hardwareplatform i tankerne. Og det varer noget, inden det bliver en realitet.

Kommentarer (17)
sortSortér kommentarer
  • Ældste først
  • Nyeste først
  • Bedste først
#1 Poul-Henning Kamp Blogger

Hvis man ser på de foregående 50 år, så er der faktisk ikke sket meget inden for egentlig programmering:

Jeg plejer at fremhæve, at vi nu selv kan bestemme hvor brede vores hulkort skal være, og at vi slipper for at støvsuge "chads" op over det hele :-)

Poul-Henning

  • 0
  • 0
#2 Carsten Sonne

Hvis man ser på de foregående 50 år, så er der faktisk ikke sket meget inden for egentlig programmering...

Hvis man kigger 25 år tilbage, så sad man og lavede sine programmer i tekst filer. Det gør vi stadig på præcis samme måde. Udviklingsmiljø, sprog og biblioteker har udviklet sig enormt, men den måde der programmeres på er uændret.

Der er ikke nogen grund til at tro det vil ændre sig markant inden for General-purpose sprog. At domæne specifikke sprog skulle blive brugbare til det som General-purpose sprog kan, er naivt. Præcis som Torben beskriver det.

Den form for intelligens som Bruce Eckel beskriver, er måske muligt ift. den rå regnekraft om 25 år. Rå regnekraft er bare ikke den eneste faktor.

Så, hvis det virkelig skal batte, så må man kunne skrive effektiv parallelprogrammering uden at skulle have en bestemt hardwareplatform i tankerne. Og det varer noget, inden det bliver en realitet.

Det er så småt ved at blive en realitet. Der findes forskellige biblioteker som stiller et rimelig tilgængeligt parallelisering framework til rådighed.

I .Net 4.0 er inkluderet sådanne paralleliseringsbiblioteker, bl.a. Parallel LINQ (PLINQ) & Task Parallel Library (TPL).

[code=csharp] int[] nums = Enumerable.Range(0, 1000000).ToArray(); long total = 0;

// Use type parameter to make subtotal a long, not an int Parallel.For( 0, nums.Length, () => 0, (j, loop, subtotal) => { subtotal += nums[j]; return subtotal; }, x) => Interlocked.Add(ref total, x) ); [/code]

Tilsvarende findes til visse andre sprog og platforme.

Mon ikke Bruce Eckel motiv blot er at fremprovokere en debat. Jeg tvivler på han selv tror på sine 'forudsigelser'.

  • 0
  • 0
#3 Nicolai Møller-Andersen

Deja vue? De har sagt, at programmørerne bliver arbejdsløse et hav af gange. Det plejer at være noget med, at programmering bliver pærelet, fordi computerne bliver bedre. Det er lidt ligesom, at husmødre kan blive racerkørerer, fordi bilerne bliver bedre. Det er da klart. Træning er ikke nødvendigt, og bilen kan selv finde vej. Inde på racerbanen ihvertfald.

Jeg husker bølgen med 4G værktøjer i starten af firserne. Dataflex var glimrende til adressebøger, men håbløst uflexibelt til større ting. Performance var heller ikke den stærkeste side. Så var der AI. Prolog var morsomt, men de egentlige løsninger udeblev, fordi det var alt for bøvlet at stoppe viden om hele verden ind i systemet. Performance var heller ikke den stærkeste side. Så kom bølgen med objekter. Jaja, man kan da nogen gange opnå lidt genbrug af kode, men objekterne koder jo ikke sig selv, og abstraktionsniveauet hæver sig meter højt og langt væk fra metallet. Derfor er performance også her problematisk. Så kom der noget rigtig AI i halvfemserne. Neurale netværk er sjove, men virkelige applikationer har det svært. De skal trænes op, og man kan ikke garantere imod "menneskelige fejl", når der er kunstige hjerner på spil. Desuden er performance et problem.

Nu skal man så læse, at trådede objekter, messagepassing og virtuel hukommelse er løsningen på alt. Bevares, det er da dejigt, at .Net kan lege med tråde, men... Alle tre ting burde jo være en del af enhver rutineret programmørs værktøjskasse, for de har eksisteret siden halvfjerserne i een eller anden form. Det eneste nye i den her suppedas er, at lineær skalering er på kanten til at blive virkelighed. Det er fedt, men det er samtidig den perfekte undskyldning for aldrig at optimere sin kode. Heldigvis vil racerkørerne altid være dem, som optimerer mere end de andre. Det kræver viden om systemet. Ikke abstraktion.

Jeg tror mere og mere på, at fremtiden vil byde på grøn kodning. Objekter, abstraktioner og myriader af pointere til pointere, garbage collection og hvad ved jeg... Alt sammen perfekt til at klappe noget bix sammen i en fart - uden den store omtanke. CPUen bruger milliarder af GHz på uproduktiv kode. Man ville kunne nedlægge atomkrafværker, hvis der blev kodet grønt.

  • 0
  • 0
#4 Carsten Sonne

@Nicolai Møller-Andersen

Overvej at lave en cost/benifit analyse det scenarie du skitsere.

Den 'grønneste' kode skrives i assembler med dyb indsigt i hardware, OS og diverse drivere.

Abstraktion giver mulighed for at være mere produktiv og giver større portabilitet samt færre fejl.

Hvor er break/even? Ikke i det scenarie du skildre.

  • 0
  • 0
#5 Carsten Sonne

Den vision Bruce Eckel skildre, er han ikke alene om at have. Microsoft er en af dem, der deler den.

Integration Services (SSIS) er let tilgængeligt og består fortrinsvis af drag-and-drop programmering. Hvis man bevæger sig uden for det domæne, det problemområde, som SSIS beskæftige sig med, kommer SSIS til kort. Her må man ty til et General-purpose sprog (.Net), for at kunne udtrykke det programmet skal gøre.

Det samme gør sig gældende for Workflow Foundation og Oslo. Oslo har erkendt problemet. I stedet er strategien, at lave et DSL der retter sig mod et bestemt domæne. Nye version af MS SQL og Excel udvider deres funktionalitet, ligeledet i et forsøg på at adressere problemet. Situationen er bare, at det eneste der reelt er sket med produkterne, er at de nu også omfatter BI som en del af domænet

Andre er også med på vognen. Inden for statistik og numerisk analyse, er SPSS udbredt. Et let tilgængeligt drag-and-drop analyse værktøj i stil med Excel. Igen, når komplekse behov og analyser melder sig, kommer SPSS til kort. I stedet må man ty til et General-purpose sprog som f.eks. Stata. SPSS tilbyder Python og SAS har deres eget halvt General-purpose og halvt Domain specific sprog.

Torben beskriver problemet således:

Men den egentlige programmeringsproces: At klarificere og konkretisere sine ideer, er ikke væsentligt anderledes nu end i 1960.

Uanset hvor meget vi anstrenger os, kommer man ikke uden om det faktum, at man skal forklare computeren hvad der er for en opgave den skal løse. Og jo mere opgaven falder uden for et specifik problemområde, jo mere detaljeret skal forklaringen være.

Der er kun en løsning på det paradoks: Intelligent software, der kan forstå et behov eller en opgave beskrivelse ud fra et helt overordnet perspektiv og herefter selv lave programmet, der kan afvikles af hardwaren. Den dag vil komme, hvor det bliver en realitet. Det er bare ikke om 25 år. Mit gæt er, at vi snakker nok nærmere 50 – 100 år.

  • 0
  • 0
#6 Nicolai Møller-Andersen

Der er sindssygt mange computere i verden. Et meget forsigtigt bud er, at de - med grøn kode - ville bruge 50% mindre strøm. Jeg tror selv, at vi skal meget højere op. Ubegribeligt mange programmer lever i 10-15 år eller mere, så programmets strømforbrug kan helt sikkert omsættes til hård vestlig valuta.

Grøn kode betyder ikke nødvendigvis, at alt skal skrives i assembler. Ligesom i andre af livets forhold er der en optimal mellemvej. Det gælder også abstraktion. Abstraktion kan give fordele, men alle opgaver har et abstraktionsniveau, som er passende. Overskrides dette fås ulemper såsom flere fejlmuligheder, dårligere stabilitet, svær vedligeholdelse og fremfor alt ringe flexibilitet. Portabilitet? Well, det meste c-kode er ret portabelt.

Alt dette er jo i virkeligheden off topic. Pointen var, at kodning ikke har ændret sig væsentligt, og så længe computeren ikke besidder menneskelige evner til at spørge ind til en opgave, så skal programmøren jonglere med semaphorer, tråde og andet guf ud fra detailviden om problemet og løsningens natur.

Der kommer så udfordringen. Når programmøren tror, at computeren tænker i java og objekter, så ligner alle løsninger søm... eller hvordan er det nu?

  • 0
  • 0
#8 Deleted User

Det er naivt at tro, at man kan blive ved med at programmere i samme stil som siden 1960, hvor man beskriver et program som en sekvens af operationer på lageret (repræsenteret som variable, objekter, og andre datastrukturer), og forvente, at computeren (repræsenteret ved oversætter og operativsystem) selv kan finde ud af at fordele arbejdet effektivt. Modsat Eckel tror jeg heller ikke, at dynamiske sprog, skyer og sværme uden videre vil løse alle problemer. Man bliver ganske enkelt nødt til at programmere på måder, hvor det kræver en indsats fra programmøren at pålægge en rækkefølge på sine operationer, modsat nu, hvor det kræver en indsats at udtrykke, at der ikke er nogen foretrukket rækkefølge.

Hvis en opgave beskrives bedst sekventielt, er det intet problem for opgaven at parallelisere denne - en sekventielt beskrevet opgave, skal naturligvis være 100% veldefineret. Dertil kommer, at vores programmeringssprog, ikke er lavet til at kunne analyseres - men problemet ligger ikke i det sekventielle, men i at sprogene er uforståelige, selv for en computer.

Som et eksempel, på denne uforståelighed, kan nævnes pointere. Gemmer du noget i lageret, hvor en pointer peger - så kan data i princippet gemmes et vilkårligt sted. Dette gør, at computeren ikke kan analysere koden. Hvis du kan begrænse område, såsom du har en struktur, eller en array, som du ved din pointer er indenfor - så gør det koden mere overskuelig for compileren, og den kan bedre forstå den. Dog, så kan det til en vis grad løses med dynamisk compilering. Den kan prioritere, at det som ikke vides og som giver problemer for paralleliseringen, udregnes først - det betyder, at bestemme pointeren prioriteres op, fordi det løser et paralleliseringsproblem. Dog, er altid bedst, at på forhånd kunne vurdere det, fordi det gør koden bliver mest fleksibel fra start. Når der skal ventes på "knuder" der løses, og at knudeløsningen skal prioriteres op, så går det naturligvis ud over noget, og derfor er bedst med programmeringsprog der ikke indeholder sådanne knuder, såsom "tilfældige" pointere. Har man en pointer, er det bedst, at antallet af addresser den kan pege på i lageret kan forudsiges, f.eks. ved den kun kan ligge indenfor en bestemt array, eller struktur.

Programmeringsmæssigt, medfører dette, at vi helst skal bruge nye metoder, når vi anvender dynamisk hukommelse. I stedet for, at bare kalde en rutine, og få tildelt noget "tilfældigt" hukommelse til en pointer - og at pointeren kan være et vilkårligt sted i lageret - så er nødvendigt, at det kan forudsiges hvilke addresser pegeren kan pege til. En peger, er som sådan intet stort problem, hvis vi på forhånd kan analysere dens udfaldsrum. Kan vi ikke dette, bliver vi nød til at vente til den får en værdi, med vores efterfølgende optimering. Og eventuelt opprioritere, at den får værdi.

Når nogle "ikke" tror på at computerne kan opfatte programmerne abstrakt, og indsé funktionen, så tror jeg, at det skyldes de ikke rigtigt har kendskab til, hvordan der oversættes mellem et program og et dataflow træ. De fleste kan, hvis der ikke er løkker og kontrol strukturer. Men, er der løkker, konstrolstrukturer, arrays osv. eller pointere - så er mange der giver op. Og ikke mindst, ved pointere, er der grund til det. Et dataflow træ, er karakteriseret ved, at programmet opdeles i sine bestanddele af små paralle processer, der kører uafhængigt. Imellem disse er datastrømme, der sender data efter actor modellen. Ethvert program, kan i princippet oversættes til et sådant dataflow, men i nogle tilfælde, vil der opstå problemer i form af låsninger - som eksempel, vil en array oftest være en memoryblock, hvor kun éen process har adgang til af gangen, og denne multiplexes så. Dette betyder, at der reelt er det samme som "låsning". I nogle tilfælde, kan det løses med mere advancerede memory modeller. Men eksempelvis pointere, kan give problemer.

Et helt traditionelt program, der ikke indeholder pointere, er det dog nemt at omsætte. Hvis det indeholder arrays, der har konstant indhold, er det også nemt. Indeholder det arrays, der får tildelt data på en tilfældig position (index), så opstår låsningsproblematikker. Ofte, anvendes en fælles datafil, med éen addresseindgang, en læse/skrive indgang, data indgang, og data udgang. Alle data, foregår da sekventielt som for en normal ram, da f.eks. læsning, medfører der skal sendes to "læs data" kommandoer på skrive/læse indgangen. Rækkefølgen for brugen af hukommelsen, tvinges til, at være som angivet i programmet. Dog, hvis man har forskellige arrays, så vil de kunne fungere uafhængigt og parallelt. Imidlertid, kan meget gøres for, at optimere anvendelsen af arrays. Som eksempel, kan brugen deles op i læse og skriveblokke, hvor at en læseblok kan udføres i tilfældig rækkefølge, og en skriveblok kan udføres samtidigt men i prioriteret rækkefølge. Dette nedsætter "tvangen" i koden, og rækkefølgen bliver mere out of order - imidlertid tvinges en blok der læser, og en blok der skriver, til at stadigt køre på skift.

Hvis der ikke anvendes index referencer, men konstante referencer, er det mere simpelt, da der præcis vides hvilken addresse der skrives/læses, og det kan oversættes til en normal variabel.

Når programmer oversættes til parallelisme, opstår et andet problem - vi får masser af parallele processer, og CPU'en indeholder kun få... Det betyder, at det skal mappes effektivt ind. Her har vi enorm stor frihed, og det betyder, at vi kan vælge mapningen afhængig af, hvad vi har brug for af data. Programmerne, bliver dermed event-drevne. Hvis vi ønsker et output, kan vi finde præcist de processer der skal udføres, for at give outputtet. Hvis vi har brug for værdien af en pointer, kan vi udføre de processer, der giver resultatet af pointeren, og dermed "låser op" for vor paralleliseringen, og muligheden for events.

En sekventiel beskrivelse af et problem, er en enentydig beskrivelse, og som sådan intet beviseligt problem for en computer. Da beskrivelsen er eksakt, så vil computeren teoretisk kunne forstå den, og mestre omorganisering, parallelisering, og enhver anden behandling af koden. Det er også muligt - men, det er bedst at lave programmeringssprogene, så de bliver mest overskuelige for compileren, fordi der så ikke opstår så mange "knuder" i computerens forståelse af et program. Det betyder ikke, at det er nødvendigt at beskrive problemet parallelt.

Det kan være smart, at kunne beskrive et problem parallelt, fordi det giver den mest optimale, og overskuelige beskrivelse af et problem. Vi ser ofte, at programmører forsøger sig med tilstandsmaskiner, for at lave et parallelt problem sekventielt - dette ødelægger programmet, og gør det uoverskueligt. Det kan gøres, fordi tilstanden, så svarer til et bestemt sted i koden, for et parallelt program, men genneralt ødelægger det et programs overskuelighed og måske også analyserbarhed.

Derfor er bedst, at programmøren selv bestemmer, om de vil angive koden i rækkefølge - eller parallelt - og at de kan vælge det, alene udfra, hvad som er mest overskueligt.

De fleste tror måske, at det store problem er at omsætte fra sekventielt til parallelt. Men, det er måske et ligeså stort problem, at gå den modsatte vej, når det skal ske fornuftigt. Du får brug for, at kunne vælge den rette rækkefølge, af millioner af små parallele processer, og dette vil ske udfra flow analyser af softwaren. Er behov for nogle data, der skal komme tidligt - så er det muligt at opnå. Har man behov for realtids svar, så er det muligt at opnå. De pågældende paths bliver gjort hurtigere, og processerne køres først. Man kan ofte bare specificere, hvor stor forsinkelsen skal være på en path, og så vil det være muligt at garantere denne. Dertil kommer prioritering - det kan være f.eks. de dele der giver klumper i koden, og hvor udførslen medfører større fleksibilitet og parallelisme. Og prioritering, så den hyppigste svartid, og middelsvartid bliver kort. En simpel task switching mellem processerne, er helt uegnet - for den giver omtrent det værste som kan opnås og ikke det bedste. Årsagen er, at denne giver en dårlig middel-forsinkelse.

Min påstand er, at det som Bruce Eckel mener er fremtidens programmeringssprog, forskningsteknisk er "lige om hjørnet". Der foregår en del forskning i området - nogle problemer er løste, andre "mindre" løste. Men ingen er bevislig uløselige - endnu. Indimellem, sker at nogle beviser noget er uløseligt, og kort tid efter, kommer en anden med et bevis for, at det kunne løses. Beviser for, at noget er umuligt, skal altid tages med et stort forbehold.

Udover, at kunne automatisk analysere software, så computeren kan abstrahere sig fra rækkefølgen, gøre det eventdrevet, og parallelisere det, så vil også være muligt, at analysere dele af koden bort - dynamisk når programmet kører, og afhængigt af omstændigheder. Efterhånden som forskningen skriver frem, vil måske også være muligt at gøre omskrivninger på koden, der løser "knuder", øger parallelisme, og fleksibiliteten i udførslen, eller måske nedsætter et programs store O funktion.

Så skal vi spå 50 år ud i fremtiden, så er store O funktionen, måske ikke hvad den har været.

  • 0
  • 0
#10 Jesper Louis Andersen

Hvis en opgave beskrives bedst sekventielt, er det intet problem for opgaven at parallelisere denne - en sekventielt beskrevet opgave, skal naturligvis være 100% veldefineret.

Det her er naturligvis løgn. Der findes en klasse af problemer, de "inherently serial problems", som netop er umulige at lave parallelle. De er stort set alle kendetegnet ved et antal af iterationer hvor hver iteration er forholdsvis lille (så det er dyrere at kommunikere end at beregne den) og enhver ny iteration afhænger af den forrige på en sådan vis at man ikke kan lave spekulativ udførsel. Beregning af Pi er eet eksempel, men en del approksimative numeriske metoder er også i denne klasse.

Derfor er bedst, at programmøren selv bestemmer, om de vil angive koden i rækkefølge - eller parallelt - og at de kan vælge det, alene udfra, hvad som er mest overskueligt.

Torben snakker sådan set bare om at man skal kunne beskrive flow i sit program mere præcist end man kan i dag - og at standardflowet i beregningen skal være sådan at det kan parallelliseres. Man skal bare sørge for at begge beskrivelsesformer, parallel som sekventiel, er lige overskuelige. Dermed bortfalder det andet problem fuldstændigt.

--

  • 0
  • 0
#11 Torben Mogensen Blogger

Torben snakker sådan set bare om at man skal kunne beskrive flow i sit program mere præcist end man kan i dag - og at standardflowet i beregningen skal være sådan at det kan parallelliseres.

Min pointe var, at gængse sprog og kodningsstile pålægger beregningerne en unødig sekventialitet. Så det er ikke så meget et ønske om mere præcis beskrivelse af flow, men snarere et ønske om, at programmører ikke bliver nødt til at overspecificere dette flow.

I et turingkomplet sprog er det formelt set umuligt for en analyse at se, hvilke dele af en specificeret sekventialitet, der rent faktisk er nødvendig. Så hvis man overspecificerer dette, taber man potentiel parallelitet.

Så jeg så gerne, at det skulle kræve mere indsats for programmøren at pålægge en sekventialitet end ikke at gøre det. Dermed reduceres risikoen for, at sekventialiteten overspecificeres.

  • 0
  • 0
#12 Deleted User

I et turingkomplet sprog er det formelt set umuligt for en analyse at se, hvilke dele af en specificeret sekventialitet, der rent faktisk er nødvendig. Så hvis man overspecificerer dette, taber man potentiel parallelitet.

Så jeg så gerne, at det skulle kræve mere indsats for programmøren at pålægge en sekventialitet end ikke at gøre det. Dermed reduceres risikoen for, at sekventialiteten overspecificeres.

At muliggøre parallelisme gør også programmet mere overskueligt - et naturligt parallelt problem, er mest overskueligt, hvis det beskrives parallelt.

Men, at gøre hele kodningen parallelt, tror jeg ikke er løsningen. Programmet, skal kunne indeholde både parallele og sekventielle dele - og compileren, må gerne kunne gøre sekventielt beskrevede dele parallelle, i den grad det er muligt. Naturligvis findes der eksempler på problemer, der ikke lader sig parallelisere, men i langt de fleste tilfælde, vil computeren kunne finde andre opgaver senere, der så kan udføres.

  • 0
  • 0
#13 Deleted User

Det her er naturligvis løgn. Der findes en klasse af problemer, de "inherently serial problems", som netop er umulige at lave parallelle.

Det er altid muligt, at omsætte en sekventiel beskrivelse, til parallele processer, der kommunikerer. Problemet er, at der kan opstå en låsning, mellem disse processer, således at problemet ikke kan udføres bedre end sekventielt. I nogle tilfælde, kan der løses op for en sådan låsning, f.eks. kan løkker foldes ud. I nogle tilfælde, kan en låsning "løses", og medføre programmet kan fortsætte, eller paralleliseres, fordi at nogle oplysninger dukker op. Som eksempel, vil skrivning til et array, hvor index er ukendt, medføre låsning, hvor ingen processer kan bruge arrayet, da enhver addresse kan få modificeret indhold. Hvis programmet kan regne index ud først, låser dette måske op for en parallelisering. I nogle tilfælde, kan compileren måske vurdere indexets grænser - f.eks. hvis en betingelse skærer muligheden bort, for værdier under, eller over en vis grænse. Det, at kende addressen som der skrives på, indenfor et interval, muliggør måske opgaven "løses", og der kan udføres parallele processer samtidigt.

Selvom enhver opgave, kan omskrives til parallele processer, er det ikke altid en fordel - afhængigheden af data mellem processerne, og låsning, medfører ofte at opgaven løses langsommere. Derfor, er det mindst ligeså vigtigt, at kunne undlade at parallelisere - eller tage en parallelisering, hvor der er låsninger, og analysere disse, så det gøres til et sekventielt program. Ved sekventialiseringen, kan tages hensyn til låsningerne, og derved udføres det langt mere optimalt, end hvis et kompliceret system skal finde ud af, hvilke processer der kan udføres, og hvilke der ikke kan. Det kan være en fordel, når det skal analyseres, at først gøre hele opgaven flow-baseret, og dermed måske parallel hvis der ikke er låsninger, og så bagefter gå tilbage igen. Ved denne process, forsvinder den indtastede rækkefølge, og resultatet afhænger dermed kun af opgaven. Alligevel, er funktionen veldeffineret, og udfra funktionen, er resultatet som tidligere. Analysen muliggør, at vi kan dele en opgave op, f.eks. efter hvilke dele der leverer et bestemt resultat - det kan være grænser for en løkke, som måske medfører låsning, og hvor at kende grænserne, vil være med til at låse problemet op. Eller, det kan være et output, til en hardwareenhed, eller skærm, hvor vi ønsker at kunne tidsoptimere, således dette output kommer først. Flow analysen muliggør, at vi kan lade automatikken analysere koden, og levere et svar til tiden, og at vi kan prioritere vores problemstillinger, således vi har mulighed, for at opprioritere udførslen af de processer, der låser et problem op, og medfører yderligere parallelisering. Der er eksempler på, at dele af en opgave helt kan undgå at blive udført, fordi resultatet ikke bruges - så her kan man måske omprioritere opgaven, så man først finder ud af, om data bruges, og undlade at udføre de processer, der ikke behøves anvendt, når data f.eks. nulstilles, eller ikke anvendes.

Prioriteringen af processerne, kan også bruges til at give brugeren en bedre oplevelse - f.eks. optimere så svartiden på en handling minimeres, og derved få computeren til at få hurtig responstid, på enten inputs, eller på forsinkelsen fra brug af tastatur/mus og til resultat på skærm.

Et andet eksempel, er middelforsinkelse, for at få en opgave udført. Er der mange opgaver, der fordeles ligeligt tidsligt, vil de alle tage lang tid. Udføres de i en fornuftig rækkefølge, vil det måske kunne optimeres til, at gå hurtigere i svartid.

Selvom vi måske derfor ikke reelt får et hurtigere program, ved at omskrive det til parallele processer, så kan det derfor godt ændre oplevelsen af koden, hvis vi på en måde, er i stand til at bruge vores omskrivning til noget.

På den anden side, er det også væsentligt, at omsætte en parallel beskrivelse, hvor der er afhængigheder, eller låsninger, til en sekventiel beskrivelse, der har taget højde for disse problematikker - for en sådan sekventialisering, vil normalt altid udføres mere optimalt, end et parallelt system, med et kompleks system til styring af låsning mellem processer. Et program i rækkefølge - eventuelt beskrevet som VLIW, er det som behandles bedst af CPU'en, af cache, og af computerens arkitektur. Man har forsøgt, at lave computere, der var rent dataflow baseret, men de performerede langt ringere for sekventielle opgaver, end en sekventiel processor. Det bedste, er normalt at kombinere de to modeller, og lade automatikken afgøre, hvordan problemet skal løses bedst, og i hvilke portioner og programstumper, at opgaven skal opdeles, for at kunne både paralleliseres effektivt med de resourcer computeren tilbyder, og at kunne indgå i et hiraki, hvor der måske er låsninger, men anvendelsen af flere processer, medfører fleksibilitet i udførslen, og at tage hensyn til prioriteringer, der må opstå under programudførslen.

I mange typer eksempler, er ikke muligt at analysere alt statisk - men visse dele kan, og det er naturligvis bedst. I andre, vil det kræve for meget hukommelse, eller være umuligt, og gøres bedst meddens programmet køres. Det rigtige, er derfor naturligvis at gøre begge dele. Visse dele, af en analyse, kræver kendskab til processorens ledige resourcer, hardware mv. og er nødvendigt at gøre umiddelbart før programmet udføres, eller under udførslen. Det kan afhænge af, om processoren har nemt ved at udnytte dens parallele resourcer, og visse typer paralleliseringer, såsom udfoldning af løkker, vil måske først ske, når processoren ikke har andet at lave, eller hvis det kan analyseres har positiv betydning for et programs flow. I nogle tilfælde, kan det også bero på statistik, f.eks. brug af programmet tidligere.

Det er sjældent, at det ikke er muligt at opnå parallelisering, men naturligvis findes der opgaver, som ikke kan paralleliseres, da en beskrivelse som parallele processer der kommunikerer, vil indeholde et låsningsproblem.

  • 0
  • 0
#14 Ulrik Rasmussen

bla bla

Jeg forstår det ikke. Prøver du at sige Jesper imod? For du har lige brugt en fristil på at komme frem til det han brugte to sætninger på at beskrive: At der er en hel del problemer der ikke kan paralleliseres, fordi de af natur har dataafhængigheder der gør at de skal beregnes sekventielt.

Hvis du var et programmeringssprog havde du vist behov for en mere koncis syntaks ...

  • 0
  • 0
#15 Deleted User

Du kan sagtens omsætte sekventielle problemer til mange parallele processer. Problemet er, at der ved de typer problemer, som kun kan udføres sekventielt, opstår et låsningsproblem. Processerne taler sammen med køer, og de vil hele tiden vente på hinanden - så selvom der er flere parallele processer, så udføres måske reelt kun en enkelt, eller ganske få processer samtidigt. Det er korrekt, at låsningen mellem de parallele processer, kan medføre at der kun udføres éen process af gangen, og dermed at der reelt ikke sker en samtidig udførsel af opgaven. Dette kan også ske, hvis du opskriver opgaver som parallele, og de udveksler data. Denne udveksling, vil oftest medfører at processerne skal vente på hinanden, og derved står de skiftevis standby, så kun éen af processerne reelt kører. Er der mulighed for en umiddelbar parallelisme, fordi der er uafhængigheder i koden, så vil opgaven udføres parallelt. En parallel fremstilling, er dermed ikke bedre end en sekventiel fremstilling, og kan ikke udføre ikke paralleliserbare opgaver parallelt.

Du kan altså godt beskrive en opgave parallelt, uden at kunne opnå parallel udførsel af opgaverne.

Med andre ord, giver jeg Jesper ret - selvom opgaverne beskrives parallelt, så medfører låsningsproblemerne, at der reelt ikke altid sker en samtidig udførsel af indstruktioner.

I langt de fleste tilfælde, kan udføres et mindre antal indstruktioner samtidigt.

Hvis compileren er god nok, kan du opnå at en sekventiel beskrivelse, er ligeså god som en parallel, og at du ikke kan parallelisere opgaven manuelt, og opnå større ydelse. Måske tværtimod, da automatikken kan gøre optimeringer undervejs.

  • 0
  • 0
#16 Jesper Louis Andersen

Du kan altså godt beskrive en opgave parallelt, uden at kunne opnå parallel udførsel af opgaverne.

En af mine datalogiske kæphæste er at definere en forskel mellem samtidighed (Concurrency) og Parallellisme:

Samtidighed handler om at beskrive et program som flere uafhængige processer. Parallellisme handler om at afvikle et program således at flere processer kører på samme tid med det formål at opnå hurtigere eksekvering.

Lidt overvejelse fører til at de to begreber egentlig ikke har noget med hinanden at gøre. Der er masser af situationer hvor det er fordelagtigt at beskrive et program som samtidige processer, men derefter afvikle programmet på en sekventiel maskine. Omvendt er der masser af programmer der umiddelbart ville kunne parallelliseres uden hensyntagen til at programmet er beskrevet sekventielt. Kig for eksempel på det typiske PHP-script kørende i en webserver over en shared-nothing struktur, som sagtens kan udnytte flere CPU-kerner når flere brugere spørger efter data.

Jeg kan godt lide opdelingen fordi vi ser ud til at få kraftigt parallelle CPU'er med mange kerner. Men vi har i årevis beskrevet programmer med samtidighed. Problemet med parallel udførsel er at det ikke bare er nok at beskrive problemet samtidigt for at opnå en hastighedsforøgelse. Kommunikation er det overskyggende problem her.

  • 0
  • 0
#17 Deleted User

Problemet med parallel udførsel er at det ikke bare er nok at beskrive problemet samtidigt for at opnå en hastighedsforøgelse. Kommunikation er det overskyggende problem her.

Det er korrekt, at netop problemet ofte er at kunne udvælge flere processer, og udføre samtidigt. I nogle tilfælde, kan antallet af processer der kan vælges imellem, udvides ved at løse bestemte opgaver, og rækkefølgen som et concurrent program afvikles, kan således have betydning for, om opgaverne kan udføres parallelt. Mangles parallele opgaver, så er vigtigt at prioritere de opgaver op, som øger parallelismen. Så opgaven, ved udførsel af et concurrent program parallelt, er ikke bare at udvælge nogle tilfældige processer og udføre, blandt de mulige - men at vælge de rette. Det betyder også noget, for forsinkelsen i programmet, og for brugerens oplevelse.

En automatisk analyse, kan ikke udføre mirakler. I nogle tilfælde, er muligt at lave simple omskrivninger, der øger parallelismen.

Det jeg vil, var hellerikke at udføre mirakler - men at forklare, at der ikke er nogen fordel i, at programmere concurrent - for opgaven bliver ikke nødvendigvis mere parallel af det. Og, den bliver ikke nødvendigvis mindre parallel, ved at indtaste programmet sekventielt, da omsættelse fra sekventielt til concurrent, kan ske automatisk. I nogle sammenhænge, vil automatiske omsættelser fungere bedre, fordi de muliggør dynamisk omsættelse, når programmet udføres, meddens en manuel omsættelse, kan sammenlignes med en statisk oversættelse. Den statiske oversættelse, svarer til det, der kan opnås af compileren på oversættelsestidspunktet. I mange tilfælde, kan bedre oversættelser opnås under udførsel, når data kendes, og det kan være svært at overskue, og oversætte "statisk", selvom det gøres i hånden.

Om opgaver beskrives sekventielt, eller concurrent, bør ikke have nogen forskel på udførslen.

Beklager at jeg lod begreberne concurrent, og parallelt "flyde" sammen. I mange tilfælde oversættes concurrent som parallelt, når det oversættes til dansk, selvom det måske er lidt forkert.

  • 0
  • 0
Log ind eller Opret konto for at kommentere