检索结果-内蒙古大学图书馆

The Zoltan and Isorropia parallel toolkits for combinatorial scientific computing: Partitioning, ordering and coloring

引用

scientific PROGRAMMING 2012年第2期20卷 129-150页

作者： Boman, Erik G. Catalyuerek, Uemit V. Chevalier, Cedric Devine, Karen D. Sandia Natl Labs Dept Scalable Algorithms Albuquerque NM 87185 USA Ohio State Univ Dept Biomed Informat Columbus OH 43210 USA Ohio State Univ Dept Elect & Comp Engn Columbus OH 43210 USA CEA Direct Applicat Mil Commissariat Energie Atom & Energies Alternat DAMDIF Arpajon France

Partitioning and load balancing are important problems in scientific computing that can be modeled as combinatorial problems using graphs or hypergraphs. The Zoltan toolkit was developed primarily for partitioning and load balancing to support dynamic parallel applications, but has expanded to support other problems in combinatorial scientific computing, including matrix ordering and graph coloring. Zoltan is based on abstract user interfaces and uses callback functions. To simplify the use and integration of Zoltan with other matrix-based frameworks, such as the ones in Trilinos, we developed Isorropia as a Trilinos package, which supports most of Zoltan's features via a matrix-based interface. In addition to providing an easy-to-use matrix-based interface to Zoltan, Isorropia also serves as a platform for additional matrix algorithms. In this paper, we give an overview of the Zoltan and Isorropia toolkits, their design, capabilities and use. We also show how Zoltan and Isorropia enable large-scale, parallel scientific simulations, and describe current and future development in the next-generation package Zoltan2.

关键词： Partitioning load balancing matrix ordering fill-reducing ordering graph coloring parallel computing combinatorial scientific computing

来源：评论

学校读者我要写书评

暂无评论

Redesigning Interactive Educational Modules for combinatorial scientific computing 19th

Redesigning Interactive Educational Modules for Combinatoria...

引用

19th Annual International Conference on Computational Science (ICCS)

作者： Rostami, M. Ali Bucker, H. Martin Friedrich Schiller Univ Jena Inst Comp Sci D-07737 Jena Germany Michael Stifel Ctr Jena Data Driven & Simulat Sci D-07737 Jena Germany

ISBN: (纸本)9783030227500;9783030227494

combinatorial scientific computing refers to the field of using combinatorial algorithms to solve problems in computational science and data science. Teaching even elementary topics from this area is difficult because it involves bridging the gap between scientific computing and graph theory. Furthermore, it is often necessary to understand not only the methodologies from mathematics and computer science, but also from different scientific domains from which the underlying problems arise. To enrich the learning process in combinatorial scientific computing, we designed and implemented a set of interactive educational modules called EXPLAIN. The central idea behind EXPLAIN is its focus on describing the equivalence of a problem in terms of scientific computing and graph theory. That is, in EXPLAIN, the scientific computing problem and its graph theoretical representation are treated as two sides of the same coin. The process of solving a problem is interactively explored by visualizing transformations on an object from scientific computing, simultaneously, with the corresponding transformations on a suitably defined graph. We describe the redesign of the EXPLAIN software with an emphasis on integrating a domain-specific scripting language and a hierarchical visualization for recursively defined problems.

关键词： combinatorial scientific computing Sparse matrices Graph models EXPLAIN Recursive nested dissection

来源：评论

学校读者我要写书评

暂无评论

A new metric enabling an exact hypergraph model for the communication volume in distributed-memory parallel applications

引用

PARALLEL computing 2013年第8期39卷 319-335页

作者： Fortmeier, O. Buecker, H. M. Auer, B. O. Fagginger Bisseling, R. H. Rhein Westfal TH Aachen Inst Comp Sci D-52056 Aachen Germany Univ Utrecht Math Inst NL-3508 TA Utrecht Netherlands

