Moores Lov i nyt lys: Software betyder mere end hardware

Optimeret software giver større performanceboost end hurtigere processorer. Det viser ny undersøgelse.

Software slår hardware med flere længder, når det gælder forbedringer af performance. Optimerede softwarealgoritmer overgår nemlig fordelene ved hurtigere processorer.

Det slår en uafhængig undersøgelse, lavet af teknologi- og videnskabsrådgivere til Det Hvide Hus i Washington, fast, ifølge New York Times.

I undersøgelsen har man blandt andet taget udgangspunkt i en benchmarktest, der strækker sig over et femtenårigt forløb. Over den periode har hastigheden for en given udregning forbedret sig med en faktor på mere end 43 millioner.

Ifølge den tyske forsker og matematiker Martin Grotschel, som deltog i undersøgelsen, så har langt størstedelen af det tal at gøre med softwareoptimeringer.

Ud fra det totale tal på 43 millioner, så har en faktor på omkring 1.000 sin forklaring i forbedringer af processorer, mens den resterende faktor på 43.000, har at gøre med optimeringer af softwarealgoritmer.

Moores Lov er opkaldt efter Intel-medstifteren Gordon Moore, der tilbage i 1965 forudsagde, at processorkraften ville fordobles for hvert halvandet år. En forudsigelse, der har holdt stik indtil videre.

Der findes imidlertid ingen lignende 'lov' for softwareperformance. Og undersøgelsen nævner da også, at en sådan lov vil være for svær at definere.

Opdateret 10:45: Gordon Moores navn rettet.

Tips og korrekturforslag til denne historie sendes til tip@version2.dk
Kommentarer (32)
sortSortér kommentarer
  • Ældste først
  • Nyeste først
  • Bedste først
Hans-Kristian Bjerregaard

Præcis (omend jeg nok ville skrive O(f(n)) da du ellers antyder at det kun gælder for lineære problemer).

Men det er da rart at der er nogen der har ville bruge tid på at vise at en maskines hastighed ikke er den dominerende faktor hvis den ikke bruges optimalt.

  • 0
  • 0
Jesper Kristensen

Når nu i har alle disse fine tal, kunne i så ikke lige fortælle hvilken test det tal kommer fra? Som i så rigtigt skriver til sidst man man ikke definere forbedringen for "software generelt", det kommer an på hvilket algoritmisk problem man ser på.

Kilden (NYT) i refererer til er noget mere præcise end V2, og siger at testen omhandler "production-planning". Men det siger stadig intet.

NYTs kilde er så noget mere præcis og skriver "a benchmark production planning model solved using linear programming".

Altså stammer de 43 millioner fra Linear Programming-problemet. Det kunne V2 godt lige have skrevet.

  • 0
  • 0
Allan Ebdrup Blogger

Hvis det minder om det Linear Programming jeg havde på uni. Så er den teoretiske maksimale tidskompleksitet ikke forbedred (det kan den så vid jeg husker ikke, N/NP-hårdt). I steder har man fundet på alle mulige heuristikker der i specielle (almindelige) tilfælde forbedrer algoritmernes gennemløbstid.
Det vi havde på kurset var ihvertfald et væld af heuristikker som virkede i specialtilfælde. Alt i alt et ret specialiceret fag, og ikke lige et kursus jeg husker som specielt spændende. Det er heller ikke noget jeg har haft brug for i praksis.

Jeg tror også det ville være svært at optimere en algoritme som fx sortering eller noget andet almindeligt man bruger hver dag, med 43.000 gange, bare pga. bedre software. Så det gælder nok mest N/NP-hårde problemer.

  • 0
  • 0
Hans-Kristian Bjerregaard

I steder har man fundet på alle mulige heuristikker der i specielle (almindelige) tilfælde forbedrer algoritmernes gennemløbstid.

Ja, gode heuristikker er essentielle for stort set alt software. Hashing (dictonaries/associative arrays/set mm.) er jo bare heuristik der baserer sig på at hashværdien for en given række elementer er ligeligt fordelt over et vist udfaldsrum.

  • 0
  • 0
Jonas Høgh

Det er ikke helt korrekt, Allan. For det første er LP-problemet løsbart i polynomiel tid. For det andet er der sket forbedringer i tidskompleksiteten for algoritmerne, ikke blot heuristiske forbedringer. Fx nævner Wikipedia-artiklen om emnet, at de første polynomielle algoritmer fra 70'erne var O(n^4), men dette blev forbedret til O(n^3.5) i 80'erne.

  • 0
  • 0
