Publikation

Forskere foreslår løsning på 25 år gammel computergåde

Forskere fra Institut for Matematik og Datalogi har udviklet en opskrift på, hvordan parallelle beregninger i computere undgår at påvirke hinanden under visse omstændigheder. Dette er vigtigt for udviklingen af fremtidige computersystemer, herunder kunstig intelligens.

Af Majken Brahe Ellegaard Christensen, , 24-04-2019

Moderne menneskers hverdag er i høj grad påvirket af teknologi. I de senere år har teknologien gjort det muligt at udvikle computersystemer, der på grund af deres evne til at arbejde i parallelle spor kan give os svar på vores spørgsmål, næsten før vi har formuleret dem.

På trods af de mange anvendelser har de underliggende metoder bag skærmen stadig nogle udfordringer, herunder inden for computernetværk. For en af disse udfordringer foreslår forskere fra SDU nu en løsning sammen med deres videnskabelige kolleger i udlandet.

Teknologiske fremskridt på kort tid

Datalogi har udviklet sig i højt tempo i løbet af det sidste halve århundrede. I løbet af få årtier har udviklingen flyttet os fra skrivemaskiner til computere, der oprindeligt tillod os at skrive tekst og udføre simple spil, til nu at kunne genkende stemmer, ansigter og ligefrem udgøre væsener i form af kunstig intelligens.

En af de største fremskridt inden for datalogi har været udviklingen af systemer, der kan fungere parallelt. Oplysninger, som i tidligere computersystemer løb frem og tilbage af samme sti, kan nu rejse gennem mange forskellige stier på samme tid, samtidig med at der sikres et resultat, som er i overensstemmelse med ”envejs” -beregningen.

Denne måde at sende information i parallelle spor bruges ikke kun i supercomputere, men også i vores daglige netværk som på internettet, hvor du kan sende en besked til din nabo, mens din nabo samtidig skriver til dig eller til en anden. Alle modtager de rigtige meddelelser, fordi beskederne med parallelle spor ikke påvirker hinanden undervejs.

Problemer i den parallelle verden

Imidlertid er de mange anvendelser af parallelle beregninger ikke helt uden problemer. Der opstår problemer, når de oplysninger, der rejser gennem netværket, ikke er uafhængige. De valgte stier gennem netværket, og selv den mindste forskel i timing blandt dem, kan derfor bestemme, hvad resultatet er. Dette er et problem, fordi det muliggør at køre samme beregning to gange og få to forskellige resultater.

Det er i øjeblikket ikke muligt at forudsige alle mulige eksekveringsveje for et program, fordi antallet af mulige interaktioner mellem parallelle komponenter i et computersystem er meget højt - meget højere end det er muligt at arbejde med.

En måde at løse dette problem på er at udvikle principper og metoder, der kan hjælpe programmører med at tilgå denne kompleksitet. Lektor Fabrizio Montesi fra Institut for Matematik og Datalogi  (IMADA) har sammen med sine kolleger udviklet en ny tilgang til at løse dette problem, som opstår ved parallel transport af information.

Inspiration fra matematik giver ny metode

Den foreslåede løsning er at anvende en metode kaldet klassiske processer (CP). Forskerne har brugt CP og såkaldt lineær logik til at kunne beskrive begrebet "parallel eksekvering" som en logisk erklæring, dvs. en klart formuleret erklæring, der virker for alle mulige scenarier.

De navngav deres nye metode HCP, som står for Hypersequent Classical Processes. Det blev for første gang præsenteret på konferencen "Symposium om programmeringsprincipper" (POPL 2019) i Lissabon, Portugal. Det er 46. gang konferencen blev afholdt, da den fandt sted i januar i år. Studiet tilbydes via åben adgang fra ACM's Proceedings i Programmeringssprog og kan læses her.

Studiet blev lavet af lektor Fabrizio Montesi fra Institut for Matematik og Datalogi på SDU sammen med postdoc Marco Peressotti og deres kollega, Wen Kokke fra Edinburgh University.