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

Parallel Communication-Avoiding Algorithm for Triangular Matrix Inversion on Homogeneous and Heterogeneous Platforms

引用

INTERNATIONAL JOURNAL OF PARALLEL PROGRAMMING 2015年第4期43卷 631-655页

作者： Mahfoudhi, Ryma Mahjoub, Zaher Nasri, Wahid Univ Tunis El Manar Fac Sci Tunis Tunis 2092 Tunisia Higher Sch Sci & Tech Tunis Tunis 1008 Tunisia

We address in this paper the parallelization of a recursive algorithm for large scale triangular matrix inversion based on the 'Divide and Conquer' (D&C) paradigm. A set of different versions of an original sequential algorithm are first presented. A theoretical performance study permits to establish an accurate comparison between the designed algorithms. Afterwards, we develop in the second part of the paper, an optimal parallel avoiding-communication algorithm for a given number of available homogeneous and heterogeneous processors. To reach this target, we use a so called 'non equitable and incomplete' version of the D&C paradigm consisting in recursively decomposing the original problem into two sub-problems of non equal sizes, then decomposing only one sub-problem in the same previous manner. The theoretical study is validated by a series of experiments achieved on three target platforms, namely an 8-core shared memory machine, a distributed memory cluster and a heterogeneous CPU-GPU cluster. The obtained results permit to illustrate the interest of the contribution.

关键词： Communication-avoiding Cost optimality distributed memory machine Divide and Conquer GPU Homogeneous platform Heterogeneous platform Load balancing Parallel algorithm Recursive algorithm Scheduling Shared memory machine Triangular matrix inversion

来源：评论

学校读者我要写书评

暂无评论

Parallel construction of Hamiltonian paths for conforming tetrahedral meshes

引用

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS 2013年第7期90卷 1366-1372页

作者： Liu, Hui Chen, Zhangxin Zhang, Linbo Univ Calgary Dept Chem & Petr Engn Calgary AB T2N 1N4 Canada Xi An Jiao Tong Univ Coll Math & Stat Ctr Computat Geosci Xian 710049 Peoples R China Acad Math & Syst Sci Beijing 100190 Peoples R China

In this paper, we address the construction of a Hamiltonian path for conforming tetrahedral meshes on distributed memory machines. The path is constrained to pass from one element to the next one through a vertex. For a conforming tetrahedral mesh whose dual graph is connected, if it can be split into many submeshes and the dual graphs of these submeshes are connected, then we can construct partial Hamiltonian paths for all submeshes independently and a Hamiltonian path for the mesh can be obtained by connecting these partial Hamiltonian paths.

关键词： adaptive finite element method tetrahedral meshes Hamiltonian path distributed memory machine parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

Hierarchical parallelisation for the solution of stochastic finite element equations

引用

COMPUTERS & STRUCTURES 2005年第14期83卷 1033-1047页

作者： Keese, A Matthies, HG Tech Univ Braunschweig Inst Comp Sci D-38092 Braunschweig Germany

As an example application the elliptic partial differential equation for steady groundwater flow is considered. Uncertainties in the conductivity may be quantified with a stochastic model. A discretisation by a Galerkin ansatz with tensor products of finite element functions in space and stochastic ansatz functions leads to a certain type of stochastic finite element system (SFEM). This yields a large system of equations with a particular structure. They can be efficiently solved by Krylov subspace methods, as here the main ingredient is the multiplication with the system matrix and the application of the preconditioner. We have implemented a "hierarchical parallel solver" on a distributed memory architecture for this. The multiplication and the preconditioning uses a-possibly parallel-deterministic solver for the spatial discretisation as a building block in a black-box fashion. This paper is concerned with a coarser grained level of parallelism resulting from the stochastic formulation. These coarser levels are implemented by running different instances of the deterministic solver in parallel. Different possibilities for the distribution of data are investigated, and the efficiencies determined. On up to 128 processors, systems with more than 5 x 107 unknowns are solved. (c) 2005 Elsevier Ltd. All rights reserved.

关键词： Stochastic finite elements parallel Krylov subspace solver distributed memory machine polynomial chaos Karhunen-Loeve expansion Stochastic elliptic partial differential equation

来源：评论

学校读者我要写书评

暂无评论

Hierarchical parallelisation for the solution of stochastic finite element equations

Hierarchical parallelisation for the solution of stochastic ...

引用

Mini Symposia on Uncertainties in Structural Mechanics Analysis and Computational Stochastic Mechanics

