中国科学院软件研究所机构知识库
Advanced  
ISCAS OpenIR  > 并行计算实验室  > 学位论文
题名:
超图划分与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.
语种: 中文
内容类型: 学位论文
URI标识: http://ir.iscas.ac.cn/handle/311060/5894
Appears in Collections:并行计算实验室 _学位论文

Files in This Item:
File Name/ File Size Content Type Version Access License
10001_200528015029009卢玥_paper.pdf(604KB)----限制开放-- 联系获取全文

Recommended Citation:
卢玥. 超图划分与SFC的比较研究和数值软件可视化界面[D]. 软件研究所. 中国科学院软件研究所. 2008-06-06.
Service
Recommend this item
Sava as my favorate item
Show this item's statistics
Export Endnote File
Google Scholar
Similar articles in Google Scholar
[卢玥]'s Articles
CSDL cross search
Similar articles in CSDL Cross Search
[卢玥]‘s Articles
Related Copyright Policies
Null
Social Bookmarking
Add to CiteULike Add to Connotea Add to Del.icio.us Add to Digg Add to Reddit
所有评论 (0)
暂无评论
 
评注功能仅针对注册用户开放,请您登录
您对该条目有什么异议,请填写以下表单,管理员会尽快联系您。
内 容:
Email:  *
单位:
验证码:   刷新
您在IR的使用过程中有什么好的想法或者建议可以反馈给我们。
标 题:
 *
内 容:
Email:  *
验证码:   刷新

Items in IR are protected by copyright, with all rights reserved, unless otherwise indicated.

 

 

Valid XHTML 1.0!
Copyright © 2007-2017  中国科学院软件研究所 - Feedback
Powered by CSpace