A Linear-Time Algorithm for Steady-State Analysis of Electromigration in General Interconnects

Dit artikel presenteert een lineaire-tijd algoritme dat, gebaseerd op fundamentele spanningsvergelijkingen, de elektromigratie-veiligheid van complexe interconnect-netwerken exact en efficiënt analyseert zonder de beperkingen van traditionele methoden.

De kern

Stel je voor dat de elektronen in een computerchip niet als stille reizigers door de draden reizen, maar als een enorme, drukke menigte mensen die door een smalle tunnel rennen.

Dit is het verhaal van elektrische migratie (EM), een groot probleem in moderne chips. Als deze "menigte" (de stroom) te lang en te hard door een metaaldraad (zoals koper) rent, duwen de elektronen de metaalatomen voor zich uit. Net als een stroomversnelling die zandkorrels wegdrijft, ontstaan er op de startplek gaten (voids) en hopen de atomen zich op de eindplek op. Uiteindelijk kan de draad breken en de chip kapot gaan.

De wetenschappers in dit paper hebben een nieuwe, supersnelle manier bedacht om te voorspellen welke draden veilig zijn en welke binnenkort zullen bezwijken. Hier is hoe het werkt, vertaald naar alledaagse taal:

1. Het oude probleem: De "Eenzame Draad"-regel

Vroeger keken ingenieurs naar elke draad alsof het een alleenstaande wandelaar was. Ze gebruikten een simpele regel (de "Blech-criterium"): Als de wandelaar niet te snel loopt en de weg niet te lang is, is hij veilig.

Maar in een echte chip zijn draden geen alleenlopers. Ze zijn verbonden in complexe netwerken, zoals een boom met takken of een spinnenweb (mesh).

• Het probleem: Als je een lange, drukke weg (hoge stroom) koppelt aan een korte, rustige weg (lage stroom), gedraagt de rustige weg zich niet meer als een alleenstaande wandelaar. De druk van de drukke weg duwt atomen de rustige weg in.
• De fout: De oude regel dacht dat de rustige weg veilig was, maar door de druk van de buren kon hij toch breken. Of andersom: een drukke weg kon veilig zijn omdat hij zijn "last" kon afgeven aan een buur. De oude methode maakte hier veel fouten in.

2. De nieuwe oplossing: Een slimme rekenmachine

De auteurs van dit paper hebben een nieuwe methode ontwikkeld die kijkt naar het hele netwerk in plaats van naar losse stukjes. Ze gebruiken twee slimme benaderingen:

Benadering A: De "Stroom-Tracker" (Current-Density)

Stel je voor dat je een postbode bent die door het hele netwerk loopt.

• Je begint bij één punt en telt voor elke stap die je zet: "Hoe hard duwen de elektronen hier?"
• Je houdt een som bij van alle duwtjes (stroom × lengte) die je hebt gezien.
• Als je bij het einde van een tak bent, weet je precies hoe groot de druk (stress) daar is.
• Het nadeel: Je moet het hele netwerk fysiek "lopen" (traverseren) om de som te maken. Dit duurt even, maar het is nog steeds heel snel.

Benadering B: De "Spannings-Spy" (Voltage-Based) – De echte doorbraak

Dit is de magische truc van het paper. De auteurs ontdekten iets verrassends:

• De duwkracht die de elektronen op de atomen uitoefenen (stroom × lengte) is precies evenredig met de spanningsdaling (IR-drop) in de draad.
• In elke chip wordt al een simpele rekensom gemaakt om te zien hoeveel spanning er overblijft op elk punt (dit doen ontwerpers al om te zorgen dat de chip werkt).
• De truc: Je hoeft het netwerk niet te lopen! Je kunt gewoon de bestaande spanningswaarden "lezen" en direct de druk op de atomen berekenen.
• Analogie: In plaats van te lopen om te tellen hoeveel mensen er in een rij staan, kijk je gewoon naar de lengte van de rij op een camera. Het resultaat is hetzelfde, maar je bent 100x sneller klaar.

3. Waarom is dit zo belangrijk?

