Zusammenfassung - Stundenglas- Sorting: Ein neuer paralleler Sortieralgorithmus und seine Implementierung

Stundenglas- Sorting: Ein neuer paralleler Sortieralgorithmus und seine Implementierung

2025-07-22 08:08:29

{"Daniel Bascones","Borja Morcillo"}

{cs.AR,B.5.0}

Stundenzeiger-Sortierung ist ein neuer paralleler Sortieralgorithmus, der entwickelt wurde, um große Datensätze mit parallelem Eingang und serieller Ausgabe effizient zu sortieren. Er erreicht eine Latenz von log(n) für die Ausgabe des ersten Elements und eine Gesamtsortierzeit von n + log(n). Dieser Algorithmus ist besonders nützlich für Anwendungen, die eine schnelle Sortierung großer Datensätze erfordern, wie z.B. das Quanten-LDPC-Dekodieren. Der Stundenzeiger-Sortieralgorithmus basiert auf einer baumartigen Struktur von Vergleichsgeräten, wobei jeder Knoten zwei Ausgaberegister hat, um den "Schwimmeffekt" zu vermeiden, der in traditionellen Sortieralgorithmen auftreten kann. Dies ermöglicht es dem Algorithmus, eine konstante kritische Länge im Verhältnis zur Eingröße aufrechtzuerhalten, was zu einem sehr skalierbaren Design führt. Der Algorithmus wurde in einem FPGA implementiert und erfolgreich in eine BP-OSD (Glaubenswahrscheinlichkeitsverbreitung - Geordnete Statistik-Dekoder)-Implementierung für das Quanten-LDPC-Codieren integriert. Diese Implementierung zeigt die Fähigkeiten des Algorithmus in realen Anwendungsfällen, wie z.B. der Echtzeitdekodierung korrekturcodierter Informationen. Hauptmerkmale des Stundenzeiger-Sortieralgorithmus sind: - O(n) Hardware-Komplexität - Latenz von log(n) für die Ausgabe des ersten Elements - Gesamtsortierzeit von n + log(n) - Skalierbares Design mit konstanter kritischer Länge - Effizient für die Sortierung großer Datensätze mit parallelem Eingang und serieller Ausgabe Der Stundenzeiger-Sortieralgorithmus stellt eine bedeutende Weiterentwicklung in den parallelen Sortieralgorithmen dar und bietet eine hoch effiziente und skalierbare Lösung für Anwendungen, die eine schnelle Sortierung großer Datensätze erfordern.