FPGA芯片最少配置的图论方法研究

国内外对于FPGA芯片最少配置的研究基本上是采取一种自底向上的方法。由于图论在电路分析中有着广泛的应用,因此,本文将图论的思想应用在FPGA最少配置的研究中,即将其内部的门单元看作图论中的点,将它们之间的连线看作图论中的线,采用了一种自顶向下的方法研究了CLB和IOB所需的最少配置次数。经过图论建模和图论的遍历分析,对于XC4000系列FPGA,得到CLB的最少配置次数为5次,IOB的最少配置次数为3次的结论。     

Graph theory for FPGA minimum configurations

A traditional bottom-up modeling method for minimum configuration numbers is adopted for the study of FPGA minimum configurations.This method is limited if a large number of LUTs and multiplexers are presented. Since graph theory has been extensively applied to circuit analysis and test,this paper focuses on the modeling FPGA configurations.In our study,an internal logic block and interconnections of an FPGA are considered as a vertex and an edge connecting two vertices in the graph,respectively.A top-down modeling method is proposed in the paper to achieve minimum configuration numbers for CLB and IOB.Based on the proposed modeling approach and exhaustive analysis,the minimum configuration numbers for CLB and IOB are five and three,respectively.