ISCAS OpenIR  > 中科院软件所  > 中科院软件所
Author: 安伟亭
Issued Date: 2007-06-07
Degree Grantor: 中国科学院软件研究所
Place of Degree Grantor: 软件研究所
Degree Level: 博士
Keyword: 数值软件 ; 并行计算 ; Trilinos项目 ; 数据划分 ; Metis软件
Alternative Title: Design of Object-Oriented Graph Partitioning software MetsiOO and its Integration Application with Trilinos
Abstract: 伴随着计算技术的发展,在实际应用需求的推动下,数值计算得到了长足进步。数值软件尤其是并行数值软件是当前数值计算的关键环节。日益增多的大规模、复杂实际应用问题,对数值软件的无缝协作不断提出更高要求。建立一套普适的数值软件互操作机制,以促进各类数值软件的集成,并便利其设计、开发和维护,具有重要意义。 Trilinos项目致力于简化数值软件的设计开发和集成应用,它在面向对象的框架内提供了优秀的并行解法器求解大规模科学计算和工程应用问题。本文分析了Trilinos的主要功能,设计特色和组织结构,重点剖析其基本的线性代数包Epetra和线性解法器包AztecOO。 利用迭代法在分布式内存并行机平台上求解一个大规模稀疏线性方程Ax = b会产生一个图划分的问题, 每次迭代的关键步骤是稀疏矩阵和向量的乘积操作,通过合理划分和矩阵A相对应的图,能够明显的减少这一步的通信量。但是Trilinos本身并没有直接提供矩阵划分的工具,本文详细介绍了稀疏矩阵的两种图划分模型,并给出它们的实现。 Metis系列软件是一个高效的数据划分工具,联合使用Metis和Trilions在并行机上求解线性问题是一种非常有效的手段,它能有效的做到负载平衡,最小化进程间的通讯。但是针对稀疏矩阵建模,调用Metis系列软件划分,然后根据划分结果把稀疏矩阵映射到不同的处理器上是一件繁琐复杂而套路化的过程。本文针对联合使用Metis和Trilinos在并行机平台上求解MatrixMarket数据库中的稀疏矩阵设计了面向对象的图划分软件包MetisOO,MetisOO对稀疏矩阵建模划分,能十分方便的和Trilinos集成使用,提供简洁的用户界面。 测试主要在实验室自行搭建的4节点Linux机群上进行。测试的项目包括不同划分方法的图划分性能:对稀疏矩阵用Trilinos的简单线性分布划分并求解;用图模型或超图模型划分矩阵,然后根据划分结果把矩阵映射到不同的进程上调用Trilinos求解。通过采用不同的矩阵划分方法启动不同数目的进程,从横向和纵向两个角度比较程序的加速比、迭代次数、和敛散性。
English Abstract: Along with the advances of computation technologies, numerical computing has made great progress and driven by the demands from practical applications. It is extremely obvious that numerical software currently is among the key points of engaging numerical computing, and this especially holds for parallel numerical software. The increasing, complex problems from real-world have the urge of making the collaboration between various numerical software systems as simple and seamless as possible. Therefore, it is helpful and impelling to establish a series of general-purpose mechanisms for the interoperability among them, thus facilitating the design, development, integration and ongoing support of mathematical software. The Trilinos Project is an effort to facilitate the design, development, and integration of mathematical software libraries. It provides parallel solver algorithms within an object-oriented software framework for the solution of large-scale engineering and scientific applications. This paper has investigated and done some research on Trilinos about its main function, design characteristic and organizational structure, with special emphasis on its basic linear algebra package: Epetra and linear solution package: AztecOO. When solving a sparse system of linear equations Ax=b via iterative methods on a parallel computer, here comes a graph partitioning problem. A key step in each iteration of these methods is the multiplication of a sparse matrix and a dense vector. Partitioning the graph corresponding to the matrix A properly, significantly reduces the amount of communication required by this step. Since Trilinos doesn’t provide any tools for data partitioning and load balance, in this paper we present two partitioning models for sparse matrix, and then give their implementation. Metis is a family of programs for partitioning unstructured graphs and hypergraphs. It is efficient to combine Metis and Trilinos to solve a sparse system of linear equations on a parallel computer, for computational load can be balanced and interprocessor communication can be minimized among processors. However, it is a complex and tedious routine to build partitioning mold for sparse matrix, call Metis to partition graph, then distribute the sparse matrix according to the partitioning result. This paper devises an object-oriented graph partitioning software MetisOO in order to facilitate combining Metis and Trilinos to solve linear system from Matrix Market database. MetisOO can be integrated with Trilinos conveniently, provide simple user interface. It is a serial graph partitioning tool and also a parallel pypergraph partitioning tool. Experiments are mainly carried out on a four-node Linux cluster put up by our laboratory. Testing items include that firstly, partition the matrix using different methods, such as simple linear distribution from Trilinos, graph model partitioning and pypergraph partitioning; then call Trilinos to solve the linear system. By making use of different partitioning methods and starting different number of process, speed-up ratio, the number of iterations, convergence of program can be compared.
Language: 中文
Content Type: 学位论文
Appears in Collections:中科院软件所

Files in This Item:
File Name/ File Size Content Type Version Access License
10001_200428015029061安伟亭_paper.doc(3653KB)----限制开放-- 联系获取全文

Recommended Citation:
安伟亭. 面向对象图划分软件MetisOO的设计及其与Trilinos的集成应用[D]. 软件研究所. 中国科学院软件研究所. 2007-06-07.
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
Social Bookmarking
Add to CiteULike Add to Connotea Add to Add to Digg Add to Reddit
所有评论 (0)
内 容:
Email:  *
验证码:   刷新
标 题:
内 容:
Email:  *
验证码:   刷新

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



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