On the mapping problem for multi-level systems

Research output: Contribution to conferencePaperpeer-review

2 Scopus citations


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.

Original languageEnglish (US)
Number of pages10
StatePublished - 1989
Externally publishedYes
EventProceedings: Supercomputing '89 - Reno, NV, USA
Duration: Nov 13 1989Nov 17 1989


OtherProceedings: Supercomputing '89
CityReno, NV, USA

All Science Journal Classification (ASJC) codes

  • General Engineering


Dive into the research topics of 'On the mapping problem for multi-level systems'. Together they form a unique fingerprint.

Cite this