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

Scalable parallel matrix multiplication on distributed memory parallel computers

JOURNAL OF parallel AND distributed COMPUTING 2001年第12期61卷 1709-1731页

作者： Li, KQ SUNY Albany Dept Comp Sci New Paltz NY 12561 USA

Consider any known sequential algorithm for matrix multiplication over an arbitrary ring with time complexity O(N(alpha)), where 2 < alpha less than or equal to 3. We show that such an algorithm can be parallelized on a distributed memory parallel computer (DMPC) in O(log N) time by using N(alpha)/log N processors. Such a parallel computation is cost optimal and matches the performance of PRAM. Furthermore, our parallelization on a DMPC can be made fully scalable, that is, for all 1 less than or equal to p less than or equal to N(alpha)/log N, multiplying two N x N matrices can be performed by a DMPC with p processors in O(N(alpha)/p) time, i.e., linear speedup and cost optimality can be achieved in the range [ 1..N(alpha)/log N]. This unifies all known algorithms for matrix multiplication on DMPC, standard or nonstandard, sequential or parallel. Extensions of our methods and results to other parallel systems are also presented. For instance, for all 1 less than or equal to p less than or equal to N(alpha)/log N, multiplying two N x N matrices can be performed by p processors connected by a hypercubic network in O(N(alpha)/p + (N(2)/p(2/alpha)) (log p)(2(alpha-1)/alpha)) time, which implies that if p = O(N(alpha)/(log N)(2(alpha-1)/(alpha-2))), linear speedup can be achieved. Such a parallelization is highly scalable. The above claims result in significant progress in scalable parallel matrix multiplication (as well as solving many other important problems) on distributed memory systems, both theoretically and practically. (C) 2001 Academic Press.

关键词： cost optimality distributed memory parallel computer linear array with reconfigurable pipelined bus system matrix multiplication module parallel computer optical model of computation scalability speedup

来源：评论

学校读者我要写书评

暂无评论

Fast and highly scalable parallel computations for fundamental matrix problems on distributed memory systems

引用

JOURNAL OF SUPERCOMPUTING 2010年第3期54卷 271-297页

作者： Li, Keqin SUNY Albany Dept Comp Sci New Paltz NY 12561 USA

We present fast and highly scalable parallel computations for a number of important and fundamental matrix problems on distributed memory systems (DMS). These problems include matrix multiplication, matrix chain product, and computing the powers, the inverse, the characteristic polynomial, the determinant, the rank, the Krylov matrix, and an LU- and a QR-factorization of a matrix, and solving linear systems of equations. Our highly scalable parallel computations for these problems are based on a highly scalable implementation of the fastest sequential matrix multiplication algorithm on DMS. We show that compared with the best known parallel time complexities on parallel random access machines (PRAM), the most powerful but unrealistic shared memory model of parallel computing, our parallel matrix computations achieve the same speeds on distributed memory parallel computers (DMPC), and have an extra polylog factor in the time complexities on DMS with hypercubic networks. Furthermore, our parallel matrix computations are fully scalable on DMPC and highly scalable over a wide range of system size on DMS with hypercubic networks. Such fast (in terms of parallel time complexity) and highly scalable (in terms of our definition of scalability) parallel matrix computations were rarely seen before on any distributed memory systems.

关键词： Cost optimality distributed memory parallel computer distributed memory system Hypercubic network Matrix computation Scalability Speedup

来源：评论

学校读者我要写书评

暂无评论

Analysis of parallel algorithms for matrix chain product and matrix powers on distributed memory systems

引用

IEEE TRANSACTIONS ON parallel AND distributed SYSTEMS 2007年第7期18卷 865-878页

作者： Li, Keqin SUNY Albany Dept Comp Sci New Paltz NY 12561 USA

Given N matrices A(1,) A(2,...,) A(N) of size N x N, the matrix chain product problem is to compute A(1) x A(2) x... x A(N). Given an N x N matrix A, the matrix powers problem is to calculate the first N powers of A, that is, A, A(2), A(3),... A(N). We solve the two problems on distributed memory systems (DMSs) with p processors that can support one-to-one communications in T(p) time. Assume that the fastest sequential matrix multiplication algorithm has time complexity O(N-alpha), where the currently best value of alpha is less than 2.3755. Let p be arbitrarily chosen in the range 1 <= p <= N alpha+1/(log N)(2). We show that the two problems can be solved by a DMS with p processors in T-chain (N, p) = [GRAPHICS] and [GRAPHICS] times, respectively, where the function log(+) is defined as follows: log(+) x = log x if x >= 1 and log(+) x = 1 if 0 < x < 1. We also give instantiations of,the above results on several typical DMSs and show that computing matrix chain product and matrix powers are fully scalable on distributed memory parallel computers (DMPCs), highly scalable on DMSs with hypercubic networks, and not highly scalable on DMSs with mesh and torus networks.

关键词： cost optimality distributed memory parallel computer distributed memory system dynamic processor allocation hypercubic network matrix chain product matrix multiplication matrix power mesh scalability speedup torus

来源：评论

学校读者我要写书评

暂无评论

A large-scale nonlinear eigensolver for the analysis of dispersive nanostructures

引用

