A parallel single row routing algorithm for hypercube multiprocessor

Arnob Roy, Jitender Deogun, Naveed A. Sherwani

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In this paper, we develop a parallel single row routing algorithm for a hypercube multiprocessor. The parallel algorithm is based on our earlier sequential O(n2log n) algorithm and an efficient allocation scheme. The algorithms uses a graph decomposition technique and modified cut-number to partition the problem into several sub-problems. Each problem is solved on a different processor and solutions are merged in parallel. We prove that the algorithm has a linear speedup (n2 log n/N). using N processors and that the allocation scheme is optimal. The experimental results show that the proposed algorithm achieves a speedup factor that is quite close to the theoretical bound while maintaining the quality of the solutions, as compared to sequential algorithms.

Original languageEnglish (US)
Title of host publication1991 Proceedings of the 34th Midwest Symposium on Circuits and Systems, MWSCAS 1991
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages459-462
Number of pages4
ISBN (Electronic)0780306201
DOIs
StatePublished - 1991
Event34th Midwest Symposium on Circuits and Systems, MWSCAS 1991 - Monterey, United States
Duration: May 14 1992May 17 1992

Publication series

NameMidwest Symposium on Circuits and Systems
ISSN (Print)1548-3746

Conference

Conference34th Midwest Symposium on Circuits and Systems, MWSCAS 1991
CountryUnited States
CityMonterey
Period5/14/925/17/92

ASJC Scopus subject areas

  • Electronic, Optical and Magnetic Materials
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'A parallel single row routing algorithm for hypercube multiprocessor'. Together they form a unique fingerprint.

  • Cite this

    Roy, A., Deogun, J., & Sherwani, N. A. (1991). A parallel single row routing algorithm for hypercube multiprocessor. In 1991 Proceedings of the 34th Midwest Symposium on Circuits and Systems, MWSCAS 1991 (pp. 459-462). [252195] (Midwest Symposium on Circuits and Systems). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/MWSCAS.1991.252195