Basic Techniques for Numerical Linear Algebra on Bulk Synchronous Parallel Computers

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Abstract

The bulk synchronous parallel (BSP) model promises scalable and portable software for a wide range of applications. A BSP computer consists of several processors, each with private memory, and a communication network that delivers access to remote memory in uniform time. Numerical linear algebra computations can bene t from the BSP model, both in terms of simplicity and eciency. Dense LU decomposition and other computations can be made more ecient by using the new technique of two-phase randomised broadcasting, which is motivated by a cost analysis in the BSP model. For LU decomposition with partial pivoting, this technique reduces the communication time by a factor of (p p + 1)=3, where p is the number of processors. Theoretical analysis, together with benchmark values for machine parameters, can be used to predict execution time. Such predictions are veri ed by numerical experiments on a 64-processor Cray T3D. The experimental results con rm the advantage of two-phase randomised broadcasting.
Original languageEnglish
Title of host publicationProceedings First Workshop on Numerical Analysis and Applications, Rousse, Bulgaria 1996
EditorsL. Vulkov, J. Wasniewski, P. Yalamov
Place of PublicationBerlin
PublisherSpringer
Pages46-57
Number of pages12
ISBN (Electronic)978-3-540-68326-1
DOIs
Publication statusPublished - 1997

Publication series

NameLecture Notes in Computer Science
Volume1196

Bibliographical note

First Workshop on Numerical Analysis and Applications, Rousse, Bulgaria 1996

Keywords

  • Wiskunde en Informatica (WIIN)
  • Mathematics
  • Wiskunde en computerwetenschappen
  • Landbouwwetenschappen
  • Wiskunde: algemeen

Fingerprint

Dive into the research topics of 'Basic Techniques for Numerical Linear Algebra on Bulk Synchronous Parallel Computers'. Together they form a unique fingerprint.

Cite this