Universität zu Köln

FieldPlacer - A flexible, fast and unconstrained force-directed placement method for heterogeneous reconfigurable logic architectures

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.

[img]
Preview
PDF (PDF-X3) - Published Version
Download (31Mb) | Preview

    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:
    AbstractLanguage
    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:
    CreatorsEmail
    Feld, Dustindustin.feld@scai.fraunhofer.de
    URN: urn:nbn:de:hbz:38-75751
    Publisher: Fraunhofer Verlag
    ISBN: 978-3-8396-1155-5
    Subjects: Data processing Computer science
    Mathematics
    Uncontrolled Keywords:
    KeywordsLanguage
    Integrierte Schaltungen und Komponenten Computerarchitekturen und Logikdesign Kombinatorik und Graphentheorie Algorithmen und DatenstrukturenGerman
    Faculty: Mathematisch-Naturwissenschaftliche Fakultät
    Divisions: Mathematisch-Naturwissenschaftliche Fakultät > Institut für Informatik
    Language: English
    Date: 2017
    Date Type: Publication
    Date of oral exam: 24 October 2016
    Full Text Status: Public
    Date Deposited: 15 May 2017 12:02:11
    Referee
    NameAcademic Title
    Jünger, MichaelProf. Dr.
    Brinkmann, AndréProf. Dr.-Ing.
    URI: http://kups.ub.uni-koeln.de/id/eprint/7575

    Actions (login required)

    View Item