论文题目: 最小自由度优先算法的改进和应用
论文类型: 硕士论文
论文专业: 计算机科学与技术
作者: 刘涛
导师: 吴为民
关键词: 布局,布图规划,最小自由度优先,确定性布局算法,六边形,三角形布局
文献来源: 清华大学
发表年度: 2005
论文摘要: 纳米技术的飞速发展对超大规模集成电路(VLSI)设计技术提出了越来越大的挑战。物理设计是集成电路设计的重要组成部分,而布局是物理设计中最重要的一环。集成电路布局问题是一个非常复杂的组合优化问题,已被证明是NP-Hard问题。基于最小自由度优先原则(LFF)的布局算法是一种确定性的布局算法,它具有多项式的时间复杂度,该算法的实验结果在面积优化方面优于基于随机优化方法的布局算法。为适应技术的发展,需要对算法做出改进和扩展,本文的工作也是围绕这方面的内容展开。首先LFF算法采用了kd-tree作为基本数据结构,而且设计了对应于kd-tree结构的自由度评测方法。尽管kd-tree是一种有效的数据结构,但是具体到LFF的算法过程上,我们期望能进一步减小算法的复杂度。同时,由于LFF算法是一种确定性的布局算法,因此我们希望LFF算法的确定性步骤能够更科学和有效。因此本文着重对LFF算法的数据结构、决策方法进行改善,以期得到更好的结果。其次,对于LFF算法首先应用在了2D直角模块的布局上,但是随着新技术的发展,新的六边形电路的出现能够为布局算法带来了新的挑战。将LFF算法应用到新的六边形/三角形布局将是这篇论文的另一个方向。
论文目录:
摘要
Abstract
第1章 引言
1.1 引言
1.2 IC CAD 技术
1.3 布图设计
1.4 布图规划与BBL 布局
1.5 基于随机优化算法的布图规划与布局
1.6 本文所完成工作
1.7 论文的组织结构
第2章 预备知识
2.1 问题描述
2.2 基本数据结构
2.3 自由度
2.4 LFF 算法基本外流程
2.5 LFF 算法基本内流程
2.6 LFF 算法复杂度分析
第3章 最小自由度优先算法的改进
3.1 最小自由度优先算法的数据结构
3.2 Region-Corner 数据结构
3.3 LFF 算法数据结构的改进
3.4 改进的最小自由度优先算法的流程
3.5 改进的最小自由度优先算法的复杂度分析
3.6 改进的最小自由度优先算法的实验结果
3.7 小结
第4章 六边形边框/三角形模块布局
4.1 问题提出
4.2 问题描述
4.3 算法流程
4.4 实验结果及复杂度分析
4.5 小结
第5章 总结和展望
5.1 论文工作总结
5.2 今后工作展望
参考文献
致谢
个人简历、在学期间发表的学术论文与研究成果
发布时间: 2007-03-14
参考文献
- [1].基于编程软件的少自由度并联机构自由度计算的相关研究[D]. 姜珊.燕山大学2013
- [2].基于最小自由度优先原则的布局算法研究[D]. 杨中.清华大学2004
- [3].四自由度视觉系统的结构设计和控制系统的实现[D]. 陈书乔.东南大学2005
- [4].基于志愿优先算法的选课系统研究[D]. 刘莲辉.湘潭大学2010
- [5].基于用户信息图谱的互联网金融虚假用户信息检测系统的设计与实现[D]. 奥渊博.太原科技大学2018
- [6].超大规模集成电路详细布局算法研究[D]. 刘杰.西安电子科技大学2010
- [7].基于力学模型的图布局算法实验性对比研究[D]. 熊杰元.山西大学2011
- [8].基于二次目标函数的标准单元布局算法研究[D]. 崔力强.西安电子科技大学2010
- [9].船舶二自由度运动仿真平台研究[D]. 余泛泳.大连海事大学2014
- [10].车辆驾驶仿真器二自由度体感仿真系统设计[D]. 王睿.西南交通大学2012
相关论文
- [1].非曼哈顿互连结构下的布图规划算法研究[D]. 魏耀广.清华大学2007
- [2].CAR构件解析器和编辑器的研究与实现[D]. 贺嘉.清华大学2005
- [3].利用SNMP代理技术改进DDN网管系统[D]. 金松.清华大学2005
- [4].异构存储区域网络中存储虚拟化技术研究[D]. 孟冉.清华大学2005
- [5].基于语义的半结构化文档检索[D]. 闫学东.清华大学2005
- [6].基于语义的网络服务匹配机制的研究与实现[D]. 张钋.清华大学2005
- [7].关键词抽取和结构化列表包装的方法研究[D]. 许晖.清华大学2005
- [8].基于机器学习的人脸面部情感图像合成[D]. 周川.清华大学2005
- [9].嵌入式信息终端硬件设计及低功耗和信号完整性研究[D]. 罗昊.清华大学2006
- [10].基于内容的视频检索[D]. 郑吴杰.清华大学2006