A hypergraph model for mapping applications with an all-neighbor communication pattern to distributed-memory computers is proposed, which originated in finite element triangulations. Rather than approximating the communication volume for linear algebra operations, this new model represents the communication volume exactly. To this end, a hypergraph partitioning problem is formulated where the objective function involves a new metric. This metric, the lambda(lambda - 1)-metric, accurately models the communication volume for an all-neighbor communication pattern occurring in a concrete finite element application. It is a member of a more general class of metrics, which also contains more widely used metrics, such as the cut-net and the (lambda - 1)-metric. In addition, we develop a heuristic to minimize the communication volume in the new lambda(lambda - 1)-metric. For the solution of several real-world finite element problems, experimental results based on this new heuristic demonstrate a small reduction in communication volume compared to a standard graph partitioner and do not show significant reductions in communication volume compared to a hypergraph partitioner using the common (lambda - 1)-metric. However, for this set of problems, the new approach does reduce actual communication times. As a by-product, we observe that it also tends to reduce the number of messages. Furthermore, the new approach dramatically reduces the communication volume for a set of sparse matrix problems that are more irregularly-structured than finite element problems. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Hypergraph Unstructured triangulation Communication volume metric Finite elements combinatorial scientific computing

来源：评论

学校读者我要写书评

暂无评论

ON TWO-DIMENSIONAL SPARSE MATRIX PARTITIONING: MODELS, METHODS, AND A RECIPE

引用

SIAM JOURNAL ON scientific computing 2010年第2期32卷 656-683页

作者： Catalyurek, Umit V. Aykanat, Cevdet Ucar, Bora Ohio State Univ Dept Biomed Informat Columbus OH 43210 USA Ohio State Univ Dept Elect & Comp Engn Columbus OH 43210 USA Bilkent Univ Dept Comp Engn Ankara Turkey Univ Lyon ENS Lyon CNRS Lab Informat ParallelismeUMRINRIAUCBL F-69364 Lyon 7 France

We consider two-dimensional partitioning of general sparse matrices for parallel sparse matrix-vector multiply operation. We present three hypergraph-partitioning-based methods, each having unique advantages. The first one treats the nonzeros of the matrix individually and hence produces fine-grain partitions. The other two produce coarser partitions, where one of them imposes a limit on the number of messages sent and received by a single processor, and the other trades that limit for a lower communication volume. We also present a thorough experimental evaluation of the proposed two-dimensional partitioning methods together with the hypergraph-based one-dimensional partitioning methods, using an extensive set of public domain matrices. Furthermore, for the users of these partitioning methods, we present a partitioning recipe that chooses one of the partitioning methods according to some matrix characteristics.

关键词： sparse matrix partitioning parallel matrix-vector multiplication hypergraph partitioning two-dimensional partitioning combinatorial scientific computing

来源：评论

学校读者我要写书评

暂无评论

Improving performance of sparse matrix dense matrix multiplication on large-scale parallel systems

引用

PARALLEL computing 2016年 59卷 71-96页

作者： Acer, Seher Selvitopi, Oguz Aykanat, Cevdet Bilkent Univ Dept Comp Engn TR-06800 Ankara Turkey

We propose a comprehensive and generic framework to minimize multiple and different volume-based communication cost metrics for sparse matrix dense matrix multiplication (SpMM). SpMM is an important kernel that finds application in computational linear algebra and big data analytics. On distributed memory systems, this kernel is usually characterized with its high communication volume requirements. Our approach targets irregularly sparse matrices and is based on both graph and hypergraph partitioning models that rely on the widely adopted recursive bipartitioning paradigm. The proposed models are lightweight, portable (can be realized using any graph and hypergraph partitioning tool) and can simultaneously optimize different cost metrics besides total volume, such as maximum send receive volume, maximum sum of send and receive volumes, etc., in a single partitioning phase. They allow one to define and optimize as many custom volume-based metrics as desired through a flexible formulation. The experiments on a wide range of about thousand matrices show that the proposed models drastically reduce the maximum communication volume compared to the standard partitioning models that only address the minimization of total volume. The improvements obtained on volume-based partition quality metrics using our models are validated with parallel SpMM as well as parallel multi-source BFS experiments on two large-scale systems. For parallel SpMM, compared to the standard partitioning models, our graph and hypergraph partitioning models respectively achieve reductions of 14% and 22% in runtime, on average. Compared to the state-of-the-art partitioner UMPa, our graph model is overall 14.5x faster and achieves an average improvement of 19% in the partition quality on instances that are bounded by maximum volume. For parallel BFS, we show on graphs with more than a billion edges that the scalability can significantly be improved with our models compared to a recently proposed two-dimen

