Near-linear wirelength estimation for FPGA placement

摘要

Avec les progrès rapides de la technologie des circuits intégrés, la longueur de fil est devenue l'une des mesures les plus critiques et importantes dans toutes les phases d'automatisation de conception physique VLSI, particulièrement dans le placement des circuits. Comme la longueur de fil précise pour un placement donné ne peut être connue qu'après routage, les estimations des longueurs de fil précises et rapides à calculer sont exigées par des algorithmes de placement sur FPGA. Dans cet article, un nouveau modèle pour évaluer la longueur de fil pendant le placement sur FPGA, appelé star+, est présenté. Le modèle proposé est continuellement différentiable et peut être utilisé avec des méthodes d'amélioration des placements à la fois analytiques et itératives. De plus, le temps nécessaire pour calculer des changements progressifs du co?t engagé par se déplacement/échange des blocs peut toujours être calculé dans le temps de O(1). Les résultats montrent que quand incorporé dans la structure bien connue VPR et testé en utilisant les 20 repères MCNC, le modèle star+ réalise une réduction de 6 à 9 % du retard du chemin critique comparé avec le modèle demi-périmètre de la longueur de fil (HPWL), en exigeant approximativement la même quantité de calcul.%With rapid advances in integrated circuit technology, wirelength has become one of the most critical and important metrics in all phases of VLSI physical design automation, especially circuit placement. As the precise wirelength for a given placement can only be known after routing, accurate and fast-to-compute wirelength estimates are required by FPGA placement algorithms. In this paper, a new model, called star+, is presented for estimating wirelength during FPGA placement. The proposed model is continuously differentiable and can be used with both analytic and iterative-improvement placement methods. Moreover, the time required to calculate incremental changes in cost incurred by moving/swapping blocks can always be computed in O(1) time. Results show that when incorporated into the well-known VPR framework and tested using the 20 MCNC benchmarks, the star+ model achieves a 6-9% reduction in critical-path delay compared with the half-perimeter wirelength (HPWL) model, while requiring roughly the same amount of computational effort.