next up previous
Next: Die Parallelisierung Up: PVM auf MPPs Previous: PVM auf MPPs

Eine einfache Anwendung

 
Figure: Ein Floorplan für einen Chip mit 25 Modulen

Als Anwendungsbeispiel dient ein Optimierungsproblem, welches durch einen parallelen Branch & Bound--Algorithmus gelöst wird. Derartige Baumsuchverfahren finden in der künstlichen Intelligenz oder in der kombinatorischen Optimierung zahlreiche Anwendungen und beinhalten eine natürliche Parallelität. Die Floorplan-Optimierung ( floorplan sizing) ist ein Problem aus dem Bereich des VLSI -Designs. Hier sind die Bausteine eines Chips auf einem Layout mit minimaler Fläche anzuordnen, wobei die relativen Positionen der einzelnen Module in der vorangehenden Plazierungs-Phase schon festgelegt wurden. Für die Module existieren mehrere alternative Ausprägungen mit unterschiedlichen Ausmaßen, gesucht ist nun eine Kombination dieser verschiedenen Alternativen, so daß sich ein rechteckiges Layout mit minimaler Fläche ergibt. Abbildung 3 zeigt einen Floorplan, der jedem der 25 Module eines Chips einen Raum zuweist und somit vorschreibt, welche Blöcke in dem Layout benachbart sind. Existieren für jedes Modul im Schnitt vier unterschiedliche Implementierungen, so gibt es insgesamt verschiedene Layouts. Diese können in einem Baum sukzessive erzeugt werden. Abbildung 4 zeigt die oberen Ebenen eines möglichen Suchbaums für den Floorplan aus Abbildung 3. Jeder innere Knoten beschreibt ein Teil-Layout, die Blätter des vollständigen Suchbaums beschreiben alle möglichen Layouts für den gesamten Chip. Ein Branch & Bound--Algorithmus durchsucht nun systematisch, ausgehend von der Wurzel, diesen Baum. Dabei wird die Suche an einer Stelle dynamisch abgebrochen und an einer anderen Stelle fortgesetzt, wenn anhand einer Heuristik abzusehen ist, daß aus dem bislang erzeugten Teil-Layout keine gute Gesamtlösung entstehen kann.

 
Figure: Die oberen Ebenen eines Suchbaums für das Floorplan-Optimierungsproblem



WWW-Administration
Thu Jul 13 19:06:34 MET DST 1995