• Snelheid: De oude methoden om te kijken of een chip veilig is, waren traag en complex. Deze nieuwe methode is lineair. Dat betekent: als je het aantal draden verdubbelt, verdubbelt de rekentijd ook. Het is niet exponentieel (zoals een reeks die uit de hand loopt). Het is alsof je van een wandeling in de sneeuw verandert in een ritje met een supersnelle trein.
• Nauwkeurigheid: Ze hebben bewezen dat hun methode exact hetzelfde resultaat geeft als dure, uren durende simulaties, maar dan in milliseconden.
• Toekomst: Omdat deze methode zo snel is, kunnen chipontwerpers nu veel vaker controleren of hun ontwerpen veilig zijn, zelfs voor de allermodernste en kleinste chips (zoals die in je telefoon of auto).

Samenvattend

Stel je voor dat je een heel groot labyrint van waterpijpen hebt.

• Oude methode: Je kijkt naar elke pijp afzonderlijk en zegt: "Deze pijp is veilig als het water niet te hard stroomt." Je mist echter dat een drukke pijp water in een rustige pijp duwt, waardoor die toch barst.
• Nieuwe methode: Je kijkt naar de druk op elk punt in het hele labyrint tegelijk. Je gebruikt een slimme formule die zegt: "De druk op punt X is gewoon het verschil in waterhoogte tussen punt X en de bron."
• Resultaat: Je ziet in een flits welke pijpen gaan lekken, zonder dat je door het hele labyrint hoeft te zwemmen.

Dit paper biedt dus de "snelle en slimme bril" die chipontwerpers nodig hebben om te voorkomen dat hun producten binnenkort stukvallen door de druk van de elektronen.

Technische samenvatting

Probleemstelling

Elektromigratie (EM) is een kritiek betrouwbaarheidsprobleem in diep geschaalde technologieën (zoals FinFET). Traditionele EM-analysemethoden volgen een tweestapsproces:

1. Filteren: Het gebruik van het Blech-criterium om "onsterfelijke" (immortal) draden te identificeren die geen EM-uitval zullen vertonen. Dit criterium is gebaseerd op het product van stroomdichtheid ($j$) en lengte ($l$) van een enkele draadsegment.
2. Analyse: Verdere analyse van de overgebleven draden met behulp van Black's vergelijking.

De beperkingen van de huidige aanpak:

• Het Blech-criterium is afgeleid voor enkele draadsegmenten met blokkerende randvoorwaarden aan beide uiteinden.
• Moderne on-chip interconnects zijn complexe bomen en netwerken (meshes) met meerdere segmenten die verschillende stroomdichtheden dragen.
• Toepassing van het Blech-criterium op deze complexe structuren leidt tot onnauwkeurige resultaten (veel foutieve positieven en negatieven).
• Bestaande fysisch gebaseerde methoden die differentiaalvergelijkingen oplossen, zijn computationally zeer duur en niet schaalbaar voor grote netwerken.

Er is dus behoefte aan een snelle, exacte methode om de steady-state spanning (stress) te berekenen in willekeurige interconnect-structuren om nauwkeurig te bepalen welke segmenten onsterfelijk zijn.

Methodologie

De auteurs baseren hun methode op de eerste principes van EM-fysica, specifiek de relatie tussen de "electron wind force" en de "back-stress force". Ze lossen de fundamentele vergelijkingen voor spanningsontwikkeling op om een lineaire tijd-algoritme te ontwikkelen.

Kernconcepten:

1. Steady-State Spanning: In de steady-state is de spanning ($\sigma$) lineair langs een draadsegment, met een helling die evenredig is met de stroomdichtheid ($\beta j$).
2. Behoud van Massa: Hoewel atomen worden getransporteerd, is er geen netto verandering in het totale aantal atomen in de draad. Dit leidt tot een integraalvoorwaarde: de integraal van de spanning over het gehele netwerk moet nul zijn (gecorrigeerd voor breedte en dikte).
3. Behandeling van Cycles: Voor netwerken met cycli (meshes) bewijzen de auteurs dat het voldoende is om een spanningstree (spanning tree) van het netwerk te analyseren. De vergelijkingen voor cycli zijn lineair afhankelijk; het breken van een cyclus levert een unieke oplossing op.

Twee voorgestelde algoritmen:
De paper introduceert twee varianten om de steady-state spanning te berekenen, beide met een lineaire complexiteit $O(|V| + |E|)$, waarbij $|V|$ het aantal knopen en $|E|$ het aantal segmenten is:

• A. Stroomdichtheid-gebaseerde methode (Current-Density-Based):

  • Vereist een traversale (bijv. Breadth-First Search) door de boomstructuur.
  • Berekent de "Blech-sum" (de algebraïsche som van $j \cdot l$) langs paden vanaf een referentieknoop.
  • Combineert deze sommen met de behouds-massa-vergelijking om de spanning in elke knoop te bepalen.

