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