# Implementierungsplan: parallele Konvertierungspipeline

## Ziel

MapTools Converter soll große OSM-PBF-Quellen auf Mehrkernsystemen deutlich schneller in
Mapsforge-`.map` und `.poi` umwandeln. Die Standardausgabe bleibt vollständig kostenlos,
offline, reproduzierbar und ohne zusätzliche Installation. Eine optionale CUDA-Beschleunigung
wird erst nach einer CPU-Baseline als austauschbares Plugin untersucht.

Die bestehende Osmosis-/Mapsforge-Pipeline bleibt während der Entwicklung als Referenz und
Fallback erhalten. Eine neue Pipeline wird erst Standard, wenn ihre Ausgabe semantisch gleichwertig
validiert ist.

## Aktueller Erkenntnisstand

- OSM-PBF besteht aus unabhängig dekomprimierbaren Fileblocks. Ein `OSMData`-Block enthält einen
  eigenen `PrimitiveBlock` samt Stringtabelle und kann deshalb parallel dekodiert werden.
- Die Reihenfolge Nodes → Ways → Relations erzeugt globale Abhängigkeiten. Dekomprimieren und
  Dekodieren sind parallelisierbar; Referenzauflösung und Multipolygon-/Küstenlogik benötigen
  definierte globale Barrieren.
- Mapsforge-Format 5 besteht aus einem Header, Zoomintervall-Subdateien, festen Kachelindexeinträgen
  und variablen Kachelnutzdaten. Kacheln können parallel vorbereitet werden, aber Offsets,
  Subdateigrößen und der finale Header müssen deterministisch zusammengeführt werden.
- Der offizielle Mapsforge-Writer parallelisiert bereits die Weg-Geometrievorbereitung, wenn der
  Parameter `threads` größer als 1 ist. MapTools setzt dafür künftig automatisch bis zu acht Threads.
  Einlesen, globale Topologie und endgültiges Schreiben bleiben im vorhandenen Writer weitgehend seriell.
- Der gemessene RAM-Modus verkürzte den Map-Schreibanteil des 15,9-MiB-Hessen-Ausschnitts von
  ungefähr 188 auf 10,8 Sekunden. Der vollständige räumliche PBF-Zuschnitt ist damit der nächste
  relevante Engpass.

## Zielarchitektur

```text
PBF-Datei
  ↓ sequenzieller Blockindex (Offsets, Größen, Typ, Reihenfolge)
begrenzte Block-Batches
  ↓ parallele Dekompression + PrimitiveBlock-Dekodierung
versioniertes Zwischenformat (Nodes, Ways, Relations, Tagstatistik)
  ↓ globale Referenzauflösung und Topologiebarriere
räumliche Feature-Shards
  ↓ paralleles Clipping, Vereinfachen, Tag-Mapping, Kachelzuordnung
fertige Kachelnutzdaten je Zoomintervall
  ↓ serieller, deterministischer Finalizer
Mapsforge .map

POI-Kandidaten aus dem Zwischenformat
  ↓ parallele Klassifikation + begrenzte Schreibwarteschlange
ein SQLite-/Mapsforge-POI-Writer
  ↓
Mapsforge .poi
```

### Zwischenformat `MTCI`

Kein Java-Objektstream und keine externe Datenbank wird vorausgesetzt. Das Arbeitsverzeichnis enthält:

- `manifest.json`: Schema-Version, Quellfingerabdruck, Quellgröße/-zeit, Grenzen, Inhaltsprofil,
  Writer-Version, Anzahl Shards und Prüfsummen
- `nodes-*.mtcn`: sortierte ID-, Koordinaten- und relevante Tagdatensätze
- `ways-*.mtcw`: Way-ID, Node-Referenzen, Tags und nach Auflösung die geografische Bounding Box
- `relations-*.mtcr`: Mitglieder, Rollen, Tags und Auflösungsstatus
- `features-z*-*.mtcf`: räumlich partitionierte, writer-neutrale Feature-Kandidaten
- `tiles-z*-*.mtct`: bereits serialisierbare Nutzdaten pro Kachelbereich

Die Dateien verwenden explizit dokumentierte Integergrößen, Byte-Reihenfolge und Längenfelder.
Jeder Shard wird zunächst als `.partial` geschrieben, mit SHA-256 abgeschlossen und dann atomar
umbenannt. Ein abgebrochener Auftrag kann nur vollständig validierte Shards wiederverwenden.

Es werden Kachelbereiche statt einzelner Dateien pro Kachel verwendet, damit auch Deutschland- oder
Europa-Exporte nicht an Dateihandle- und Dateisystemgrenzen stoßen.

## Arbeitsblöcke und Checkliste

