On the mapping problem for multi-level systems

Hierarchically structured arrays of processors have been widely used in the low-level and intermediate-level phases of computer vision, because tasks in these phases require both local and global operations when the two-dimensional array structure of the image is considered. The author introduces mapping (process assignment) algorithms for systems in the above class. It is the first time in parallel computer vision that both the domain and the range of the mapping functions are in a general set of hierarchically structured arrays of processors. More specifically, the systems being studied are not necessarily homogeneous; the processor powers of processors at different levels and the reductions between different pairs of consecutive levels are allowed to vary. Efficient mapping is achieved by first proposing objective functions, so that each objective function measures the quality of a given mapping with respect to a particular optimization goal. Mapping algorithms, one for each objective function, that attempt to produce an optimal mapping by minimzing the corresponding objective function are then proposed. It is proved theoretically that the mapping algorithms always yield an optimal solution for systems composed of processors with identical processing powers.