作者： Keese, A Matthies, HG Tech Univ Braunschweig Inst Comp Sci D-38092 Braunschweig Germany

关键词： Stochastic finite elements parallel Krylov subspace solver distributed memory machine polynomial chaos Karhunen-Loeve expansion Stochastic elliptic partial differential equation

来源：评论

学校读者我要写书评

暂无评论

Elimination of redundant messages with a two-pass static analysis algorithm

引用

PARALLEL COMPUTING 2002年第3期28卷 433-453页

作者： Girault, A INRIA Rhone Alpes BIP Project F-38334 St Ismier France

Eliminating redundant messages in distributed programs leads to the reduction of communication overheads, and thus to the improvement of the overall performances of the distributed program. Therefore, a lot of work has been done recently to achieve this goal. In this paper, we present an algorithm for eliminating redundant messages in parallel programs that have been distributed automatically. This algorithm works on program whose control flow is as general as possible, i.e.,, contains gotos. Precisely, the control flow is a finite deterministic automaton with a DAG of actions in each state. Our algorithm proceeds in two passes: First a global data-flow analysis which computes, for each state of the automaton, the set of distant variables that are known at the beginning of the state. Then a local elimination which removes redundant messages locally in each state of the automaton. We present the algorithms as well as the corresponding time and memory costs. (C) 2002 Elsevier Science B.V, All rights reserved.

关键词： redundant message elimination static analysis data-flow analysis parallel program optimisation distributed memory machine

来源：评论

学校读者我要写书评

暂无评论

Contention resolution in hashing based shared memory simulations

引用

SIAM JOURNAL ON COMPUTING 2000年第5期29卷 1703-1739页

作者： Czumaj, A Auf der Heide, FM Stemann, V Univ Gesamthsch Paderborn Heinz Nixdorf Inst D-33095 Paderborn Germany Univ Gesamthsch Paderborn Dept Comp Sci D-33095 Paderborn Germany

In this paper we study the problem of simulating shared memory on the distributed memory machine (DMM). Our approach uses multiple copies of shared memory cells, distributed among the memory modules of the DMM via universal hashing. The main aim is to design strategies that resolve contention at the memory modules. Extending results and methods from random graphs and very fast randomized algorithms, we present new simulation techniques that enable us to improve the previously best results exponentially. In particular, we show that an n-processor CRCW PRAM can be simulated by an n-processor DMM with delay O(log log log n log* n), with high probability. Next we describe a general technique that can be used to turn these simulations into time-processor optimal ones, in the case of EREW PRAMs to be simulated. We obtain a time-processor optimal simulation of an (n log log log n log* n)-processor EREW PRAM on an n-processor DMM with delay O( log log log n log* n), with high probability. When an (n log log log n log* n)-processor CRCW PRAM is simulated, the delay is only by a log* n factor larger. We further demonstrate that the simulations presented can not be significantly improved using our techniques. We show an Omega(log log log n/log log log log n) lower bound on the expected delay for a class of PRAM simulations, called topological simulations, that covers all previously known simulations as well as the simulations presented in the paper.

关键词： PRAM distributed memory machine randomized shared memory simulations hashing

来源：评论

学校读者我要写书评

暂无评论

Performance of the Hough transform on a distributed memory multiprocessor

引用

MICROPROCESSORS AND MICROSYSTEMS 1999年第7期22卷 355-362页

作者： Underhill, A Atiquzzaman, M Ophel, J Univ Dayton Dept Elect & Comp Engn Dayton OH 45469 USA La Trobe Univ Sch Comp Sci & Comp Engn Bundoora Vic 3083 Australia

The Hough transform is a projection-based transform which can be used to detect shapes in images. One of the disadvantages of the transform is its requirement for large amounts of computing power. Parallel machines have given programmers the potential for incredible computing power. To obtain maximum performance from parallel machines, parallel algorithms should be designed to reflect the architecture of the parallel machine. The work reported in this paper compares the performance obtained in running several parallel versions of the Hough transform on a Fujitsu AP1000 distributed memory multiprocessor. (C) 1999 Published by Elsevier Science B.V.

关键词： Hough transform distributed memory machine performance evaluation

来源：评论

学校读者我要写书评

暂无评论

Efficient PRAM simulation on a distributed memory machine

引用

ALGORITHMICA 1996年第4-5期16卷 517-542页