关键词： Irregular applications Sparse matrices Sparse matrix dense matrix multiplication Load balancing Communication volume balancing Matrix partitioning Graph partitioning Hypergraph partitioning Recursive bipartitioning combinatorial scientific computing

来源：评论

学校读者我要写书评

暂无评论

A RECURSIVE BIPARTITIONING ALGORITHM FOR PERMUTING SPARSE SQUARE MATRICES INTO BLOCK DIAGONAL FORM WITH OVERLAP

引用

SIAM JOURNAL ON scientific computing 2013年第1期35卷 C99-C121页

作者： Acer, Seher Kayaaslan, Enver Aykanat, Cevdet Bilkent Univ Dept Comp Engn Ankara Turkey

We investigate the problem of symmetrically permuting a square sparse matrix into a block diagonal form with overlap. This permutation problem arises in the parallelization of an explicit formulation of the multiplicative Schwarz preconditioner and a more recent block overlapping banded linear solver as well as its application to general sparse linear systems. In order to formulate this permutation problem as a graph theoretical problem, we define a constrained version of the multiway graph partitioning by vertex separator (GPVS) problem, which is referred to as the ordered GPVS (oGPVS) problem. However, existing graph partitioning tools are unable to solve the oGPVS problem. So, we also show how the recursive bipartitioning framework can be utilized for solving the oGPVS problem. For this purpose, we propose a left-to-right bipartitioning approach together with a novel vertex fixation scheme so that existing 2-way GPVS tools that support fixed vertices can be effectively and efficiently utilized in the recursive bipartitioning framework. Experimental results on a wide range of matrices confirm the validity of the proposed approach.

关键词： sparse square matrices block diagonal form with overlap graph partitioning by vertex separator recursive bipartitioning partitioning with fixed vertices combinatorial scientific computing

来源：评论

学校读者我要写书评

暂无评论

ALGEBRAIC DISTANCE ON GRAPHS

引用

SIAM JOURNAL ON scientific computing 2011年第6期33卷 3468-3490页

作者： Chen, Jie Safro, Ilya Argonne Natl Lab Div Math & Comp Sci Argonne IL 60439 USA Univ Minnesota Twin Cities Dept Comp Sci & Engn Minneapolis MN 55455 USA

Measuring the connection strength between a pair of vertices in a graph is one of the most important concerns in many graph applications. Simple measures such as edge weights may not be sufficient for capturing the effects associated with short paths of lengths greater than one. In this paper, we consider an iterative process that smooths an associated value for nearby vertices, and we present a measure of the local connection strength (called the algebraic distance;see [D. Ron, I. Safro, and A. Brandt, Multiscale Model. Simul., 9 (2011), pp. 407-423]) based on this process. The proposed measure is attractive in that the process is simple, linear, and easily parallelized. An analysis of the convergence property of the process reveals that the local neighborhoods play an important role in determining the connectivity between vertices. We demonstrate the practical effectiveness of the proposed measure through several combinatorial optimization problems on graphs and hypergraphs.

关键词： graph connectivity measure combinatorial scientific computing stationary iterative process

来源：评论

学校读者我要写书评

暂无评论

DISTRIBUTED-MEMORY PARALLEL ALGORITHMS FOR DISTANCE-2 COLORING AND RELATED PROBLEMS IN DERIVATIVE COMPUTATION

引用

SIAM JOURNAL ON scientific computing 2010年第4期32卷 2418-2446页

作者： Bozdag, Doruk Catalyurek, Uemit V. Gebremedhin, Assefaw H. Manne, Fredrik Boman, Erik G. Ozguner, Fuesun Ohio State Univ Dept Biomed Informat Columbus OH 43210 USA Ohio State Univ Dept Elect & Comp Engn Columbus OH 43210 USA Purdue Univ Dept Comp Sci W Lafayette IN 47907 USA Univ Bergen Dept Informat N-5008 Bergen Norway Sandia Natl Labs Scalable Algorithms Dept Albuquerque NM 87185 USA

