Scalable parallel coset enumeration: bulk definition and the memory wall (Q697483): Difference between revisions

Die Autoren gehen davon aus, dass Ermittlung der Nebenklassen (coset) sehr großer Gruppen, welche definiert sind durch eine Menge generierender Relationen, mit Rechner-Algorithmen durch Parallelisierung im Zeitbedarf nur schwierig einzuschränken ist. Berichtet werden Ergebnisse ihrer Suche nach Zeitgewinn bringenden Verfahren und Verbesserungen bisher schon bekannter Vorschläge; Haupt-Basis ist das bekannte Tabellenverfahren von Todd und Coxeter (1936). Einleitend wird deren Prinzip kurz dargestellt und damit die Definitionen für alles Folgende präzise beschrieben. Als nächstes werden die bisher erkannten Schwierigkeiten beim Parallelisieren der Rechnerprogramme diskutiert, insbesondere die bei sehr großen Gruppen auftretenden Verzögerungen durch die bekannten Maschineneigenschaften bezüglich Speicherzugriff (latency) bei vielen\break gleichzeitig zugreifenden Prozessoren. Als Hauptteil folgt Erläuterung, wie durch gezielte heuristische Vorgehensweisen wesentlich mehr Parallelität für das Auffüllen der Nebenklassen-Tabelle bewirkt werden kann. Benutzt werden dazu Ergebnisse kürzlich erfolgter Publikationen der Autoren. Als Beispiel wird die Lyons-Gruppe vorgestellt, definiert durch 53 Relationen aus fünf Generator-Elementen -- die Tabelle hat dabei rund 1000 Spalten --; ferner andere Gruppen, welche bekanntermaßen mit schwieriger Parallelisierung behaftet sind. Ausführlich sind anhand von umfangreichen Messungen für diverse Ansätze wesentliche Algorithmus- und Maschinen-bedingte Einflüsse untersucht, welche die Laufzeit bestimmen, und ihre Ursachen genauer beschrieben, besonders die als ``bulk definition'' und ``memory wall'' bezeichneten, wie sie bei vielen gleichartigen Vorhaben auftreten. Bei Lyons-Gruppe ergab sich mit 64 Prozessoren eine mehr als dreifache Beschleunigung gegenüber Ein-Prozessor-Programmierung.