Self-organized Wiring and Arrangement of Responsive Modules (SWARM)

Ziel

Neuartige Methodik für den Layoutentwurf analoger integrierter Schaltungen zur Kombination prozeduraler und optimierender Automatisierungsstrategien

Motivation

Während der Layoutentwurf digitaler integrierter Schaltungen durch optimierende Algorithmen weitgehend automatisiert wurde, konnten sich derartige Ansätze im Analogbereich bislang nicht industriell etablieren. Stattdessen basiert der Analogentwurf noch immer auf der mühsamen manuellen Entwurfsarbeit erfahrener Layoutexperten. Obwohl der Entwurfsfluss durch prozedurale Generatoren unterstützt wird, beschränken sich diese meist auf ganz grundlegende Schaltungskomponenten. Die Entwurfsproduktivität ist daher immer noch um mehrere Größenordnungen höher als bei Digitalschaltungen, was den technologischen Fortschritt multifunktionaler Mikroelektroniksysteme dramatisch bremst.

Stand der Technik

Existierende Automatisierungsansätze können grundsätzlich in die beiden oben erwähnten Automatisierungsstrategien unterteilt werden. Diese folgen, akademisch betrachtet, zwei grundlegend verschiedenen Paradigmen: optimierende Algorithmen arbeiten top-down und können Entwurfsanforderungen explizit berücksichtigen (sofern diese formal beschrieben wurden), aber nicht implizit. Prozedurale Generatoren hingegen arbeiten bottom-up und können Entwurfsanforderungen implizit berücksichtigen (sofern dies vom Generatorentwickler vorgedacht wurde), aber nicht explizit.

Unser Ansatz

Da die Stärken und Schwächen der zwei Automatisierungsstrategien sich in dieser Hinsicht ergänzen, ist anzunehmen, dass eine Kombination beider Paradigmen (bottom-up meets top-down) weitaus mehr Potenzial hat, das Entwurfsproblem in seiner Gesamtheit zu lösen als optimierungsbasierte oder generatorbasierte Ansätze für sich allen. Doch weil die zwei Strategien komplementär sind, sind sie auf der anderen Seite auch inkompatibel. So steckt die wissenschaftliche Herausforderung in der Frage: wie verheiratet man die zwei grundlegend verschiedenen Automatisierungsparadigmen?

Die SWARM-Methodik

Self-organized Wiring and Arrangement of Responsive Modules (SWARM) ist eine interdisziplinäre Methodik, die das Entwurfsproblem mit einem dezentralisierten Multi-Agenten-System angeht. Das Grundprinzip besteht darin, ähnlich dem Zusammentreiben einer Schafherde, reaktionsfähige Layoutmodule (realisiert als kontextbewusste prozedurale Generatoren) in einer benutzerdefinierten Layoutzone interagieren zu lassen. Jedes Modul darf sich –als Agent– selbständig bewegen, drehen und verformen, wobei ein übergeordnetes Kontrollorgan die Zone schrittweise verkleinert um die Interaktion auf zunehmend kompakte Layoutanordnungen hinzulenken.

Nutzen

Die prozeduralen Layoutmodule können ihre jeweiligen Entwurfsanforderungen implizit berücksichtigen, während das Kontrollorgan optimierend wirkt und übergeordnete Entwurfsanforderungen explizit auferlegen kann. Konflikte werden mit diesem bottom-up-meets-top-down Konzept über die Interaktion gelöst. Durch die Berücksichtigung diverser Selbstorganisationsgrundsätze ist SWARM sogar in der Lage, das Phänomen der Emergenz hervorzurufen: obwohl jedes Modul nur eine begrenzte Sichtweise hat und egoistisch seine eigenen Ziele verfolgt, können sich auf globaler Ebene bemerkenswerte Gesamtlösungen herausbilden.

Beispiele

Emergenz kann man in der Natur beobachten, unter anderem bei einem Vogelschwarm: obwohl jeder Vogel autonom agiert, ergibt sich kollektives Schwarmverhalten. Mehrere Beispiele veranschaulichen dieses emergente Verhalten auch in SWARM.

Das folgende Platzierungsproblem (bei dem die Module sich nur bewegen, aber nicht drehen oder verformen dürfen) zeigt, dass sogar optimale Lösungen aus der Modulinteraktion entstehen können.

Die Anwendung von SWARM auf Place-and-Route-Probleme (hier: ein Transkonduktanzverstärker) verdeutlicht, dass die Module es schaffen, sowohl ihre lokalen Entwurfsanforderungen (z.B. die verschachtelte Anordnung ihrer Bauteile) als auch globale Entwurfsanforderungen (wie die explizit auferlegte Layoutkontur) zu erfüllen.

Ausblick

Die SWARM-Methodik wird mit dem Konzept der Smart Particles weiterentwickelt.