FPGA工艺映射算法研究

摘要

FPGA工艺映射是将工艺无关的逻辑网表转化成与目标FPGA结构相关网表的过程。传统FPGA的工艺映射主要是基于查找表(LUT)的电路覆盖，以达到面积和时序性能的最优。但是随着FPGA设计技术的发展，FPGA软件算法面临着许多新的问题和挑战。本论文着眼于FPGA的工艺映射算法，主要分析和研究了传统的工艺映射算法及其改进，并针对新型异构FPGA提出基于函数分类和布隆过滤器的工艺映射算法;同时针对CAD软件算法的测试难题，提出了基于JTAG的自动测试系统和方法。
　　1.针对基于LUT的FPGA结构，本文系统介绍了传统的工艺映射算法，并仔细研究了当前的主要改进算法。DAOmap算法在保证延时最优的同时，通过采用多种启发式的优化手段，尽可能减少面积;ABC工具中的FPGA工艺映射算法则继续改进了分割的计算方法，加速枚举过程，提出全局和局部两个层次的启发式面积优化方法，并利用无损综合增强映射效果;FDMap算法在传统结构化映射算法的框架下，引入对时序器件和宏单元的拆分处理方法，使其能够处理更加复杂的电路。
　　2.目前商用的FPGA器件可编程逻辑单元(CLB)结构越加复杂，除了含有最基本的LUT和时序器件以外，还有很多辅助元件用来高效地实现各种逻辑功能。在对电路网表划分后，由于结构化的映射算法不能对这种异质结构进行电路匹配，因此本文提出基于函数分类和布隆过滤器的异质结构FPGA工艺映射算法，能够灵活地对不同配置的异构CLB进行工艺映射。同时将其与函数分类算法结合，解决了原始布隆过滤器算法所需匹配库过大的难题。通过针对MCNC例子的实验表明，函数分类算法可以将布尔匹配库大小降至原始的5％，而结合动态训练的过滤算法可以额外减小13％的LUT个数。
　　3.在CAD软件算法如工艺映射的设计改进过程中，我们经常需要修改底层的算法，而任何微小的改动都可能影响结果的正确性，而现今缺少如何验证的方法。本文提出了基于JTAG的自动测试系统与方法，将整个测试流程全自动化，在每次算法更新后都能够得到完善的回归测试，大大提升软件的健壮性和正确率。

目录

摘要

第1章 引言

1．1 FPGA设计简介

1．1．1 FPGA结构介绍

1．1．2 FPGA的CAD流程介绍

1．2 研究背景

1．3 主要工作

1．4 论文组织结构

第2章 传统工艺映射算法

2．1 概述

2．2 基础知识

2．2．1 电路描述方式

2．2．2 具体问题描述

2．3 传统结构化工艺映射

2．3．1 整体流程

2．3．2 分割枚举

2．3．3 分割排序

2．4 主要改进算法

2．4．1 DAOmap

2．4．2 ABC工具

2．4．3 FDMap算法

2．5 本章小结

第3章 基于函数分类和布隆过滤器的工艺映射算法

3．1 概述

3．2 基于布尔匹配的异构算法

3．2．1 布尔匹配

3．2．2 SAT问题描述

3．2．3 基于SAT的布尔匹配

3．3 基于布隆过滤器的工艺映射算法

3．3．1 布隆过滤器

3．3．2 哈希函数选取

3．3．3 匹配查找表存储空间

3．3．4 过滤策略

3．3．5 实验结果与分析

3．4 基于函数分类和布隆过滤器的工艺映射

3．4．1 布尔函数函数分类

3．4．2 根据函数分类减小匹配库

3．4．3 函数分类算法

3．4．4 实验结果与分析

3．5 本章小结

第4章 基于JTAG的自动测试方法

4．1 概述

4．2 JTAG边界扫描技术

4．3 自动测试系统

4．4 自动测试方法

4．5 实验结果与分析

4．6 本章小结

第5章 总结与展望

5．1 工作总结

5．2 工作展望

参考文献

致谢

声明