Allan Ebdrup Blogger

Ja, jeg tænkte nok jeg var på dybt vand, men jeg tvivler stadig på at udsagnet om at forbedringer i software er vigtigere end hardware forbedringer holder i generelt.

  • 0
  • 0
Michael Jensen

Den rigtige compiler har også enorm betydning. Husker fra mine egne forsøg tilbage omkring 90, at hvis man programmerede i assembler i stedet for f.eks Pascal var hastigheds gevinsten en faktor 10-100. Selvfølgelig er compilere bedre i dag, men de er stadigvæk langt fra optimale.

  • 0
  • 0
Uffe Kousgaard

Jeg kan huske tilsvarende forsøg, da jeg fik min første turbopascal 3. Der var min assembler kun 2 gange hurtigere end pascal og så gad jeg ikke bruge mere tid på assembler. Gevinsten stod simpelthen ikke mål med indsatsen.

Selvfølgelig kan softwareforbedringer give store effekter, hvis udgangspunktet er dårligt nok. Softwaren kan også optimeres til den specifikke hardware, hvis man ved noget om level 1 cache, harddiskens cache eller lignende.

  • 0
  • 0
Flemming Hansen

At jeg ikke fatter meget af hvad folk skriver i denne tråd :-)

Men jeg husker de gamle C64/Amiga-dage hvor folk virkelig forstod at presse maskinerne til det yderste. Hvis man var lige så engageret i den slags i dag kunne vi have den ondeste hastighed på alt lige fra OS til diverse spil, og vi ville måske ikke behøve at købe CPU'er og grafikkort der kan varme det meste af huset op.

Men det ville jo gå ude over et kæmpe hardware-branche der nok ikke er interesseret i at computere pludselig får forlænget deres levetid.

  • 0
  • 0
Allan Ebdrup Blogger

Ja, gode heuristikker er essentielle for stort set alt software. Hashing (dictonaries/associative arrays/set mm.) er jo bare heuristik der baserer sig på at hashværdien for en given række elementer er ligeligt fordelt over et vist udfaldsrum.

Ja det er ikke for at forklejne gode heuristikker, det jeg mente var bare at LP er er ret specielt problem og det der gælder for hastighedsoptimering på netop dette problem gælder ikke generelt.
Hvis jeg kigger udelukkende på algoritmer, så er der ikke mange af de algoritmer jeg bruger til hverdag der er blevet forbedret indenfor de sidste mange år (sortering, mængde-operationer og måske lidt graf-algoritmer).
Men hvis jeg kigger på den software jeg benytter generelt, er der sket store forbedringer. fx eventloops i Node.js, NoSQL-databaser.

  • 0
  • 0
Troels Henriksen

Men tror du ikke at algoritmiske forbedringer også ligger til grund for mange af disse programmer? Algoritmer er ikke bare quicksort. Derudover synes jeg at oplægget til denne artikel er mærkværdigt - at "software betyder mere end hardware" afhænger vel af om den oprindelige software var velskrevet? Man kan dog argumentere for det ud fra et upraktisk teoretisk synspunkt, idet hardwarehastighed stiger med polynomiel hast, hvor du derimod nemt kan skrive et dårligt program hvis køretid kan forbedres eksponentielt ved omskrivning. Nyttighedsværdien af denne opdagelse overlades til læseren.

  • 0
  • 0
Torben Mogensen Blogger

Den rigtige compiler har også enorm betydning. Husker fra mine egne forsøg tilbage omkring 90, at hvis man programmerede i assembler i stedet for f.eks Pascal var hastigheds gevinsten en faktor 10-100. Selvfølgelig er compilere bedre i dag, men de er stadigvæk langt fra optimale.

Compileren betyder ganske rigtigt en del, men en forbedret compiler kan kun give en konstant faktor forbedring, hvor en bedre algoritme f.eks. kan nedsætte fra kvadratisk til lineær tid eller sågar fra eksponentiel tid til polynomisk tid.

NP-hårde problemer har (såvidt vi ved) eksponentiel køretid i værste tilfælde uansetvalg af algoritme, men det giver en hel del at nedsætte køretid fra f.eks. fra 2^n til 1.9^n, og selv om det ikke altid er muligt at forbedre værstetilfældet, så kan nye algoritmer ofte nedsætte køretiden for de fleste realistiske tilfælde.

