图划分方法及其在分布式网络环境下的应用

发布时间：2019-04-13 18:37

【摘要】：图划分具有广泛的应用,例如,应用于VLSI(大规模集成电路)设计,并行计算,数据挖掘和图像分割等,儿乎涵盖了科学与工程的各个领域,因此得到了国内外学者的普遍关注和大量研究。这些研究主要分为两类,一类是专注于图划分算法的研究,另类关注的是图划分应用于不同领域存在的问题。由于图划分是NP-完全问题,所以促使人们不断给出更好的划分方法,本文系统地研究了图划分算法和划分工具。针对图划分在分布式网络环境下应用于并行计算、工业网络优化设计和路网(空间网络)数据有效存储存在的问题,引入了0-1规划理论、非线性规划理论、组合优化理论、聚类图模型、聚类超图模型以及数据聚合技术等,给出了改进的方法和模型,并提出了相应的验证算法。通过大量实验验证了所提方法和模型的正确性和有效性,解决了图划分在这些应用中存在的关键问题。本文主要工作包括以下几个方面： (1)对图划分算法进行了系统、全面地概括和总结,随着图划分问题的不断发展和人们研究的深入,给出了图划分算法当前一些较新的研究成果,以及目前比较流行的图划分工具。 (2)针对图划分应用于分布式并行计算只能表达对称和双向依赖关系的问题,提出了基于O-1规划方法的并行计算图划分模型,该模型能够表达非对称和单向依赖关系的问题,克服了图划分模型表达问题的局限性,并且该模型能够准确区分通信的发送方与接收方。在一些数据集上的实验表明,该模型在负载均衡系数相对小的情况下比标准图划分模型平均减少了5%的通信量。 (3)针对标准图划分模型应用于并行计算不能准确表达通信量,也不能考虑通信延迟和通信量的分布情况对并行性能的影响,提出了改进的图划分模型,该模型采用边界割度量,准确地表达了通信量,并使用多目标代价函数,综合考虑了通信延迟和通信量的分布情况对并行性能的影响。在此基础上,提出了更复杂的改进超图划分模型,该模型既能克服图划分模型应用的局限性,也能考虑通信延迟和通信量的分布情况对并行性能的影响。对提出的模型给出了相应的验证算法,实验结果表明所提模型是正确和有效的。 (4)针对分布式网络控制中的工业网络优化设计问题,提出了基于非线性0—1规划理论对其进行建模,然后通过互联网上求解优化问题常用的求解器NEOS服务器进行求解,克服了使用图划分策略得到的结果需要进一步近似才能得到最终问题求解的不足。在一些数据集上的实验结果表明,所提方法是有效的,并且对于一些小规模的数据集要优于图划分得到的结果。同时,提出了非线性0—1规划与图划分相结合的方法解决工业网络的优化设计问题。 (5)为了在分布式交通控制中有效的聚合查询处理,路网数据应该有效的组织和存储,针对这一问题提出了基于聚类图模型的改进方法,使用边界割衡量后继搜索操作的磁盘访问代价,解决了先前基于聚类图模型不能正确表达后继搜索操作磁盘访问代价的不足。同时利用了磁盘记录先前的访问日志来估计每个网络元素将来的访问频率和磁盘的访问模式,然后使用图划分分配路网数据到磁盘页,这样可以有效地进行路网数据的组织和存储,从而使聚合查询处理的磁盘访问代价最小化,并通过实验验证了所提方法的有效性。
[Abstract]:......
【学位授予单位】：大连理工大学
【学位级别】：博士
【学位授予年份】：2012
【分类号】：TP333.35;TP301.6

【引证文献】