不相交路径问题及其在ATLAS编译系统中的应用

论文摘要

ATLAS语言是一种高级测试语言,其编译系统需要完成常规语句的编译和设备分配两方面工作。设备分配是决定整个编译器成功与否的关键,解决它需要涉及不相交路径问题,然而在图中构造不相交路径是一类困难的组合优化问题,目前还没有很好的解决方法。现有自动测试系统中一般通过设计具有良好结构的开关网络来降低软件解决设备分配问题的难度。在本文中,我们围绕着ATLAS设备分配对不相交路径问题做了基本的研究。首先,本文考察几类特殊图中的不相交路径问题,使用得到的相关结论指导ATLAS开关网络的设计过程。其次,引入时间因素,我们对不相交路径问题进行推广并提出一个基于启发的在线算法,该算法能很好的解决具有普遍输入的不相交路径问题。最后介绍如何将ATLAS设备分配问题抽象为不相交路径问题并使用我们设计的算法进行设备分配。我们还对该算法实现与另外两种ATLAS设备分配解决方案的性能进行了比较,结果表明本文的算法能更好的解决ATLAS设备分配问题。

论文目录

• 提要
• 第一章 绪论
• 1.1 问题定义
• 1.2 研究现状和意义
• 1.3 本文所做的工作
• 第二章 背景知识
• 2.1 MENGER 定理
• 2.2 网络流理论
• 2.2.1 网络流与Fold-Fulkerson 定理
• 2.2.2 路径问题的网络流描述
• 2.3 两类特殊图定义
• 第三章 特殊图中不相交路径问题
• 3.1 完全图和完全二分图中边不相交路径问题
• 3.1.1 完全图中边不相交路径问题
• 3.1.2 完全二分图中边不相交路径问题
• 3.2 分裂图中边不相交路径问题
• 3.2.1 顶点不相交路径
• 3.2.2 边不相交路径
• 3.3 一类特殊图中的不相交路径问题
• 3.3.1 顶点不相交路径
• 3.3.2 边不相交路径
• 3.4 非阻塞网络设计
• 第四章 一个任意图中不相交路径算法
• 4.1 基本算法
• 4.1.1 算法基本描述
• 4.1.2 启发函数
• 4.1.3 算法正确性证明
• 4.1.4 算法分析
• 4.2 问题和算法推广
• 4.2.1 问题的推广形式
• 4.2.2 算法推广
• 4.2.3 算法改进
• 第五章 ATLAS 设备分配系统设计与实现
• 5.1 ATLAS 设备系统
• 5.1.1 ATLAS 测试需求
• 5.1.2 ATLAS 设备分配策略
• 5.2 ATLAS 开关网络
• 5.2.1 开关模型
• 5.2.2 开关数据库及其图结构
• 5.2.3 设备匹配
• 5.3 分配算法实现
• 5.3.1 设备分配原理
• 5.3.2 算法实现
• 5.4 各种实现方法比较
• 第六章总结
• 参考文献
• 摘要
• ABSTRACT
• 致谢
• 导师及作者简介