### P0 – Baseline und Messbarkeit

- [x] bestehende Hessen-Messwerte dokumentieren
- [x] RAM-/HD-Umschaltung für kleine beziehungsweise große Eingaben einführen
- [x] vorhandene Mapsforge-Mehrkernoption mit maximal acht Threads aktivieren
- [x] phasenbezogenen Fortschrittsbalken und Prozentwerte anbinden
- [ ] reproduzierbaren End-to-End-Benchmark für 0,5 %, 2,5 %, 25 % und 100 % Hessen erstellen
- [ ] CPU-Zeit, Wall-Clock, Heap, GC, gelesene/geschriebene Bytes und temporären Speicher erfassen
- [ ] Java Flight Recorder für Parser, Auflösung und Writer getrennt auswerten

Abnahme: Jede Optimierung wird gegen dieselben Eingaben und Inhaltsprofile gemessen; Ergebnisse landen
maschinenlesbar als JSON und lesbar in `documentation/performance.md`.

### P1 – Paralleler PBF-Blockdecoder

- [x] vorhandenen Blockindex als alleinigen sequenziellen Reader nutzen
- [x] feste Anzahl Block-Batches mit Backpressure einführen
- [ ] ZLIB-, RAW-, LZ4- und ZSTD-Blobs in einem begrenzten CPU-Pool dekomprimieren
- [x] ZLIB- und RAW-Blöcke in einem begrenzten CPU-Pool verarbeiten
- [x] `PrimitiveBlock` unabhängig und parallel dekodieren
- [x] Ergebnisse mit Blocksequenznummern deterministisch an den nächsten Verarbeitungsschritt übergeben
- [ ] Puffer wiederverwenden und maximale Blobgrößen vor Allokationen prüfen
- [ ] beschädigte, übergroße und abgebrochene Batches testen

Best Practice: Anzahl CPU-Worker standardmäßig `max(1, logische Kerne - 1)`, konfigurierbar und auf
16 begrenzt. Eine beschränkte Warteschlange verhindert, dass ein schneller Decoder den RAM füllt.

Abnahme: Vollständiges Dekodieren der Hessen-PBF ist mindestens 2,5-mal schneller als der aktuelle
Osmosis-Zuschnitts-Parser, bleibt deterministisch und überschreitet das festgelegte Speicherbudget nicht.

### P2 – ID-Shards und Referenzauflösung

- [x] versionierte Node-, Way- und Relation-Shards mit festen Binärheadern schreiben
- [x] Shards stabil nach ID partitionieren und Tags deterministisch serialisieren
- [x] Manifest, Dateigrößen und SHA-256-Prüfsummen erzeugen
- [x] vollständige Shardverzeichnisse atomar abschließen und Abbruchreste bereinigen
- [x] räumliche Primärnodes sowie zugehörige Ways bestimmen
- [x] Relationsabhängigkeiten schließen und fehlende Mitglieder regionaler Extrakte protokollieren
- [x] ausgewählte Shards materialisieren und sämtliche Referenzen unabhängig validieren
- [x] standardkonforme OSM-PBF direkt aus MTCI schreiben und mit Mapsforge 0.29 prüfen
- [ ] Nodes nach stabiler ID-Partition in sortierte Shards schreiben
- [x] Ways und Relations zunächst als kompakte Referenzdatensätze speichern
- [ ] externe Sortierung mit begrenzten Speichersegmenten implementieren
- [ ] Node-Koordinaten für Ways blockweise auflösen
- [ ] Way-Bounding-Boxen berechnen und räumlich irrelevante Ways verwerfen
- [ ] Relation-Mitglieder und Rollen auflösen
- [ ] Zyklen, fehlende Mitglieder und sehr große Relationen begrenzen und protokollieren

Abnahme: Der gewählte Ausschnitt enthält dieselben referenziell benötigten Nodes, Ways und Relations
wie der bestehende Osmosis-Referenzexport.

### P3 – Globale Topologie

- [ ] Multipolygone vor der Kachelverteilung vollständig zusammensetzen
- [ ] innere/äußere Ringe, Rollen und ungültige Geometrien behandeln
- [ ] Küstenlinien und vollständig von Wasser bedeckte Kacheln global bestimmen
- [ ] Labelpositionen und implizite Way-Relationen kompatibel zu Mapsforge berechnen
- [ ] Topologieergebnisse als unveränderliche Feature-Shards abschließen

Abnahme: Wasserflächen, administrative Grenzen, Gebäude-Multipolygone und Küstenlinien stimmen in
definierten visuellen und strukturellen Testgebieten mit dem Referenzwriter überein.

### P4 – Parallele Kachelvorbereitung

