Tree codes and sort-and-sweep algorithms for neighborhood computation: A cache-conscious comparison

Dit artikel vergelijkt de prestaties van sort-and-sweep- en boomcode-algoritmen voor de berekening van buurdeeltjes in tweedimensionale DEM-simulaties, waarbij de boomcode een licht betere prestatie en betere mogelijkheden voor parallelisatie biedt ten koste van een aanzienlijk hogere cyclomatische complexiteit.

De kern

Hier is een uitleg van het wetenschappelijke artikel in eenvoudig Nederlands, met behulp van alledaagse vergelijkingen.

De Kern: Hoe vinden we wie wie raakt?

Stel je voor dat je een enorme danszaal hebt vol met duizenden mensen (deeltjes) die rondlopen en soms tegen elkaar aanbotsen. Dit is wat computers doen bij simulaties van granulaat, zoals zand of korrels. De computer moet constant weten: "Wie raakt wie?"

Als er 12.000 mensen in de zaal zijn, en de computer moet elke persoon met elke andere persoon vergelijken, duurt het eeuwen. Dat is te traag. Daarom gebruiken wetenschappers slimme trucs om alleen naar de mensen te kijken die echt dicht bij elkaar staan.

In dit artikel vergelijken de auteurs twee van deze slimme trucs:

1. De "Sorteer-en-Sweep" methode.
2. De "Boom-code" (Tree-code) methode.

---

1. De Twee Methoden: Een Vergelijking

Methode A: De "Sorteer-en-Sweep" (De Lijst-Organisator)

Stel je voor dat je een lange rij mensen hebt die in een gang staan.

• Hoe het werkt: De computer maakt een lijst van iedereen, gesorteerd op hun positie (bijvoorbeeld van links naar rechts).
• De truc: Als iemand beweegt, schuift hij in de lijst op. De computer kijkt alleen naar de mensen die nu naast elkaar in de lijst staan. Als je lijst gesorteerd is, hoef je niet iedereen met iedereen te vergelijken, maar alleen je directe buren.
• Het nadeel: Het is alsof je een grote lijst moet herschrijven elke keer dat iemand een stapje zet. Als iedereen tegelijk beweegt, moet je de hele lijst opnieuw sorteren. Dat kost veel tijd en energie.

Methode B: De "Boom-code" (De Slimme Kaart)

Stel je voor dat je de danszaal in vier kwadranten deelt (noord, zuid, oost, west).

• Hoe het werkt: Je maakt een hiërarchische kaart (een boom). Als een kwadrant te vol is, deel je het weer in vier kleinere stukjes op. Je bouwt zo een "boom" van gebieden.
• De truc: Als iemand beweegt, hoeft de computer niet de hele lijst te herschrijven. Hij hoeft alleen de persoon in de boom te verplaatsen naar het juiste vakje. Als twee vakjes leeg zijn, weet je direct dat die mensen elkaar niet kunnen raken.
• Het voordeel: Het is veel sneller om alleen de kleine veranderingen in de boom bij te werken, in plaats van de hele lijst opnieuw te sorteren.

---

2. Wat hebben ze ontdekt? (De Resultaten)

De auteurs hebben deze twee methoden getest op een computer met duizenden deeltjes (zoals een draaiende trommel met stenen). Hier zijn de belangrijkste bevindingen, vertaald naar begrijpelijke termen:

🚀 Snelheid: De Boom wint

De "Boom-code" was ongeveer 10% sneller dan de "Sorteer-en-Sweep" methode.

• Analogie: Het is alsof je een boek zoekt in een bibliotheek. De "Sorteer-en-Sweep" methode is alsof je elke keer dat een boek verplaatst wordt, de hele catalogus opnieuw moet typen. De "Boom-code" is alsof je alleen het label op het specifieke plankje aanpast. Voor grote systemen wint de boom het.

💾 Het Geheugenprobleem (Cache)

Computers hebben een klein, supersnel geheugen (de "cache") en een groot, traag geheugen (de "RAM").

• Als de computer te veel data moet ophalen uit het trage geheugen, wordt hij traag.
• De "Boom-code" is slimmer in hoe hij data onthoudt. Hij gebruikt de snelle cache beter, vooral als de computer een modernere processor heeft (zoals de Apple M-chips die in de test werden gebruikt).
• Vergelijking: De "Sorteer-en-Sweep" methode loopt vaak vast omdat hij constant nieuwe data moet halen uit de "kelder" (het trage geheugen), terwijl de "Boom-code" zijn spullen netjes in de "werkruimte" (cache) houdt.

🧩 De Prijs: Complexe Code

