Aarhus University Seal

Regnekraften fra et grafikkort finder den billigste pris på de hoteller, der ligger tættest på strandkanten

Det koster for meget computerkraft og tager for lang tid, er nogle af årsagerne til at vi ikke får den billigste pris, når vi leder efter hotellet så tæt på strandkanten, som muligt. Det viser Kenneth Sejdenfaden Bøghs forskning, der har udviklet en metode, der ved hjælp af et grafikkort, giver de bedste tradeoffs eller den bedste afbalancering af søgninger.

af Sebastian von Cappelen

Hvis vi leder efter et hotel i en badeby, vil vi ofte gerne minimere afstanden til stranden og samtidig finde det billigste hotel tættest på stranden. De hoteller, der ligger et stenkast fra bølgeskvulpene, har en tendens til at være dyrest. Det er sjældent muligt at finde en perfekt afvejning mellem disse faktorer, som passer alle mennesker, da det er forskelligt fra person til person, hvor meget man er villig til at give for et hotel, i forhold til, hvor tæt det er på stranden. Det ville dog være en fordel, hvis man kunne undgå at se på meget dyre hoteller, som ligger langt fra stranden. Skyline-problemet forsøger at gøre dette på den mest effektive måde. https://en.wikipedia.org/wiki/Pareto_efficiency#Pareto_frontier

 

- I dag er det ofte prisen, der er den styrende faktor i søgninger på nettet. Når du laver søgningen og siger, at det skal være inden for en bestemt ramme, så får du en stor mængde hoteller, som du skal sortere i manuelt. Det er en afvejning, som folk bruger timer på hver gang, de søger på nettet, fortæller Kenneth Sejdenfaden Bøgh, der er ph.d.-studerende på Institut for datalogi på Aarhus Universitet. Han har skrevet kandidatspeciale om problemstillingen, og specialet blev sidste år nomineret til Specialeprisen af Dansk Selskab for Datalogi.

 

Det er en enorm kompleks beregning, hvor der fx skal tages højde for om der er balkon, antal værelser, om der er pool eller andre ting. Den samme slags afvejning gælder, hvis man leder efter en brugt bil, der har kørt færrest kilometer til den bedste pris. 

 

Det er den subjektive vurdering, der er styrende, når mennesker selv sorterer i søgeresultater, forklarer han, og for mange kan det blive uoverskueligt, hvis der er for mange valgmuligheder. Hvis vi kunne få computeren til først at fjerne alle de resultater der, objektivt set, ikke er interessante, ville det være lettere at finde det man søger. Dog er det meget dyrt at få computeren til at lave denne vurdering, da alle hoteller eller biler først skal sammenlignes. Dette koster enten for meget computerkraft eller også vil det tage for lang tid.

 

Og i et onlinesystem, hvor der er en bruger, der sidder og venter, så vil det betyde, at man skal vente i minutter. Det er der ingen af de store databasefirmaer som Google, Oracle eller IBM, der vil acceptere og derfor anvendes denne type søgning ikke endnu.

 

Men sådan behøver det ikke være, forklarer Kenneth Sejdenfaden Bøgh. Han har i sit speciale udviklet en metode, der ved hjælp af grafikkort, finder alle de bedste tradeoffs, altså afbalancering imellem pris og det man efterspørger.

 

- Vi fjerner alt det uinteressante, hvilket vil sige, at vi fjerner alle hoteller, som bliver slået på både pris og afstanden til stranden af et andet hotel. Det er et relativt simpelt problem, men det er dyrt at beregne. Ideen er, at hver gang du har et nyt hotel eller en bil, så skal du enten finde et andet punkt i datasættet, som er bedre, eller sammenligne det nye datapunkt med alle de eksisterende. I værste tilfælde, hvor du ikke kan fjerne nogle punkter, skal du sammenligne alle hoteller eller biler med alle andre. Det tager lang tid, fortæller han.

 

Han har i sit speciale anvendt et grafikkort, som udover at kunne vise grafik i meget høj opløsning, også er en kraftig computer i sig selv. Den er over ti gange så kraftig som en almindelig computer. Samtidig er prisen meget lav i forhold til en computer.

 

- Udfordringen med grafikkortet er, at det er en meget specialiseret computer, der ikke er særlig intelligent. Den er bygget til at lave millioner af uafhængige beregninger parallelt. Den kan ikke både lægge to tal sammen og trække fra på en gang. Vi skal derfor, og det er det, som mit speciale har handlet om, undgå at lave forskellige beregninger på en gang og i stedet parallelt lave den samme beregning hver gang, men på forskellig data, fortæller han.

 

Skyline-problemet har været undersøgt i over ti år og der er udgivet omkring 1600 artikler om emnet.

 

- Jeg er meget stolt over at komme i finalen. Det er en kæmpe ære. Det er også lidt sjovt, fordi jeg har været tutor for de to fra Aarhus, der vandt, så det er også fedt, at vi har fået prisen tilbage til Aarhus, siger han.

 

Fra seks timer til otte minutter

Han er i øjeblikket i gang med sin ph.d. og her arbejder han videre med at bruge grafikkortet til at løse beregnings-intensive problemer. Sammen med iNANO er han gået i gang med at analysere CT-scanninger på knogler.

 

- Målet er at finde ud af, hvordan celler snakker sammen inde i knoglerne. De har titusinder af billeder liggende af CT-scanninger af knogler, men de har aldrig været analyseret i deres helhed. Det skyldes blandt andet, at der har manglet software der var effektiv nok, så derfor ser vi på, om vi kan gøre det mere effektivt og få et komplet billede af, hvordan en knogle opfører sig. Det går den rigtige vej, da en beregning, der tidligere tog seks timer, nu tager otte minutter, forklarer han.

 

Se hans speciale her