Article

Free access

On the mapping problem for multi-level systems

Author:

S. G. ZiavrasAuthors Info & Claims

Supercomputing '89: Proceedings of the 1989 ACM/IEEE conference on Supercomputing

Pages 399 - 408

https://doi.org/10.1145/76263.76307

Published: 01 August 1989 Publication History

Abstract

Hierarchically-structured arrays of processors have been widely used in the low-level and the intermediate-level phases of computer vision. This is because tasks in these phases require both local and global operations, when the two-dimensional array structure of the image is considered. This paper 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 here are not necessarily homogeneous; the processing 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 minimizing the corresponding objective function, are then proposed. It is proven theoretically that our mapping algorithms always yield an optimal solution for systems composed of processors with identical processing powers. In all other cases, some assignment choices in the algorithms allow to take advantage of the increased processing powers of processors.

References

[1]

N. Ahuja and S. Swamy, ~Multiprocessor Pyramid Architectures for Bottom-Up Image Analysis,~ IEEE Trans. on Pattern Anal. and Mach. Irtel., Vol. PAMI-6, No. 4, pp. 463-474, July 1984.

Digital Library

[2]

S.H. Bokhari, ~On the Mapping Problem," IEEE Trans. on Comp., Vol. C-30, pp. 207-214, Mar. 1981.

[3]

S.W. Bollinger and S.F. Midkiff, ~Processor and Link Assignment in Multicomputers Using Simulated Anneafing," in Proc. Intern. Conf. on Paral. Proc., pp. 1-7, Aug. 1988.

[4]

V. Cantoni and S. Levialdi, n Multiprocessor Computing for Images," Proc. IEEE, Special Issue on Comp. Vision, Vol. 76, No. 8, pp. 959-969, Aug. 1988.

[5]

T.F. Chan and Y. Sand, "Multigrid Algorithms on the Hypercube Multiprocessor,~ IEEE Trans. on Comp., Vol. C-35, No. 11, pp. 969-977, Nov. 1986.

Digital Library

[6]

P. Clermont and A. Merigot, "Real Time Synchronization in a Multi-SIMD Massively Parallel Machine," in Proc. Conf. on Arch. for Pattern Anal. and Math. Iutel., pp. 131-136, 1987.

[7]

C.R. Dyer, ~A VLSI Pyramid Machine for Hierarchical Parallel Image Processing," in Proc. Pattern Recogn. and Image Proc., pp. 381-386, 1981.

[8]

W.D. Hfilis, Th___ee Connection Machine, MIT Press, Cambridge, MA, 1985.

[9]

M. Katevenis, Reduced Instruction Se__.~ Computer Architectures for VL.SI, MIT Press, 1985.

Digital Library

[10]

M. Mxreska, M.A. Lavin and H. Li, "Parallel Architectures for Vision," Proc. IEEE, Special Issue on Comp. Vision, Vol. 76, No. 8, pp. 959-969, Aug. 1988.

[11]

A.P. Reeves, ~Pyramid Algorithms on Processor Arrays,~ in Pyramidal Systems fo__r.r Computer Vision, V. Cantoni and S. Levialdi (Eds.), Springer- Verlag, New York, NATO ASI Series F, Vol. 25, pp. 195-214, 1986.

Digital Library

[12]

A. Rosenfeld {Ed.), Multiresolution Image Processing and Analysis, Springer-Verlag, York, 1984.

[13]

Q.F. Stout, ~Hypercubes and Pyramids,~ in Pyramidal Systems fo__rr Computer Vision, V. Cantoni and S. Levialdi (Eds.}: Springer-Verlag, New York, pp. 75-89, 1986.

Digital Library

[14]

S.L. Tanimoto, "A Pyramidal Approach to Parallel Processing,~ in Proc. 10th Intern. Con}. on Comp. Arch., pp. 372-378, 1983.

Digital Library

[15]

D. Terzopoulos, "Concurrent Multilevel Relaxation," in Proc. image Underst. Workshop, L.S. Baumann (Ed.), Miami Beach, FL, 1985.

[16]

L. Uhr (Ed.), Parallel Computer Vision, Academic Press, New York, 1987.

