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

基于直流通路模块(DCCB)的快速电路划分算法

作　者: 周晓伟
导　师: 杨华中
学　校: 清华大学
专　业: 电子科学与技术
关键词: SPICE 多核并行计算电路划分 DCCB SCC VTM和DDM
分类号: TN402
类　型: 硕士论文
年　份: 2009年
下　载: 6次
引　用: 0次
阅　读: 论文下载

内容摘要

随着集成电路(Very Large Scale Integrated circuits,VLSI)的高速发展,电路的设计规模越来越庞大,结构越来越复杂,系统规模、时钟频率和器件密度都急剧增长。这一发展趋势使得常用的一系列辅助集成电路设计仿真工具(如SPICE、Spectre等)在仿真周期、仿真效率方面面临严峻的考验。另一方面,近年来多核CPU飞速发展并逐渐占据CPU市场的主导,很多核的CPU也在国外一些实验室问世(MIT RAW 64, Intel Polaris 80)。针对目前常用的电路仿真软件,设计一套和成熟的多核CPU硬件结构配套的电路划分、任务分配和并行迭代软件算法是多核并行加速仿真这一课题的一个关键点。为此,本文从电路物理结构出发,在图论基础上吸取现有VLSI电路的一些经验规律,针对并行SPICE电路仿真提出一种基于直流通路的模块(DCCB)的快速电路划分算法。依实际划分电路算法的流程,本文详细讨论了读入识别电路网单、建立记录电路各元件信息、具有直流通路的MOS晶体管群(DCCB)的划分、基于Tarjan递归算法的强连通分量(SCC)识别,对以SCC为基本单元的精简图进行划分这几个重要环节及其中应用的一些优化策略。算法的机器时间主要由电路中元器件的数目决定,同时也受电路网络中DCCB和SCC数目的一定影响。采用DCCB为基单元的算法和原始的基本算法在一些实际的测试电路上进行了机器时间、划分解质量,并行迭代的收敛速度等一系列比较,实验的结果基本附和理论分析和预测,令人满意。与几种经典的传统划分算法相比较,本论文提出的算法本身有明显的速度提高;同时,系统中对网络的DCCB分块和组合部分有很好的稳定性,受电路规模增大,结构变化和参数设置变化的影响非常小。十年来,电路划分相关算法已取得很大进展,并基本形成一套理论和方法

全文目录

摘要  2-3
Abstract  3-7
第1章引言  7-14
  1.1 超大规模集成电路的发展  7-8
  1.2 EDA 仿真工具简介  8-10
  1.3 多核CPU 的现状和发展趋势  10
  1.4 多核CPU 并行计算与电路划分  10-12
  1.5 论文内容及结构  12-14
第2章传统电路划分方法简介  14-21
  2.1 电路划分问题简介  14-15
  2.2 电路划分问题的经典算法  15-21
    2.2.1 Kernighan-Lin（k-L）算法  16-17
    2.2.2 Fiduccia-Mattheyses（F-M）算法  17-18
    2.2.3 模拟退火/遗传算法  18-19
    2.2.4 时序驱动的划分算法（簇生长算法）  19-21
第3章电路划分的图论基础  21-31
  3.1 图的定义和术语  21-23
  3.2 图的存储结构  23-24
  3.3 无向图中的顶点分裂  24
  3.4 图的遍历  24-27
    3.4.1 深度优先搜索  25-26
    3.4.2 广度优先搜索  26-27
  3.5 求图的连通分量  27-29
  3.6 有向无环图  29-31
    3.6.1 3.6.1 有向无环图的定义  29
    3.6.2 有向图的拓扑顺序  29-31
第4章读入电路网单和识别DCCB  31-43
  4.1 CMOS 数字电路网络  32-33
  4.2 基于DCCB 的子网络的划分  33-43
    4.2.1 分块算法的图论分析  35-38
    4.2.2 实际算法程序中DCCB 分块算法的实现  38-41
    4.2.3 子网络划分示例  41-43
第5章子网络排序和识别SCC  43-49
  5.1 子网络排序的图论分析  43-45
  5.2 实际算法程序中衍生图排序识别SCC 算法的实现  45-47
  5.3 子网络排序和识别SCC 示例  47-49
第6章算法实现中的一些策略和改进  49-57
  6.1 Trie 树存储和查询节点名  49-53
  6.2 过大环的检测和“忽略”  53-57
第7章实验数据和结果评估  57-70
  7.1 实验程序的结构和功能说明  57
  7.2 已测电路示例及测试结果评估  57-70
    7.2.1 示例电路一：两位计数器[9]  57-64
    7.2.2 示例电路二：射频前端中的电荷泵  64-70
第8章总结和工作展望  70-76
  8.1 工作总结  70-71
  8.2 后续工作计划和展望  71-76
    8.2.1 SPICE 算法内核、DDM 算法和VTM 算法简介  71-72
    8.2.2 实验计划的并行仿真方案  72-74
    8.2.3 基于多核结构的任务分配  74-76
参考文献  76-79
致谢  79-80
个人简历、在学期间发表的学术论文与研究成果  80

基于直流通路模块(DCCB)的快速电路划分算法

内容摘要

全文目录

相似论文