skip to main content

Nearly Logarithmic-Time Parallel Algorithms for the Class of ±2b ASCEND Computations on a SIMD Hypercube

Nassimi, D

Journal of Parallel and Distributed Computing, March 1994, Vol.20(3), pp.289-302 [Periódico revisado por pares]

Texto completo disponível

Ver todas as versões
Citações Citado por
  • Título:
    Nearly Logarithmic-Time Parallel Algorithms for the Class of ±2b ASCEND Computations on a SIMD Hypercube
  • Autor: Nassimi, D
  • Assuntos: Computer Science
  • É parte de: Journal of Parallel and Distributed Computing, March 1994, Vol.20(3), pp.289-302
  • Descrição: Recently, we studied two important classes of algorithms requiring ±2 b communications: ±2 b -descend, and ±2 b -ascend. Given an N -element input A [0 : N − 1], where N = 2 n , the descend class consists of n iterations. For b = n − 1, n − 2, ..., 0, iteration b computes the new value of each A [ i ] as a function of the previous-iteration values of A [ i ], A [ i + 2 b mod N ], and A [ i − 2 b mod N ]. (Batcher′s odd-even merge falls into this class.) The ascend class is similar except that the iterations are for b = 0, 1, ..., n − 1. Let N = 2 n be the number of processors in a SIMD hypercube which restricts all communications to a single fixed dimension at a time. For the descend class, we developed an efficient O ( n ) algorithm on a SIMD hypercube. And for the ascend class, we obtained a simple O ( n 2 /log n ) algorithm, requiring O ( n ) words of local memory per processor. In this paper, we develop two new algorithms for the ascend class on a SIMD hypercube. The first algorithm runs in O ( n 1.5 ) time and requires O (1) space per PE. The second algorithm runs in [formula] time and requires O (log n ) space per PE.
  • Idioma: Inglês

Buscando em bases de dados remotas. Favor aguardar.