Er is echter een prijs voor die snelheid.

• De "Boom-code" is veel ingewikkelder om te schrijven en te onderhouden.
• Analogie: De "Sorteer-en-Sweep" methode is als een simpele fiets: makkelijk te repareren, maar niet supersnel. De "Boom-code" is als een Formule 1-auto: hij gaat veel sneller, maar als er iets stukgaat, moet je een heel team mechanici hebben om het te fixen. De code is zo complex dat hij volgens strenge regels als "onbeheersbaar" zou worden gezien, maar voor deze specifieke simulaties is die complexiteit nodig om snel te zijn.

🛠️ Compileren vs. Interpreteren

De auteurs testten ook of het verschil in snelheid groter wordt als je de code "vertaalt" naar een snellere taal (C-code) in plaats van het in een trage taal (MATLAB) te laten draaien.

• Het resultaat: De vertaalde code was 8 tot 18 keer sneller.
• Vergelijking: Het is alsof je een boodschap eerst uitspreekt in een taal die de computer moet vertalen (traag), versus het direct schrijven in de taal die de computer begrijpt (snel).

---

3. Conclusie voor de Leek

Dit artikel zegt eigenlijk:

"Als je een simulatie hebt met veel deeltjes die bewegen (zoals zand in een draaiende trommel), is de 'Boom-code' de beste keuze. Hij is sneller en gebruikt het computergeheugen slimmer. Maar wees gewaarschuwd: het is een heel moeilijk stukje code om te bouwen en te begrijpen. Als je het niet nodig hebt (bijvoorbeeld bij heel weinig deeltjes), is de simpele 'Sorteer-en-Sweep' methode misschien makkelijker genoeg."

Kort samengevat:

• Sorteer-en-Sweep: De betrouwbare, simpele fiets. Goed voor kleine tochten.
• Boom-code: De snelle Formule 1-auto. Perfect voor lange, drukke ritten, maar lastig te onderhouden.

De auteurs raden de Boom-code aan voor grote, complexe simulaties, omdat de snelheidswinst de moeite van het complexe ontwerp ruimschoots waard is.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "Tree codes and sort-and-sweep algorithms for neighborhood computation: A cache-conscious comparison" in het Nederlands.

Titel: Tree-codes en sort-and-sweep-algoritmen voor buurtberekening: Een cache-bewuste vergelijking

Auteurs: Dominik Krengel, Yuki Watanabe, Ko Kandori, Jian Chen, Hans-Georg Matuttis.

---

1. Probleemstelling

In Discrete Element Method (DEM) simulaties is het berekenen van interacties tussen deeltjes (buurtberekening) vaak een prestatieknelpunt, vooral bij systemen met veel deeltjes. Traditionele methoden zoals Verlet-lijsten of gekoppelde cellen moeten vaak de volledige lijst van contacten bij elke tijdstap herbouwen of maken risicovolle aannames over de maximale verplaatsing van deeltjes.

De twee meest voorkomende geavanceerde methoden zijn:

1. Sort-and-sweep: Sorteert de extremale coördinaten (bounding boxes) van de deeltjes. Dit is efficiënt omdat het alleen deeltjes behandelt waarvan de relatieve positie in één coördinatenrichting verandert. Echter, alle richtingen moeten voor alle deeltjes worden verwerkt.
2. Tree-codes (Quadtree): Houdt rekening met alleen aangrenzende deeltjes via een hiërarchische ruimtelijke indeling.

Het artikel onderzoekt de prestaties van deze twee methoden, met name in de context van cache-geheugen. Traditionele complexiteitsanalyses (O(N) vs O(N log N)) negeren vaak de tijd die nodig is voor gegevensoverdracht tussen geheugen en CPU. In moderne architecturen kan een gebrek aan cache-efficiëntie leiden tot significante prestatieverlies door "cache misses", zelfs als het algoritme theoretisch efficiënt is.

2. Methodologie

De auteurs hebben een uitgebreide benchmark uitgevoerd om de prestaties van sort-and-sweep en tree-codes te vergelijken voor 2D DEM-simulaties van veelhoekige deeltjes in een roterende trommel (tot 12.000 deeltjes).

• Implementatie: De algoritmen zijn geïmplementeerd in MATLAB (interpreter) en gecompileerd naar C-code via "MATLAB Coder" om compiler-optimisaties te testen.
• Hardware: Tests zijn uitgevoerd op verschillende systemen met variërende cache-groottes en geheugentechnologieën:
  • Intel Xeon processors (DDR3 vs DDR4 geheugen).
  • Apple Silicon (M2 en M4 chips) met hun unieke P-cores (performance) en E-cores (efficiency) en verschillende cache-hierarchieën.
