A New Class of Geometric Analog Error Correction Codes for Crossbar Based In-Memory Computing

Dit artikel onderzoekt een nieuwe familie van geometrische foutcorrectiecodes voor analoge in-memory computing op kruisbalken, waarbij een geometrische analyse wordt ontwikkeld om de m-hoogteprofielen van deze codes te karakteriseren voor het hanteren van meerdere uitschieters.

De kern

Titel: De Nieuwe "Veiligheidsnetten" voor de Computer van de Toekomst

Stel je voor dat je een enorme, super-snelle rekenmachine bouwt die niet werkt met de traditionele 0-en en 1-en van onze huidige computers, maar met analoge signalen. Denk aan het draaien van een knop op een ouderwetse radio: je kunt de knop op oneindig veel posities zetten, niet alleen op "aan" of "uit". Deze nieuwe technologie, genaamd In-Memory Computing, belooft kunstmatige intelligentie (zoals ChatGPT of zelfrijdende auto's) veel sneller en zuiniger te maken.

Maar er is een probleem: deze analoge systemen zijn erg kwetsbaar. Ze lijken op een groep muzikanten die samen spelen.

1. De kleine ruis: Soms is er een beetje achtergrondgeluid (zoals een zacht gefluister). Dit zijn kleine foutjes die overal een beetje voorkomen.
2. De grote blunder: Soms slaat één muzikant volledig de plank mis en schreeuwt hij een valse noot die alles overstemt. In de computerwereld noemen we dit een "outlier" (een uitschieter).

Deze grote blunders zijn dodelijk voor de berekening. Als je één verkeerde noot hebt, is het hele liedje verpest.

Het Probleem: De Bestaande Netten zijn te Klein

Tot nu toe hadden onderzoekers al "veiligheidsnetten" (foutcorrigerende codes) bedacht om deze fouten op te vangen. Maar deze netten waren vaak te klein of te specifiek. Ze konden misschien één grote blunder opvangen, maar als er twee of drie muzikanten tegelijk de toon verdraaiden, viel het systeem in elkaar. Er was een tekort aan flexibele netten die voor verschillende soorten en maten van fouten werkten.

De Oplossing: Een Nieuw Type "Geometrisch Net"

In dit paper presenteren de auteurs een nieuwe familie van veiligheidsnetten, gebaseerd op geometrie.

Stel je voor dat je een net maakt van een driedimensionaal object, zoals een dodecaëder (een figuur met 12 vlakken, net als een twaalfzijdige dobbelsteen) of een icosahedron (een figuur met 20 vlakken).

• De onderzoekers gebruiken de hoekpunten en lijnen van deze perfecte vormen om hun "net" te bouwen.
• Door de wiskundige eigenschappen van deze vormen te analyseren, kunnen ze precies voorspellen hoe het net zich gedraagt als er fouten in het systeem sluipen.

Hoe Werkt Het? (De "Hoogte"-Metriek)

De auteurs gebruiken een slimme maatstaf die ze de "m-hoogte" noemen.

• De Analogie: Denk aan een berg met verschillende pieken. De hoogste piek is de grootste fout. De "m-hoogte" is de verhouding tussen de hoogste piek en de (m+1)-de hoogste piek.
• De Doelstelling: Je wilt dat deze verhouding zo klein mogelijk is. Als de hoogste piek niet veel hoger is dan de andere pieken, is het makkelijker om de echte fout te vinden en te corrigeren zonder de rest van de muziek te verstoren.

De paper laat wiskundig bewijzen dat deze nieuwe geometrische netten (de "dual polygonal" en "dual polyhedral" codes) een zeer gunstige "m-hoogte" hebben. Ze zijn zo ontworpen dat ze:

1. Meerdere grote blunders tegelijk kunnen opsporen en corrigeren.
2. Zelfs als de fouten enorm groot zijn, het systeem stabiel houden.

Waarom is dit Belangrijk?

Voor de toekomst van kunstmatige intelligentie is dit een game-changer.

• Betrouwbaarheid: Computers die in het geheugen rekenen (in-memory computing) kunnen nu veel vaster rekenen, zelfs als de hardware niet perfect is.
• Efficiëntie: Je hoeft geen extra dure hardware te bouwen om fouten te voorkomen; je lost het op met slimme wiskunde (de geometrische codes).
• Flexibiliteit: De onderzoekers hebben niet alleen één oplossing gevonden, maar een heel nieuw type "netten" dat voor veel verschillende situaties werkt, van simpele tot complexe fouten.

Samenvattend

Stel je voor dat je een orkest hebt dat een symfonie speelt voor een robot. De robot is erg snel, maar erg gevoelig voor één valse noot. De auteurs van dit paper hebben een nieuw soort muziekpartituur ontworpen. Dit partituur is zo gebouwd (op basis van perfecte geometrische vormen) dat het orkest zelfs als drie muzikanten tegelijk de toon missen, de melodie toch perfect kan herstellen.

Dit maakt de weg vrij voor snellere, zuinigere en betrouwbaardere AI-systemen in de toekomst.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "A New Class of Geometric Analog Error Correction Codes for Crossbar Based In-Memory Computing", geschreven in het Nederlands.

Titel: Een nieuwe klasse van geometrische analoge foutcorrectiecodes voor crossbar-gebaseerde in-memory computing

1. Het Probleem

Analoge in-memory computing (IMC) op resistieve crossbars is een veelbelovende technologie om de "von Neumann-bottleneck" te doorbreken en vector-matrixvermenigvuldigingen voor Deep Neural Networks (DNN's) te versnellen. Een kritieke uitdaging bij deze technologie is de aanwezigheid van ruis in de analoge signalen.

Het ruismodel in dit scenario is gemengd en bestaat uit twee soorten fouten:

• Beperkte-magnitude fouten (LMEs): Kleine, wijdverspreide verstoringen veroorzaakt door programmeer- en lees-/schrijfstoringen.
• Onbeperkte-magnitude fouten (UMEs): Grote, geïsoleerde "uitbijters" (outliers) veroorzaakt door defecten zoals vastzittende cellen of kortsluiting.

Hoewel DNN's vaak tolerant zijn voor kleine LMEs, zijn ze zeer kwetsbaar voor grote UMEs. Bestaande analoge foutcorrectiecodes (ECC) zijn beperkt in hun beschikbaarheid en kunnen vaak slechts één outlier detecteren of corrigeren. Er is een gebrek aan code-families die een breed scala aan code-lengtes en dimensies kunnen dekken met de capaciteit om meerdere outliers te hanteren.

2. Methodologie

De auteurs analyseren en ontwikkelen een nieuwe familie van geometrische codes, specifiek gericht op dual polygonale codes en dual polyhedrale codes. De kern van de methodologie ligt in een geometrische analyse van de m-hoogte profielen ($m$-height profiles) van deze codes.

• Definitie van m-hoogte: De $m$-hoogte van een codewoord $c$ wordt gedefinieerd als de verhouding tussen de grootste absolute waarde van een element en de $(m+1)$-grootste absolute waarde ($h_m(c) = c^{(0)} / c^{(m)}$). De $m$-hoogte van de code $C$ is het maximum van deze verhouding over alle codewoorden.
• Relatie met foutcorrectie: Een kleinere $m$-hoogte correleert direct met een sterkere capaciteit om UMEs te lokaliseren en te detecteren. De voorwaarde voor het corrigeren van $\tau$ outliers en detecteren van $\tau + \sigma$ outliers wordt bepaald door de verhouding $\Delta/\delta \geq 2(h_{2\tau+\sigma}(C) + 1)$.
• Geometrische Analyse: In plaats van alleen te vertrouwen op lineaire programmering (zoals in eerdere werken), gebruiken de auteurs een zuiver geometrische benadering:
  • Voor dual polygonale codes ($k=2$): De generatorvectoren zijn gelijkmatig verdeelde eenheidsvectoren over een halve cirkel. De auteurs analyseren de symmetrie en beperken het zoekgebied voor de informatievector tot een fundamenteel domein ($\alpha \in [0, \pi/2n]$). Ze leiden een gesloten formule af voor de $m$-hoogte op basis van de hoek $\alpha$.
  • Voor dual polyhedrale codes ($k=3$): De auteurs analyseren codes gebaseerd op de icosahedron (dual icosahedral) en de dodecahedron (dual dodecahedral). Door gebruik te maken van de symmetrie van deze veelvlakken, reduceren ze het 3D-probleem tot het analyseren van een fundamenteel driehoekig gebied op het oppervlak van de veelvlakken. Ze gebruiken barycentrische coördinaten en analyseren de monotonie van de doelwitfuncties (verhoudingen van projecties) binnen deze gebieden om de maximale $m$-hoogte te vinden.

3. Belangrijkste Bijdragen

1. Geometrische Karakterisering: De paper biedt een alternatieve, geometrische analyse voor dual polygonale en dual polyhedrale codes, wat leidt tot exacte karakteriseringen van hun $m$-hoogte profielen.
2. Gesloten Formules voor Polygonale Codes: Voor dual polygonale codes met $k=2$ wordt een exacte formule afgeleid voor de $m$-hoogte, afhankelijk van of $m$ even of oneven is. Dit bevestigt eerdere resultaten maar biedt een dieper inzicht in de structuur.
3. Analyse van 3D-Structuren: Voor het eerst wordt een uitgebreide analyse uitgevoerd voor dual icosahedrale en dual dodecahedrale codes. De auteurs identificeren de kritieke richtingen (hoekpunten en randen van de fundamentele driehoeken) waar de $m$-hoogte zijn maximum bereikt.
4. Bepaling van Optimale Richtingen: De paper identificeert specifiek welke informatievectoren (richtingen) de slechtste $m$-hoogte veroorzaken, wat essentieel is voor het ontwerpen van robuuste systemen.

4. Resultaten

De auteurs hebben de $m$-hoogte profielen voor de geanalyseerde codes kwantitatief bepaald:

• Dual Polygonale Codes:

  • De $m$-hoogte wordt gemaximaliseerd bij specifieke hoeken ($\alpha = 0$ of $\alpha = \pi/2n$).
  • Voor $m$ even is de maximale $m$-hoogte: $\frac{\cos(\pi/2n)}{\cos((m+1)\pi/2n)}$.
  • Voor $m$ oneven is de maximale $m$-hoogte: $\frac{1}{\cos((m+1)\pi/2n)}$.

• Dual Icosahedrale Codes (gebaseerd op 12 vectoren):

  • $m=1, 2$: $m$-hoogte = $\sqrt{5}$.
  • $m=3$: $m$-hoogte = $2 + \sqrt{5}$.
  • Voor $m \geq 4$ is de code MDS (Maximum Distance Separable), wat betekent dat de $m$-hoogte oneindig is (er bestaat een codewoord met $m$ nullen).

• Dual Dodecahedrale Codes (gebaseerd op 20 vectoren):

  • $m=1$: $m$-hoogte = $3\sqrt{5}$.
  • $m=2$: $m$-hoogte = $\phi$ (de gulden snede, $\approx 1.618$).
  • $m=3$: $m$-hoogte = $4 - \sqrt{5}$.
  • $m=4$: $m$-hoogte = $3$.
  • $m=5$: $m$-hoogte = $3$.
  • $m=6$: $m$-hoogte = $2 + 3\sqrt{5}$.
  • $m=7$: $m$-hoogte = $5 + 2\sqrt{5}$.

De resultaten tonen aan dat deze geometrische codes zeer lage $m$-hoogtes hebben voor kleine $m$, wat betekent dat ze zeer effectief zijn in het lokaliseren van meerdere outliers.

5. Betekenis en Impact

Deze studie is van groot belang voor de ontwikkeling van betrouwbare analoge in-memory computing systemen:

• Robuustheid: De afgeleide codes bieden een theoretisch onderbouwde manier om meerdere grote fouten (outliers) te corrigeren in crossbar-architecturen, wat essentieel is voor de praktische implementatie van DNNs in hardware.
• Ontwerprichtlijnen: Door de exacte $m$-hoogte profielen te kennen, kunnen systeemontwerpers de trade-off tussen code-lengte, dimensie en fouttolerantie beter bepalen.
• Uitbreiding van de Literatuur: De paper vult een gat in de bestaande literatuur door een nieuwe klasse van codes te analyseren die verder gaat dan de eerdere beperkte families. Het bewijst dat geometrische structuren (zoals veelvlakken) een rijke bron zijn voor het ontwerpen van hoogwaardige analoge foutcorrectiecodes.
• Toekomstige Richting: Hoewel de analyse voor polygonale en polyhedrale codes succesvol is, blijft de uitbreiding van deze geometrische methode naar andere code-families een open probleem, wat nieuwe onderzoeksrichtingen opent.

Kortom, dit werk levert een fundamentele bijdrage aan de theorie van analoge foutcorrectie en biedt concrete, wiskundig onderbouwde oplossingen voor de betrouwbaarheidsuitdagingen in de volgende generatie neuromorfe computing hardware.