Information Requirements and the Implications for Parallel Computation
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 1/epsilon, 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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 1988
- Accession Number
- ADA207802
Entities
People
- Patrick H. Worley
Organizations
- Stanford University