Hukommelsesfejl skal løses med algoritmer
En lille fejl kan gøre din søgning på Google forgæves. Men nu vil to forskere fra Aarhus Universitet med såkaldte fejltolerante algoritmer komme fejlene i forkøbet.

Gerth Stølting Brodal med en gammeldags telefonbog. Nu er han med til at udvikle nye algoritmer, der kan søge i telefonbøger selv om der er fejl i dem. (Foto: Jesper Voldgaard)

Gerth Stølting Brodal med en gammeldags telefonbog. Nu er han med til at udvikle nye algoritmer, der kan søge i telefonbøger selv om der er fejl i dem. (Foto: Jesper Voldgaard)

Fart er ikke alt. Hvad hjælper det, at en supersmart algoritme hjælper en computer til at regne superhurtigt, hvis en pludselig fejl i hukommelsen får computeren til at gå ned med et brag?

Det vil professor Lars Arge (ph.d) og lektor Gerth Stølting Brodal (ph.d.) fra Datalogisk Institut på Aarhus Universitet forsøge at forhindre ved at udvikle såkaldte fejltolerante algoritmer - altså algoritmer, der bliver ved med at køre, selv om der er fejl. Begge er tilknyttet det datalogiske grundforskningscenter Madalgo (Massive Data Algorithmics), hvor Lars Arge er centrets leder.

Fejl i hukommelsen udmønter sig ved, at processoren ikke får de værdier tilbage fra hukommelsen (RAM'en), som den skrev i den. En sådan pludselig fejl kan forårsages af baggrundsstrålingen.

Når en meget energirig ladet partikel passerer gennem en RAM-celle, kan den efterlade et spor af elektrisk ladning ved sammenstød med atomerne i mikrochippen, og denne ladning kan være stor nok til at ændre en bit fra 0 til 1 eller omvendt. Sådan en hændelse kaldes Single Event Upset.

Fejl ødelægger søgning

Fakta

VIDSTE DU

En algoritme er en nøje og utvetydig opskrift på, hvordan en opgave skal løses skridt for skridt.

For en almindelig familie-pc er risikoen til at overse. Den kører ikke så længe ad gangen, så hukommelsen er ret stabil. Men hvis man har millioner af maskiner, der kører hele tiden - som f.eks. Google, er risikoen for fejl i hukommelsen meget større. Risikoen bliver også større, hvis man bruger billig hukommelse.

»Hvis der er en fejl i hukommelsen, kan det ødelægge f.eks. en binær søgning. Med fejltolerante algoritmer i binære søgninger nøjes man ikke med at slå op midt i dataene. Man laver samtidig et eller flere redundante opslag og verificerer, at det, man tidligere fandt, er rigtigt,« forklarer Gerth Stølting Brodal.

Binære søgninger går ud på at lede efter et element i en gruppe sorterede data ved først at kigge på det midterste element og se, om det er større eller mindre end det element, der søges efter. Derefter kigger man på det midterste element i det delinterval, som elementet findes i, og så videre.

Christensen bli'r væk

Det svarer til at lede efter Christensen i en telefonbog.

Med fejltolerante algoritmer i binære søgninger nøjes man ikke med at slå op midt i dataene. Man laver samtidig et eller flere redundante opslag og verificerer, at det, man tidligere fandt, er rigtigt.

Gerth Stølting Brodal

Først slår man op cirka i midten af bogen ved f.eks. Jensen. Allerede dér ved man, at Christensen befinder sig i den første halvdel af bogen. Så slår man op i midten af den første halvdel ved Eriksen og ved så, at Christensen er i første fjerdedel af bogen. Så halverer man igen og finder Bruun, hvorfor Christensen må være i den følgende ottendedel af bogen. Sådan fortsætter man, til Christensen er fundet.

Men hvis der er en fejl i telefonbogen, så man i midten af den finder en Andersen, vil algoritmen lede efter Christensen i anden halvdel af bogen, selv om han er i første halvdel. Så finder man aldrig Christensen, og han må sidde og vente forgæves ved telefonen.

Er algoritmen fejltolerant nøjes man altså ikke med at slå op midt i bogen, man kigger flere steder på én gang for at sikre, at det første fund er korrekt. Er den ikke det, finder algoritmen selv ud af det og lokaliserer alligevel Christensen.

»Vi har teorien på plads og arbejder nu på at finde ud af, om det kan laves i praksis,« siger Lars Arge.

Lavet i samarbejde med Alexandra Instituttet.

Videnskab.dk Podcast

Lyt til vores seneste podcast herunder eller via en podcast-app på din smartphone.

Corona-tal

Videnskab.dk går i dybden med den seneste corona-forskning. Læs vores artikler i temaet her.

Hver dag opdaterer vi også de seneste tal.

Dyk ned i grafer om udviklingen i antal smittede, indlagte, døde og vaccinationer i Danmark og alle andre lande.

Ny video fra Tjek

Tjek er en YouTube-kanal om videnskab henvendt til unge.

Indholdet på kanalen bliver produceret af Videnskab.dk's videojournalister med samme journalistiske arbejdsgange, som bliver anvendt på Videnskab.dk.

Hej! Vi vil gerne fortælle dig lidt om os selv

Nu hvor du er nået helt herned på vores hjemmeside, er det vist på tide, at vi introducerer os.

Vi hedder Videnskab.dk, kom til verden i 2008 og er siden vokset til at blive Danmarks største videnskabsmedie med over en halv million brugere om måneden.

Vores uafhængige redaktion leverer dagligt gratis forskningsnyheder og andet prisvindende indhold, der med solidt afsæt i videnskabens verden forsøger at give dig aha-oplevelser og væbne dig mod misinformation.

Vores journalister fortæller historier om både kultur, astronomi, sundhed, klima, filosofi og al anden god videnskab indimellem - i form af artikler, podcasts, YouTube-videoer og indhold på sociale medier.

Vi stiller meget høje krav til, hvordan vi finder og laver vores historier. Vi har lavet et manifest med gode råd til at finde troværdig information, og vi modtog i 2021 en fornem pris for vores guide til god, kritisk videnskabsjournalistik.

Vores redaktion gør en dyd ud af at få uafhængige forskere til at bedømme betydningen af nye studier, og alle interviewede forskere citat- og faktatjekker vores artikler før publicering.

Hvis du går rundt og undrer dig over stort eller småt, vil vi elske at høre fra dig og forsøge at give dig svar med forskernes hjælp. Send bare dit spørgsmål til vores brevkasse Spørg Videnskaben.

Vi håber, at du vil følge med i forskningens forunderlige opdagelser her på Videnskab.dk.

Få et af vores gratis nyhedsbreve sendt til din indbakke. Du kan også følge os på sociale medier: Facebook, Twitter, Instagram, YouTube eller LinkedIn.

Med venlig hilsen

Videnskab.dk