开关盒布线设计报告.doc

面向对象编程技术课程设计报告 姓 名： 何文韬 学 号： 21509149 院 系： 电信 控制 邮 箱： 1305415168qq.com 完成日期： 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 结果分析及不足由于“后期优化”部分的算法实现较复杂，此处的深搜代码实现的不是十分正确，剪枝不够，导致有些连线不能在有限时间内计算出来，只能以后再做完善。关于程序耗时，前面的操作耗时几乎可以忽略，最主要的耗时部分是“后期优化”部分，此部分有相应的宽搜和深搜代码，宽搜代码耗时不会很高，主要是后面的深搜代码，目前对深搜的剪枝不够，有时会出现运行不完的现象，不过，正常情况下，是会在百毫秒的数量级内完成的。