The distance-2 graph coloring problem aims at partitioning the vertex set of a graph into the fewest sets consisting of vertices pairwise at distance greater than 2 from each other. Its applications include derivative computation in numerical optimization and channel assignment in radio networks. We present efficient, distributed-memory, parallel heuristic algorithms for this NP-hard problem as well as for two related problems used in the computation of Jacobians and Hessians. Parallel speedup is achieved through graph partitioning, speculative (iterative) coloring, and a bulk synchronous parallel-like organization of parallel computation. Results from experiments conducted on a PC cluster employing up to 96 processors and using large-size real-world as well as synthetically generated test graphs show that the algorithms are scalable. In terms of quality of solution, the algorithms perform remarkably well-the numbers of colors used by the parallel algorithms are observed to be very close to the numbers used by their sequential counterparts, which in turn are quite often near optimal. Moreover, the experimental results show that the parallel distance-2 coloring algorithm compares favorably with the alternative approach of solving the distance-2 coloring problem on a graph G by first constructing the square graph G(2) and then applying a parallel distance-1 coloring algorithm on G(2). Implementations of the algorithms are made available via the Zoltan toolkit.

关键词： distance-2 graph coloring distributed-memory parallel algorithms Jacobian computation Hessian computation sparsity exploitation automatic differentiation combinatorial scientific computing

来源：评论

学校读者我要写书评

暂无评论

1.5D PARALLEL SPARSE MATRIX-VECTOR MULTIPLY

引用

SIAM JOURNAL ON scientific computing 2018年第1期40卷 C25-C46页

作者： Kayaaslan, Enver Aykanat, Cevdet Ucar, Bora NTENT Inc 1808 Aston Ave Carlsbad CA 92008 USA Bilkent Univ Dept Comp Engn TR-06800 Ankara Turkey ENS Lyon CNRS 46 Allee Italie F-69364 Lyon France ENS Lyon CNRS LIP UMR5668INRIAUCBL 46 Allee Italie F-69364 Lyon France

There are three common parallel sparse matrix-vector multiply algorithms: 1D row-parallel, 1D column-parallel, and 2D row-column-parallel. The 1D parallel algorithms offer the advantage of having only one communication phase. On the other hand, the 2D parallel algorithm is more scalable, but it suffers from two communication phases. Here, we introduce a novel concept of heterogeneous messages where a heterogeneous message may contain both input-vector entries and partially computed output-vector entries. This concept not only leads to a decreased number of messages but also enables fusing the input- and output-communication phases into a single phase. These findings are exploited to propose a 1.5D parallel sparse matrix-vector multiply algorithm which is called local row-column-parallel. This proposed algorithm requires a constrained fine-grain partitioning in which each fine-grain task is assigned to the processor that contains either its input vector entry, its output-vector entry, or both. We propose two methods to carry out the constrained fine-grain partitioning. We conduct our experiments on a large set of test matrices to evaluate the partitioning qualities and partitioning times of these proposed 1.5D methods.

关键词： sparse matrix partitioning parallel sparse matrix-vector multiplication directed hypergraph model bipartite vertex cover combinatorial scientific computing

来源：评论

学校读者我要写书评

暂无评论

RELAXATION-BASED COARSENING FOR MULTILEVEL HYPERGRAPH PARTITIONING

引用

MULTISCALE MODELING & SIMULATION 2019年第1期17卷 482-506页

作者： Shaydulin, Ruslan Chen, Jie Safro, Ilya Clemson Univ Sch Comp Clemson SC 29631 USA Thomas J Watson Res Ctr IBM Yorktown Hts NY 10598 USA

Multilevel partitioning methods that are inspired by principles of multiscaling are the most powerful practical hypergraph partitioning solvers. Hypergraph partitioning has many applications in disciplines ranging from scientific computing to data science. In this paper we introduce the concept of algebraic distance on hypergraphs and demonstrate its use as an algorithmic component in the coarsening stage of multilevel hypergraph partitioning solvers. The algebraic distance is a vertex distance measure that extends hyperedge weights for capturing the local connectivity of vertices which is critical for hypergraph coarsening schemes. The practical effectiveness of the proposed measure and corresponding coarsening scheme is demonstrated through extensive computational experiments on a diverse set of problems. Finally, we propose a benchmark of hypergraph partitioning problems to compare the quality of other solvers.

关键词： hypergraph partitioning multilevel algorithms coarsening matching vertex similarity measure combinatorial scientific computing

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：