A Complexity Agnostic Clustering Engine for Time Projection Chambers and its Implementation in FPGA

Dit paper beschrijft een complexiteitsongevoelige clustering-engine voor tijdprojectiekamers, geïmplementeerd in een FPGA, die inputdata in twee fasen verwerkt om hits binnen dezelfde clusters te groeperen met een voorspelbare en lineaire verwerkingstijd, ongeacht de complexiteit van het evenement.

De kern

Stel je voor dat je een enorme, chaotische zee van losse puzzelstukjes hebt. Deze stukjes komen uit een heel speciaal apparaat (een Time Projection Chamber of TPC) dat deeltjes in deeltjesfysica vastlegt. Het probleem is dat deze puzzelstukjes niet in de juiste volgorde aankomen. Sommige stukjes horen bij dezelfde "deeltjesbaan" (een cluster), maar ze zijn door elkaar heen gemengd met stukjes van andere banen.

In de oude manier van werken (met software op een normale computer) moest je elke puzzelstukjes één voor één vergelijken met alle andere stukjes om te zien of ze bij elkaar horen. Dat is als proberen een naald te vinden in een hooiberg, terwijl je elke hooiberg opnieuw moet doorzoeken. Dit kost veel tijd en wordt onbeheersbaar langzaam als er meer deeltjes zijn.

De oplossing in dit papier: Een slimme, snelle "Puzzel-robot" op een chip.

De auteurs van dit paper hebben een speciale schakeling gebouwd op een FPGA (een programmeerbare computerchip) die dit probleem oplost. Hier is hoe het werkt, vertaald naar alledaagse taal:

1. Het idee: Geen naalden zoeken, maar een adresboekje gebruiken

Stel je voor dat je een enorme postkantoor hebt. In plaats van dat postbodes rondlopen om te kijken wie bij wie hoort, heeft iedereen een postbus met een uniek adres (bijvoorbeeld: "Straat 5, Huis 10").

• De TPC-data: Elke "hit" (een signaal van een deeltje) heeft een adres: op welk tijdstip en op welke positie (kanaal) kwam het binnen.
• De RAM-geheugen: De chip gebruikt een soort digitaal adresboekje (geheugen) waar ze elke aankomende puzzelstukje direct in de juiste vakjes zetten. Ze hoeven niet te zoeken; ze weten precies waar het hoort.

2. De twee fases: Vullen en Lezen

De robot werkt in twee duidelijke fases, net als het vullen en legen van een bus:

• Fase 1: Het Vullen (Data Filling)
  Alle puzzelstukjes (hits) komen binnen en worden direct in hun eigen vakje in het geheugen gezet. De robot schrijft ook een lijstje bij: "Stukje A is in vak 1, stukje B in vak 2". Dit gaat razendsnel.
• Fase 2: Het Lezen (Data Outputting)
  Nu begint het magische deel. De robot kijkt naar zijn lijstje en begint bij het laatste stukje dat binnenkwam. Hij vraagt zich af: "Wie zit er direct naast dit stukje?"
  • Als er een stukje naast zit (op een naburig kanaal of tijdstip), dan horen ze bij dezelfde cluster. De robot pakt die ook mee en kijkt weer naar de volgende buur.
  • Hij volgt zo een spoor van puzzelstukjes die bij elkaar horen, totdat het spoor ophoudt. Dan springt hij naar het volgende losse stukje op zijn lijstje en begint een nieuw spoor.

3. Waarom is dit zo slim? (De "Complexiteit-Agnostic" truc)

In de oude software-methoden werd het werk langzamer naarmate er meer deeltjes waren (zoals $O(n^2)$: als je 100 deeltjes hebt, is het werk 10.000 keer zo zwaar als bij 1 deeltje).
Deze nieuwe chip werkt altijd even snel, ongeacht hoeveel deeltjes er zijn (zoals $O(n)$).

• De analogie: Of je nu 10 puzzelstukjes hebt of 10.000, de robot doet precies hetzelfde: hij vult het adresboekje en loopt er dan één keer doorheen. De tijd die het kost is altijd precies twee keer zo lang als de tijd om te vullen. Er is geen "trage" fase die plotseling langzamer wordt als het drukker wordt.

