Er en supercomputer for dyr? Så brug en superalgoritme
more_vert
close
close

Vores nyhedsbreve

close
Ved at tilmelde dig accepterer du vores Brugerbetingelser og accepterer, at Mediehuset Ingeniøren og IDA-gruppen lejlighedsvis kan kontakte dig om arrangementer, analyser, nyheder, tilbud mm via telefon, SMS og email. I nyhedsbreve og mails fra Mediehuset Ingeniøren kan findes markedsføring fra samarbejdspartnere.

Er en supercomputer for dyr? Så brug en superalgoritme

Super-algoritmer er et brugbart alternativ til supercomputere, mener forskerne på det nyoprettede forskningscenter Madalgo (Center for Massive Data Algorithmics), ved Datalogisk Institut, Århus Universitet.

En supercomputer har tusinder af CPU'er og terabytes af dynamisk hukommelse. Den arbejder måske flere tusind gange hurtigere end den hurtigste pc. Kan en nok så snedig algoritme virkelig erstatte sådanne monster-kræfter?

»Ja, det kan den. I visse situationer kan vi sætte farten op med en million gange, hvis vi tænker os om,« siger professor Lars Arge, der leder forskningscentret.

Lars Arge, som han er fotograferet på algoritmeforskernes egen hjemmeside.

Han var i en årrække professor ved Duke University i USA, og her hjalp han for eksempel de lokale forskere med at optimere en algoritme, som blev brugt til at kortlægge vands bevægelser i terrænet. Forskernes oprindelige beregning tog tre uger per datakørsel, men med en bedre algoritme kom de ned på to timer.

Brug alle data, der læses på harddisken

Madalgo blev startet i marts i år og rummer ifølge lederens udsagn en håndfuld af verdens skrappeste algoritme-professorer, dels fra MIT (Massachusetts Institute of Technology), dels fra Max Planck Institute for Informatics (MPI).

Lars Arges eget speciale er I/O-algoritmer, som vedrørende data, der suser ind og ud af computeren - eller ind og ud af processoren, for den sags skyld. I/O-algoritmer er et af centrets fire arbejdsområder.

»Der er virkelig meget at hente her. Hvis for eksempel en beregning skal bruge nogle data, som ikke findes i den dynamiske hukommelse (DRAM), så vil computeren hente en klump data fra harddisken. Men harddisken er en million gange langsommere end DRAM, så hver udflugt til harddisken koster virkelig meget tid.,« forklarer Lars Arge.

Desuden læser computeren data fra en harddisk i store blokke ad gangen. Mange af disse data skal ikke bruges. Så hvis forskerne også kan udvikle algoritmen til at udvælge fornuftigt, så den i hvert hug får flere brugbare data, er der vundet yderligere store mængder tid.

Helt det samme forhold gør sig gældende, hvis der ikke er data nok i processorens Level2-cache, som er endnu hurtigere end DRAM - og Level1-cache er hurtig i forhold til Level2. Og registrene er hurtige i forhold til Level1 cache.

»Meningen er, at algoritmer skal designes, så de er optimale, uanset hvilken cache vi taler om,« fortæller Lars Arge han.

Det er Madalgos andet ben.

Video på mobilen kun muligt med superalgoritmer

Det tredje er streaming-algoritmer, og det handler ikke nødvendigvis om grafik.

»Streaming forekommer, når datamængderne er så store, at der ikke er tid til at hente dem mere end én gang. Det er for eksempel teleselskabet AT&T's statusmeddelelser fra telefonroutere i det store telefonnet. De ankommer løbende i enorme mængder og fortæller om routernes øjeblikkelige tilstand. De er kun vigtige i øjeblikket, og ti sekunder senere er de ligegyldige,« siger Lars Arge.

Man kan også nævne det faktum, at mobiltelefoner med små CPU'er er i stand til at streame video. Det lader sig kun gøre på grund af superalgoritmer.

Beviset for den bedste metode

Madalgos fjerde ben gælder at få algoritmerne til at virke i praksis og demonstrere, at der kommer noget ud af anstrengelserne.

Forskningen på Madalgo sker på to fronter: De øvre og de nedre grænser.

De øvre grænser handler om at vise, at en algoritme kan køre hurtigere.

»Og blot man har fundet én metode, der er hurtigere, så er det jo bevist,« påpeger Lars Arge.

De nedre grænser gælder om at bevise, at der ikke findes metoder, der er bedre end den bedste, man kender.

»Det er praktisk, for så behøver man ikke kaste flere ressourcer efter den. Det kan sagtens lade sig gøre, og det er en stor disciplin inden for det, vi laver. Men det er vanskeligere, for så skal man jo have alle tænkelige metoder dækket ind,« forklarer algoritme-professoren.

Madalgo har fået 30 millioner kroner fra Danmarks Grundforskningsfond og dertil kommer 30 millioner kroner fra andre kilder. 30 millioner kroner svarer omtrent til prisen på en moderne supercomputer.

Dokumentation

Madalgos hjemmeside

Det er jo klart at jo flere timer man bruger på algoritmen jo bedre bliver den, det er da logik for burhøns. Jeg har brugt computere til at løse rigtigt mange tekniske udfordringer. Når jeg støder ind i en teknisk forhindring hvor jeg mener computeren er et muligt værktøj er min første tanke altid:

Kan man løse det her med brute force??

Det er fordi brute force algoritmer som regel er ufatteligt nemme og hurtige at kode fordi alle mulighederne blot skal afprøves. Så hvorfor skal jeg bruge kostbar arbejdstid på at opfinde noget smart, når jeg kan lade PC'en finde løsningen hurtigere medens jeg laver noget andet?

  • 0
  • 0

Hvorfor bruge tid...? Til daglig laver jeg CFD vha koden fluent, og hvis det kunne komme til at gå en million gange hurtigere, ville det da være meget dejligt :o)

  • 0
  • 0

Hvis de computer messige problemer som du tumler med kan løses med brute force = exhaustive search, så kan det ikke være ret store problemer. Der er mange ting som ikke ville kunne løses inden for universets levetid på den måde. Den eneste slags problemer man vil løse på den måde er dem hvor man er tvunget til det. F.eks. NP complete problemer.

Tag f.eks. folding@home som er et distribueret netværk som udgør en supercomputer. Der er mange mennesker der stiller deres computerkraft til rådighed for folding@home.

Hvis så en lille gruppe på 5 mand bruger lad os sige 500 mandetimer på at lave folding algoritmen 5 gange hurtigere, ja så er de 500 timer da hurtigt tjent hjem. For slet ikke at tale om hvis de kunne få den til at køre med en bedre kompleksitet.

  • 0
  • 0