Scalable parallel coset enumeration: bulk definition and the memory wall
type: Item
instance of: scholarly article
title: Scalable parallel coset enumeration: bulk definition and the memory wall
zbMATH Open document ID: 1017.20021
author: Gene Cooperman
author: V. S. Grinberg
published in: Journal of Symbolic Computation
publication date: 2002-09-17T00:00:00Z
review text: 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.
reviewed by: K. G. Brokate
Mathematics Subject Classification ID: 20F05
Mathematics Subject Classification ID: 68W10
Mathematics Subject Classification ID: 20D08
Mathematics Subject Classification ID: 20-04
Mathematics Subject Classification ID: 68W30
zbMATH DE Number: 1801673
zbMATH Keywords: parallel coset enumeration
zbMATH Keywords: bulk definition
zbMATH Keywords: memory wall
zbMATH Keywords: Todd-Coxeter coset enumeration
zbMATH Keywords: parallelization
zbMATH Keywords: Lyons sporadic group
zbMATH Keywords: algorithms
describes a project that uses: STAR/MPI
describes a project that uses: ParGAP
describes a project that uses: TOP-C
MaRDI profile type: Publication
full work available at URL: jsco.2002.0523
OpenAlex ID: W2016054777
cites work: On doing Todd-Coxeter coset enumeration in parallel
cites work: Q4227329
cites work: Q3684301
cites work: A note on the Todd-Coxeter coset enumeration algorithm
cites work: Implementation and Analysis of the Todd-Coxeter Algorithm
cites work: Parallel GAP: Mature interactive parallel computing
cites work: Q4531745
cites work: Q3241233
cites work: Programmierung der Restklassenabzählung einer Gruppe nach Untergruppen
cites work: Parallel coset enumeration using threads
cites work: Q4270319
cites work: Q3682657
cites work: Q3950713
cites work: Q5183705
cites work: A practical method for enumerating cosets of a finite abstract group
DOI: 10.1006/JSCO.2002.0523
description: scientific article; zbMATH DE number 1801673