Preserving Clusters in Error-Bounded Lossy Compression of Particle Data

Probleemstelling

In wetenschappelijke toepassingen zoals kosmologie, moleculaire dynamica en fluïdynamica worden enorme datasets gegenereerd die vaak worden gecomprimeerd met foutgebonde verliesbeperking (lossy compression) om opslag- en I/O-kosten te verlagen. Bestaande compressoren (zoals SZ3, ZFP, Draco) garanderen alleen dat de positie van individuele deeltjes binnen een bepaalde foutmarge ($\xi$) blijft.

Het kritieke probleem is dat deze puntsgewijze foutgrenzen geen garantie bieden voor het behoud van clustering-structuren (bijvoorbeeld "Friends-of-Friends" of FoF in de kosmologie). Zelfs kleine verstoringen in de coördinaten kunnen leiden tot:

1. Het onbedoeld verbreken van verbindingen tussen deeltjes die dichter bij elkaar liggen dan de link-lengte ($b$).
2. Het onbedoeld creëren van valse verbindingen.
   Dit resulteert in een verkeerde clusterconnectiviteit, wat de wetenschappelijke validiteit van downstream-analyses (zoals het bepalen van de massa van donkere materie-halo's) ernstig kan ondermijnen. Bestaande oplossingen vereisen ofwel extreem strikte foutgrenzen (wat de compressieverhouding drastisch verlaagt) of het opslaan van extra metadata (cluster-toewijzingen), wat aanzienlijke opslagoverhead met zich meebrengt.

Methodologie

De auteurs stellen een correctiegebaseerde techniek voor die wordt toegepast op de ontcomprimeerde data van bestaande compressoren. De kern van de methode is het formuleren van het behoud van clusters als een beperkt optimalisatieprobleem.

1. Identificatie van Kwetsbare Paren:

   • De methode identificeert "kwetsbare" deeltjesparen: paren waarvan de oorspronkelijke afstand dicht bij de link-lengte $b$ ligt (binnen een straal van $b \pm 2\sqrt{3}\xi$).
   • Hiervoor wordt een ruimtelijke partitie (cell-based partitioning) gebruikt om de zoekruimte te beperken tot aangrenzende cellen, wat de complexiteit verlaagt van $O(N^2)$ naar $O(N \cdot \bar{\rho})$.

2. Beperkt Optimalisatieprobleem:

   • Het doel is om de coördinaten van de "bewerkbare" deeltjes (die deel uitmaken van kwetsbare paren) aan te passen zodat de connectiviteit wordt hersteld, terwijl de oorspronkelijke foutgrens $\xi$ strikt wordt gehandhaafd.
   • Een verliesfunctie (loss function) wordt gedefinieerd die boetert voor verbindingen die onterecht zijn verbroken of onterecht zijn gecreëerd.
   • De optimalisatie wordt opgelost met Projected Gradient Descent (PGD). Na elke gradiëntstap worden de coördinaten geprojecteerd terug naar de toegestane "box" (binnen de foutgrens $\xi$).

3. Veiligheidsmarge en Quantisatie:

   • Om fouten door quantisatie van de correcties te voorkomen, wordt de foutgrens tijdens de optimalisatie iets verkleind ($\xi' = \xi(1 - 2^{-m})$).
   • De uiteindelijke correcties worden gecomprimeerd als een bitmask (welke coördinaten zijn aangepast) en gekwantiseerde waarden, die vervolgens losslessly worden gecomprimeerd (Huffman + ZSTD).

4. Implementatie:

   • De algoritme is geïmplementeerd met GPU-versnelling en MPI-distributie voor schaalbaarheid op clusters.
   • Het ondersteunt zowel single-node systemen als multi-node MPI-omgevingen voor exascale-werklasten.

Belangrijkste Bijdragen

1. Nieuw Correctie-algoritme: Een methode die single-linkage clustering behoudt onder verliesbeperking, zonder de compressieverhouding van de basiscompressor significant te verlagen.
2. GPU en Gedistribueerde Parallelisme: Een schaalbare, data-parallelle solver die werkt op CPU en GPU clusters via MPI, met een focus op het minimaliseren van communicatie-overhead.
3. Uitgebreide Evaluatie: Rigoureuze validatie op datasets uit kosmologie (HACC), moleculaire dynamica (EXAALT) en fluïdynamica (FPM), vergeleken met state-of-the-art compressoren (SZ3, ZFP, Draco, LCP).

Resultaten

De experimenten tonen aan dat de methode zeer effectief is:

• Behoud van Clusters: De methode herstelt de FoF-clusterconnectiviteit bijna perfect. De Matthews Correlation Coefficient (MCC) voor het bestaan van verbindingen nadert 1,0, zelfs bij relatief hoge foutmarges waar standaard compressoren falen.
• Halo Mass Function (HMF): De statistische verdeling van halo-massa's (een cruciale metriek in de kosmologie) wordt nauwkeurig behouden, met een aanzienlijk lagere relatieve fout vergeleken met de basiscompressoren.
• Opslag-Overhead: De overhead voor het opslaan van de correcties is verwaarloosbaar (vaak < 1% extra opslag) en leidt tot een netto verbeterde effectieve compressieverhouding in vergelijking met het gebruik van extreem strikte foutgrenzen.
• Prestaties:
  • De GPU-implementatie bereikt een 62x snelheidswinst ten opzichte van de CPU-baseline.
  • De methode schaalt goed tot 1024 MPI-ranks (weak scaling) met een efficiency van 72,6%, hoewel communicatie en I/O op zeer grote schaal de beperkende factoren worden.
  • De doorvoersnelheid (throughput) is concurrerend met bestaande compressoren, vooral op datasets met een lage dichtheid van kwetsbare paren.

Betekenis en Impact

Dit werk lost een fundamenteel probleem op in de wetenschappelijke datacompressie: het compromis tussen compressie-efficiëntie en het behoud van structurele integriteit.

• Wetenschappelijke Validiteit: Het stelt onderzoekers in staat om verliesbeperkte compressie te gebruiken zonder de risico's van verkeerde wetenschappelijke conclusies door verbroken clusters.
• Efficiëntie: Het elimineert de noodzaak om ofwel near-lossless compressie te gebruiken (wat inefficiënt is) of enorme metadata-array's op te slaan.
• Schaalbaarheid: De implementatie is klaar voor exascale-computing, wat essentieel is voor toekomstige simulaties met biljoenen deeltjes.

Samenvattend biedt deze paper een robuuste, schaalbare oplossing die de integriteit van kritieke wetenschappelijke structuren (clusters) garandeert binnen de grenzen van verliesbeperkte compressie, waardoor de opslagkosten voor grote wetenschappelijke datasets drastisch kunnen worden verlaagd zonder in te leveren op de kwaliteit van de analyse.