## Abstract

Recently, we have studied two important classes of algorithms requiring ±2^{b} communications: ±2^{b}-descend, and ±2^{b}-ascend. Let N = 2^{n} be the number of PEs in a SIMD hypercube which restricts all communications to a single fixed dimension at a time. In [5], we developed an efficient O(n) algorithm for the descend class. In [6], we obtained a simple O(n^{2}/log n) algorithm for the ascend class, requiring O(log n) words of local memory per PE. In this paper, we present 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, which is discussed only briefly here, runs in O(n√n/log n) time and requires O(log n) space per PE.

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

Title of host publication | Proceedings of the International Conference on Parallel Processing |

Publisher | Publ by IEEE |

Pages | 122-129 |

Number of pages | 8 |

ISBN (Print) | 0818626720 |

State | Published - Dec 1 1992 |

Event | Proceedings of the 6th International Parallel Processing Symposium - Beverly Hills, CA, USA Duration: Mar 23 1992 → Mar 26 1992 |

### Other

Other | Proceedings of the 6th International Parallel Processing Symposium |
---|---|

City | Beverly Hills, CA, USA |

Period | 3/23/92 → 3/26/92 |

## All Science Journal Classification (ASJC) codes

- Hardware and Architecture