具有广泛适应性的高性能FPGA映射算法研究

论文摘要

FPGA设计包括芯片硬件结构设计和配套软件系统设计两大部分,其中软件系统设计必须与芯片硬件结构相匹配。由于FPGA可编程逻辑单元硬件结构的多样性,可编程逻辑块的映射工具总是和某种特定的硬件结构相结合的,大大限制了可编程逻辑块映射工具的灵活性。基于数学中图模式匹配的概念,提出了一种对含LUT、DFF、MUX和快速进位链的FPGA可编程逻辑单元都能有较好适应性的映射算法FDUMAP,从而在算法通用性方面取得了一定的突破。但存在的问题是,随着逻辑单元基本功能元件种类的增加,该算法的复杂度成指数规律增加。另外,该算法在性能上也无法与专用映射算法相比拟。本文针对现代主流FPGA逻辑单元结构特征进行了共性分析,提取出具有共性的元件,如:LUT、DFF、MUX,F5MUX,AND门和XOR门,提出的映射算法不但能处理含LUT、DFF、MUX和快速进位链的逻辑单元,而且还能处理现代FPGA逻辑单元中经常出现的、专门为实现特殊电路功能的元件如F5MUX,AND门和XOR门等,因而具有更广泛的适应性,能很好地处理现代FPGA逻辑单元的结构特征,并且适用于任意规模,包含任意种元件类型的新型芯片结构。为了降低算法的复杂度,本文提出了对可编程逻辑单元分层、分类的映射思想;为了提高逻辑单元的映射效率,在映射过程中引入了匹配度系数,从而在算法的复杂度和性能方面得到了大幅度的提高。同时实验结果表明,该工具映射结果可以和专用逻辑块映射工具相媲美甚至超越。

论文目录

• 摘要
• Abstract
• 第1章 引言
• 1.1 FPGA简介
• 1.1.1 FPGA的发展
• 1.1.2 FPGA基本结构
• 1.2 FPGA CAD软件系统
• 1.2.1 软件系统介绍
• 1.2.2 系统模块划分
• 1.3 主要研究工作
• 1.4 论文组织
• 第2章 研究背景
• 2.1 FPGA总体硬件结构
• 2.2 学术界逻辑映射算法
• 2.2.1 学术界逻辑映射流程
• 2.2.2 可编程逻辑块结构
• 2.2.3 可编程逻辑块模型
• 2.2.4 学术界逻辑映射算法
• 2.3 商业芯片逻辑映射算法研究
• 2.3.1 商业芯片的FPGACAD流程
• 2.3.2 商用芯片逻辑块结构
• 2.3.3 商业芯片逻辑块模型
• 2.3.4 商业芯片逻辑映射算法
• 2.4 可编程逻辑块映射目标
• 2.4.1 学术界Cluster模型
• 2.4.2 UCLA的Complex PLB模型
• 2.4.3 商用FPGA
• 2.4.4 调研总结
• 2.5 本章小结
• 第3章 通用可编程逻辑块映射数学建模
• 3.1 子图同构算法
• 3.1.1 基本定义
• 3.1.2 基本的搜索算法
• 3.2 数学建模
• 3.2.1 实现目标
• 3.2.2 基于实际电路特点的改进
• 3.2.3 建模示例
• 3.3 本章小结
• 第4章 通用可编程逻辑块映射算法
• 4.1 问题的描述和基本定义
• 4.2 方法实现
• 4.2.1 PLB的功能电路集的生成
• 4.2.2 降低复杂度
• 4.2.3 提高每个PLB的利用率
• 4.2.4 算法实现
• 4.3 本章小结
• 第5章 实验结果和分析
• 5.1 软件设计及实现
• 5.2 实验结果及分析
• 5.3 实验结果分析总结
• 5.4 本章小结
• 第6章 总结与展望
• 6.1 工作总结
• 6.2 未来工作展望
• 参考文献
• 致谢
• 攻读学位期间科研成果