- [ ] globale Tagtabellen vor Beginn der Kachelworker einfrieren
- [ ] Features je Zoomintervall und Kachelbereich partitionieren
- [ ] Clipping, Vereinfachung, Subtile-Bitmap und Delta-/Double-Delta-Auswahl parallel ausführen
- [ ] POIs und Ways je Zoomstufe stabil nach OSM-ID und Writerregeln sortieren
- [ ] pro Kachel Zoomtabelle, POI-Block und Way-Block vorserialisieren
- [ ] Work-Stealing nur innerhalb einer Phase verwenden; Ausgabe bleibt über Kachelschlüssel geordnet
- [ ] übergroße Kacheln und 39-Bit-Offsetgrenzen explizit prüfen

Abnahme: Ein erneuter Lauf mit gleicher Quelle und Konfiguration erzeugt identische Kachel-Shard-
Prüfsummen, unabhängig von Threadanzahl und Fertigstellungsreihenfolge.

### P5 – Mapsforge-Format-5-Finalizer

- [ ] Writer für Header und globale POI-/Way-Tagtabellen implementieren
- [ ] Subdateien in Zoomintervallreihenfolge erzeugen
- [ ] Kacheln strikt zeilenweise schreiben und 5-Byte-Indexeinträge berechnen
- [ ] Wasserflag, leere Kacheln und identische Folgeoffsets korrekt setzen
- [ ] Subdateistart/-größe und endgültige Dateigröße im Header nachtragen
- [ ] Finalizer streamend und ohne vollständige Ausgabedatei im RAM betreiben
- [ ] atomaren Abschluss und Wiederanlauf pro Subdatei vorsehen

Abnahme: Mapsforge Reader 0.29 öffnet jede erzeugte Datei; Grenzen, Startposition, Zoomintervalle,
Tags und Objektzählungen entsprechen der Referenz. Zusätzlich werden Stichproben in MapTools gerendert.

### P6 – Parallele POI-Pipeline

- [ ] POI-Kandidaten bereits beim PBF-Dekodieren markieren
- [ ] Kategorie-/Tag-Mapping parallel vorbereiten
- [ ] Datensätze räumlich sharden und stabil sortieren
- [ ] einen einzelnen gebatchten Datenbankwriter mit Transaktionen verwenden
- [ ] optional mehrere temporäre POI-Datenbanken evaluieren und deterministisch zusammenführen
- [ ] `.poi` mit Mapsforge-Reader und SQL-Integritätsprüfungen validieren

Hinweis: SQLite besitzt nur einen Writer zur selben Zeit. Parallelisiert werden Dekodierung,
Klassifikation und Vorbereitung; der Commitpfad erhält eine begrenzte Eingabewarteschlange.

### P7 – Fortschritt, Abbruch und Wiederaufnahme

- [x] Blockscan, Cacheaufbau, Auswahl, Materialisierung und PBF-Ausgabe als getrennte UI-Phasen melden
- [x] validen MTCI-Quellcache anhand des SHA-256-Fingerabdrucks wiederverwenden
- [x] bei Fehlern automatisch auf die bestehende Osmosis-Pipeline zurückfallen
- [ ] Gesamtfortschritt aus gewichteten Arbeitseinheiten statt geschätzter Zeit berechnen
- [ ] Blöcke, Objekte, Shards und Kacheln als echte Nenner verwenden
- [ ] Phase, Prozent, Laufzeit, Durchsatz, aktive Worker und Restarbeit anzeigen
- [ ] Abbruch kooperativ durch alle Warteschlangen propagieren
- [ ] abgeschlossene Shards nach Manifestprüfung wiederverwenden
- [ ] veraltete oder inkompatible Zwischenstände automatisch erkennen

Abnahme: Der Fortschritt ist monoton, erreicht nur bei validiertem Ergebnis 100 % und ein Wiederanlauf
nach Abbruch überspringt nachweisbar abgeschlossene Arbeit.

### P8 – Optionaler CUDA-/GPU-Proof-of-Concept

- [x] austauschbare Dekompressions-API mit ServiceLoader und sicherem CPU-ZLIB-Fallback einführen
- [x] CUDA-Laufzeitkandidaten erkennen, ohne eine CUDA-Installation vorauszusetzen
- [ ] zuerst mit JFR belegen, dass Dekompression mindestens 25 % der CPU-Laufzeit beansprucht
- [ ] NVIDIA-GPU, Treiberversion, verfügbaren Gerätespeicher und nvCOMP-Unterstützung erkennen
- [ ] JNI-Brücke als optionales, separat ladbares Modul kapseln
- [ ] ZLIB/Deflate-Blobs in Batches an nvCOMP übergeben
- [ ] gepinnte Hostpuffer und mindestens zwei CUDA-Streams zum Überlappen von I/O, Transfer und
  Dekompression evaluieren
