Loading…
Optimierung der Verdrahtbarkeit unter Berücksichtigung heterogener Verdrahtungsressourcen hierarchischer FPGA-Architekturen
Matrose, Valerij
Die vorliegende Arbeit beschreibt den Aufbau und die zugrunde gelegten Algorithmen des Clustering- und Platzierwerkzeugs PALLAs für die kommerziellen Altera-FPGAs. Während der Entwicklung von PALLAs wurden verschiedene Clustering- und Platzieralgorithmen im Hinblick auf die Architektur der kommerziellen Altera-FPGAs neu implementiert und miteinander verglichen. Die dabei aufgedeckten Stärken und Defizite der einzelnen Algorithmen wurden analysiert und dokumentiert, die dabei gewonnen Erkenntnisse flossen in die Entwicklung und Optimierung der Kernalgorithmen von PALLAs. Aufgrund der Festlegung auf eine kommerzielle FPGA-Zielarchitektur konnte eine der wesentlichen Schwächen der analysierten Clustering- und Platzierverfahren aufgedeckt werden: Strukturelle Vereinfachungen des häufig eingesetzten klassischen Modells eines hierarchischen FPGA schränken die Effektivität dieser Verfahren bei real existierenden FPGA-Architekturen ein. Die großen FPGA-Hersteller bieten in der Regel low-cost FPGA-Familien mit einigen wenigen und high-end FPGA-Familien mit zahlreicheren Verdrahtungsebenen an. Ist die Geschwindigkeit eines Designs unkritisch, kann unter Umständen eine vertikale Migration zu einem Baustein mit weniger Verdrahtungsressourcen vollzogen werden, was in der Praxis mit einer Kostenersparnis verbunden ist. Ob ein Migrationsschritt möglich ist, hängt bei den Designs mit hohem Verdrahtungsressourcenbedarf davon ab, ob die Verdrahtbarkeit der Designs gewährleistet werden kann. Deshalb ist es von entscheidender Bedeutung, dass die Clustering- und Platzieralgorithmen bei der Verbesserung der Verdrahtbarkeit die besonderen Merkmale der FPGA-Zielarchitekturen berücksichtigen und ausnutzen. Bei dem Clustering-Entwurfsschritt versucht PALLAs, die Interkonnektivität innerhalb der Logikblöcke und somit die Nutzung der lokalen Verdrahtungsressourcen zu erhöhen. Auf diese Weise werden der globale Verdrahtungsressourcenbedarf verringert und die Verdrahtbarkeit der Designs erhöht. Die bisherigen Arbeiten dokumentieren gut den großen Einfluss von Clustering auf die Verdrahtbarkeit der platzierten Designs. Ein bisher unterschätzter Aspekt ist hingegen die Tatsache, dass auch bei gleichzeitigem Clustering und Platzierung der Logikzellen in einem einzigen Entwurfsschritt das initiale Clustering der Logikzellen sich auf die nachfolgende Platzierung auswirkt. Deshalb bleibt Clustering als Vorstufe zur Platzierung, unabhängig von der Art der Platzierung, ein kritischer Entwurfsschritt. Die Verbesserung der Verdrahtbarkeit erfolgt beim Platzieren mit PALLAs durch eine Reduzierung der zur globalen Verdrahtung erforderlichen Leitungslängen. Die Schätzung der erforderlichen Leitungslängen findet mit einer modifizierten Bounding-Box-Kostenfunktion statt. In diese Kostenfunktion fließen zusätzliche Gewichtungsfaktoren ein, die Besonderheiten der gegebenen Verdrahtungsarchitektur und verdrahtungsgünstigere Platzierpositionen berücksichtigen. Um FPGA-Bereiche mit lokaler Überbenutzung der Verdrahtungsressourcen aufzuspüren, kann deren Nutzung über die gesamte FPGA-Fläche modelliert werden. Eine weitere Steigerung der Verdrahtbarkeit wird erreicht, indem die globalen Verdrahtungsressourcen in den Bereichen mit überbenutzten Verdrahtungsressourcen künstlich verknappt und somit entlastet werden. Bei kostensensitiven Designs mit hohem Verdrahtungsressourcenbedarf können die in PALLAs implementierten Clusteringund Platzierstrategien eine vertikale Migration zu einem preiswerteren FPGA ermöglichen. Das entwickelte Werkzeug PALLAs wurde in den bestehenden Entwurfsfluss der Altera-Quartus-II-Software eingebettet, was eine realistische Analyse des Ressourcenbedarfs und des Zeitverhaltens der erzeugten Platzierungen ermöglichte. Die Wirksamkeit der neu entwickelten gegenüber einigen bekannten Verfahren aus dem Forschungsumfeld und der herstellereigenen Software wird anhand zahlreicher Benchmarkschaltungen belegt. Mit den entwickelten Verfahren war es möglich, den Verdrahtungsressourcenbedarf der Schaltungen um bis zu 21% zu verringern und den maximalen Takt dieser um bis zu 25% zu erhöhen.
The following work presents the architecture and the underlying algorithms of the clustering and placement tool PALLAs for commercial Altera FPGAs. During the development of PALLAs a variety of clustering and placement algorithms found in literature were reimplemented with respect to the particular architecture of the Altera FPGAs and then evaluated with respect to their efficiency. The algorithm's strengths and deficiencies were investigated and in turn used to develop and optimize new core clustering placement realized in the PALLAs system. Since this work is restricted to a particular commercial FPGA architecture one of the main deficiencies of the investigated clustering and placement algorithms where uncovered: Structural simplifications found in traditional methods designed for hierarchical FPGAs strongly degrade efficiency for real world FPGA architectures. Most commercial FPGA vendors feature two different architecture types on their product portfolio: A low cost version with limited amounts of routing resources and a high-end variant with an abundance of routing resources. For target applications where speed is not critical, vertical migration to a device with limited routing resources might be possible which in turn leads to significant economical advantages. If the aforementioned vertical migration process is possible for large design with high interconnect complexity largely depends on the quality of the applied clustering and placement algorithms for a given design and how well they make use of the target architecture's interconnect properties. Therefore it is imminent that clustering and placement algorithms are aware of the target architecture's particular routing capabilities in order to improve on a design's overall routability. During clustering the PALLAs systems seeks to improve interconnectivity within any given logic block which in turn increases the utilization of local routing resources. Hence, global interconnect resources will be spared and the overall routability of a design will increase. Previous work strongly underlines the impact of clustering on overall routability for any placed design. Yet, one aspect which was previously unaccounted for is the fact, that with simultaneous clustering and placement of logic cells the initial clustering of a logic cell strongly influences the pending phase of placement. Therefore clustering as a precursor or placement remains a critical design step independently from the actual placement algorithm. The PALLAs system increases routability during placement by reducing the segment length of networks subject to global routing. Estimation of the segment length is performed using a modified bounding-box cost function which introduces additional weighting factors taking into account the particular interconnect capabilities of a given FPGA architecture and its cost efficient placement alternatives. In order to uncover areas with over-utilization of local interconnect resources for a given design, the latter is modelled for the FPGA's floorplan in total. An additional increase in overall routability is obtained by shortening global interconnect resources for areas with over-utilization of local interconnect resources on purpose. As a consequence the clustering and placement algorithms implemented in the PALLAs system provide the necessary means to allow vertical migration to cost efficient FPGAs for designs with a high demand of global interconnect resources. The PALLAs system integrates seamlessly into the existing Altera Quartus II design flow which allows an in-detail analysis of resource usage and timing properties of the generated placements for complex real world designs. The efficacy of the new clustering and placement algorithms is proven by direct comparison to existing methods from academia as well as the commercial variants provided by Altera Quartus II. Results for numerous benchmark designs were investigated. As a result the new clustering and placement algorithms lead to an overall reduction of interconnect utilization of up to 21% as well as to a frequency speedup of up to 25%.
