针对FPGA复杂可编程逻辑单元的快速布尔匹配方法研究

摘要

自上世纪80年代第一块现场可编程门阵列(Field Programmable Gate Array，FPGA)芯片问世以来，FPGA凭借其开发周期短、非重复性工程(Non-RecurringEngineering，NRE)费用低等特点，在诸如产品原型设计、中低规模产量电路系统实现等应用领域中，牢牢占据市场份额。进入到21世纪，半导体工业遇到新的问题。一方面随着工艺尺寸降低，芯片的生产制造成本持续上升，导致专用集成电路的开发成本居高不下；另一方面功耗问题限制了电路频率的提高，使得集成电路向多核结构发展。在众多解决方案中，FPGA具有天然的低开发成本、高度并行处理架构的优势，因而受到越来越多的关注和青睐，开始进入到通讯、网络、高性能计算等应用领域。　　布尔匹配是现场可编程门阵列设计自动化流程中的一个核心子问题，主要解决可编程逻辑单元结构是否能够实现给定的布尔函数的问题，在工艺映射、逻辑再综合及新型结构评估等方面有着广泛应用。为了以较小的面积代价灵活地实现更多的逻辑功能，可编程逻辑单元结构经历了由简单到复杂、由同质向异质结构发展的过程。一个理想的针对可编程逻辑单元的布尔匹配方法需要兼顾灵活性、伸缩性、速度与空间开销等多个方面。在目前现有的匹配方法中，基于布尔可满足性问题的匹配方法具有最佳灵活性，但却由于其高计算复杂度而难以应用到复杂大规模可编程逻辑单元中。在本论文中，在布尔可满足性问题匹配方法的基础上，提出两种快速且不失灵活性的布尔匹配方法。　　针对基于布尔可满足性问题的匹配方法在可实现函数与不可实现函数运行时间上的巨大差异，本文提出通过构建匹配查找表的方法在匹配初期阶段快速排除大部分的不可实现函数，以提高匹配速度。主要贡献在于：(1)利用不同电路中普遍存在的局部相似性，提出采用电路训练的方法来提取有效数据，减小数据挖掘工作量；(2)提出采用布隆过滤器(Bloom Filter)数据结构为基础构建匹配查找表，以高效的方式保存经过训练的匹配结果，使得查找表能够安置于目前主流台式电脑的内存中；(3)提出两种过滤策略，用户可以根据需要进行匹配时间与匹配质量两方面的折衷。实验结果表明，应用于电路逻辑再综合，本文所提出的方法比最新的基于布尔可满足性问题的匹配方法快80倍，而电路而积仅增加0.5％。　　随着云计算时代的来临，软件即服务(Software as a Service，SsaS)这种独特的软件开发模型给信息产业的各方面都带来了深远的影响。本论文的第二部分，以针对复杂可编程逻辑单元的布尔匹配问题作为一个具体实例，分析SaaS给集成电路设计自动化领域所带来机遇和挑战。具体地，包括以下工作：(1)提出布尔匹配问题的软件即服务模式解决方案与结构框架，并对其安全性、成本和性能等方面做出评估；(2)分析讨论了云端数据存储的特点与要求，利用键/值数据库构建匹配查找表，完全排除求解布尔可满足性问题的需要；(2)探索了在网络传输、服务器端与客户端配置等方面的优化。实验结果表明，与最新的基于布尔可满足性问题的匹配方法相比，所提出的基于软件即服务模式的方法提速863倍。