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

遗传算法在VLSI设计自动化中的应用研究

作　者: 王小港
导　师: 姚林声
学　校: 中国科学院上海冶金研究所
专　业: 微电子学与固体电子学
关键词: 基于遗传算法 应用研究 VLSI 电路划分 测试矢量 测试集 穷举算法 顺序向量 组合逻辑电路 多层通道布线
分类号: TN402
类　型: 博士论文
年　份: 2001年
下　载: 365次
引　用: 17次
阅　读: 论文下载
 

内容摘要


遗传算法不仅仅是一种单纯的优化算法，而是一种以进化思想为基础的一般方法，对于复杂问题的解决是一个有力工具。遗传算法是概率性全局收敛的，具有并行性搜索、全局性优化、算法设计简单、操作性强、效率高以及不依赖于问题的模型等特性。近些年来遗传算法作为一种自适应启发式概率性迭代式全局搜索算法，在许多方面得到了应用。 本文在详细分析了遗传算法的原理的基础上，着重研究了VLSI的划分、布局、布线、测试生成以及测试集的极小化等优化问题，并设计了相应的遗传算法。论文的主要工作和创新有： 1．简单回顾了遗传算法的发展历程，并介绍了遗传算法的最新发展。对遗传算法的选择、交叉、变异等遗传算子进行了讨论，给出了遗传算法的结构以及遗传算法设计的重点，详细阐述了遗传算法的积木块理论，模式定理和NFL（No Free Lunch）原理。 2．分析了VLSI电路划分的性质和特点，提出了基于遗传算法的VLSI电路的划分方法，设计了适用于电路划分的遗传算法，该算法不仅可以完成电路的二划分和K划分问题，还能对有面积约束的多目标电路划分问题进行优化，得到了比较满意的结果。 3．研究了布局和布图规划问题，提出了一种新的基于遗传算法的VLSI布图规划方法。在染色体的表达中，对软模块的不同形状和硬模块的布局方向进行了编码，并设计了有效的启发式解码方法进行解码。算法能完成对布局面积和模块连线总长度同时进行优化的多目标优化问题，其结果优于现有算法。 4．研究了多层通道布线问题，提出了一种基于通孔数最小化的多层通道布线算法。算法采用非预留层模型，首先根据线网之间的位置关系利用遗传算法将各线网合理地分配到对应的布线层中去，然后利用遗传算法得到相关有线层中线网的最佳布线顺序向量，最后根据得到的顺序向量利用“沉积法”将各线网布于合理的通道上。该算法克服了传统通孔优化算法中原始布线对优化结果的不利影响，使通孔的优化达到很好的效果，其结果优于已有算法。 5．讨论了组合逻辑电路的故障诊断的方法，故障的类型。并在详细分析伪穷举算法的基础上，给出了基于遗传算法的适用于伪穷举算法的分块算法（DGP-GA）和着色方法（MCR-GA）。可以大大减少电路完全测试所需的测试矢量的数目，对加速测试过程和减小测试代价有积极的意义。 6．讨论了测试集的优化问题，通过对编码方式的讨论，评估函数的设计，分别给出了面向测试矢量的测试集优化遗传算法和面向故障的测试集优化算法，较好的解决了测试矢量集最小化问题。

全文目录


中文摘要  7-9
英文摘要  9-11
第一章 引言  11-22
  1．1 集成电路CAD技术的发展  11-12
  1．2 VLSI设计流程  12-13
  1．3 布图设计过程  13-14
  1．4 布局和布线的复杂性分析  14-16
  1．5 布图模式  16-18
    1．5．1 全定制设计模式  16
    1．5．2 标准单元设计模式  16-17
    1．5．3 门阵列设计模式  17
    1．5．4 门海设计模式  17
    1．5．5 现场可编程门阵列  17-18
    1．5．6 不同设计方法的比较  18
  1．6 测试生成和测试集优化  18-20
  1．7 遗传算法  20
  1．8 本文结构  20-22
