Accession Number:

ADA207802

Title:

Information Requirements and the Implications for Parallel Computation

Descriptive Note:

Doctoral thesis

Corporate Author:

STANFORD UNIV CA DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1988-06-01

Pagination or Media Count:

149.0

Abstract:

The best serial algorithms for numerically approximating the solution of a linear partial differential equation PDE exploit knowledge of the solution operator. This dissertation describes how the solution operator also influences the behavior of parallel algorithms. Approximating the solution at a single location in the problem domain is considered. A lower bound on the error in the approximation is derived that is a function of the amount of data used and the smoothness of the data functions. From this one can derive a lower bound on the parallel complexity of algorithms that approximate the solution. The lower bound is a linear function of log 1epsilon, where epsilon is an upper bound on the error. Thus the parallel complexity increases as epsilon decreases, independent of the number of processors used. An algorithm is also constructed whose parallel complexity is of this form, proving that the form of the bound is the best possible. The execution time of parallel algorithms is a function of both the communication costs and the parallel complexity. We describe bounds on the communication cost of parallel algorithms that are functions of the distance between collaborating processors. If the interconnection network of a multiprocessor is a D dimensional grid, then we prove that the execution time of algorithms that approximate the solution is bounded from below by a linear function of epsilon exp-gamma d 1, where gamma is a positive constant determined by the smoothness of the data functions. Thus, for small epsilon the communication costs are the dominant constraints on the optimal performance.

Subject Categories:

  • Numerical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE