论文部分内容阅读
完整的FPGA设计包含了FPGA芯片的硬件结构设计及其配套软件系统设计两大部分。FPGA的软件系统必须与其硬件系统一一对应,由于FPGA可编程逻辑单元硬件结构的多样性,往往每开发出一款FPGA芯片,映射模块都需要重新进行开发,这给研究和生产都带来了极大的不便利。近年来学术界的一种基于图模式匹配的逻辑块映射算法FDUMAP在算法通用性方面取得了一定的突破,但随着逻辑单元基本功能元件种类的增加,该算法的复杂度成指数规律增加,且该算法在性能上也远逊于专用映射工具。 本文的工作所负责的内容即为FPGA软件流程中的逻辑映射模块。本文在FDUMAP的基础上,通过对现代主流FPGA的逻辑单元结构的分析和归纳,针对逻辑单元结构的共性,提出了一种用数字序列描述逻辑单元和用户电路并进行匹配的FPGA逻辑单元映射算法NSM。NSM中定义了一套完整的转换规则,该规则可以将映射算法所需要的电路信息用一串简单的数字描述出来,并通过比对数字序列的方法完成映射。NSM算法适用于包括XilinxSpartan系列和Virtex系列等多种主流FPGA逻辑单元的映射,同时,NSM的转换规则中设有一定的开放数值选项,用以将NSM扩展应用到未来可能出现的新的FPGA逻辑单元结构中去。NSM算法的最高复杂度为O(n2),远低于其他基于匹配的映射算法O(nm)的复杂度,其中n为用户电路中元件的总数,m为FPGA逻辑单元在某一种配置下的元件数。 除了对运算速度进行优化外,NSM算法还就逻辑单元映射后的资源利用率和通用性等方面进行了优化。在测试中,NSM显现出了广泛的适应性以及可与专用的映射工具相比拟的性能。除此之外,在NSM算法的扩展性应用中,本文提出了弹性装箱FlexPack的概念,首次在FPGA逻辑单元映射中引入了可调整大小的“宏逻辑块”的概念,将多个逻辑单元视作一个整体的“宏逻辑块”进行映射,从而使用户电路的局部逻辑在FPGA上得到更高效地实现,突破了以往映射模块只能以单个逻辑单元为目标进行映射的局限。测试表明,FlexPack在对中小规模的用户电路应用中显示出了良好的性能。