4. De test: Het werkt in de praktijk

De auteurs hebben dit gebouwd op een goedkope test-chip (een Cyclone V FPGA) die werkt op 200 MHz (dat is razendsnel, 200 miljoen keer per seconde).
Ze hebben het getest met willekeurige, chaotische data. Het resultaat?

• De robot nam de rommelige input en gaf een geordende output.
• Alle puzzelstukjes die bij elkaar hoorden, kwamen nu achter elkaar uit de machine.
• Zelfs bij zeer lange, ingewikkelde banen (clusters) werkte het perfect.

5. Een extra trucje voor de perfecte volgorde

Soms begint de robot in het midden van een cluster en loopt hij naar beide kanten op. Dat is prima voor de meeste analyses, maar als je echt wilt dat een cluster van "begin tot einde" in de juiste volgorde staat, kun je gewoon twee robots achter elkaar zetten.

• De eerste robot sorteert de stukjes.
• De tweede robot pakt die output en sorteert ze nog een keer, zodat ze nu echt van begin tot eind lopen.

Conclusie

Dit paper beschrijft een slimme manier om de chaos van deeltjesfysica-data te ordenen. In plaats van te rekenen met zware software die traag wordt, gebruiken ze een slimme hardware-chip die werkt als een super-snel postkantoor met een adresboekje. Hierdoor kunnen toekomstige experimenten (zoals die in het Fermi National Accelerator Laboratory) veel meer data verwerken, zonder vast te lopen, en dat allemaal in real-time.

Technische samenvatting

Probleemstelling

In moderne experimenten voor hoge-energiefysica en kernfysica worden Time Projection Chambers (TPC) veelvuldig gebruikt. Een cruciale taak in de data-verwerking van TPC's is clustering: het groeperen van data-punten ("hits") die behoren tot hetzelfde geladen deeltje-spoor.

