Evaluating the Trade-Offs in the Parallelization of Probabilistic Search Algorithms

• R. L. Carceroni University of Rochester
• W. Meira Jr. UFMG
• R. Stets University of Rochester
• S. Dwarkadas University of Rochester

DOI: https://doi.org/10.5753/sbac-pad.1997.22627

Resumo

Neste trabalho propomos uma estratégia de paralelização especulativa para algoritmos de Busca Probabilística. Um algoritmo de Busca Probabilística paralelo é implementado para o Problema da Correspondência, cuja resolução é necessária em várias aplicações de visão computacional com requerimentos de tempo real. Essa implementação é executada em um cluster de oito DEC AlphaServer 2100 4/233 conectadas por um DEC Memory Channel. Apresentamos e discutimos resultados com quatro sistemas de tempo de execução: Memória Compartilhada com coerência por Hardware (HSM), Memória Compartilhada Distribuída (DSM) com coerência por software (Cashmere-2L), Memória Distribuída Refletiva (RSM), e troca de mensagens (Digital PVM). Dentre estes, o sistema de tempo de execução que normalmente é o menos eficiente (RSM) apresenta o melhor desempenho, mostrando que a estratégia de paralelização do algoritmo e a seleção do ambiente de execução se influenciam mutuamente e não podem ser consideradas isoladamente.

Referências

R. A. Brooks. Symbolic reasoning among 3-D models and 2-D images. Artificial Intelligence, 17:285-348, 1981.

R. B. Gillett. Memory channel network for PCI. IEEE Micro, pages 12-18, 1996.

R. B. Gillett and R. Kaufmann. Experiente using the first-generation memory channel for PCI network. Submitted for publication.

E. Grimson and T. Lozano-Pérez. Localizing overlapping parts by searching the interpretation tree. IEEE Trans. on Pattem Analysis and Machine Intelligence, 9:469-482, 1987.

E. L. Lawler and D. E. Wood. Branch-and-bound methods: A survey. Operations Research, 14:699-719, 1966.

D. G. Lowe. Fitting parameterized three-dimensional models to images. IEEE Trans. on Pattern Analysis and Machine Intelligence, 13(5):441-450, 1991.

D. G. Lowe. Robust model-based motion tracking through the integration of search and estimation. Intemational Journal of Computer Vision, 8(2):113-122, 1992.

R. Stets, S. Dwarkadas, N. Hardavellas, L. Kontothanassis G. Hunt, S. Parthasarathy, and M.Scott. CASHMERE-2L: Software coherent shared memory on a clustered remote-write network. In Proc. 16th Symposium on Operating Systems Principies, 1997.

V. Sunderam. PVM: A framework for parallel and distributed computing. Concurrency: Practice and Experience, 4(2):315-339, 1990.