## Abstract

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.

Original language | English (US) |
---|---|

Pages (from-to) | 289-302 |

Number of pages | 14 |

Journal | Journal of Parallel and Distributed Computing |

Volume | 20 |

Issue number | 3 |

DOIs | |

State | Published - Jan 1 1994 |

## All Science Journal Classification (ASJC) codes

- Software
- Theoretical Computer Science
- Hardware and Architecture
- Computer Networks and Communications
- Artificial Intelligence