• B. Spannings-gebaseerde methode (Voltage-Based):

  • Traversale-vrij: Deze methode maakt gebruik van de bestaande spanningen ($V$) die al worden berekend tijdens de standaard circuit-simulatie (voor IR-drop analyse).
  • De auteurs bewijzen dat de $j \cdot l$ "drop" over een segment direct evenredig is met de IR-drop ($V_t - V_s$) over dat segment.
  • De spanning kan dus worden berekend door alleen de knoopspanningen en de geometrie van de draden te gebruiken, zonder extra traversalen door het graf. Dit maakt deze methode nog sneller.

Belangrijkste Bijdragen

1. Eerste Lineaire Tijd Oplossing: Dit is de eerste methode die een exacte steady-state EM-analyse biedt voor algemene boom- en mesh-structuren met lineaire tijdcomplexiteit.
2. Exacte Fysische Basis: In tegenstelling tot empirische heuristieken, is de methode afgeleid uit fundamentele differentiaalvergelijkingen en behoudswetten.
3. Relatie tussen IR-drop en EM: De auteurs bewijzen dat de IR-drop over een draadsegment direct evenredig is met het verschil in spanning aan de uiteinden. Dit betekent dat het minimaliseren van IR-drop ook direct bijdraagt aan het verminderen van EM-gevoeligheid.
4. Validatie van Mesh-structuren: Het paper toont wiskundig aan dat de analyse van een spanningstree voldoende is voor meshes, wat een fundamentele uitbreiding is ten opzichte van eerdere werken die zich beperkten tot eenvoudige lijnen of bomen.
5. Twee Efficiënte Varianten: Het introduceren van de voltage-based methode die geen traversale vereist, wat de rekentijd aanzienlijk verlaagt in vergelijking met de stroomdichtheid-methode.

Resultaten

De methoden zijn getest op diverse benchmarks, waaronder IBM power grid benchmarks en moderne technologieën (12nm FinFET, 28nm FDSOI, 45nm Open-source).

• Nauwkeurigheid: De resultaten van de voorgestelde methoden komen exact overeen met numerieke simulaties van COMSOL (een geavanceerde FEM-solver), maar worden in milliseconden berekend in plaats van uren.
• Onnauwkeurigheid van Blech: Vergelijkingen tonen aan dat het traditionele Blech-criterium bij multi-segment draden aanzienlijk faalt:
  • Het labelt vaak mortal (kwetsbare) segmenten als onsterfelijk (False Positives), wat leidt tot onopgemerkte uitval.
  • Het labelt soms onsterfelijke segmenten als mortal (False Negatives), wat leidt tot overdesign.
• Snelheid:
  • De voltage-based methode is 1.5x tot 2.7x sneller dan de stroomdichtheid-methode omdat deze geen traversale vereist.
  • De methoden schalen perfect naar grote netwerken (bijv. benchmarks met >1.6 miljoen segmenten) met rekentijden van enkele seconden.
• Foutanalyse: In IBM-benchmarks bleek het Blech-criterium honderdduizenden fouten te maken (zowel FP als FN), terwijl de nieuwe methode consistent de juiste classificatie gaf.

Significantie

Deze paper biedt een fundamentele doorbraak in de betrouwbaarheidsanalyse van geïntegreerde schakelingen:

• Vervanging van Blech: Het biedt een wiskundig onderbouwde vervanging voor het verouderde Blech-criterium, specifiek ontworpen voor de complexe, multi-segment netwerken van moderne chips.
• Efficiëntie: Door de lineaire tijdcomplexiteit en de mogelijkheid om bestaande spanningsdata te hergebruiken, kan EM-analyse nu worden geïntegreerd in vroege ontwerpfases zonder de rekentijd te verzwaren.
• Ontwerpoptimalisatie: De directe link tussen spanning (stress) en IR-drop suggereert nieuwe wegen voor geoptimaliseerd power grid design dat zowel spanningsdaling als elektromigratie gelijktijdisch adresseert.

Kortom, de auteurs hebben een snelle, exacte en schaalbare oplossing ontwikkeld die het risico op elektromigratie-fouten in moderne chips veel nauwkeuriger kan voorspellen dan bestaande methoden.