超大规模集成电路布线中的图论问题研究
本文选题：VLSI + 通道布线 ； 参考：《安徽理工大学》2017年硕士论文
【摘要】：大规模集成电路设计(VISI)中的线网关系可以用点和边来描述,这样组合图论思想就可以应用到VLSI物理设计中,在物理设计的研究过程中,使用图论的方法来研究问题已经成为一个主流的方向。本论文我们用组合图论的思想方法来解决VLSI物理设计中通道布线的轨道高度问题。第一章是绪论部分。本章介绍了 VLSI的设计流程和国内外研究现状,以及与布线有关的其他物理设计流程,通过这些介绍,刻画了布线在物理设计中的作用,并展示了本论文研究的意义。第二章是通道布线的算法综合介绍。通道布线的问题可以分为很多种情况,每一种都需要不同的算法思想,本章我们从布线的节点位置关系和布线的层数来分类介绍不同的算法思想和算法结论。第三章是给定水平约束图为路的通道布线算法设计与分析。通过分析水平约束图的结构特点得到线网的结构关系,进而设计算法,并分析算法的时间复杂性和我们设计的算法的优势。第四章给定水平约束图为星图的通道布线算法设计与分析。通过分析水平约束图的结构特点得到线网的结构关系,进而设计算法,并分析算法的时间复杂性和算法的优势。
[Abstract]:The line network relationship in VISI can be described by point and edge, so the combinatorial graph theory can be applied to the VLSI physical design. In the course of the study of physical design, using graph theory to study the problem has become a mainstream direction. This paper is solved by the thought method of combinatorial graph theory. The problem of track height of channel wiring in VLSI physical design. Chapter 1 is the introduction part. This chapter introduces the design process of VLSI and the current research status at home and abroad, as well as other physical design processes related to wiring. Through these introductions, it depicts the role of wiring in physical design, and shows the significance of the research in this paper. The second chapter is The problem of channel wiring can be divided into many kinds of situations, each of which needs different algorithm thought. In this chapter, we introduce different algorithm ideas and algorithm conclusions from the location relation of the wiring and the number of the wiring. The third chapter is a channel routing algorithm for the fixed level constraint graph. By analyzing the structural characteristics of the horizontal constraint graph, the structure relationship of the line network is obtained, and then the algorithm is designed, and the time complexity of the algorithm and the advantages of the algorithm we design are analyzed. In the fourth chapter, the design and analysis of the channel routing algorithm for the star map are given by the given horizontal constraint graph. The line network is obtained by analyzing the structure characteristics of the horizontal constraint graph. Then we design the algorithm and analyze the time complexity and the advantage of the algorithm.
【学位授予单位】：安徽理工大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157.5
【相似文献】
相关期刊论文 前3条
1 李明栋;王植林;;住宅装修布线的发展和存在的问题[J];科技信息;2009年16期
2 陈善为;;CAM工程建模中细分布线技术的原理及应用[J];贵州大学学报(自然科学版);2014年02期
3 ;[J];;年期
相关会议论文 前2条
1 李然山;李强;何伟;;综合布线的发展[A];中国通信学会2002年光缆电缆学术年会论文集[C];2002年
2 魏发远;;虚拟布线技术[A];中国工程物理研究院科技年报（2005）[C];2005年
相关重要报纸文章 前10条
1 中国电子科技集团公司第二十八研究所 张豫沛;6类布线如鲠在喉[N];计算机世界;2005年
2 本报记者 张欣;平平淡淡才是真[N];计算机世界;2003年
3 张欣;从“智控归一”看端到端布线[N];计算机世界;2003年
4 本报记者 吴作鹏;综合布线：更宽广 更智能[N];计算机世界;2004年
5 本报记者 张欣;布线的归属[N];计算机世界;2003年
6 ;6类标准水落石出[N];网络世界;2002年
7 马健;六类布线系统提升楼盘信息化[N];中国房地产报;2003年
8 康宁布线中国市场中心;慎待六类布线[N];中国计算机报;2002年
9 ;近看大唐电信综合布线系统[N];网络世界;2008年
10 本报记者 晓夏;从综合布线走向智能楼控[N];计算机世界;2003年
相关博士学位论文 前2条
1 庄昌文;超大规模集成电路若干布线算法研究[D];电子科技大学;2001年
2 李祥友;激光微细熔覆电子浆料柔性布线技术与设备[D];华中科技大学;2005年
相关硕士学位论文 前10条
1 褚静;超大规模集成电路布线中的图论问题研究[D];安徽理工大学;2017年
2 陈科;基于SAT的FPGA布线技术研究[D];北京交通大学;2010年
3 张柯;激光直写布线技术的应用研究[D];长春理工大学;2009年
4 刘静波;综合布线系统在长春机场的应用与设计[D];吉林大学;2009年
5 楼定华;非曼哈顿结构通道布线算法研究[D];电子科技大学;2005年
6 张孙勇;基于图论的单元上通道布线算法研究[D];电子科技大学;2006年
7 常琳;FPGA布线技术的研究[D];北京交通大学;2014年
8 占国华;嵌入式高性能数据处理系统的高速布线技术及SI分析[D];上海交通大学;2007年
9 廖海涛;测试芯片设计中布线算法的研究与实现[D];浙江大学;2014年
10 黄世杰;考虑串扰效应与时延的多级布线器研究[D];上海交通大学;2008年
，本文编号：2027866
本文链接：https://www.wllwen.com/kejilunwen/yysx/2027866.html
