Analysis of task mapping for parallel supercomputers.

摘要

This thesis concentrates on mapping applications to parallel computers with complex network architectures. The common practice of assigning tasks to processors without regard to the communication pattern of the problem or the network topology of the machine is an inefficient one. This approach has not caused any serious performance degradation for systems with small numbers of processors connected by simple, usually all-connected, networks. However, near-optimal performance for most general applications and architectures cannot be achieved without the incorporation of a sound mathematical model which represents the problem and the machine and predicts the relative runtimes for various mappings.;Many models have been developed, each appropriate under some circumstances. Few, however, deliver decent performance for selected scientific computing applications on a variety of architectures. We analyze the performance of several models on an assortment of problems on four computers with different network topologies. We attempt to improve upon models currently in use by developing methodologies to incorporate factors that are recognized as significant yet often ignored or poorly represented.;The two major problems studied in this thesis are integral components of many common applications: matrix multiplication and the fast Fourier transform. Each has been implemented on a Beowulf cluster, a distributed symmetric multiprocessing system, and two cellular architectures of differing topology. Our results reveal the great dependence of the performance of an application on the mapping model.;In addition to illustrating the significance of task mapping, we also address the difficulty that determining an efficient model can be a time-consuming operation. Our work seeks to remedy this problem by proposing guidelines for choosing an optimal method of task assignment, based on the applications and the architectures of the networks to be utilized. The goal is to use these guidelines as the foundation for a much more desirable programming paradigm: automatic parallelization.