Umfang

Dieses Thema eignet sich als Bachelorarbeit.

Empfohlene Vorkenntnisse

  • gute C Kenntnisse

Problem

Eine sehr spannende Datenstruktur ist HAMT. Diese Hash Tries implementieren assoziativen Speicher (lies: Maps, dicts, …), sind jedoch minimal langsamer als Hash Maps, benötigen dafür in der Regel weniger Speicher.

Im verteilten Model Checking verwenden wir eine Variante vom Hash Trie, die im Shared Memory liegt. Dort werden zur Synchronisation Locks verwendet. Da wir aber nur Key-Value Paare einfügen oder Werte updaten, jedoch nie Schlüssel entfernen, ist eine Implementierung via compare-and-swap möglich.

Eine mögliche Implementierung wird in diesem Artikel beschrieben. Jedoch wird dort angenommen, dass ein Garbage Collector für den Shared Memory vorhanden ist. In unserem Anwendungsfall sind alle Prozesse durchnummeriert und eine maximale Anzahl zur compile-time bekannt. Dadurch kann man auf den Garbage Collector verzichten, wenn man stattdessen reference counting implementiert.

Minimalanforderungen

  • Implementierung eines lock-free Hash Tries. Dazu kann auf bereits vorhandenem Code aufgebaut werden.

Erweiterungen

  • Überarbeiten der bisherigen Shared Memory Implementierung des Hash Tries.
  • Extraktion eines Hash Tries, der nur im lokalen, Prozess-eigenen Speicher arbeitet.

Kontakt

Philipp Körner
Raum 25.12.02.56
p.koerner@hhu.de