• Software-beperking: Traditionele software-oplossingen gebruiken geneste lussen met een tijdscomplexiteit van O(n²), waarbij n het aantal hits in een gebeurtenis is. Dit is te traag voor real-time trigger-systemen.
• Huidige FPGA-oplossingen: Bestaande hardware-oplossingen in Field-Programable Gate Arrays (FPGA's) proberen dit op te lossen door hardwareblokken te "unrollen" (paralleliseren). Dit werkt echter alleen binnen strikte limieten voor het aantal hits per gebeurtenis of per cluster. Bij complexe gebeurtenissen falen deze systemen vaak of hebben ze een niet-bepaalde (non-deterministische) verwerkingstijd met een resterende O(n²)-term.
• Doel: Er is behoefte aan een clustering-engine die voorspelbare tijd garandeert, ongeacht de complexiteit van de gebeurtenis, en die in O(n) tijd werkt.

Methodologie

De auteurs hebben een nieuwe clustering-engine ontworpen die gebruikmaakt van indexering en blokken RAM-geheugen om de O(n²)-complexiteit te elimineren. De kern van de methode bestaat uit twee fasen:

1. Data-vullingsfase (Data Filling Phase):

   • Inkomende hits (bestaande uit een header en ADC-waarden) worden in een buffer opgeslagen.
   • De header van elke hit wordt gebruikt om een vermelding te maken in een Hit ID RAM. Dit RAM is georganiseerd als een 2D-array (Tijdbins op de X-as, Kanalen op de Y-as).
   • Het RAM slaat een "Hit Valid" vlag en een "Hit Number" (een doorlopende teller van de inputstroom) op.
   • Een Bit Register markeert welke hits zijn verwerkt.

2. Data-uitvoerfase (Data Outputting Phase):

   • Deze fase duurt exact even lang als de vullingsfase, wat zorgt voor voorspelbare timing.
   • Een Priority Encoder selecteert de hoogste nog niet-gelezen Hit Number.
   • De Hit Indexing Unit leest de huidige hit uit en zoekt actief naar buren in het Hit ID RAM. Een cluster wordt gedefinieerd als hits in aangrenzende kanalen (CH+1 of CH-1) met gelijke of aangrenzende tijdbins.
   • Het systeem zoekt eerst naar CH+1, daarna naar CH-1. Als er geen buren meer zijn, springt het systeem terug naar de Priority Encoder om de volgende ongelezen hit te starten.
   • Geheugenarchitectuur: Om snelle burenzoekopdrachten mogelijk te maken, wordt het Hit ID RAM geïmplementeerd met vier fysieke RAM-blokken. Dit stelt het systeem in staat om gelijktijdig de huidige hit en de aangrenzende tijdbins (TM+1, TM, TM-1) voor de aangrenzende kanalen (CH+1 en CH-1) te adresseren binnen één cyclus.

Tijdspecificaties:

• Het lezen van een hit kost precies 8 klokcycli.
• De totale verwerkingstijd is exact twee keer de tijd van de data-vullingsfase (geen resterende O(n²)-term).
• Het systeem is complexiteitsagnostisch: het kan omgaan met willekeurige aantallen clusters en hits per cluster, zolang het totale aantal hits binnen een vooraf ingesteld limiet blijft.

Belangrijkste Bijdragen

• Deterministische Verwerkingstijd: De engine garandeert een vaste verwerkingstijd die lineair is met het aantal hits, zonder afhankelijkheid van de complexiteit van de gebeurtenis.
• Indexering in plaats van Unrolling: In plaats van hardware te unrollen (wat resources verslindt en limieten oplegt), wordt gebruikgemaakt van RAM-gebaseerde indexering om clusters in O(n) tijd te vinden.
• Data-integriteit: De engine behoudt de volledige datapakketten (header + ADC-waarden) en herordent ze alleen zodat hits van dezelfde cluster achter elkaar worden uitgegeven.
• Cascadering voor Volledige Ordening: Hoewel de engine clusters groepeert, kan de startpunt van een cluster willekeurig zijn (midden van de cluster). De auteurs tonen aan dat door twee engines in cascade te schakelen, de hits binnen een cluster volledig van begin tot eind kunnen worden gesorteerd.

Resultaten

De engine is geïmplementeerd en getest op een Altera Cyclone V FPGA (TERASIC C5G module) met een lage kostprijs.

• Frequentie: Het systeem draait stabiel op 200 MHz, wat dicht bij het maximum van het gebruikte RAM-blok (275 MHz) ligt.
• Resourcegebruik: Het verbruikt een zeer klein aantal FPGA-resources (logische elementen en blokken geheugen), wat maakt dat meerdere kopieën van de engine in bestaande TPC-leessystemen kunnen worden ondergebracht.
• Testscenario's:
  • Getest met gesimuleerde gebeurtenissen met willekeurige hit-volgorde.
  • Een testgebeurtenis met ~110 hits en 28 clusters toonde aan dat hits correct werden gegroepeerd en herordend.
  • Tests met extreem lange clusters bevestigden de robuustheid en complexiteits-onafhankelijkheid.
  • De test met twee gekaskadeerde engines bevestigde dat hits binnen een cluster volledig van eind tot eind gesorteerd kunnen worden.

Betekenis en Toekomstperspectief

Deze paper presenteert een doorbraak voor real-time trigger-systemen in TPC's.

• Schalbaarheid: Omdat de meeste huidige TPC-leessystemen (voor gas- of vloeibaar argon) lagere sample-frequenties hebben (50 MHz of 2 MHz) dan de 200 MHz van deze engine, is het zeer waarschijnlijk dat één of twee kopieën van deze engine voldoende zijn om de datastroom in real-time te verwerken.
• Hardware-efficiëntie: De lage resource-gebruik maakt het mogelijk om deze technologie in bestaande, grootschalige experimenten te integreren zonder de FPGA-capaciteit te overschrijden.
• Toepasbaarheid: De methode biedt een oplossing voor het fundamentele probleem van O(n²)-complexiteit in clustering, waardoor het mogelijk wordt om complexe gebeurtenissen in real-time te verwerken zonder data te verliezen of vertraging op te lopen.