I fremtiden bliver forbedret software endnu mere vigtigt, for nye processorer bliver ikke væsentligt hurtigere til at udføre sekventiel kode, så for at udnytte den ekstra maskinkraft, skal man lave sine programmer massivt parallelle. Så den tid er forbi, hvor man "bare" kunne købe en ny og hurtigere maskine til sine gamle programmer, hvis datamængderne voksede så meget, at den gamle maskine var for langsom.

Det er naivt at tro, at compileren kan parallelisere ens gamle programmer, så man slipper ikke for at lave ny software. Men heri ligger også en stor potentiel gevinst: Vi kan måske med tiden slippe af med forældede sprog som COBOl og C, når folk ikke bare kan flytte deres programmer til nye maskiner for at få dem til at køre hurtigere. Hvis der skal laves ny kode, kan man ligeså godt gøre det i et moderne sprog i stedet for at forsøge at parallelisere programmer i sprog, der slet ikke er gearet til parallelisme.

Man kan sammenlige med overgangen fra hestevogne til motorkøretøjer: I starten lignede motorkøretøjerne hestevognene, for det var hvad man kendte. Men efterhånden fandt man på løsninger, der passede bedre til motorkøretøjer, og en moderne bil ligner ikke en hestevogn ret meget (udover, at den har fire hjul).

På samme måde ser vi nu sprog til parallelisme, der ligner COBOL og C, for det er hvad programmørerne kender. Men med tiden vil de parallelle sprog ændre sig til noget helt anderledes, og man vil se på de nuværende parallelle sprog med samme overbærende smil, som vi i dag ser på gamle motorkøretøjer med kuskesæder og lignende levn fra hestevogne.

  • 0
  • 0
Benny Olsen

Der har gennem tiden været mange forsøg på at bevise det modsatte, men hver gang software folkene har optimeret noget programel, så har de tilføjet en tilsvarende mængde fejl, og inden programmellet er afluset så er hastigheden på en ny computer til samme pris steget mere end end programfolkene kunne opnå med deres optimering.

Den nye computer løser alle opgaver hurtigere, ikke kun dem som softwarefolket har fokus på.

  • 0
  • 0
Torben Mogensen Blogger

Den nye computer løser alle opgaver hurtigere, ikke kun dem som softwarefolket har fokus på.

Det har ganske rigtigt været tilfældet i de sidste 30 år, men nye computere bliver ikke markant hurtigere til at køre sekventielle programmer, og parallelisering kræver omkodning. Så du slipper ikke for at have softwarefolk omkring, hvis du vil have dine programmer til at køre væsentligt hurtigere på din nye computer -- med mindre, at de allerede er kodet til at kunne bruge et ubegrænset antal processorkerner.

  • 0
  • 0
Allan Ebdrup Blogger

Det har ganske rigtigt været tilfældet i de sidste 30 år, men nye computere bliver ikke markant hurtigere til at køre sekventielle programmer, og parallelisering kræver omkodning.

I princippet har du ret. Men i praksis er der en helt række problemer der ikke kræver omkodning.
Alle systemer (fx webservere, databaser) hvor du har mange samtidige brugere der benytter samme system, kan allerede gøre brug af flere processorkerner.
En stor del af de systemer der allerede i dag presser grænsen for hvad man kan på een processorkerne er allerede skrevet til at kunne køre parallelt (hvis det er nødvendigt), der vil man måske nærmere kunne sige at det efterhånden slet ikke var nødvendigt at køre dem parallelt, fordi processorne er blevet så meget hurtigere ;-)
Jeg har ikke set mange eksempler på at omkodning har været nødvendig. Jo i billedbehandling, raytracing, CAD, mpg3 encoding, videoencoding. Men jeg tror ikke der kommer en hel ny bølge af omskrivninger til software der kan køre parallelt, som du antyder med din hestevogn/bil analogi.

  • 0
  • 0
Jesper Louis Andersen

Den nye computer løser alle opgaver hurtigere, ikke kun dem som softwarefolket har fokus på.

Umiddelbart er det en unuanceret antagelse efter min mening. Der er visse problemtyper hvor din eneste chance er at lave softwaren om, deriblandt alle problemer der ligger i klassen af NP-hårde problemer f.eks: Hvis du kan løse en probleminstans af størrelse 100 på 24 timer, så vil en dobbelt så hurtig computer sætte dig i stand til at knække et problem med 101 i størrelse. Det er ikke ualmindeligt at softwareoptimering lader dig løse en instans af størrelsen 10000 på samme tid.

