学位论文 > 优秀研究生学位论文题录展示

FPGA软件装箱算法研究

作　者: 龚爱慧
导　师: 童家榕；王伶俐
学　校: 复旦大学
专　业: 微电子学与固体电子学
关键词: 现场可编程门阵列计算机辅助设计装箱 CSPack RePack
分类号: TN791
类　型: 硕士论文
年　份: 2011年
下　载: 33次
引　用: 0次
阅　读: 论文下载

内容摘要

与ASIC相比,FPGA的可编程特性使得电路设计具有开发周期短、芯片设计成本低以及电路功能可重配置等优点。随着半导体工艺的发展和市场需求的推动,现代FPGA芯片的可编程结构越来越复杂,其可配置功能也愈来愈强大,这使得用户在利用FPGA进行电路设计时更加依赖计算机辅助设计工具,因此对FPGA计算机辅助设计工具的改进具有重要意义。本文着重研究与FPGA硬件功能实现紧密相关的FPGA软件流程中的装箱算法,分析目前流行装箱算法的研究现状,概括各个算法的优缺点并针对当前装算法所面临的重要挑战,提出相应有效的改进算法。现代FPGA芯片结构更新较快且风格迥异,如何开发适应各种不同的,复杂可编程单元结构且能利用结构本身的优良特性对用户电路进行优化的算法是当前装箱算法的难点。本文针对上述困难提出了一种基于CSP图匹配的装箱算法CSPack,该算法在用户电路中利用图匹配根据XML格式描述的芯片功能配置库找出满足约束的子电路,并基于布通率和时序驱动的思想以指令的形式将子电路映射到可编程逻辑块内。实验表明,该算法能够灵活针对复杂可编程结构FPGA进行装箱,且通过指定电路优化规则,装箱后可编程逻辑块数目减少了5.7%,同时时序性能提升了7.8%。随着FPGA逻辑容量和互连资源的极大丰富,复杂高性能用户电路设计对布通率和时序性能的要求也日益提升。传统装箱算法都是尝试达到100%的逻辑利用率,对于某些应用这样的方法可能会造成电路局部拥堵导致电路无法布通的情况,因此如何开发针对布通率要求和时序性能较高的算法是另一装箱算法难点。本文针对这一困难提出RePack装箱算法,该算法尝试平衡逻辑资源和互连资源的需求,对布线拥挤度较高的区域采用CLB稀疏的方法,将拥挤处的BLE扩展到非拥挤区域,通过迭代的CAD流程不断降低布线通道宽度需求同时改进时序驱动算法的种子及候选BLE的选取方法进行装箱。实验表明,该算法能够将电路时序性能提升8.3%,布线通道宽度减少37%,逻辑利用率提高36%。面向应用多核结构研究是当前的研究热点,因此开发相应的计算机辅助设计软件具有积极意义。本文根据已有研究成果CSPack和RePack(?)将其核心思想应用于多核开发软件辅助设计中,提出总体软件设计流程,基于高层综合工具GAUT生成的控制数据流图,利用图匹配找出相应的数据通路和控制逻辑。实验表明,该软件流程能够映射DSP类的典型应用,如FFT,并能够帮助硬件设计者进行结构评估。

全文目录

摘要  5-6
Abstract  6-7
1 引言  7-16
  1.1 FPGA硬件简介  7-9
  1.2 FPGA CAD流程  9-14
    1.2.1 逻辑综合模块简介  10
    1.2.2 工艺映射模块简介  10-11
    1.2.3 装箱模块简介  11-12
    1.2.4 布局模块简介  12-13
    1.2.5 布线模块简介  13-14
  1.3 论文贡献  14-15
  1.4 论文组织  15-16
2 背景研究  16-21
  2.1 基于面积优化的装箱算法  16-17
  2.2 基于时序优化的装箱算法  17-21
3 CSPack装箱算法  21-36
  3.1 装箱问题描述  21
  3.2 图匹配问题作为一个CSP  21-24
    3.2.1 CSP问题描述  21-22
    3.2.2 CSP图匹配问题  22
    3.2.3 CSP求解优化  22-24
  3.3 构造装箱问题的CSP模型  24-27
    3.3.1 将电路图转换成简单图  24-25
    3.3.2 构造CSP的变量集合和值域  25-26
    3.3.3 构造CSP的约束集合  26-27
  3.4 电路改写  27-30
    3.4.1 指令系统设计  27-28
    3.4.2 电路改写举例  28-30
  3.5 CSPack算法实现  30-36
    3.5.1 CSPack算法流程  30-31
    3.5.2 CSPack算法举例  31-32
    3.5.3 电路优化  32-33
    3.5.4 CSPack算法实验结果  33-35
    3.5.5 CSPack算法总结及展望  35-36
4 RePack装箱算法  36-53
  4.1 装箱问题描述  36-37
  4.2 装箱算法研究现状  37-42
    4.2.1 基于布通率的装箱算法iRAC  37-40
    4.2.2 基于拥挤度驱动的装箱算法  40-42
  4.3 装箱实现  42-45
    4.3.1 布线拥挤度估算  42-43
    4.3.2 增量装箱  43-45
  4.4 RePack CAD迭代流程  45-47
    4.4.1 CAD迭代流程图  45-46
    4.4.2 RePack算法伪代码  46-47
  4.5 RePack算法实验结果  47-52
  4.6 RePack算法总结与展望  52-53
5 面向领域多核处理器软件辅助设计  53-60
  5.1 多核处理器背景简介  53-54
  5.2 多核处理器软件设计研究现状  54-55
  5.3 面向应用多核软件辅助设计  55-58
    5.3.1 面向应用多核体系方案  55-56
    5.3.2 总体软件设计流程  56-57
    5.3.3 算法举例  57-58
  5.4 总结  58-60
6 总结与展望  60-61
参考文献  61-65
致谢  65-66
攻读学位期间科研贡献  66-67

FPGA软件装箱算法研究

内容摘要

全文目录

相似论文