CSPack:采用CSP图匹配的新型装箱算法  

CSPack:A Novel Packing Algorithm Based on CSP Graph Matching

作　　者：龚爱慧[1] 梁绍池[1] 陈志辉[1] 王伶俐[1] 童家榕[1] 

机构地区：[1]复旦大学专用集成电路与系统国家重点实验室,上海201203

出　　处：《计算机辅助设计与图形学学报》2010年第11期1998-2003,2012,共7页Journal of Computer-Aided Design & Computer Graphics

基　　金：国家"八六三"高技术研究发展计划(2009AA012201);国家自然科学基金(60676020);上海市浦江人才计划(2008)

摘　　要：现代FPGA芯片可编程单元的日益复杂化对装箱提出了更大挑战,为了使依赖硬件结构的装箱过程不断适应芯片结构变化的过程,提出一种基于CSP图匹配的装箱算法CSPack.用配置库来描述芯片可编程逻辑块的各种电路功能,根据配置库并利用CSP图匹配算法进行电路匹配,找出满足约束的子电路,并以指令的形式将子电路映射到可编程逻辑块内.该算法已经应用于复旦大学自主研发的FPGA芯片FDP2008软件流程的装箱模块中,且针对不同芯片系列只需修改描述芯片功能配置的文件就能实现装箱.实验结果表明,与T-VPack算法相比,CSPack算法在时序性能上提升了6.1%,同时可减少1.4%的芯片占用面积.Increasing complexity of modern FPGA＇s configurable elements raises greater challenges for packing.A novel packing algorithm CSPack based on CSP graph matching is presented.It implements circuits matching utilizing constraint satisfaction problem techniques to find sub-circuits satisfying constraints and designs a set of instructions system for mapping them into CLBs.CSPack has been used in the packing module which is part of the CAD flow for Fudan University＇s self-developed FPGA named FDP2008 and only needs to modify files describing configurations of different FPGAs can implement packing operations for target chips.Experimental results show that CSPack compared with T-VPack achieves 6.1% increase in timing performance and 1.4% reduction in chip area.

关 键 词：约束满足性问题 图匹配 电路改写 装箱 FPGA 

分 类 号：TN47[电子电信—微电子学与固体电子学]