基于李群机器学习算法的智能布线

论文摘要

矩阵布线是微电子电路系统的关键技术之一,也是一个复杂而庞大的工程。从第一个基于有网格的Lee算法,到D.W.Hightower提出的逃避法概念布线,期间印刷电路板布线算法得到空前的发展。随着电子元器件结构的变化的复杂性问题,现有的自动布线算法越来越不能满足人们的要求,本文选择李群机器学习来做一种尝试性的研究,将布线问题转化为在点集合中求布线点间的最短路径的问题,从而得到最优布线路径。经过之前一系列的努力,取得的成绩包括如下。在分析已有自动布线算法的基础上,给出基于李群机器学习算法的智能布线技术。其主要内容有:1.将李群机器学习模型、子空间轨道生成广度优先算法及深度优先算法,作为支持本文算法的理论基础。2.结合图论知识和人工智能解决问题的思路,将布线问题转化为一种偏序关系,描述为一种格结构,从而得到速度快、具有高布通率的智能布线算法。这部分是本文的重点。3.分析数据,通过具体实例给出了解决的详细方案,给出算例,并总结出算法的特点。本文提出的自动布线算法,在实验测试运行中被证明了能够满足一定的实际应用的要求,达到了预期目标。当然,本文算法在应用中还存在部分限制,还有许多方面需要进一步展开研究。

论文目录

• 中文摘要
• Abstract
• 第一章 绪论
• 1.1 课题背景
• 1.2 电子设计技术的发展状况
• 1.2.1 CAD、CAE 和 ESDA 的概念和特点
• 1.2.2 PCB 布局布线概况
• 1.2.3 李群机器学习的发展状况
• 1.3 自动布线的作用
• 1.4 设计系统中自动布线的基本概念和分类
• 1.4.1 基本概念介绍及布线设计目标
• 1.4.2 目前面临的问题和分类
• 1.5 自动布线算法的概况及分析
• 1.5.1 迷宫算法及其衍生算法
• 1.5.2 线探索算法及其改进算法
• 1.6 其它算法简介
• 1.7 研究内容和意义
• 1.7.1 研究内容
• 1.7.2 研究意义
• 1.8 本章小结
• 第二章 李群机器学习及相关知识点
• 2.1 图论、四维二叉树及动态规划算法概述
• 2.2 李群机器学习子空间轨道生成算法
• 2.2.1 LML 中 Dynkin 图、偏序集及格的基本概念
• 2.2.2 LML 子空间轨道生成广度优先及深度优先学习算法
• 2.2.3 LML 子空间轨道带有启发信息的生成学习算法
• 2.3 本章小结
• 第三章 基于LML 算法的智能布线
• 3.1 LML 的智能布线算法概述
• 3.2 设计目标
• 3.2.1 设计的一般要求
• 3.2.2 综合考虑的设计目标
• 3.2.3 LML 智能布线算法的设计目标
• 3.3 布通率影响因素及解决方法
• 3.3.1 PCB 布线顺序的影响及常用处理方法
• 3.3.2 基于LML 学习子空间的干扰图排序方法
• 3.4 基本线型及规定
• 3.5 最短路径搜索及举例
• 3.6 本章小结
• 第四章 实例分析
• 4.1 LML 智能布线算法的数据结构
• 4.2 综合性能测试与分析以及与已有迷宫算法的比较
• 4.3 相关问题分析
• 4.3.1 算法实现中的问题
• 4.3.2 进一步改进的方法
• 4.4 本章小结
• 第五章 结束语
• 5.1 总结
• 5.2 展望
• 参考文献
• 攻读学位期间公开发表的论文
• 致谢