作者： Karp, RM Luby, M Heide, FMAD UNIV CALIF BERKELEY BERKELEY CA 94720 USA INT COMP SCI INST BERKELEY CA 94704 USA UNIV PADERBORN HEINZ NIXDORF INST D-33095 PADERBORN GERMANY UNIV PADERBORN DEPT COMP SCI D-33095 PADERBORN GERMANY

We present algorithms for the randomized simulation of a shared memory machine (PRAM) on a distributed memory machine (DMM). In a PRAM, memory conflicts occur only through concurrent access to the same cell, whereas the memory of a DMM is divided into modules, one for each processor, and concurrent accesses to the same module create a conflict. The delay of a simulation is the time needed to simulate a parallel memory access of the PRAM. Any general simulation of an m processor PRAM on an n processor DMM will necessarily have delay at least min. A randomized simulation is called time-processor optimal if the delay is O(m/n) with high probability. Using a novel simulation scheme based on hashing we obtain a time-processor optimal simulation with delay O(log log(n) log*(n)). The best previous simulations use a simpler scheme based on hashing and have much larger delay: Theta(log(n)/log log(n)) for the simulation of an n processor PRAM on an n processor DMM, and Theta(log(n)) in the case where the simulation is time-processor optimal. Our simulations use several (two or three) hash functions to distribute the shared memory among the memory modules of the PRAM. The stochastic processes modeling the behavior of our algorithms and their analyses based on powerful classes of universal hash functions may be of independent interest.

关键词： PRAM simulation distributed memory machine universal hashing stochastic modeling balls and bins

来源：评论

学校读者我要写书评

暂无评论

An interprocedural framework for determining efficient array data redistributions

引用

JOURNAL OF INFORMATION SCIENCE AND ENGINEERING 1998年第1期14卷 27-51页

作者： Gupta, SKS Krishnamurthy, S Colorado State Univ Dept Comp Sci Ft Collins CO 80523 USA Univ Illinois Dept Comp Sci Urbana IL 61801 USA

Modifying the data distributions over the course of a program to adapt to variations in the data reference patterns at different points may lead to significant computational benefits. However, these modifications themselves result in data redistribution overheads because of the interprocessor communication involved. Moreover, modifying distributions across procedure boundaries is more complex because of the impreciseness in the available information and the need to perform global data-flow analysis. This paper presents a framework to Emd good distributions for the global arrays at different program points in the presence of procedure calls. The distributions are chosen for their ability to offset the redistribution overheads by contributing significantly towards increasing the performance gains. The framework uses interprocedural analysis and dynamic programming techniques. Experimental results obtained by testing the dynamic programming algorithm on some standard HPF programs indicate that it is possible to determine efficient data redistributions at compile-time.

关键词： data redistribution distributed memory machine compiler optimization dynamic programming High Performance Fortran (HPF) interprocedural analysis intermediate representations flow analysis

来源：评论

学校读者我要写书评

暂无评论

memory management techniques for Time Warp on a distributed memory machine 95

Memory management techniques for Time Warp on a distributed ...

引用

Proceedings of the ninth workshop on Parallel and distributed simulation

作者： Bruno R. Preiss Wayne M. Loucks Dept. of Elec. and Comp. Eng. University of Waterloo Waterloo ON N2L 3G1

ISBN: (纸本)9780818671203

This paper examines memory management issues associated with Time Warp synchronized parallel simulation on distributed memory machines. The paper begins with a summary of the techniques which have been previously proposed for memory management on various parallel processor memory structures. It then concentrates the discussion on parallel simulation executing on a distributed memory computer—a system comprised of separate computers, interconnected by a communications network. An important characteristic of the software developed for such systems is the fact that the dynamic memory is allocated from a pool of memory that is shared by all of the processes at a given *** paper presents a new memory management protocol, pruneback, which recovers space by discarding previous states. This is different from all previous schemes such as artificial rollback and cancelback which recover memory space by causing one or more logical processes to roll back to an earlier simulation *** paper includes an empirical study of a parallel simulation of a closed stochastic queueing network showing the relationship between simulation execution time and amount of memory available. The results indicate that using pruneback is significantly more effective than artificial rollback (adapted for a distributed memory computer) for this problem. In the study, varying the memory limits over a 2:1 range resulted in a 1:2 change in artificial rollback execution time and almost no change in pruneback execution time.

关键词： memory management protocol memory management techniques distributed memory machine time warp simulation distributed memory systems memory protocols time warp synchronized parallel simulation closed stochastic queueing network pruneback queueing theory communications network storage management

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：