UML类图层次化自动布图算法

UML类图能够有效地帮助软件工程师理解大规模的软件系统,而优化图元的空间布局可以增强类图的可读性和可理解性.由于类图中继承关系具有明显的层次特性,因此类图自动布局大多采用层次化的布图算法.此外,类图布局需要考虑相关的领域知识以及绘制准则,因而通用嵌套有向图层次化布局算法不能直接用于类图的绘制,它们必须加以扩展.但是,已有的类图层次化方法并没有考虑类图中图元的嵌套关系,这将导致自动布局方法不能处理类图中包与类、接口之间的包含关系.在考虑图绘制美学、UML类图绘制以及软件可视化等相关知识的基础上,选取了一组布     

构造面向对象系统依赖图技术研究

本文分析了现有面向对象图形表示方案存在的问题,在此基础之上,提出了基于波动效应分析构造面向对象系统依赖图的方法,通过引入波动效应分析,来完善面向对象程序的语义和减小构图的复杂性,在波动效应分析的基础之上,构造类图、改造面向过程的系统依赖图,结合两个图来描述面向对象程序。通过类图描述不同类之间的关联关系和类的内部定义,在类图中表达过程依赖,改造面向过程的系统依赖图用于表达控制依赖和数据依赖。文中给出了计算波动效应和构造系统依赖图的算法描述。     

利用公共子序列求解固定边框布图问题

提出一种新的固定边框的布图算法．该算法采用SP表示方法，以公共子序列为基础，在随机搜索过程中限定布图宽度的变化，从而使减小芯片面积的目标与固定边框的目标在一定程度上取得一致．与现有的固定边框布图算法相比，文中算法在边框更紧凑、宽长比更大的条件下具有更高的成功率和更短的运行时间．此外，文中算法在布图初始阶段就可以对固定边框的合理性进行评估，避免了因给定的边框不合理而带来的时间上的浪费．     

壁勾链：一个应用于IC布图系统的数据结构

以IC布图应用为背景,本文提出一个表示平面正交矩形划分的称为“壁勾链”的数据结构。它通过定义一组区域邻接指针,把矩形划分上的所有区域勾链起来。基于壁勾链数据结构,平面矩形划分上的点定位、邻域查找、路径搜索等操作可以迅速而有效地完成。壁勾链数据结构可以完整描述矩形划分的几何信息和拓扑信息,适应IC布图系统各个过程对布图表示的要求,可以作为一个集成布图系统中统一的布图表示数据结构。     

基于Single-Sequence布图规划边界约束问题的研究

布图规划是VLSI设计中非常重要的步骤。在计算机辅助设计中,布图被表示成编码以使其容易被计算机处理。Single-Sequence就是一种非常有用的表示布图的编码方法。一个布图中,一些模块如输入输出模块,必须放置在芯片的边界处,这种限制被称为边界约束。本论文提出了用模拟退火算法寻求最优布图的方法,有效地解决了布图规划的边界约束问题。     

一种C++程序的分层切片方法

该文介绍了一种C++程序的分层切片方法。通过构造系统程序层依赖图、类层依赖图、方法层依赖图和语句层依赖图,对C++程序进行分层切片,有效地表示了C++中的单重继承、多重继承、多态和动态绑定,该方法比其它C++切片技术更清晰地描述了C++程序中类之间的各种关系和消息传递机制。     

VLSI平面布图规划中模拟退火算法的加速策略

布局是现代VLSI物理设计中十分关键的步骤,而模拟退火等智能算法在针对宏模块布局的平面布图规划问题中得到广泛应用。针对应用于VLSI平面布图规划的模拟退火算法进行了研究和分析,并针对布图本身特性在退火算法中采用了一种导向性的邻域构造策略来加速算法的收敛,有效地提高了平面布图规划中模拟退火算法的搜索效率。     

随程序规模动态调整的通道优化布线算法

针对常规层次型布图算法在大规模程序中布线混乱的缺点,借鉴Sugiyama层次布局算法,提出了一种随着程序规模动态调整的通道优化布线算法。通过将节点的通道数目与程序规模建立函数关系,以解决现有算法在布图时出现的线路重叠和效率低下的问题;在布图中结合广义张量平衡思想,以减少交叉并实现布图的美观性;并根据调用节点之间的相对位置关系,给出了相应的线路分配和申请策略,实现了布线的有序性。实践证明,该算法能够提高布图效率,有效地减少交叉,实现节点的有序布线和实现简单等优点。     

融合结构与属性相似性的加权图聚集算法

图聚集技术是将一个大规模图用简洁的小规模图来表示,同时保留原始图的结构和属性信息的技术。现有算法未同时考虑节点的属性信息与边的权重信息,导致图聚集后与原始图存在较大差异。因此,提出一种同时考虑节点属性信息与边权重信息的图聚集算法,使得聚集图既保留了节点属性相似度又保留了边权重信息。该算法首先定义了闭邻域结构相似度,通过一种剪枝策略来计算节点之间的结构相似度;其次使用最小哈希(MinHash)技术计算节点之间的属性相似度,并调节结构相似与属性相似所占的比例;最后,根据2方面相似度的大小对加权图进行聚集。实验表明了该算法可行且有效。     

基于新约束图模型的布图规划和布局算法

布图规划和布局构形的表示是基于随机优化方法的布图规划和布局算法的核心问题.针对Non-slicing结构的布图规划和布局,提出了一种新的基于约束图表示的模型.基于该模型及其性质,可以得到近似O(n)时间复杂度的有效的布局算法.通过引入变形网格的假设,得到了一种新的更加精确的Non-Slicing结构的表示模型:梯形网格模型.其空间复杂度为n(3+lg[n]),时间复杂度为O(n),解空间规模为n!2^3n-7.已经证明,梯形网格模型可以表示所有的Slicing结构的布局,同时又可以有效地表示Non-Slicing结构的布局,而时间复杂度与Slicing表示相同.实验结果表明,该表示优于刚刚发表的O-tree模型.梯形网格模型是一种拓扑模型,而O-tree的表示依赖于模块的尺寸,因而梯形网格能更有效地处理含有软模块的的布图规划问题.