Abstract
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 bliver betegnet 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 orienteringer — har 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 chip design.
| Originalsprog | Engelsk |
|---|
| Udgivelsessted | København |
|---|---|
| Forlag | Museum Tusculanum |
| Antal sider | 95 |
| ISBN (Trykt) | 978-87-981270-4-8 |
| Status | Udgivet - 2009 |