Modeling, predicting, and optimizing parallel performance of grid structured problems

The performance of parallel computers can be greatly affected by a user's choices of data distribution and logical processor configuration. Selecting optimal choices for such user specifiable parameters may be easier if the performance of the target machine can be predicted by a performance model. Models for parallel performance on the IBM SP for grid structured problems are considered. Such problems are ubiquitous in scientific computing and frequently are characterized by a nearest neighbor communication pattern. Bounds are derived for the size of the solution space of data distributions and logical processor configurations for problems with nearest neighbor communication. Proofs are derived that exclude a substantial number of non-optimal choices of data distribution and logical processor configuration. Algorithms are given that are intended to predict parallel performance for a model application and allow the user to select optimal choices for parameters that can be specified. Experimental evidence is presented that suggests that performance on the SP is characterized fairly accurately by a specific model. Experimental evidence also suggests that an algorithm exists to optimize a user's choices of data distribution and logical processor configuration for grid structured problems on the SP.