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

现代FPGA芯片可编程单元的日益复杂化对装箱提出了更大挑战,为了使依赖硬件结构的装箱过程不断适应芯片结构变化的过程,提出一种基于CSP图匹配的装箱算法CSPack.用配置库来描述芯片可编程逻辑块的各种电路功能,根据配置库并利用CSP图匹配算法进行电路匹配,找出满足约束的子电路,并以指令的形式将子电路映射到可编程逻辑块内.该算法已经应用于复旦大学自主研发的FPGA芯片FDP2008软件流程的装箱模块中,且针对不同芯片系列只需修改描述芯片功能配置的文件就能实现装箱.实验结果表明,与T-VPack算法相比,CSPack算法在时序性能上提升了6.1%,同时可减少1.4%的芯片占用面积.     

基于布线资源图的FPGA互连测试算法

分析基于静态随机访问内存的FPGA开关盒互连资源,提出一种自动生成且与应用无关的测试配置集算法,通过建立布线资源图,根据线网的走向动态设定各边的权重,利用改进的Kruskal算法,自动产生测试配置集。对于FPGA不同的互连结构,该算法对互连资源中的开路和短路故障的覆盖率能够达到100%,且具有测试配置个数少、运行速度快以及与具体硬件结构无关等优点。