Parallelisierung von Graphersetzungssystemen

Zusammenfassung:

In dieser Arbeit werden Parallelisierungskonzepte für Graphersetzungssysteme erarbeitet und das erste verfügbare parallele Graphersetzungssystem vorgestellt. Basierend auf den Eigenschaften von Rubini-Graphen wurde dazu ein neues Partitionierungsverfahren für Graphen entwickelt.

An einem Beispiel aus der Genetik wird gezeigt, dass die Graphersetzung den Anforderungen für moderne, kommerziell nutzbare Problemstellungen gewachsen ist. In den Testszenarien wurde durch die Parallelisierung die Leistung mehr als verdoppelt. Die Arbeit dient gleichermaßen als Fallstudie für die Anwendungsparallelisierung und beschreibt allgemeine Problemstellungen und Lösungsansätze, die auch in anderen Anwendungen auftreten können.   Bisher konnten Softwareentwickler darauf vertrauen, dass jede neue Prozessorgeneration ihre Leistung verdoppelte und damit alle Anwendungen ohne Änderungen am Programmcode schneller wurden. Diese Leistungssteigerung wurde hauptsächlich durch erhöhte Taktraten erzielt. Eine weitere Erhöhung der Taktraten ist praktisch nicht mehr handhabbar, da der Kühlungsaufwand zu hoch wird. Die Prozessorhersteller sind daher dazu übergegangen, bei unveränderter Taktrate mehrere Rechenkerne auf einem Chip unterzubringen. Eine Verdopplung der Rechenkerne entspricht theoretisch einer Verdopplung der Rechenleistung.   Um dieses Potenzial zu nutzen müssen Anwendungen jedoch parallelisiert, d.h. in mehrere Ausführungsfäden aufgeteilt sein. Dies ist derzeit nur bei wenigen Anwendungen der Fall. Die Parallelisierung von Anwendungen ist eine der größten gegenwärtigen Herausforderungen der Informatik: Die notwendige Abänderung bestehender Software ist äußerst komplex und fehleranfällig.   In der vorgestellten Arbeit wird gezeigt, wie Graphersetzungssysteme modifiziert werden können, um von Mehrkernarchitekturen zu profitieren.   Bei der Graphersetzung werden Graphen nach einem vorgegebenen Regelwerk verändert. Jede Regel definiert ein Suchmuster, das im Graphen zu finden ist, sowie eine Modifikation, die beim Auffinden einer Musterinstanz durchgeführt wird. Hierbei können beispielsweise Knoten entfernt oder Kanten bearbeitet werden. Ein System, welches diesen Vorgang unterstützt, wird als Graphersetzungssystem bezeichnet. Diese verbrauchen ein hohes Maß an Rechenoperationen. Die hohe Rechenlast hat bisher dazu geführt, dass Graphersetzung nur in wenige praktische Anwendungen außerhalb des akademischen Bereichs vorgedrungen ist.   In dieser Arbeit wird vorgeschlagen, den Graphen zum Zweck der parallelen Suche und Transformation zu partitionieren. Dazu wurde, basierend auf den Eigenschaften von Rubini-Graphen, ein neues Partitionierungsverfahren entwickelt: Entsprechend der gewünschten Anzahl an Gebieten werden zufällige, möglichst äquidistante Knoten des Graphen ausgewählt. Diese repräsentieren die Bezugspunkte. Anschließend wird jeder übrige Knoten einem Bezugspunkt zugeordnet. Als Metrik dient hierbei die Anzahl der Kanten, die bis zu den Bezugspunkten traversiert werden müssen. Jeder Bezugspunkt bildet mit den ihm zugeordneten Knoten eine Partition. Diese Rubini-Partitionierung lässt sich parallel ausführen. Hierbei wird nebenläufig von jedem Bezugspunkt ausgehend eine Breitensuche gestartet. Die Bezugspunkte finden somit selbst ihre zugehörigen Knoten.    

  Zur Validierung der in dieser Arbeit vorgestellten Parallelisierungskonzepte wurde das Graphersetzungssystem GrGen.NET parallelisiert. GrGen.NET wurde an der Universität Karlsruhe entwickelt und ist das derzeit schnellste verfügbare Graphersetzungssystem. Bei der Parallelisierung mussten erhebliche Änderungen an der Anwendungsarchitektur vorgenommen werden. Insbesondere die Wahl der Datenstrukturen war kritisch. Ferner enthält GrGen.NET Optimierungen, die entfernt und in veränderter Art wieder eingefügt werden mussten, um eine parallele Ausführung zu ermöglichen.   Die in dieser Arbeit entwickelte parallele Version von GrGen.NET stellt das erste mehrkernfähige Graphersetzungssystem dar. Bei Aufgaben wie der Suche nach großen Mustern konnte die Rechenzeit halbiert werden.   Obwohl diverse Anwendungsgebiete denkbar sind, wird die Graphersetzung bisher nur sporadisch eingesetzt. Ursächlich war bislang die unzureichende Ausführungsgeschwindigkeit bestehender Graphersetzungssysteme, als auch deren Einschränkung bezüglich der Zahl der verarbeitbaren Graphelemente.   In dieser Arbeit wird mit der Genetik ein Anwendungsfall von praktischer Relevanz beschrieben, der in besonderem Maße durch eine Parallelisierung profitiert. Es wird gezeigt, dass moderne Graphersetzungssysteme eine große Zahl von Graphelementen beherrschen können: Der Anwendungsfall verarbeitet mehr als 25 Millionen Graphelemente und belegt somit die Eignung von Graphersetzungssystemen für Aufgaben mit großen Datenmengen.   Genetiker benötigen in hohem Maße Unterstützung durch die Informatik: Sowohl analytische als auch simulative Anwendungen werden zur Verarbeitung und Auswertung der anfallenden Daten verwendet. Insbesondere die simulativen Ansätze sind jedoch noch weit davon entfernt, die genetischen Prozesse einer Zelle vollständig und korrekt umzusetzen. In dieser Arbeit wird die Simulation der Genexpression mit Hilfe der Graphersetzung verwirklicht. Bei einem Gen handelt es sich um einen zusammenhängenden Abschnitt auf der DNA eines Lebewesens, der den Aufbau, sozusagen den "Bauplan", eines Proteins enthält. Proteine wiederum sind die Bausteine von Körperzellen. Mit Genexpression wird der Prozess bezeichnet, der anhand eines Gens ein Protein erzeugt. Der Prozess gliedert sich in zwei Schritte: Bei der Transkription wird ein Gen kopiert, so dass es an anderer Stelle in der Zelle verwendet werden kann. Das Molekül, das diesen Bauplan repräsentiert, wird als RNA bezeichnet. Der zweite Schritt ist die Translation, bei der der kopierte Bauplan Schritt für Schritt von einem Enzym verarbeitet wird, wobei Aminosäuren entsprechend der Anweisungen der RNA zum fertigen Protein zusammengesetzt werden.   In der Arbeit wurde das Genom von Escherichia Coli (E.coli) gewählt. E. coli ist ein Bakterium, das Biologen als Modellorganismus dient und dessen genetischer Aufbau seit langem erforscht wird. Das Graphersetzungssystem ist in der Lage, Gene innerhalb des Genoms von Escherichia Coli zu finden und die zugehörigen Proteine zu „erzeugen“. Anhand von Gendatenbanken wie Ecocyc wurde überprüft, dass die die erzeugten Proteine aus den korrekten Aminosäuresequenzen bestehen. Zur Umsetzung der Genexpression wurden Graphersetzungsregeln entwickelt, die chemische Prozesse auf der DNA und zugehörigen Enzymen repräsentieren. Die DNA selbst wird als Kette von durch Kanten verbundene Knoten repräsentiert. Hierbei steht jeder Knoten für ein Nucleotid, die elementaren Bausteine der DNA. Bei der Verarbeitung von Escherichia Coli werden etwa 25 Millionen Graphelemente (Knoten & Kanten) verarbeitet.  

Kontakt: http://www.ipd.uka.de/Tichy/people.php?id=72