第二章 遗传算法的发展及理论基础  22-46
  2．1 进化算法简介  22-27
    2．1．1 遗传算法（Genetic algorithms，GA）  23-24
    2．1．2 进化规划（Evolutionary programming，EP）  24-25
    2．1．3 进化策略（Evolution strategies，ES）  25
    2．1．4 三种进化算法的关系  25-27
  2．2 遗传算法的特点、结构和理论研究  27-33
    2．2．1 遗传算法的历史  27-29
    2．2．2 传统遗传算法的结构  29-32
    2．2．3 遗传算法的特点  32-33
  2．3 遗传算法的理论基础  33-39
    2．3．1 模式定理  33-36
    2．3．2 积木块假设  36-37
    2．3．3 遗传算法的收敛性  37-38
    2．3．4 No Free Lunch定理  38-39
  2．4 遗传算法的发展  39-45
    2．4．1 并行遗传算法  39-43
    2．4．2 层次遗传算法  43-45
  2．5 遗传算法的设计重点  45
  2．6 小结  45-46
第三章 基于遗传算法的VLSI电路划分方法  46-56
  3．1 引言  46-47
  3．2 电路划分问题  47-48
  3．3 电路划分算法的回顾  48-49
  3．4 电路划分的遗传算法设计  49-52
    3．4．1 编码方式  49
    3．4．2 染色体的交叉  49-50
    3．4．3 染色体的变异  50
    3．4．4 评估函数  50-51
    3．4．5 染色体的选择  51-52
  3．5 算法流程  52-53
    3．5．1 算法流程图  52
    3．5．2 初始化  52
    3．5．3 初始种群的产生  52-53
    3．5．4 循环结束的判别  53
  3．6 算法复杂性分析  53
    3．6．1 算法的时间复杂度  53
    3．6．2 算法的空间复杂度  53
  3．7 实验结果  53-55
    3．7．1 二划分的测试  53-54
    3．7．2 K划分多约束情况的测试  54-55
  3．8 小结  55-56
第四章 基于遗传算法的VLSI布图规划方法  56-70
  4．1 布图规划和布局  56
  4．2 VLSI布图规划问题的描述  56-60
    4．2．1 数据结构  56-57
    4．2．2 版图结构  57-58
    4．2．3 布局中的线长估计  58-60
  4．3 布图规划和布局算法的回顾  60-62
  4．4 染色体的编码和评估函数  62-63
    4．4．1 染色体编码  62
    4．4．2 评估函数的设计  62-63
  4．5 布图规划问题的遗传算法设计  63-65
    4．5．1 染色体的选择  63
    4．5．2 染色体的交叉  63-64
    4．5．3 染色体的变异  64-65
  4．6 启发式解码算法  65-66
    4．6．1 解码规则  65
    4．6．2 启发式算法  65-66
  4．7 算法复杂度分析  66-67
    4．7．1 算法的时间复杂度  66
    4．7．2 算法的空间复杂度  66-67
  4．8 实验结果和讨论  67-69
    4．8．1 算法的总流程  67
    4．8．2 实验结果  67-69
  4．9 小结  69-70
第五章 遗传算法在通道布线中的应用  70-91
  5．1 通道布线  70-74
    5．1．1 通道布线概念的提出  70-71
    5．1．2 基于网格的通道布线模型  71
    5．1．3 水平约束和垂直约束  71-73
    5．1．4 连通孔数最小化通道布线的图论模型  73-74
  5．2 布线的主要算法的回顾  74-76
  5．3 通孔最小化三层布线的算法步骤  76-77
  5．4 最佳着色的遗传算法模型  77-79
    5．4．1 染色体的表达  77
    5．4．2 目标函数的确定  77-78
    5．4．3 交叉、变异和选择  78-79
  5．5 线网排序的遗传算法模型  79-81
    5．5．1 初始群体的产生  79
    5．5．2 适值函数的确定  79-80
    5．5．3 选择  80
    5．5．4 交叉  80
    5．5．5 变异  80-81
  5．6 “沉积法”布线  81-84
    5．6．1 A类和C类线网的布线  81-82
    5．6．2 B类线网的布线  82-84
  5．7 布线总流程图  84-85
  5．8 通孔最小化多层通道布线算法  85-86
    5．8．1 多层通孔最小化通道布线算法  85-86
    5．8．2 计算复杂性分析  86
  5．9 实验结果及讨论  86-89
    5．9．1 实验结果  86-89
    5．9．2 讨论  89
  5．10 小结  89-91
