Problem size, parallel architecture, and optimal speedup

David M. Nicol, Frank H. Willard

Research output: Contribution to journalArticle

Abstract

The communication and synchronization overhead inherent in parallel processing can lead to situations where adding processors to the solution method actually increases execution time. Problem type, problem size, and architecture type all affect the optimal number of processors to employ. In this paper we examine the numerical solution of an elliptic partial differential equation in order to study the relationship between problem size and architecture. The equation's domain is discretized into n2 grid points which are divided into partitions and mapped onto the individual processor memories. We analytically quantify the relationships among grid size, stencil type, partitioning strategy processor execution time, and communication network type. In doing so, we determine the optimal number of processors to assign to the solution (and hence the optimal speedup), and identify (i) the smallest grid size which fully benefits from using all available processors, (ii) the leverage on performance given by increasing processor speed or communication network speed, and (iii) the suitability of various architectures for large numerical problems. Finally, we compare the predictions of our analytic model with measurements from a multiprocessor and find that the model accurately predicts performance.

Original languageEnglish (US)
Pages (from-to)404-420
Number of pages17
JournalJournal of Parallel and Distributed Computing
Volume5
Issue number4
DOIs
StatePublished - Aug 1988
Externally publishedYes

Fingerprint

Parallel architectures
Parallel Architectures
Telecommunication networks
Speedup
Grid
Communication Networks
Execution Time
Partial differential equations
Synchronization
Data storage equipment
Communication
Elliptic Partial Differential Equations
Processing
Parallel Processing
Multiprocessor
Leverage
Assign
Partitioning
Quantify
Partition

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Artificial Intelligence

Cite this

Problem size, parallel architecture, and optimal speedup. / Nicol, David M.; Willard, Frank H.

In: Journal of Parallel and Distributed Computing, Vol. 5, No. 4, 08.1988, p. 404-420.

Research output: Contribution to journalArticle

@article{b9fe40ee981f434caf5e7b461480b7e8,
title = "Problem size, parallel architecture, and optimal speedup",
abstract = "The communication and synchronization overhead inherent in parallel processing can lead to situations where adding processors to the solution method actually increases execution time. Problem type, problem size, and architecture type all affect the optimal number of processors to employ. In this paper we examine the numerical solution of an elliptic partial differential equation in order to study the relationship between problem size and architecture. The equation's domain is discretized into n2 grid points which are divided into partitions and mapped onto the individual processor memories. We analytically quantify the relationships among grid size, stencil type, partitioning strategy processor execution time, and communication network type. In doing so, we determine the optimal number of processors to assign to the solution (and hence the optimal speedup), and identify (i) the smallest grid size which fully benefits from using all available processors, (ii) the leverage on performance given by increasing processor speed or communication network speed, and (iii) the suitability of various architectures for large numerical problems. Finally, we compare the predictions of our analytic model with measurements from a multiprocessor and find that the model accurately predicts performance.",
author = "Nicol, {David M.} and Willard, {Frank H.}",
year = "1988",
month = "8",
doi = "10.1016/0743-7315(88)90005-6",
language = "English (US)",
volume = "5",
pages = "404--420",
journal = "Journal of Parallel and Distributed Computing",
issn = "0743-7315",
publisher = "Academic Press Inc.",
number = "4",

}

TY - JOUR

T1 - Problem size, parallel architecture, and optimal speedup

AU - Nicol, David M.

AU - Willard, Frank H.

PY - 1988/8

Y1 - 1988/8

N2 - The communication and synchronization overhead inherent in parallel processing can lead to situations where adding processors to the solution method actually increases execution time. Problem type, problem size, and architecture type all affect the optimal number of processors to employ. In this paper we examine the numerical solution of an elliptic partial differential equation in order to study the relationship between problem size and architecture. The equation's domain is discretized into n2 grid points which are divided into partitions and mapped onto the individual processor memories. We analytically quantify the relationships among grid size, stencil type, partitioning strategy processor execution time, and communication network type. In doing so, we determine the optimal number of processors to assign to the solution (and hence the optimal speedup), and identify (i) the smallest grid size which fully benefits from using all available processors, (ii) the leverage on performance given by increasing processor speed or communication network speed, and (iii) the suitability of various architectures for large numerical problems. Finally, we compare the predictions of our analytic model with measurements from a multiprocessor and find that the model accurately predicts performance.

AB - The communication and synchronization overhead inherent in parallel processing can lead to situations where adding processors to the solution method actually increases execution time. Problem type, problem size, and architecture type all affect the optimal number of processors to employ. In this paper we examine the numerical solution of an elliptic partial differential equation in order to study the relationship between problem size and architecture. The equation's domain is discretized into n2 grid points which are divided into partitions and mapped onto the individual processor memories. We analytically quantify the relationships among grid size, stencil type, partitioning strategy processor execution time, and communication network type. In doing so, we determine the optimal number of processors to assign to the solution (and hence the optimal speedup), and identify (i) the smallest grid size which fully benefits from using all available processors, (ii) the leverage on performance given by increasing processor speed or communication network speed, and (iii) the suitability of various architectures for large numerical problems. Finally, we compare the predictions of our analytic model with measurements from a multiprocessor and find that the model accurately predicts performance.

UR - http://www.scopus.com/inward/record.url?scp=0012803459&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0012803459&partnerID=8YFLogxK

U2 - 10.1016/0743-7315(88)90005-6

DO - 10.1016/0743-7315(88)90005-6

M3 - Article

AN - SCOPUS:0012803459

VL - 5

SP - 404

EP - 420

JO - Journal of Parallel and Distributed Computing

JF - Journal of Parallel and Distributed Computing

SN - 0743-7315

IS - 4

ER -