• Optimalisaties: Er is gekeken naar het effect van inlining (het direct in de aanroepende functie plaatsen van subfuncties) op de prestaties en de cyclomatische complexiteit.
• Specifieke aanpassingen: Voor de tree-code is een "minimale boom" (minimum tree) ontwikkeld waarbij celgroottes variëren, in tegenstelling tot eerdere methoden die alleen gelijke celgroottes gebruikten. Dit maakt het zoeken naar buren in lineaire tijd mogelijk. Grote deeltjes (zoals wanden) worden opgesplitst in kleinere bounding boxes om in de boom te passen.

3. Belangrijkste Bijdragen

• Cache-bewuste analyse: Het artikel benadrukt dat de prestatie van buurtalgoritmen niet alleen afhangt van het aantal operaties, maar sterk beïnvloed wordt door cache-misses en geheugenbandbreedte.
• Vergelijking van complexiteit: Het toont aan dat hoewel beide methoden theoretisch O(N) zijn voor updates, de tree-code in de praktijk efficiënter is door minder cache-belasting en betere parallelisatiemogelijkheden.
• Ontwikkeling van een "Minimale Tree": Een nieuwe implementatie van quadtree-codes die celgroottes dynamisch aanpast, wat leidt tot snellere zoekopdrachten vergeleken met eerdere Vemuri-achtige benaderingen.
• Analyse van Inlining: Het onderzoek toont aan dat inlining alleen voordelig is bij zeer grote systemen (>10.000 deeltjes) en dat dit ten koste gaat van de leesbaarheid en testbaarheid van de code (cyclomatische complexiteit).

4. Resultaten

• Prestatieverschil: De tree-code is over het algemeen sneller dan de sort-and-sweep methode. Voor de onderzochte systemen nam de tree-code ongeveer 90% van de CPU-tijd in beslag die nodig was voor sort-and-sweep.
• Update-tijd: Het bijwerken van de boomstructuur kostte slechts 1/10e van de tijd die nodig was voor het hersorteren in de sort-and-sweep methode.
• Invloed van Hardware:
  • Processoren met langere kloksnelheid maar langzamere geheugeninterface (DDR3) waren soms trager dan processoren met lagere kloksnelheid maar sneller geheugen (DDR4). Dit bevestigt dat geheugenbandbreedte en cache-grootte kritischer zijn dan pure kloksnelheid.
  • Apple M4-chips presteerden aanzienlijk beter dan Intel Xeon, vooral bij kleinere systemen, maar het voordeel nam iets af bij zeer grote systemen door bandbreedtebeperkingen.
• Effect van Inlining:
  • Voor kleine systemen (<5.000 deeltjes) gaf inlining geen voordeel of zelfs een nadeel door cache-overbelasting.
  • Voor grote systemen (>10.000 deeltjes) werd inlining efficiënter, maar de cyclomatische complexiteit steeg drastisch (van ~70 naar 273), wat de code "niet testbaar" maakt volgens software-engineering standaarden.
• Gecompiliteerde vs. Interpreteerde Code: Gecompiliteerde C-code (via MEX) was 8 tot 18 keer sneller dan de geïnterpreteerde MATLAB-code, vooral bij grotere systemen waar cache-efficiëntie belangrijker werd.

5. Betekenis en Conclusie

Het artikel concludeert dat tree-codes een superieur alternatief zijn voor sort-and-sweep in 2D DEM-simulaties met veel bewegende deeltjes, vooral vanwege:

1. Snellere updates: Minder tijd nodig voor het bijwerken van de datastructuur.
2. Beter parallelisatiepotentieel: De boomstructuur maakt fijnkorrelige parallelisatie mogelijk, terwijl sort-and-sweep beperkt is tot grove parallelisatie per richting.
3. Cache-efficiëntie: De boomstructuur vermindert het aantal cache-misses in vergelijking met het hersorteren van lijsten.

Nadelen: De prijs voor deze prestatiewinst is een aanzienlijk hogere cyclomatische complexiteit (moeilijk te onderhouden en testen code). Voor systemen met zeer grote deeltjesverdeling of langafstandsinteracties (zoals in SPH of MPS) zijn beide methoden minder geschikt vanwege de frequente wijzigingen in de buurtlijsten.

De studie biedt een waardevol inzicht voor ontwikkelaars van DEM-software: voor grote, dynamische systemen loont de moeite om de complexiteit van tree-codes te accepteren, mits de code goed wordt geoptimaliseerd (inlining, compilatie) en rekening wordt gehouden met de specifieke cache-architectuur van de gebruikte hardware.