Stuttgart, Univ., Studienarb., 1998.

Stuttgart, Univ., Diplomarb., 1998.

Unser Forschungsvorhaben hat die Entwicklung, Analyse und Implementierung von Partitionierungsalgorithmen für industrierelevante Modelle kompletter Prozessorstrukturen mit mehreren Millionen Elementen auf der Gate-Ebene in Vorbereitung der parallelen zyklusbasierten Logiksimulation zum Ziel. Dabei verkörpern die von uns auf Basis der sequentiellen Simulatoren TEXSIM und MVLSIM entwickelten Simulatoren parallelTEXSIM, parallelMVLSIM und der im Berichtszeitraum realisierte dlbSIM das unmittelbare Anwendungsfeld. Aufbauend auf dem im bisherigen Projektverlauf entstandenen formalen Modell der parallelen Simulation, der hierarchichen Partitionierungsstrategie sowie den in diesem Rahmen entwickelten Partitionierungsalgorithmen konzentrierten wir uns in der laufenden Arbeit auf die Erweiterung des Parametrisierungskonzepts für Partitionierungsalgorithmen und die Beschleunigung der Partitionierung durch deren Parallelisierung.

Die vorliegende Arbeit untersucht Möglichkeiten der Parallelisierung von Evolutionären Algorithmen, welche hier zur Partitionierung von Daten füur die parallele Logiksimulation benutzt werden. Neben einer allgemeinen Einführung in Grundbegriffe und Methoden von Evolutionären Algorithmen, Parallelverarbeitung, Logiksimulation und Datenpartitionierung wird das im Rahmen dieser Diplomarbeit entwickelte Programmpaket pga vorgestellt, sowie auf die darin benutzten Parallelisierungsmethoden und Kommunikationsstrukturen eingegangen.

Eine sehr häufig benutzte Gruppe von Partitionierungsverfahren im VLSI-Design sind die Iterative Improvement Algorithms. Diese Verfahren lösen das Min-Cut Problem für Graphen bzw. Hypergraphen. Dabei soll der Graph bzw. Hypergraph in möglichtst unabhängige Teile aufgeteilt werden. Der Ausgangspunkt bei den Iterative Improvement Algorithms ist eine Anfangspartition, die sukzessiv durch geringfügige Änderungen verbessert wird. Mit diesen Verfahren können sehr gute Partitionen in einer sehr geringen Zeit erzeugt werden. In dieser Diplomarbeit wird die Anpassung der Iterative Improvement Algorithms auf die Partitionierung für die parallele Logiksimulation vorgestellt. Dabei wurden verschiedene Strategien für eine Anpassung der Iterative Improvement Algorithms untersucht.

Der Entwurf komplexer VLSI-Strukturen erfordert eine durchgängige Begleitung durch Verifikationsprozesse. eine Hauptform der Entwurfsverifikation ist die Simulation. Im Rahmen der Systemsimulation kompletter Prozessorstrukturen auf Register-Transfer-/Gate-Ebene (Logiksimulation verkörpern die Test-Cases (Stimuli Microcode- bzw. Maschinencode-Sequenzen. Bei entsprechenden Simulationsläufen kann das Verhältnis der Simulationslaufzeit zur simulierten CPU-Zeit bis zu 7 Größenordnungen betragen. Um interessierende Simulationen (z. B. Laden eines Beriebssystems, Benchmarks, ...) im Rahmen vernünftiger Entwicklungszeiten realisieren zu können, ist eine entscheidende Beschleunigung der Logiksimulation erforderlich. Ein Weg in diese Richtung besteht in ihrer Parallelisierung. Ausgangspunkt für die Konzipierung unseres DFG-Projekts ist die Parallelisierung des auf Basis des clock-cycle Algorithmus arbeitenden funktionellen Logiksimulators TEXSIM für lose gekoppelte Prozessorsysteme unter Ausnutzung der modellinhärenten Parallelität. Dabei wird von einer statistischen Partitionierung vorliegender Modelle zur Festlegung der Modellteile ausgegangen, die auf den einzelnen, in die parallele Simulation einbezogenen Prozessoren behandelt werden.

Die enorme Komplexität in naher Zukunft absehbarer VLSI-Schaltkreisentwicklungen bedingt auf allen Entwurfsebenen sehr zeitintensive Simulationsprozesse. Eine Antwort auf diese Herausforderung besteht in der Parallelisierung dieser Prozesse. Es wird ein Forschungsvorhaben vorgestellt, welches auf eine effektive Partitionierung von Modelldatenstrukturen im Vorfeld compilergesteuerter Logiksimulationen auf Parallelrechnern mit lose gekoppelten Prozessoren gerichtet ist. Im Rahmen dieses Projekts sollen ausgehend von einem Graphen-Modell Partitionierungsalgorithmen entwickelt, theoretisch untersucht sowie Kriterien für ihren Einsatz in Abhängigkeit von anwendungstypischen Modelleigenschaften abgeleitet werden. Zur experimentellen Unterstützung ist die Entwicklung einer parallel arbeitenden Testumgebung für die Analyse relevanter Modelldatenstrukturen vorgesehen. Eine Erweiterung dieser Umgebung zu einer Softwarekomponente, welche im Ergebnis eines Präprocessing von Modelldatenstrukturen Partitionierungsalgorithmen auswählt und realisiert, soll schließich in ein System zur Logiksimulation auf der Basis parallel arbeitender Instanzen eines der führenden heute kommerziell verfügbaren funktionellen Logiksimulatoren eingebunden werden.

Eine wichtige Form der Verifkation von komplette Prozessorstrukturen umfassenden VLSI-Entwürfen stellt die funktionelle Logiksimulation auf Gatter- und Register-Ebene dar. Im Kontext der Entwicklung eines parallelen Logiksimulationssystems auf Basis des nach dem clock-cycle-Algorithmus arbeitenden funktionellen Simulators TEXSIM (IBM) ist die der parallelen Simulation vorangehende Modellpartitionierung Gegenstand der Betrachtung. Ausgehend von einem strukturellen Hardware-Modell wird auf der Basis des Cone-Begriffs ein zweistufiger hierarchischer Partitionierungsansatz im Rahmen einer k-stufigen Strategie vorgestellt. Dieser Ansatz gibt Untersuchungen zur Kombination von Algorithmen Raum. Ein Superpositionsprinzip für Partitionen gestattet die Verschmelzung der Resultate von Partitionierungsverfahren einer Hierarchiestufe. Mit dem Backward-Cone-Concentration-Algorithmus (n-BCC) und dem Minimum-Overlap-Cone-Cluster-Algorithmus (MOCC) werden im Rahmen unseres bottom-up-Partitionierungsansatzes zwei neue Modellpartitionierungsverfahren eingeführt.