超图划分与SFC的比较研究和数值软件可视化界面
文献类型：学位论文
| 作者 | 卢玥 |
| 学位类别 | 博士 |
| 答辩日期 | 2008-06-06 |
| 授予单位 | 中国科学院软件研究所 |
| 授予地点 | 软件研究所 |
| 关键词 | 超图 多级划分 空间填充曲线 数据剖分 可视化界面 |
| 其他题名 | Comparision of hypergraph partitionging and SFC and Visual interface for numerical computing software package |
| 中文摘要 | 本文重点对超图划分和空间填充曲线两类算法进行比较研究。在大规模科学计算的中，并行计算效率提升的一个关键在于将数据进行剖分，分配到相应处理器中，以及对处理器中的数据进行动态调整，数据剖分和数据调整是实现处理器节点之间负载均衡的关键。针对数据剖分和数据调整问题，目前主要通过两类手段解决，分别称为拓扑手段和几何手段。而超图划分和空间填充曲线作为这两类手段的代表，在数据剖分和数据调整过程中得到了广泛的应用。 解决超图划分问题的经典算法中，应用最为广泛是启发式算法，如FM算法等。本文以FM算法为例，给出了较为详细的分析。随着问题规模的不断扩大，这些传统的算法消耗的时间急剧增加，研究者们因此又提出了对超图进行多级划分的算法框架。本文将对这一算法框架的各阶段细节进行分析。 空间填充曲线可以对离散的多维空间进行线性遍历，将多维的问题转化为一维的问题。利用这种特性，在数据剖分过程中可以将数据进行排序，根据这一顺序对数据进行剖分。本文对空间填充曲线的生成和应用，以及几类常用的空间填充曲线的顺序编码生成算法进行分析。 超图划分和空间填充曲线在数据剖分应用中各有优缺点。超图划分对节点间通信量等优化目标可以进行更为准确的计算，可以得到对更为有效的减少节点间通信量的数据剖分，但是超图划分这一过程本身所需要的时间较多；而空间填充曲线可以在很短的时间内对数据进行剖分，但是无法对优化目标进行准确计算。我们对两者在数据剖分中的应用，以及应用不同的划分模型对整体计算的影响进行了分析比较，并进行了实验对观点进行了验证。 在文章的最后，结合实际项目对数值软件可视化界面的设计进行了阐述。 |
| 英文摘要 | In this paper, we compare hypergraph partitioning with space-filling curve algorithm. In scientific computations, it is an important step to partition data to processors or repartition data dynamically to maintain load balance. There are two categories of method to solve data partitioning/repartitioning problem, which called topologic methods and geomtric methods. Hypergraph partitioning and space-filling curve are both successful model for partition data, which are the representive of the two categories. Both model are used widely. There are a lot of heuristic algorithm to solve hypergraph partitioning, we introduce FM algorithm in this paper. But these algorithm that partition the hypergaph directly can’t meet the actual need while the scale of problem growing. Therefore, multilevel paradigm is proposed. We will discuss some detail of the paradigm in this paper, and propose an effctive way to refine the partition. Discrete space-filling curves are commonly used to reduce a multi-dimensional problem to a one-dimensional problem. The space-filling curve is essentially a linear traversal of the discrete multi-dimensional space. With the traversal of space-filling curve, data in multi-dimension is sorted and can be partitioned by perform one-dimension partitioning of the curve. In this paper, we discuss the generation and application of space-filling curve. Hypergraph partitioing and space-filling curve have their advantages and disadvantages. We compare effect of hypergraph partitioning with space-filling curve, and discuss the influence of different partition model to the computing, then make some experiment to prove our point. At the last of this paper, we discuss the design of visual interface of numerical computing software package. |
| 语种 | 中文 |
| 公开日期 | 2011-03-17 |
| 页码 | 68 |
| 源URL | [http://124.16.136.157/handle/311060/5894]  |
| 专题 | 软件研究所_并行计算实验室 _学位论文 |
| 推荐引用方式 GB/T 7714 | 卢玥. 超图划分与SFC的比较研究和数值软件可视化界面[D]. 软件研究所. 中国科学院软件研究所. 2008. |
入库方式： OAI收割
来源：软件研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。