Digital Library

[17]

S.G. Ziavras, "Techniques for Efficient Mappings of Deterministic Algorithms onto Multi-Level Systems," in preparation.

Cited By

Ziavras SSiddiqui M(2006)Pyramid mappings onto hypercubes for computer vision: Connection machine comparative studyConcurrency: Practice and Experience10.1002/cpe.43300506035:6(471-489)Online publication date: 24-Oct-2006
https://doi.org/10.1002/cpe.4330050603
Ziavras S(1993)Efficient Mapping Algorithms for a Class of Hierarchical SystemsIEEE Transactions on Parallel and Distributed Systems10.1109/71.2501024:11(1230-1245)Online publication date: 1-Nov-1993
https://dl.acm.org/doi/10.1109/71.250102
Ziavras S(1990)High performance mapping for massively parallel hierarchical structures[1990 Proceedings] The Third Symposium on the Frontiers of Massively Parallel Computation10.1109/FMPC.1990.89467(251-254)Online publication date: 1990
https://doi.org/10.1109/FMPC.1990.89467

Index Terms

On the mapping problem for multi-level systems
1. Computer systems organization
  1. Architectures
    1. Parallel architectures
      1. Systolic arrays
2. Computing methodologies
  1. Artificial intelligence
    1. Computer vision
      1. Computer vision tasks
        Scene understanding
  2. Computer graphics
    1. Image manipulation
      1. Image processing

Recommendations

On the Mapping Problem

In array processors it is important to map problem modules onto processors such that modules that communicate with each other lie, as far as possible, on adjacent processors. This mapping problem is formulated in graph theoretic terms and shown to be ...
Multi-level document classifications with self-organising maps
IDEAL'05: Proceedings of the 6th international conference on Intelligent Data Engineering and Automated Learning

The Self-Organising Map (SOM) is widely used to classify document collections. Such classifications are usually coarse-grained and cannot accommodate accurate document retrieval. A document classification scheme based on Multi-level Nested Self-...
Reducing Cache Conflicts by Multi-Level Cache Partitioning and Array Elements Mapping

This article presents an algorithm to reduce cache conflicts and improve cache localities. The proposed algorithm analyzes locality reference space for each reference pattern, partitions the multi-level cache into several parts with different sizes, and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

Supercomputing '89: Proceedings of the 1989 ACM/IEEE conference on Supercomputing

August 1989

849 pages

ISBN:0897913418

DOI:10.1145/76263

Chairman:
F. Ron Bailey

Copyright © 1989 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGARCH: ACM Special Interest Group on Computer Architecture
IEEE-CS: Computer Society

In-Cooperation

Los Alamos National Labs: Los Alamos National Labs
NASA: National Aeronatics and Space Administration
Argonne Natl Lab: Argonne National Lab

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 August 1989

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SC '89

Sponsor:

SIGARCH
IEEE-CS

SC '89: International Conference for High Performance Computing, Networking, Storage and Analysis

November 12 - 17, 1989

Nevada, Reno, USA

Acceptance Rates

Overall Acceptance Rate 1,516 of 6,373 submissions, 24%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
238
Total Downloads

Downloads (Last 12 months)29
Downloads (Last 6 weeks)5

Reflects downloads up to 17 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ziavras SSiddiqui M(2006)Pyramid mappings onto hypercubes for computer vision: Connection machine comparative studyConcurrency: Practice and Experience10.1002/cpe.43300506035:6(471-489)Online publication date: 24-Oct-2006
https://doi.org/10.1002/cpe.4330050603
Ziavras S(1993)Efficient Mapping Algorithms for a Class of Hierarchical SystemsIEEE Transactions on Parallel and Distributed Systems10.1109/71.2501024:11(1230-1245)Online publication date: 1-Nov-1993
https://dl.acm.org/doi/10.1109/71.250102
Ziavras S(1990)High performance mapping for massively parallel hierarchical structures[1990 Proceedings] The Third Symposium on the Frontiers of Massively Parallel Computation10.1109/FMPC.1990.89467(251-254)Online publication date: 1990
https://doi.org/10.1109/FMPC.1990.89467

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents