Er en supercomputer for dyr? Så brug en superalgoritme

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?

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)

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.

Så vidt jeg ved, passer påstanden om, at det pga. superalgoritmer, at en mobiltelefon med en forholdsvis svag CPU er i stand til at streame video ikke helt.

I artiklen står der noget højere oppe, at superalgoritmen gør, at der beregnes, hvor det er mest optimalt at udføre arbejdet - altså hvilken cache (level1,2, ram, harddisk, registre) der skal bruges. Denne optimeringsudvælgelse får man ikke meget ud af i en mobiltelefon.

Jeg vil påstå, at grunden til at en mobiltelefon og andre små enheder kan lave så kraftfulde funktioner (som normalt ville kræve en noget større processor), skyldes at man designer chippen hardwaremæssigt anderledes - altså at man fysisk strømliner chippen til at lave en bestemt opgave. Denne teknik bruges også i f.eks. trådløse routere, hvor en speciel chip (eller et område i chippen) står for krypteringen. Denne chip er designet specielt til denne opgave, og kan på denne måde blive mindst 1000 gange så effektiv - se f.eks. følgende artikel her på siden: http://ing.dk/artikel/82562

Nu står der faktisk i artiklen, at en superalgoritme kan trække på mange forskellige metoder til at gøre tingene mere effektivt. IO-algoritmer som behandler "cache-optimering" var en type af superalgoritme, men der står også, at det er typen streamings-algoritmer, som gør det muligt for en mobiltelefon med en svag CPU at vise video. Derfor virker dit argument med cache og mobiltelefoner ikke.

Eller har jeg misforstået noget?

I fremtiden, tror jeg en stor del af computerens hastighed fremkommer ved brug af superalgorithmer. Det er ikke kun styring af cache - denne opgave er forholdsvis banal, og jeg tror ikke de store udfordringer ligger her. Måske virker den advanceret, men langtfra i forhold til det der kommer efter.

Det er muligt, at analysere normale enkelttrådede programer, til at blive parallele. At "udfolde" løkker, således indholdet opfattes parallelt. At prioritere disse millioner processer som programmet til sidst består af, og tage hensyn til læsetid fra harddisk, og accesstid på ram og dens cache, og hvor stor ønsket svartid der er på de forskellige tasks. Men man kan gå videre i at få computeren til at forstå hvad den laver, således den simpelthen selv får idéerne til optimeringer af softwaren, og med tiden vil de blive bedre til at optimere matematik og software, end mennesker er - ligesom skak computere har overgået os for længst, vil computernes forståelse for det software de udfører også overgå vores forstand. Om mange år, vil computerne arbejde på tværs over landegrænser via Internet, og en computer har måske løsningen til en opgave, fordi den kender den der har stillet opgaven, og dette kan så bruges af den der løser opgaven. Computerens software løses, og har en lavet en opgave, og en anden søger at løse opgaven, får computerne globalt set den samlede kunnen, og kan løse selv umulige opgaver. Ting som del og hers, er forholdsvis simpelt, og mange algorithmer som bobbelsort, kviksort osv. vil kunne omskrives automatisk til bedre algorithmer. I mange tilfælde, kan computeren selv finde en bedre algorithme, end den som kodes ind.

Det går et stykke tid inden ovenstående nås. Men det er muligt, og det er ikke specielt svær. Nogle har allerede nået lidt - men desvære er det kun tale om forbedringer i størrelsen 10% på computerrens hastighed, og dette er så lidt, at det er dårligere at offentliggøre, end et undlade. Offentliggørelse vil kunne føre til, at man siger det ikke er nogen fremtid i det.

Trin 1 er naturligvis, at få computerne til at "forstå" deres kode selv. Herefter, at virkeligt begynde at interessere sig for at "behandle kode" som matematik, i stedet for at kun udføre det. Først, er det strukturen, at opbygge grafer osv. som kan analyseres, og heraf også at tidsmæssigt optimere, f.eks. med hensyn til cache.

Senere vil algorithmerne nå mere. Mange programmer er så simple, at de kan løses indefra, og derved opstår en O(log(n)) afhængighed, af noget som før var O(n). Dette gør visse simple ting hurtigere, som mennesker også nemt kan se, man ofte ikke får gjort. Senere, vil den sikkert klare de normale kendte problemstillinger på baggrund af del og hersk, såsom bobbelsort mv. der automatisk omskrives af algorithmerne, efter de er analyseret og forstået. Her er det ikke kun bobbelsort, men også alt der i struktur minder om denne.

Fremtiden er programmer der gør programmer hurtigere. Det er det, som vil sætte computerne i stand til at blive intelligente - på sigt.

I første omgang, skal vi bort fra den normale traditionelle opfattelse, hvor man "arbejder og pukler", og går over til at "analysere og løse". Dette er essensen bag fremtidens computerkunst. Dette vil også sætte computerne i stand til at kompilere software til mange forskellige typer processorer, og kunne anvende disse optimalt, samt klare problemer som cache, og forsinkelser i forbindelse med harddisk. Alene det, at forstå et pentium maskinprogram, og analysere denne, så den automatisk implementeres i en anden processorakitekur, og eventuelt i en FPGA eller special cpu, er en opgave der åbentbart lader vente på sig.

Der er ingen tvivl om, at superalgorithmer er fremtiden. Og måske vil de blive så advanceret, at computerens "intelligens" gør vi kan indtaste matematiske problemer, som vi finder dem mest nemme at indtaste, og så kan computeren med deres databaser over løsning af programmre opnå at få langt bedre store O funktioner, end vi manuelt formår at opnå. Men det går nok nogen år før det opnås.