- [ ] CPU-Fallback pro Batch und für Systeme ohne NVIDIA-GPU garantieren
- [ ] Übertragungszeit, Batchgröße und Energieverbrauch gegen paralleles CPU-ZLIB messen
- [ ] CUDA-/nvCOMP-Lizenz- und Distributionsbedingungen vor einer Bündelung prüfen
- [ ] Plugin bei Fehlern vollständig deaktivierbar halten

Nicht für die GPU vorgesehen sind Protobuf-Objektaufbau, ID-Joins, Relationstopologie, JTS-Clipping,
variable Mapsforge-Codierung und der finale Dateiwriter. Diese Arbeit ist verzweigt, speicherindirekt oder
seriell und würde meist mehr Transferkosten als Nutzen verursachen.

Go/No-Go-Kriterium: GPU-Unterstützung wird nur weitergeführt, wenn sie auf einer handelsüblichen
NVIDIA-GPU den gesamten End-to-End-Auftrag um mindestens 20 % beschleunigt. Ein schnellerer isolierter
Deflate-Mikrobenchmark genügt nicht.

### P9 – Integration und Freigabe

- [ ] Feature-Flag `parallelPipeline` bis zur vollständigen Abnahme beibehalten
- [ ] automatische Referenzvergleiche alte gegen neue Pipeline ausführen
- [ ] Windows- und Linux-x64-Pakete ohne GPU-Abhängigkeit erzeugen
- [ ] optionales CUDA-Modul getrennt paketieren
- [ ] Hessen-, Deutschland- und synthetische Grenzfalltests abschließen
- [ ] Speicherprofile für 4-, 8-, 16- und 32-Kern-Systeme dokumentieren
- [ ] Zwischenformat und Mapsforge-Finalizer formatstabil dokumentieren

## Reihenfolge und Entscheidungstore

1. P0 und P1 zuerst: Sie liefern Messbarkeit und einen wiederverwendbaren parallelen Decoder.
2. P2 und P3 vor Kachelparallelisierung: Ohne korrekte globale Referenzen entstehen stille Kartenfehler.
3. P4 und P5 gemeinsam als CPU-Prototyp: Erst danach kann der alte Writer ersetzt werden.
4. P6 kann nach stabilem Zwischenformat parallel zu P4/P5 entwickelt werden.
5. P7 vor öffentlicher Aktivierung.
6. P8 erst nach Profildaten der fertigen CPU-Pipeline.
7. P9 ersetzt den bestehenden Fallback erst nach bestandener Gleichwertigkeitsprüfung.

## Leistungsziele

- Hessen, kleiner Ausschnitt: mindestens Faktor 3 gegenüber dem bisherigen End-to-End-Ablauf
- CPU-Auslastung in parallelen Phasen: durchschnittlich mindestens 60 % der verfügbaren logischen Kerne
- serieller Finalizer: höchstens 15 % der End-to-End-Laufzeit
- Standard-Speicherbudget: automatisch, maximal 25 % des physischen RAMs und ohne manuelle Einrichtung
- keine große Quelle und keine vollständige `.map` gleichzeitig im Heap
- deterministische semantische Ausgabe bei 1, 2, 4, 8 und 16 Worker-Threads
- jederzeit funktionsfähiger CPU-Fallback ohne CUDA, Zusatzinstallation oder Internetzugriff

## Quellen und Formatgrundlagen

- [OpenStreetMap OSM-binary](https://github.com/openstreetmap/OSM-binary)
- [OpenStreetMap PBF-Format](https://wiki.openstreetmap.org/wiki/PBF)
- [Mapsforge Binary Map File Specification](https://github.com/mapsforge/mapsforge/blob/master/docs/Specification-Binary-Map-File.md)
- [Mapsforge Map-Writer Optionen](https://github.com/mapsforge/mapsforge/blob/master/docs/Getting-Started-Map-Writer.md)
- [Mapsforge MapFileWriter](https://github.com/mapsforge/mapsforge/blob/master/mapsforge-map-writer/src/main/java/org/mapsforge/map/writer/MapFileWriter.java)
- [NVIDIA nvCOMP](https://docs.nvidia.com/cuda/nvcomp/)
- [NVIDIA CUDA Asynchronous Execution](https://docs.nvidia.com/cuda/cuda-programming-guide/02-basics/asynchronous-execution.html)
- [NVIDIA CUDA Best Practices](https://docs.nvidia.com/cuda/cuda-c-best-practices-guide/)
