skip to main content

Nearly logarithmic-time parallel algorithms for the class of +or-2/sup b/ ASCEND computations on a SIMD hypercube

Nassimi, D

Proceedings Sixth International Parallel Processing Symposium, 1992, pp.122-129

Texto completo disponível

Ver todas as versões
Citações Citado por
  • Título:
    Nearly logarithmic-time parallel algorithms for the class of +or-2/sup b/ ASCEND computations on a SIMD hypercube
  • Autor: Nassimi, D
  • Assuntos: Parallel Algorithms ; Concurrent Computing ; Hypercubes ; Routing ; Computational Intelligence Society ; Communication System Control ; Algorithm Design and Analysis ; Genetic Mutations ; Arithmetic
  • É parte de: Proceedings Sixth International Parallel Processing Symposium, 1992, pp.122-129
  • Descrição: Recently, the author has studied two important classes of algorithms requiring +or-2/sup b/ communications: +or-2/sup b/-descend, and +or-2/sup b/-ascend. Let N=2/sup n/ be the number of PEs in a SIMD hypercube which restricts all communications to a single fixed dimension at a time. He has developed an efficient O(n) algorithm for the descend class, and also obtained a simple O(n/sup 2//logn) algorithm for the ascend class, requiring O(logn) words of local memory per PE. In the present paper he presents two new algorithms for the ascend class on a SIMD hypercube. The first algorithm runs in O(n/sup 1.5/) time and requires O(1) space per PE. The second algorithm, which is discussed only briefly, runs in O(n square root n/log n) time and requires O(logn) space per PE.<>
  • Idioma: Inglês

Buscando em bases de dados remotas. Favor aguardar.