开关盒布线设计报告 本文关键词：布线，开关，报告，设计
开关盒布线设计报告 本文简介：面向对象编程技术课程设计报告姓名：何文韬学号：21509149院系：电信控制邮箱：[email protected]完成日期：2015-12-09开关盒布线问题1问题分析开关盒布线问题，从整个系统实现上分析，应包含以下几方面：开关盒的创建、载入与保存，可布线判断，布线算法的实现，界面显示等等。1.1
开关盒布线设计报告 本文内容：
面向对象编程技术课程设计报告
姓
名：
何文韬
学
号：
21509149
院
系：
电信
控制
邮
箱：
[email protected]
完成日期：
2015-12-09
开关盒布线问题
1
问题分析
开关盒布线问题，从整个系统实现上分析，应包含以下几方面：开关盒的创建、载入与保存，可布线判断，布线算法的实现，界面显示等等。
1.1
开关盒的创建、载入、与保存
需定义相关C++类描述开关盒属性及其相关操作，属性包括开关盒尺寸、线宽、线间距、引脚分布、布线网组等；在软件界面设置各参数后，需将开关盒参数保存至数据库，并且，随时可以从数据库中调出已经建立好的开关盒进行重新布线、修改等操作；数据库的相关操作使用MFC的DAO数据库接口。运行环境选择VS2005。
1.2
可布线判断
可布线判断，即判断针对当前开关盒属性，在各引线不交叉的前提下，是否可以完成各网组的布线。值得注意的是，网组的可布线与否应当取决于两方面：网组逻辑是否可布线（网组间存在交叉则肯定不能布），与实际布线是否可完成（受限于开关盒尺寸、线宽及线间距等参数，逻辑上可以布线但实际中可能无法完成）。故可布线判断分为两部分：初步的可布线逻辑判断，和最后的实际布线探测。
1.3
布线算法实现
实现布线，需考虑诸多问题，如布线路径的表示方法、怎样引入线间最小间距限制等等，综合考虑，采用一个二维网格地图来划分开关盒，将很方便的解决这些问题，如图1.1所示:
图1.1
将开关盒布线区域划分为二维网格
每个正方形网格的边长即等于线宽加上线间距，即可引入线宽、线间距等参数的限制；每一个网格就是一个路径节点，我们要获得两个引脚之间的导线路径，即计算出路径所经过的节点即可。
经过上面的预处理后，布线问题可简化为二维地图的约束化路径搜索问题。具体搜索过程见第二部分-算法选择与方案设计。
1.4
界面显示
编写简单的MFC基于对话框的界面应用程序，完成各功能交互，重写对话框的Opaint()函数，完成开关盒及布线的绘制；通过设置定时器可实现布线过程的动态绘制。
2
算法选择与方案设计
基于上面的问题分析，下面着重介绍布线的实现过程。
2.1
布线过程整体方案设计
值得注意的是，开关盒的布线过程应该是一个整体优化的过程，而不是简单的各条连接线按顺序搜索路径（因为一个局部连线路径虽然可行，但很有可能会影响其它路径的连接，导致全局整体布线效果差，最坏的情况还可能导致本可以完成布线，却最终因一条路径的选取影响了全局，而导致整体布线失败）。
直觉上，可以在完成当前导线连接的过程中，实时的调节之前已经连接好的线路，进而达到最后的整体最优。然而，实际中，调节已经连接完毕的线路实现复杂，且没有很好地理论指导，难于实现。
总结上面所述，就是在连接每一条线路时，由于缺乏对全局的观测（因为全局到最后才能观测到），当前线路几乎不可能（或很难）连接成最优的。
为解决上面的问题，这里提出了一个理念：整体布线最优=布线的最小实现+后期优化；下面依次解释一下各个概念：
（1）整体布线最优：整体最优其实有很多种描述方法，比如说整体线路长度最短，或者说整体线路看起来比较美观（这个其实没有准确的描述）；这里，我们选取整体线路看起来比较美观作为布线最优，选取了一个定量的方式来描述“美观”，即每条线在不影响可布线的前提下，尽可能少拐弯。
（2）布线的最小实现：即最大可能的保证当每一条连线不会影响到其它连线。实现过程很简单，通俗的说，就是按照每一条连线的两个端点距离由小到大的顺序，搜索路径，在搜索路径的过程中，尽可能让线路贴边走，如图2.1所示：
图2.1
布线的最小实现
从图2.1可以看出，布线的最小实现已经完成了布线任务，只是，看起来不是很美观。
这里值得说明的是，从直观的观察上即可看出，能否实现布线的最小实现，是开关盒可布线与否的充要条件。即回答了1.2中的问题。
布线最小实现过程：在1.3中介绍的划分好二维网格后，由起点到终点，使用深度优先搜索探测路径，在所搜的过程中，要时刻根据目标点与当前点的位置关系，调整搜索的方向为“贴边”的方向，这样最后的路径才是一条“贴边”的路径。
（3）后期优化：在介绍整体布线最优时已经提到，本文中的最优原则即是每条线在不影响可布线的前提下，尽可能少拐弯。在实现了布线最小实现的前提下，我们再按顺序对每一条线路进行优化，此时优化可以观测到全局，因为布线的最小实现即是全局，这样，每条线的优化以已完成的最小实现为限制，不会影响到全局的整体布线。
拐弯最少，是一个优化问题，在实现的过程中使用了宽度优先搜索的方法，先从起点到终点，计算出需最少拐弯个数；再根据计算出的最少拐弯个数，利用深度优先搜索，记录下这条路径。
2.2
整体方案流程
根据2.1中描述的“整体布线最优=布线的最小实现+后期优化”原则，设计了如图2.2的方案流程：
图2.2
开关盒布线整体方案流程
3
编程实现
3.1软件交互界面
软件系统采用MFC基于对话框的界面程序框架，所设计的软件系统界面如图3.1所示：
图3.1
软件系统界面
点击“手动创建新开关盒”按钮，下方参数控件变为可用，可设置开关盒参数；
点击“从数据库中导入新开关盒”按钮，即可从数据库中调出已有的所有开关盒，选择其中一条记录，点击“导入”，即可导入此开关盒，见图3.2：
图3.2
从数据库中导入开关盒
手动创建或从数据库导入开关盒后，点击“开始布线”按钮，可完成布线功能；
右侧显示窗口，显示开关盒状态及布线结果，为防止动态显示时屏幕闪烁问题，采用双缓存策略进行实时显示（即创建内存DC）。
选择“实时显示”单选按钮后，布线结果将以动态形式显示。
3.2
算法编程实现
定义了若干C++类用来描述开关盒各属性及其相关操作，定义的类主要包括：开关盒类CSwitchBox，连接类CConnection，引脚类CPin，二维网格节点类CNode；
实现的过程中主要用到的算法是深度优先搜索和宽度优先搜索，深度优先搜索由递归实现，宽搜最少拐弯数时，采用宽搜+优先队列技术；具体实现过程见代码。
3.3
运行结果
下面是几组开关盒的运行结果，均已在数据库中保留：
图3.3
示例1结果
图3.4
示例4结果
3.4
结果分析及不足
由于“后期优化”部分的算法实现较复杂，此处的深搜代码实现的不是十分正确，剪枝不够，导致有些连线不能在有限时间内计算出来，只能以后再做完善。
关于程序耗时，前面的操作耗时几乎可以忽略，最主要的耗时部分是“后期优化”部分，此部分有相应的宽搜和深搜代码，宽搜代码耗时不会很高，主要是后面的深搜代码，目前对深搜的剪枝不够，有时会出现运行不完的现象，不过，正常情况下，是会在百毫秒的数量级内完成的。