Parallelisierung von Graphenersetzungs-Systemen

  • Links:Diplomarbeit
  • Aktuelle Graphersetzungssysteme nutzen nur einen Ausführungsfaden. Das Leistungspotential von Mehrkernarchitekturen bleibt ihnen daher verschlossen. In dieser Arbeit werden sowohl das Parallelisierungspotential von Graphersetzungssystemen als auch Ansätze zur Implementierung aufgezeigt. Als Parallelisierungsstrategie wird hierbei, neben weiteren Konzepten, die Zerlegung von Graphen in Partitionen und die gleichzeitige Ausführung von Such- und Ersetzungsschritten beschrieben. Zur Validierung wird eine Implementierung der vorgestellten Parallelisierungskonzepte für das Graphersetzungssystem GrGen.NET durchgeführt. Des Weiteren wird mit der Genetik eine Anwendungsdomäne der Graphersetzung vorgestellt, die durch ihren hohen Bedarf an Rechenleistung in besonderem Maße durch eine Parallelisierung profitiert.