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

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.