第六章 基于遗传算法的测试生成和故障测试集最小化方法  91-116
  6．1 VLSI故障测试  91-92
  6．2 故障的类型和故障模型  92-93
    6．2．1 故障的分类  92
    6．2．2 故障的模型  92-93
  6．3 伪穷举测试  93-97
    6．3．1 电路划分  93-95
    6．3．2 多输出电路  95-97
  6．4 伪穷举测试传统的分块方法  97-99
  6．5 伪穷举测试的遗传算法设计  99-104
    6．5．1 针对多输出电路的图的着色问题的遗传算法（MCR-GA）  99-101
    6．5．2 多输出电路的图的着色问题的遗传算法（MCR-GA）的复杂性  101-102
    6．5．3 针对电路的有向图划分的遗传算法（DGP-GA）  102-103
    6．5．4 针对电路的有向图划分的遗传算法（DGP-GA）的复杂性分析  103-104
    6．5．5 测试结果与分析  104
  6．6 完全测试集的极小化  104-105
  6．7 故障测试集最小化问题的遗传算法设计  105-108
    6．7．1 编码方式  105-106
    6．7．2 评估函数  106
    6．7．3 染色体的选择、交叉和变异  106
    6．7．4 惩罚法和改进法  106-107
    6．7．5 面向测试矢量的遗传算法的复杂性分析  107-108
  6．8 面向故障的遗传算法  108-112
    6．8．1 编码方式  108
    6．8．2 染色体的交叉  108-109
    6．8．3 染色体的变异  109-110
    6．8．4 评估函数  110
    6．8．5 染色体的选择  110
    6．8．6 算法流程  110-112
    6．8．7 面向故障的遗传算法复杂性分析  112
  6．9 实验结果  112-115
  6．10 小结  115-116
第七章 总结与展望  116-118
参考文献  118-129
发表文章目录  129-130
致谢  130

相似论文

  1. 老子思想在中学语文教学中的应用研究,G633.3
  2. 中医升降理论治疗慢性肾衰的应用研究,R277.5
  3. 探究式教学在体育教育专业武术专选课中的应用研究,G852-4
  4. 植物色彩在城市园林中的应用研究,TU986
  5. 概念图在高中生物教学中的应用研究,G633.91
  6. 合作学习在初中生物教学中的应用研究,G633.91
  7. 论光电幕墙在建筑幕墙设计中的发展及应用,TU228
  8. 石化企业ERP系统的应用研究,TP315
  9. 基于有限元分析软件的仓泵焊接研究与应用,TG457.2
  10. 在线体育视频剪辑系统中元数据的应用研究,TP391.41
  11. 电石灰改良盐渍土底基层试验研究,U412.22
  12. 江西高校Office Hours制度应用研究,G434
  13. 低碳理念在旅游规划中的应用研究,F592;F205
  14. 六西格玛管理在电信基站故障管理中的应用,TN929.5
  15. 虞山绿茶设施摊放技术研究,S571.1
  16. 动态教学赛模式在高校排球普修课教学中的应用研究,G842-4
  17. “脚靶训练”与“手靶训练”在跆拳道横踢技术教学中的应用研究,G886
  18. 支持MBAFF运动估计引擎的VLSI设计与研究,TN47
  19. 寄存器文件的可测性设计与实现,TN407
  20. GS省公路建设“统货统还”融资管理方式应用研究,F542
  21. 动力博弈系统及混沌理论在演化中的应用研究,O225

中图分类: > 工业技术 > 无线电电子学、电信技术 > 微电子学、集成电路（IC） > 一般性问题 > 设计
© 2012 www.xueweilunwen.com