Consideration of local structures in hierarchical partitioning of integrated circuit netlists modelled by hypergraphs

Die vorliegende Arbeit befasst sich mit der hierarchischen Partitionierung von Hypergraphen, die im Prozess der Chipentwicklung durch Netzlisten einer integrierten Schaltung entstehen. Das Problem der Partitionierung ist dabei NP-schwer, sodass Heuristiken für die entsprechende Partitionierung verwendet werden. Erschwerend kommt hinzu, dass die Hypergraphen meist eine große Ordnung, mehr als 105 Knoten, aufweisen. Ziel dieser Arbeit ist es, ein Modell für eine derartige Partitionierung zu erstellen, welches Resultate aus vorangegangenen Arbeiten berücksichtigt und die Platzierung der Elemente des integrierten Schaltkreises im Fokus hat. Des Weiteren wird die Tauglichkeit vorhandener Algorithmen auf die erwähnte Modellierung geprüft, weiter werden vorhandene Algorithmen modifiziert und eigene Algorithmen konzipiert. Dabei wird darauf geachtet, dass die Algorithmen auf Hypergraphen mit großer Ordnung anwendbar sind. Diese Algorithmen werden dazu auf Hypergraphen des Benchmarks "ISPD 05/06" angewandt.