computer PHYSICS COMMUNICATIONS 2013年第8期184卷 1898-1906页

作者： Guo, Hua Arbenz, Peter Oswald, Benedikt ETH Dept Comp Sci CH-8092 Zurich Switzerland Paul Scherrer Inst CH-5234 Villigen Switzerland

We introduce the electromagnetic eigenmodal solver code FemaxxNano for the numerical analysis of nanometer structured optical systems, a scientific field generally know as nanooptics. FemaxxNano solves the electric field vector wave equation and calculates the electromagnetic eigenmodes of nearly arbitrary 3-dimensional resonators, embedded either in free-space, vacuum or a background medium. Here, the study of the interaction between nanometer sized metallic structures and light is at the heart of the physical problem. Since metals in the optical region of the electromagnetic spectrum are highly dispersive and, thus, dissipative, dielectric media, we eventually obtain a nonlinear eigenvalue problem. We discretize the electromagnetic eigenvalue problem with the finite element method (FEM) in 3-dimensional space and on unstructured tetrahedral grids. We introduce a fully iterative scheme to solve the nonlinear problem for complex coefficient matrices that depend on wavelength. We investigate the properties of the algorithm in detail and demonstrate its performance by analyzing a nanometer sized optical dimer structure, a specific type of optical antenna, on distributed-memory parallel computers. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Nanooptics Dispersive dielectrics Eigenmodal calculation 3D unstructured grid Nonlinear eigenvalue problem distributed memory parallel computer

来源：评论

学校读者我要写书评

暂无评论

Sufficient conditions for the determination and use of data in the same granular parallel computation process

引用

COMPUTATIONAL MATHEMATICS AND MATHEMATICAL PHYSICS 2014年第8期54卷 1316-1326页

作者： Likhoded, N. A. Belarusian State Univ Minsk 220030 BELARUS

parallel algorithms for distributed memory computers should be granular, in which case the set of algorithmic operations is split into sets known as computation grains, or tiles. Conditions are proposed and proved under which data is used in the same granular computation process where it was determined. These conditions can be used to estimate the number of communication operations in alternative versions of parallel algorithms.

关键词： parallelization of algorithms distributed memory parallel computer reduction in data exchange

来源：评论

学校读者我要写书评

暂无评论

The software on the VP500 system

引用

SYSTEMS AND computerS IN JAPAN 1996年第4期27卷 25-40页

作者： Okada, S Sakamoto, Y Asai, N FUJITSU SHIZUOKA ENGN LTD NUMAZU 410JAPAN

The VPP500 system is a commercial, distributed memory, parallel computer system based on vector parallel architecture. The software of the VPP500 system is described here. The OS is UNIX-based, enhanced with distributed parallel features. A system that is easy to use and has high performance requires a (1) realized one-system image;(2) pursued ultrahigh performance;and (3) enhanced operation of the system. To satisfy two fundamental requirements of a language processor system, (1) effective use of the existing program assets and (2) extraction of potential performance of hardware system, we have implemented VPP Fortran (the standard FORTRAN77 enhanced with the features of parallel processing). The various data on VPP Fortran show that the VPP500 system, which consists of hardware, OS and language processor system, has both high performance and high efficiency.

关键词： VPP500 distributed memory parallel computer vector parallel distributed parallel OS parallel language VPP Fortran

来源：评论

学校读者我要写书评

暂无评论

IMPLEMENTATION OF THE Z-BUFFER ALGORITHM ON A RECONFIGURABLE NETWORK OF PROCESSORS

引用

International Journal of Pattern Recognition and Artificial Intelligence 1992年第2N03期6卷 417-436页

作者： JIAN-JIN LI SERGE MIGUET YVES ROBERT Laboratoire de l'Informatique du Parallélisme LIP-IMAG Ecole Normale Supérieure de Lyon 69364 Lyon Cedex 07 France This work has been supported by the Research Projects C3 of CNRS and CMaP of IMAG and by the ESPRIT Basic Research Action 3280 "NANA" of the EEC.

This paper describes the parallel implementation of the Z-Buffer algorithm on a distributed memory machine. The Z-Buffer is one of the most popular techniques used to generate a representation of a scene consisting of objects in a three-dimensional world. We propose and compare two different parallel implementations on a reconfigurable network of Transputers. In the first approach, the description of the scene is distributed among the processors configured as a tree. The picture is processed in a pipelined fashion, in order to output parts of the image during the computation of the remainder. We show the influence of the degree and the height of the tree on the global performance of the algorithm. In a second approach, both the picture and the scene description are distributed to the processors. We have therefore to redistribute dynamically the tiles among the processors at the beginning of the computation. To perform this redistribution, a special algorithm is designed for the case where the processors are configured as a unidirectional or bidirectional ring. Then we implement a greedy algorithm that enables us to perform the redistribution on an arbitrary interconnection network. We show that the two approaches are complementary: for small pictures or large scenes, a tree-based algorithm performs better than a redistribution-based algorithm, but for large pictures or smaller scenes, it is the other way round. We obtain substantial speedups over the sequential implementation, with up to 32 processors.

关键词： Z-Buffer algorithm scan conversion distributed memory parallel computer reconfigurable interconnection network speedup divide-and-conquer load balancing

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：