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

block recursive algorithm TO GENERATE JACOBI-SETS

PARALLEL COMPUTING 1993年第5期19卷 481-496页

作者： MANTHARAM, M EBERLEIN, PJ Department of Computer Science University at Buffalo State University of New York Buffalo NY 14260 USA

The pairs in the set {(i, j)\1 less-than-or-equal-to i < j less-than-or-equal-to n} can be distributed into (n-1) sets, such that each set contains exactly n/2 disjoint pairs. We refer to these (n-1) sets as complete Jacobi-sets. Gao and Thomas have [4] developed a recursive algorithm for exchanges of elements on a hypercube configuration to generate complete Jacobi sets. Inspired by the algorithm we present a block recursive algorithm to generate these sets continuously and return to its initial state after the last Jacobi set has been generated. In the process of the derivation of the BR algorithm, we developed some interesting combinatorial properties on the hypercube topology related to the Jacobi-sets. We include those results in this paper. An important application of the Jacobi-sets lies in the parallel implementation for Jacobi-type methods. The order in which the pairs (i, j) are chosen is important in defining these algorithms. We present in this paper a study on the effect of different orderings on the convergence of Jacobi-type methods. Our tests indicate that the ordering defined by our block recursive algorithm is as good as the odd-even ordering.

关键词： JACOBI-SETS JACOBI-TYPE METHODS HYPERCUBE TOPOLOGY block recursive algorithm ORDERINGS

来源：评论

学校读者我要写书评

暂无评论

Synthesizing efficient out-of-core programs for block recursive algorithms using block-cyclic data distributions

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 1999年第3期10卷 297-315页

作者： Li, ZY Reif, JH Gupta, SKS IBM Corp Network Comp Softare Div Res Triangle Pk NC 27709 USA Duke Univ Dept Comp Sci Durham NC 27708 USA Colorado State Univ Dept Comp Sci Ft Collins CO 80523 USA

In this paper, we present a framework for synthesizing I/O efficient out-of-core programs for block recursive algorithms, such as the fast Fourier transform (FFT) and block matrix transposition algorithms. Our framework uses an algebraic representation which is based on tensor products and other matrix operations. The programs are optimized for the striped Vitter and Shriver's two-level memory model in which data can be distributed using various cyclic(B) distributions in contrast to the normally used physical track distribution cyclic(B-d), where B-d is the physical disk block size. We first introduce tensor bases to capture the semantics of block-cyclic data distributions of out-of-core data and also data access patterns to out-of-core data. We then present program generation techniques for tensor products and matrix transposition. We accurately represent the number of parallel I/O operations required for the synthesized programs for tensor products and matrix transposition as a function of tensor bases and data distributions. We introduce an algorithm to determine the data distribution which optimizes the performance of the synthesized programs. Further, we formalize the procedure of synthesizing efficient out-of-core programs for tensor product formulas with various block-cyclic distributions as a dynamic programming problem. We demonstrate the effectiveness of our approach through several examples. We show that the choice of an appropriate data distribution can reduce the number of passes to access out-of-core data by as large as eight times for a tensor product and the dynamic programming approach can largely reduce the number of passes to access out-of-core data for the overall tensor product formulas.

关键词： parallel I/O program synthesis data distribution tensor product block recursive algorithm fast Fourier transform

来源：评论

学校读者我要写书评

暂无评论

A programming methodology for designing block recursive algorithms

引用

JOURNAL OF INFORMATION SCIENCE AND ENGINEERING 2006年第1期22卷 95-121页

作者： Fan, MH Huang, CH Chung, YC Liu, JS Lee, JZ Feng Chia Univ Dept Informat Engn & Comp Sci Taichung 407 Taiwan Natl Tsing Hua Univ Dept Comp Sci Hsinchu 300 Taiwan Natl Dong Hwa Univ Dept Comp Sci & Informat Engn Hualien 974 Taiwan

In this paper, we use the tensor product notation as the framework of a programming methodology for designing block recursive algorithms. We first express a computational problem in its matrix form. Next, we formulate a matrix equation for the matrix of the computational problem. Then, we try to find a solution of the matrix equation such that the solution is composed of simple matrices. Finally, we recursively factorize the subproblem to obtain a tensor product formula representing an algorithm for the given problem. In this methodology, the operations of a tensor product formula can be mapped to language constructs of high-level programming languages. That is, we can generate computer programs, including programs for parallel computers and distributed-memory multiprocessors, from tensor product formulas. In this paper, we use the parallel prefix problem and the discrete Fourier transform problem as examples to illustrate the methodology and derive various parallel prefix and fast Fourier transform algorithms.

关键词： programming methodology tensor product block recursive algorithm parallel processing distributed processing parallel prefix fast Fourier transform

来源：评论

学校读者我要写书评

暂无评论

EXTENT - A PORTABLE PROGRAMMING ENVIRONMENT FOR DESIGNING AND IMPLEMENTING HIGH-PERFORMANCE block recursive algorithmS

EXTENT - A PORTABLE PROGRAMMING ENVIRONMENT FOR DESIGNING AN...

引用

Supercomputing 94

作者： DAI, DL GUPTA, SKS KAUSHIK, SD LU, JH SINGH, RV HUANG, CH SADAYAPPAN, P JOHNSON, RW OHIO STATE UNIV DEPT COMP & INFORMAT SCICOLUMBUSOH 43210

