Pressemeddelelse – Københavns Universitet

12. maj 2010

Pressemeddelelse

Ny banebrydende it-forskning sætter helt nye standarder for optimering af chipdesign - men er chip-producenterne parat til at omstille sig?

 

Når institutleder ved Datalogisk Institut ved Københavns Universitet (DIKU), Martin Zachariasen, fredag den 21. maj 2010 kl. 14.00 forsvarer den naturvidenskabelige doktorgrad med afhandlingen Fixed Orientation Interconnection Problems: Theory, Algorithms and Applications, sammenfattes 10 års intensiv forskning i at skabe nye muligheder i udformningen af integrerede kredsløb (chips).

Mere om tid og sted for doktordisputatsforsvaret - (åbent for alle interesserede)

De fleste mennesker har et meget klart billede af, hvordan en chip ser ud. En lille rektangulær brik med en masse påloddede kontaktpunkter og ledninger, der løber på langs og på tværs (i forskerjargon kaldet Manhattan-arkitektur).

Teoretisk vil en chip kunne effektiviseres med op til 30%, hvis dens ledninger kan forløbe i andre retninger end lodret og vandret. I praksis har det vist sig at udgøre et ualmindelig svært teoretisk og praktisk problem, som i et årti har udfordret it-forskere verden over.

Martin Zachariasen har i godt 10 år forsket i at løse et optimeringsproblem, i forskerkredse kaldet Steinerproblemet, der kort fortalt går ud på at udregne den korteste vej mellem en række faste forbindelsespunkter.

Nu ser det endelig ud til at være lykkedes: At knække den teoretiske algoritme-kode for ledningsforløb i vilkårlige retninger. Det vil betyde hurtigere og effektivere chips og mulige milliardgevinster i industrien som potentiel gevinst.

Chip-industrien har ganske vist hidtil forholdt sig tøvende med at omsætte Martin Zachariasens teoretiske arbejde til praktisk produktion af de nye, mere effektive chips, selv om der potentielt er store fordele at hente. En mulig forklaring er, at erhvervslivet skal investere store summer i en omstilling af produktionsapparatet, og at der skal vedtages nye tekniske standarder, der sikrer en ensartet udrulning af produktionsmetoden på globalt plan. Der er dog ikke tvivl om, at industrien på sigt vil tage anvendelsen i brug, nu hvor det teoretiske grundlag er tilvejebragt.

Om forskningen og disputatsen, der har været undervejs siden 1999, siger Martin Zachariasen.

"Siden jeg blev færdig med min ph.d. i 1998, der i øvrigt også handlede om Steiner-problemet, har jeg forsket videre i at udvikle algoritmer, der kan danne grundlag for at skabe bedre og mere effektivt chip-design.

I 2002 oplevede jeg og mine samarbejdspartnere fra Melbourne University lidt af et gennembrud, da vi udviklede en metode til at udvide antallet af ledningsretninger i en chip. Med vores metode var det muligt at lade ledningerne løbe i flere uniforme, dvs. symmetriske, retninger. Dette kunne reducere ledningsforbruget, og dermed forøge hastigheden og reducere strømforbruget i en chip.

Målet var dog endnu ikke nået - min ambition var at finde en metode til også at få ledningerne til at løbe i vilkårlige retninger. Dette problem ansporede mig til at forske videre og i 2006 lykkedes det faktisk at udvikle en algoritme, der tillod design af kredsløb med ledninger i mange vilkårlige retninger med et fast retningsforløb."

Et af afhandlingens hovedbidrag er da også netop et helt nyt paradigme for konstruktion af netforbindelser på en chip under en generel arkitektur med faste orienteringer. I afhandlingen dokumenteres, at der er klare fordele ved at benytte mere end to orienteringer i chip-design.

Afhandlingens styrke er, at den ikke udelukkende er teoretisk funderet, men at metoden løbende er blevet testet i et ægte produktionsmiljø. Martin Zachariasen har som led i sin forskning samarbejdet med en chipproducent for at sikre, at metoden også har hold i virkeligheden. 

Yderligere information om eller eksemplarer af afhandlingen kan fås ved henvendelse til Martin Zachariasen på martinz@diku.dk eller tlf. 35 32 13 57.

Kort CV

Ud over en bachelorgrad i datalogi fra Færøernes Universitet, har Martin Zachariasen en bachelor i matematik, samt en MSc. og en ph.d. i datalogi fra Københavns Universitet.

Han har siden 1995 været fast tilknyttet Datalogisk Institut, Københavns Universitet, som først ph.d.-studerende, dernæst adjunkt og siden 2001 som lektor. Martin Zachariasen blev i 2008 udpeget som institutleder for DIKU.

Forskning i udlandet

  • 1996 - 1997:   Gæsteforsker ved the Combinatorial Optimization Group, Eindhoven University of Technology, Holland.
  • 1999 - 2000:   Gæsteforsker ved Forschungsinstitut für Diskrete Mathematik, Bonn, Tyskland.
  • 2002 - 2007:   Korttids-udstationeringer som inviteret gæsteforsker ved University of Melbourne, Australien.

Resume af afhandlingen

I forbindelse med design af integrerede kredsløb (chips) indgår der en række såkaldte forbindelsesproblemer. En moderne chip består af flere milliarder transistorer, som skal forbindes med metalledninger på chippens overflade. Disse metalledninger lægges i et (lille) antal lag, således at uafhængige elektriske net ikke overlapper med hinanden. Den traditionelle fremstillingsteknologi kan kun håndtere horisontale og vertikale forbindelser på chippens overflade og betegnes Manhattan-arkitektur.

De seneste 10 år har interessen for generelle arkitekturer, hvor mere end to orienteringer kan benyttes til at forbinde transistorerne, været stigende. Denne udvikling har resulteret i en betydelig forskning i forbindelsesproblemer med faste (men ellers vilkårlige) orienteringer. Minimering af forbindelsernes længde - det såkaldte Steiner problem med faste orienteringerhar været genstand for særlig opmærksomhed.

Denne doktorafhandling består af 12 forskningsartikler samt en oversigtsartikel om Steiner problemet med faste orienteringer - med nogle af dets generaliseringer. Et af hovedbidragene er en lineær-tids algoritme, der kan konstruere et minimalt Steiner træ for en given topologi. Desuden vises, at samme problem kan løses ved hjælp af lineær programmering. For det generelle problem, hvor topologien er ukendt, præsenteres en eksakt algoritme, der kan løse problemet med flere tusinde punkter til optimalitet. Der præsenteres et nyt paradigma for konstruktion af netforbindelser på en chip under en generel arkitektur med faste orienteringer. Resultaterne dokumenterer, at der er klare fordele ved at benytte mere end to orienteringer i chip design.

Afhandlingen afsluttes med en beskrivelse af en række generaliseringer af Steiner problemet, der udspringer fra chip design. Der præsenteres et katalog af problemer, som kan løses på det såkaldte Hanan gitter. Desuden behandles generaliseringer, som kan håndtere signalforsinkelser og gruppeforbindelser. Til sidst gives en række egenskaber for Steiner problemet med tilladt rotation af de faste orienteringer.

Resultaterne udgør et væsentligt teoretisk og algoritmisk bidrag til forståelsen af Steiner problemet med faste orienteringer. Desuden fokuserer afhandlingen på anvendelser i chipdesign.