超图划分与SFC的比较研究和数值软件可视化界面

本文重点对超图划分和空间填充曲线两类算法进行比较研究。在大规模科学计算的中，并行计算效率提升的一个关键在于将数据进行剖分，分配到相应处理器中，以及对处理器中的数据进行动态调整，数据剖分和数据调整是实现处理器节点之间负载均衡的关键。针对数据剖分和数据调整问题，目前主要通过两类手段解决，分别称为拓扑手段和几何手段。而超图划分和空间填充曲线作为这两类手段的代表，在数据剖分和数据调整过程中得到了广泛的应用。 解决超图划分问题的经典算法中，应用最为广泛是启发式算法，如FM算法等。本文以FM算法为例，给出了较为详细的分析。随着问题规模的不断扩大，这些传统的算法消耗的时间急剧增加，研究者们因此又提出了对超图进行多级划分的算法框架。本文将对这一算法框架的各阶段细节进行分析。 空间填充曲线可以对离散的多维空间进行线性遍历，将多维的问题转化为一维的问题。利用这种特性，在数据剖分过程中可以将数据进行排序，根据这一顺序对数据进行剖分。本文对空间填充曲线的生成和应用，以及几类常用的空间填充曲线的顺序编码生成算法进行分析。 超图划分和空间填充曲线在数据剖分应用中各有优缺点。超图划分对节点间通信量等优化目标可以进行更为准确的计算，可以得到对更为有效的减少节点间通信量的数据剖分，但是超图划分这一过程本身所需要的时间较多；而空间填充曲线可以在很短的时间内对数据进行剖分，但是无法对优化目标进行准确计算。我们对两者在数据剖分中的应用，以及应用不同的划分模型对整体计算的影响进行了分析比较，并进行了实验对观点进行了验证。 在文章的最后，结合实际项目对数值软件可视化界面的设计进行了阐述。