Communication and matrix computations on large message passing systems
type: Item
instance of: scholarly article
title: Communication and matrix computations on large message passing systems
zbMATH Open document ID: 0713.65106
DOI: 10.1016/0167-8191(90)90156-4
author: G. W. Stewart
published in: Parallel Computing
publication date: 1990-01-01T00:00:00Z
full work available at URL: http://hdl.handle.net/1903/541
review text: This paper studies the consequences for matrix computations of working with a large number of general purpose processors, say from 10000 to 20000, connected through a topology that allows any processor to communicate directly only to its immediate neighbors, and assuming a rate of a million arithmetic operations per second for each processor. (No such a system has been built so far.) One consequence of these hypotheses is that problems can be posed that are too large to be solved in a reasonable amount of time. This suggests that the next generation of parallel computers must be designed to solve smaller matrix problems faster, rather than to solve the largest problems they could handle. To be computationally intensive, parallel algorithms must communicate a lot. However, it is known that the rate of computation to communication decreases with problem size. But if a problem is large enough to be efficiently solved, is it also so large that its solving can only be reached in an unreasonable time span? The author partitions an arbitrary matrix into square submatrices and assigns these to individual processors. Some typical communication tasks are then considered and their implementation done in two types of networks: a grid and a hypercube. The communication times for problems of different sizes are then computed and compared with the computation costs, so as to determine break-even points. The main result assures that the efficiency of certain important matrix algorithms at fine granularity is restricted by the granularity of the communication. A remedy, called simple streaming, is then proposed.
Mathematics Subject Classification ID: 65Y05
Mathematics Subject Classification ID: 65Y10
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 65F30
Mathematics Subject Classification ID: 68W15
Mathematics Subject Classification ID: 65Y20
zbMATH DE Number: 4174308
zbMATH Keywords: concurrent calculations
zbMATH Keywords: message passing systems
zbMATH Keywords: timing analysis
zbMATH Keywords: matrix computations
zbMATH Keywords: parallel computers
zbMATH Keywords: parallel algorithms
zbMATH Keywords: hypercube
zbMATH Keywords: communication times
zbMATH Keywords: computation costs
zbMATH Keywords: efficiency
MaRDI profile type: Publication
OpenAlex ID: W1999928392
description: scientific article; zbMATH DE number 4174308