A simple and realistic parallel computing model, characterized by two parameters (input size n and number of processors p), in which local computation rounds alternate with global communication rounds, with the goal of minimizing the number of communication rounds.?Granularity: A measure of the size of the components, or descriptions of components, that make up a system. In parallel computing, granularity refers to the amount of computation that can be performed by the processors before requiring a communication stepto exchange data.?Scalability: A desirable property of a system, a network, or a process, which indicates its ability to either handle growing amounts of work in a graceful manner, or to be readily enlarged.
Published in Chapter:
Communication Issues in Scalable Parallel Computing
C.E.R. Alves (Universidade Sao Judas Tadeu, Brazil), E.N. Caceres (Universidade Federal de Mato Grosso do Sul, Brazil), F. Dehne (Carleton University, Canada), and S.W. Song (Universidade de Sao Paulo, Brazil)
Copyright: © 2010
|Pages: 18
DOI: 10.4018/978-1-60566-661-7.ch017
Abstract
In this book chapter, the authors discuss some important communication issues to obtain a highly scalable computing system. They consider the CGM (Coarse-Grained Multicomputer) model, a realistic computing model to obtain scalable parallel algorithms. The communication cost is modeled by the number of communication rounds and the objective is to design algorithms that require the minimum number of communication rounds. They discuss some important issues and make considerations of practical importance, based on our previous experience in the design and implementation of parallel algorithms. The first issue is the amount of data transmitted in a communication round. For a practical implementation to be successful they should attempt to minimize this amount, even when it is already within the limit allowed by the CGM model. The second issue concerns the trade-off between the number of communication rounds which the CGM attempts to minimize and the overall communication time taken in the communication rounds. Sometimes a larger number of communication rounds may actually reduce the total amount of data transmitted in the communications rounds. These two issues have guided us to present efficient parallel algorithms for the string similarity problem, used as an illustration.