Regular mapping of multi-dimensional data on parallel processors

Abstract

This thesis presents a generalized framework for the mapping and remapping of large regularly-gridded multidimensional data sets on a parallel computer. We address two problems that influence the efficiency with which parallel computers can be exploited in image processing, visualization and simulation applications. The data mapping problem is the task of describing the layout of multi-dimensional data set on a parallel array. This layout has a significant effect on the choice and efficiency of processing algorithms. The data remapping problem is the task of moving data dynamically between data mappings to provide portability between applications, libraries and external devices, and allows the description of a class of data transformations of. use in a variety of data processing algorithms. We develop the k-Tile format, which provides a concise and flexible data mapping description for multidimensional data arrays on multidimensional devices, and allows the specification of many commonly used parallel data mappings, geometric transformations of these mappings, data replication and data padding. Using the k-Tile format we define Parallel mapping functions (PMFs), which provide a general system for performing many remapping tasks. We introduce efficient algorithms for performing a subset of PMFs on a crossbarconnected parallel processing array with indirect addressing, and demonstrate an efficient implementation of these algorithms on a MasPar MP-1 computer. We also explore the problems involved in producing a complete implementation of PMFs on the MasPar, and suggest further work needed to produce such a system. We show examples of the use of the k-Tile format and PMFs for the data mapping directives of High Performance Fortran, in image processing algorithms and in visualization applications. Show more