Ambros Marzetta. ZRAM: A Library of Parallel Search Algorithms and Its Use in Enumeration and Combinatorial Optimization. PhD thesis Nr. 12699, ETH Zürich. Abstract in English ZRAM Hauptseite

Kurzfassung

ZRAM ist eine Programmbibliothek, welche die Leistung paralleler Rechner dem Gebiet der kombinatorischen Optimierungs- und Aufzählungsalgorithmen zugänglich macht. Es enthält eine Sammlung paralleler Suchmaschinen für Branch-and-Bound, Reverse-Search und Backtracking sowie ein Werkzeug zur Grössenabschätzung von Suchbäumen. Die Schnittstelle der Bibliothek verbirgt die Komplexität der Parallelisierung vor dem Programmierer. ZRAM enthält die erste parallele Implementierung des Reverse-Search-Algorithmus und die erste parallele Branch-and-Bound-Maschine, die man unterbrechen und neu starten kann. Es enthält auch als erste Bibliothek paralleler Suchalgorithmen ein Werkzeug, das die Grösse von Suchbäumen abschätzt. Dieses Werkzeug dient dazu, die beschränkten Ressourcen an Rechenzeit den erfolgversprechendsten Berechnungen zuzuteilen. Die Kombination dieser Elemente und deren effiziente Implementierung ermöglichten es uns, grosse kombinatorische Optimierungs- und Aufzählungsprobleme zu lösen. Darunter sind bisher ungelöste Instanzen des quadratischen Zuordnungsproblems und die Aufzählung der Ecken hochdimensionaler Polyeder. Die Flexibilität von ZRAM zeigt sich im breiten Spektrum der Anwendungen (u.a. quadratisches Zuordnungsproblem, Aufzählung von Ecken und Facetten eines Polyeders, Arrangements von Hyperebenen, 15-Puzzle, euklidische Spannbäume, zusammenhängende Teilgraphen). Einige seiner Anwender hatten wenig oder gar keine Erfahrung mit parallelem Programmieren und bekamen erst dank ZRAM Zugang zu Parallelrechnern. Anhand von ZRAM haben wir gezeigt, was für Anforderungen an eine Bibliothek paralleler Suchalgorithmen zu stellen sind und dass eine Strukturierung in die vier Schichten Anwendung, Suchmaschinen, virtuelle Maschine und Systemanpassung sinnvoll ist.