Omvendt er der andre problemtyper hvor vi er tæt på at have den optimalt hurtigste løsningsmetode - og der kan det formentlig bedre antages at hardwaren vil skabe hastighedsforøgelsen. Men hardwaren er dels bundet af at memorybåndbredden "kun" stiger med 7% per år, ca. Det er en fordobling på omkring 10 år, så for mange problemer hjælper meget mindre end man tror med en hurtigere computer (parallel eller ej).

  • 0
  • 0
Jesper Louis Andersen

Alle systemer (fx webservere, databaser) hvor du har mange samtidige brugere der benytter samme system, kan allerede gøre brug af flere processorkerner.

Det virker kun fordi du har shared-nothing og dermed har kodet dit program til at være parallelt. Problemtypen er af en karakter, hvor du har så mange brugere at du stort set kan give hver bruger sin egen processorcore og du er done. Men der findes også problemer hvor det ikke er muligt :)

  • 0
  • 0
Michael Jensen

Selv en faktor 2 var ikke dårligt dengang. Det kunne gøre maskinen hurtig nok til ens spil eller lignende ;) Og hvis det endelig skal være er det kun de inderste løkker som man virkelig fik noget ud af at optimere. Et gæt vil være at et program bruger 99% af tiden i 1% af koden. Eller endnu mere.

i dag er compileren/programmøren er nødt til at vide noget om processoren/infrastrukturen koden skal køre på. PHKs Varnish projekt er et godt eksempel på det. Infrastrukturen er klart det vigtigste i denne sammenhæng (med mindre alt kan ligge i cache om bord på CPUen). For normalt laver en CPU ikke noget i langt over halvdelen af tiden. Men venter på data.

  • 0
  • 0
Jonas Høgh

Tag et kig på Riak, eller Google's BigTable. Du smider ganske vist consistency-garantien, men derimod vinder du shared-nothing (essentielt set).

Undskyld, jeg formulerede mig uklart. Jeg mente blot, at et ganske alm. RDBMS sagtens kan være "multicore-egnet" (som Allan beskrev det) uden at det er shared-nothing.

  • 0
  • 0
Bjarke Walling

(...) Hvis jeg kigger udelukkende på algoritmer, så er der ikke mange af de algoritmer jeg bruger til hverdag der er blevet forbedret indenfor de sidste mange år (sortering, mængde-operationer og måske lidt graf-algoritmer). (...)

Apropos sortering, så kig på den nye implementering af C++'s standard library libc++, en del af LLVM-projektet. De har optimeret sortering i forhold til den rimelig udbredte libstdc++, se slide 54 på http://www.llvm.org/devmtg/2010-11/Hinnant-libcxx.pdf … de taber en lille smule hastighed for helt tilfældige data, men vinder i mange andre situationer. Igen handler det om heuristik.

  • 0
  • 0
Allan Ebdrup Blogger

Man kunne godt frygte at det er lidt som at vælge den optimale pivot i quicksort. På papiret er tidskompleksiteten bedre, men i praksis kan det ikke betale sig og man vælger bare et tilfældigt pivot i stedet. Det er een ting at nogle få testcases kører hurtigere, men i praksis, spiller det også ind hvor meget algoritmen fyller i processor cache, og hvad initieringen koster, hvis man har mange små sorteringer, og 1000 andre scenarier. Hvis det virkeligt er bedre at ens sorteringsalgoritme genkender patterns, vil det sprede sig til andre implementatione. Personligt tvivler jeg på at det kommer til at ske. Men vi får se...

  • 0
  • 0
Lars Ole Belhage

Denne 1. kommentar var vel den mest sigende!

Hvis man ikke har lært om O(n) eller Ackermann har man ikke en chance!

Det meste af det software vi er tvunget til at bruge er lavet af folk som ikke havde det i fokus (fx troede de at alt kunne løses i 640kbyte ram ;) )
Eller de havde andre forældede flaskehalse i tankerne (fx relationelle database)

Selvfølgeligt er tankesættet (algoritmen) det vigtigste for performance - og sproget vi udtrykker os i komplet ligegyldigt! (hardware, vhdl, fortran, c, erlang - eller et af Torbens(?) favorit funktionsprogrammeringssprog)

  • 0
  • 0
Mark Gjøl

Moores Lov er opkaldt efter Intel-medstifteren Gordon Moore, der tilbage i 1965 forudsagde, at processorkraften ville fordobles for hvert halvandet år

Well, antallet af transistorer ville fordobles hvert andet år, ikke ydeevne.

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