Universität zu Köln

Feld, Dustin (2017). FieldPlacer - A flexible, fast and unconstrained force-directed placement method for heterogeneous reconfigurable logic architectures. PhD thesis, Universität zu Köln.

Preview

PDF (PDF-X3) DustinFeld_PhDThesis.pdf - Published Version Download (32MB)

Abstract

The field of placement methods for components of integrated circuits, especially in the domain of reconfigurable chip architectures, is mainly dominated by a handful of concepts. While some of these are easy to apply but difficult to adapt to new situations, others are more flexible but rather complex to realize. This work presents the FieldPlacer framework, a flexible, fast and unconstrained force-directed placement method for heterogeneous reconfigurable logic architectures, in particular for the ever important heterogeneous FPGAs. In contrast to many other force-directed placers, this approach is called ‘unconstrained’ as it does not require a priori fixed logic elements in order to calculate a force equilibrium as the solution to a system of equations. Instead, it is based on a free spring embedder simulation of a graph representation which includes all logic block types of a design simultaneously. The FieldPlacer framework offers a huge amount of flexibility in applying different distance norms (e. g., the Manhattan distance) for the force-directed layout and aims at creating adapted layouts for various objective functions, e. g., highest performance or improved routability. Depending on the individual situation, a runtime-quality trade-off can be considered to either produce a decent placement in a very short time or to generate an exceptionally good placement, which takes longer. An extensive comparison with the latest simulated annealing placement method from the well-known Versatile Place and Route (VPR) framework shows that the FieldPlacer approach can create placements of comparable quality much faster than VPR or, alternatively, generate better placements in the same time. The flexibility in defining arbitrary objective functions and the intuitive adaptability of the method, which, among others, includes different concepts from the field of graph drawing, should facilitate further developments with this framework, e. g., for new upcoming optimization targets like the energy consumption of an implemented design.

Item Type:	Thesis (PhD thesis)
Translated abstract:	Abstract Language Das Gebiet der Platzierungsverfahren für Komponenten integrierter Schaltkreise wird, insbesondere im Sektor der rekonfigurierbaren Chiparchitekturen, im wesentlichen von einer Handvoll Konzepten dominiert. Während einige davon einfach anzuwenden aber schwer an neue Situationen anzupassen sind, sind andere flexibler aber relativ komplex zu realisieren. Diese Arbeit präsentiert das FieldPlacer Framework, eine flexible, schnelle und uneingeschränkte kräftebasierte Platzierungsmethode für heterogene rekonfigurierbare Logikarchitekturen, insbesondere für die immer wichtiger werdenden heterogenen FPGAs. Im Gegensatz zu den meisten anderen kräftebasierten Platzierungsverfahren wird dieser Ansatz hier ‘uneingeschränkt’ genannt, da er keine a priori fixierten Logikelemente erfordert um ein Kräftegleichgewicht als Lösung eines Gleichungssystems zu bestimmen. Stattdessen basiert der Ansatz auf einer freien Spring-Embedder Simulation einer Graphrepräsentation des Designs, welche alle Logikblocktypen simultan einschließt. Das FieldPlacer Framework bietet große Flexibilität in der Anwendung verschiedener Distanz-Normen (z. B. der Manhattan-Distanz) für das kräftebasierte Layout mit dem Ziel, angepasste Layouts für verschiedene Zielfunktionen zu erstellen, beispielsweise höchste Performanz oder verbesserte Verdrahtbarkeit. Abhängig von der individuellen Situation kann ein Laufzeit-Qualität Kompromiss gewählt werden, um entweder eine ordentliche Platzierung in sehr kurzer Zeit oder eine außerordentlich gute Platzierung in längerer Zeit zu produzieren. Ein umfangreicher Vergleich zum aktuellen Simulated Annealing Platzierungsverfahren aus dem bekannten Versatile Place and Route (VPR) Framework zeigt, dass der FieldPlacer Ansatz Lösungen vergleichbarer Qualität deutlich schneller erstellen kann als VPR oder, alternativ, eine bessere Platzierung in ähnlicher Zeit erzeugen kann. Die Flexibilität in der Definition beliebiger Zielfunktionen und die intuitive Anpassungsfähigkeit des Frameworks, welches unter anderem auf verschiedenen Konzepten aus dem Graphenzeichnen basiert, soll weitere Entwicklungen mit jenem ermöglichen, z. B. für neuartige Optimierungsziele wie den Energieverbrauch eines implementierten Designs. German
Creators:	Creators Email ORCID ORCID Put Code Feld, Dustin dustin.feld@scai.fraunhofer.de UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-75751
Date:	2017
Publisher:	Fraunhofer Verlag
ISBN:	978-3-8396-1155-5
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects:	Data processing Computer science Mathematics
Uncontrolled Keywords:	Keywords Language Integrierte Schaltungen und Komponenten Computerarchitekturen und Logikdesign Kombinatorik und Graphentheorie Algorithmen und Datenstrukturen German
Date of oral exam:	24 October 2016
Referee:	Name Academic Title Jünger, Michael Prof. Dr. Brinkmann, André Prof. Dr.-Ing.
Refereed:	Yes
URI:	http://kups.ub.uni-koeln.de/id/eprint/7575