ISBN: (纸本)0818666056

EXTENT is an EXpert system for TENsor product formula Translation. In this paper we present a programming environment for automatic generation of parallel/vector programs from tensor product formulas. A tensor (Kronecker) product based programming methodology is used for designing high performance programs on various architectures. In this programming methodology, block recursive algorithms such as the fast Fourier transform and Strassen's matrix multiplication algorithm are expressed as tensor product formulas involving tensor product and other matrix operations. A tensor product formula can be systematically translated to parallel and/or vector code for various parallel architectures. A prototype system which generates programs for the Cray Y-MP, Cray T3D, and Intel Paragon has been developed. Performance results for some generated programs are presented.

关键词： PARALLEL PROGRAMMING ENVIRONMENT TENSOR (KRONECKER) PRODUCT block recursive algorithm PARALLEL PROGRAM SYNTHESIS

来源：评论

学校读者我要写书评

暂无评论

A programming methodology for designing block recursive algorithms on various computer networks

A programming methodology for designing block recursive algo...

引用

31st International Conference on Parallel Processing (ICPP 2002)

作者： Fan, MH Huang, CH Chung, YC Feng Chia Univ Dept Informat Engn Taichung 40724 Taiwan

ISBN: (纸本)0769516807

In this paper, we use the tensor product notation as the framework of a programming methodology for designing block recursive algorithms on various computer networks. In our previous works, we propose a programming methodology for designing block recursive algorithms on shared-memory and distributed-memory multiprocessors without considering the interconnection of processors. We extend the work to consider the block recursive algorithms on direct networks and multistage interconnection networks. We use parallel prefix computation as an example to illustrate the methodology. First, we represent the prefix computation problem as a computational matrix which may not be suitable for deriving algorithms on specific computer networks. In this methodology, we add two steps to derive tensor product formulas of parallel prefix algorithms on computer networks: (1)decompose the computational matrix into two submatrices, and (2) construct an augmented matrix. The augmented matrix can be factorized so that each term is a tensor product formula and can fit into a specified network topology. With the augmented matrix, the input data is also extended. It means, in addition to the input data, an auxiliary vector as temporary storage is used. The content of temporary storage is relevant to the decomposition of the original computational matrix. We present the methodology to derive various parallel prefix algorithms on hypercube, omega, and baseline networks and veri,, correctness of the resulting tensor product formulas using induction.

关键词： programming methodology tensor product block recursive algorithm parallel processing parallel prefix hypercube network omega network baseline network

来源：评论

学校读者我要写书评

暂无评论

AN ALGEBRAIC-THEORY FOR MODELING DIRECT INTERCONNECTION NETWORKS

AN ALGEBRAIC-THEORY FOR MODELING DIRECT INTERCONNECTION NETW...

引用

SUPERCOMPUTING 92 CONF

作者： KAUSHIK, SD SHARMA, S HUANG, CH JOHNSON, JR JOHNSON, RW SADAYAPPAN, P Department of Computer and Information Science Ohio State University Columbus 43210 OH United States Department of Mathematics and Computer Science Drexel University Philadelphia 19176 PA United States Department of Computer Science St. Cloud State University St. Cloud 56301 MN United States

ISBN: (纸本)0818626305

We present an algebraic theory based on tensor products for modeling direct interconnection networks. This algebraic theory has been used for designing and implementing block recursive numerical algorithms on shared-memory vector multiprocessors. This theory can be used for mapping algorithms expressed in tensor product form onto distributed-memory architectures. In this paper, we focus on the modeling of direct interconnection networks. Rings, n-dimensional meshes, and hypercubes are represented in tensor product form. algorithm mapping using tensor product formulation is demonstrated by mapping matrix transposition and matrix multiplication onto different networks. © 1992 IEEE.

关键词： TENSOR PRODUCT block recursive algorithm DIRECT INTERCONNECTION NETWORK algorithm MAPPING

来源：评论

学校读者我要写书评

暂无评论

Tensor product formulation for Hilbert space-filling curves

引用

JOURNAL OF INFORMATION SCIENCE AND ENGINEERING 2008年第1期24卷 261-275页

作者： Lin, Shen-Yi Chen, Chih-Shen Liu, Li Huang, Chua-Huang Feng Chia Univ Dept Comp Sci & Informat Engn Taichung 407 Taiwan Taipei Med Univ Grad Inst Med Informat Taipei 110 Taiwan

We present a tensor product formulation for Hilbert space-filling curves. Both recursive and iterative formulas are expressed in the paper. We view a Hilbert space-filling curve as a permutation which maps two-dimensional 2(n) x 2(n) data elements stored in the row major or column major order to the order of traversing a Hilbert curve. The tensor product formula of Hilbert space-filling curves uses several permutation operations: stride permutation, radix-2 Gray permutation, transposition, and anti-diagonal transposition. The iterative tensor product formula can be manipulated to obtain the inverse Hilbert permutation. Also, the formulas are directly translated into computer programs which can be used in various applications including image processing, VLSI component layout, and R-tree indexing, etc.

关键词： tensor product block recursive algorithm Hilbert space-filling curve stride permutation gray permutation transposition anti-diagonal transposition data allocation

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：