## Abstract

We identify an important class of parallel computations, called ±2^{b} - descend, with an efficient implementation on a hypercube. Given the input A[0: N - 1], a computation in this class consists of log N iterations. Iteration 6, 6 = logN - 1,.,0, computes the new value of each A[i] as a function of A[i], A[i+2^{b}] and A[i-2^{b}]. We obtain a general algorithm for implementing any computation in this class in O(logN) time on a SIMD hypercube. Our general descend algorithm results in an efficient O(log N) implementation of Batcher's odd-even merge algorithm on a hypercube. The best previously known implementation of odd-even merge on a SIMD hypercube requires O(log^{2} N) time.

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

Title of host publication | Proceedings - 5th International Parallel Processing Symposium, IPPS 1991 |

Publisher | Institute of Electrical and Electronics Engineers Inc. |

Pages | 2-9 |

Number of pages | 8 |

ISBN (Electronic) | 0818691670, 9780818691676 |

DOIs | |

State | Published - Jan 1 1991 |

Event | 5th International Parallel Processing Symposium, IPPS 1991 - Anaheim, United States Duration: Apr 30 1991 → May 2 1991 |

### Publication series

Name | Proceedings - 5th International Parallel Processing Symposium, IPPS 1991 |
---|

### Conference

Conference | 5th International Parallel Processing Symposium, IPPS 1991 |
---|---|

Country/Territory | United States |

City | Anaheim |

Period | 4/30/91 → 5/2/91 |

## All Science Journal Classification (ASJC) codes

- Hardware and Architecture
- Artificial Intelligence
- Computer Networks and Communications
- Computer Science Applications
- Computational Mathematics

## Fingerprint

Dive into the research topics of 'Efficient implementations of a class of ±2^{b}parallel computations on a SIMD hypercube'. Together they form a unique fingerprint.