Hierarchical FPGA placement

S. Areibi; G. Grewal; D. Banerji; P. Du

摘要

Les réseaux logiques programmables (FPGA) sont des circuits pouvant réaliser la majorité des tâches de circuits numériques en programmant les portes logiques et leurs interconnections. L'utilisation de FPGA s'est développée presque exponentiellement parce que ces circuits réduisent nettement les délais de conception ainsi que les coûts de production comparativement à des circuits intégrées à applications spécifiques (ASIC). Des outils d'aide à la conception par ordinateur efficaces sont requis pour la compilation de la description matérielle dans le fichier de configuration du FPGA afin d'implémenter les circuits désirés. Actuellement le temps de compilation pour des applications FPGA d'envergure (8 millions de portes logiques) est majoritairement composé du temps de positionnement et du choix des parcours des signaux. Ce temps peut aisément prendre des heures et même des jours. Avec la disponibilité prochaine de circuits FPGA de 40 millions de portes logiques en vue, ces temps de compilation prohibitifs peuvent annuler l'avantage des FPGA sur les ASIC en termes de temps de mise en marché. Cet article présente deux nouvelles méthodes de positionnement heuristique qui réduisent significativement le temps de calculs requis pour atteindre des positionnements de haute qualité, par rapport à l'outil habituel de placement et de routage (VPR). Le premier algorithme est une amélioration du recuit simulé (SA) qui tente de résoudre le problème de positionnement du haut vers le bas en considérant tous les modules à un niveau uniforme. Le second algorithme est une approche hiérarchique basée sur une procédure en deux étapes qui débute du bas vers le haut (regroupant des modules hautement connectés ensemble) et ensuite du haut vers le bas (distribution).%Field-programmable gate arrays (FPGAs) are semiconductor chips that can realize most digital circuits on site by specifying programmable logic and their interconnections. The use of FPGAs has grown almost exponentially because they dramatically reduce design turnaround time and startup cost for electronic products compared with traditional application-specific integrated circuits (ASICs). Efficient computer-aided-design tools are required to compile hardware descriptions into bitstream files that are used to configure the target FPGA to implement the desired circuits. Currently, the compile time, which is dominated by placement and routing time, can easily be hours or even days for large (8-million-gate) FPGAs. With 40-million-gate FPGAs on the horizon, these prohibitively long compile times may nullify the time-to-market advantage of FPGAs. This paper presents two novel placement heuristics that significantly reduce the computation time required to achieve high-quality placements, compared with the versatile place and route (VPR) tool. The first algorithm is an enhancement of simulated annealing (SA) that attempts to solve the placement problem top-down by considering all modules at the flat level. The second algorithm involves a hierarchical approach based on a two-step procedure that first proceeds bottom-up (grouping highly connected modules together) and then top-down (declustering). The overall effect is to reduce the number of entities needing to be considered at each level, such that time-consuming methods like SA become feasible for very large problems. Experimental results show a 70-80% reduction in runtime, coupled with very high-quality placements.

机译：可编程逻辑网络（FPGA）是可以通过对逻辑门及其互连进行编程来执行大多数数字电路任务的电路。 FPGA的使用几乎成倍增长，因为与用于特定应用（ASIC）的集成电路相比，这些电路大大缩短了设计时间并降低了生产成本。为了实现所需的电路，需要有效的计算机设计辅助工具来编译FPGA配置文件中的硬件描述。当前，大规模FPGA应用（800万个逻辑门）的编译时间主要由定位时间和信号路径的选择组成。这个时间可能很容易花费数小时甚至数天。随着即将到来的具有4000万逻辑门的FPGA电路的可用性，这些令人望而却步的编译时间可能抵消了FPGA在ASIC方面的上市时间优势。本文介绍了两种新的启发式定位方法，与通常的定位和路由工具（VPR）相比，它们可以显着减少实现高质量定位所需的计算时间。第一种算法是对模拟退火（SA）的改进，它试图通过考虑所有模块处于统一水平来解决自上而下的定位问题。第二种算法是基于两步过程的分层方法，该过程从下至上（将高度连接的模块分组在一起），然后从上至下（分布）开始。％现场可编程门阵列（FPGA）是通过指定可编程逻辑及其互连可以在现场实现大多数数字电路的半导体芯片。 FPGA的使用几乎成倍增长，因为与传统的专用集成电路（ASIC）相比，FPGA大大减少了电子产品的设计周转时间和启动成本。需要有效的计算机辅助设计工具来将硬件描述编译为比特流文件，这些文件用于配置目标FPGA以实现所需的电路。目前，对于大型（800万门）FPGA，编译时间主要由布局和布线时间决定，很容易需要数小时甚至数天。随着4000万门FPGA的出现，这些过长的编译时间可能使FPGA的上市时间优势丧失。与通用的布局和路线（VPR）工具相比，本文提出了两种新颖的布局启发式方法，可显着减少实现高质量布局所需的计算时间。第一种算法是模拟退火（SA）的增强，它试图通过在平面级别上考虑所有模块来自上而下解决布局问题。第二种算法涉及一种基于两步过程的分层方法，该过程首先进行自下而上（将高度连接的模块分组在一起），然后进行自上而下（分簇）。总体效果是减少了每个级别需要考虑的实体数量，从而使SA之类的耗时方法对于非常大的问题变得可行。实验结果表明，运行时间减少了70-80％，并且质量非常高。

Hierarchical FPGA placement

摘要

著录项

相似文献

相关主题

期刊订阅