Parallel algorithms for hypercube allocation

Yeim-Kuan Chang, L. N. Bhuyan

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

4 Citations (Scopus)

Abstract

Parallel algorithms of the hypercube allocation strategies are considered. Although the sequential algorithms of various hypercube allocation strategies are easier to implement, their worst case time complexities exponentially increase as the dimension of the hypercube increases. The authors show that the free processors can be utilized to perform the allocation jobs in parallel to improve the efficiency of the hypercube allocation algorithms. A modified parallel algorithm for the single Gray-Code (GC) strategy is proposed and is shown to be able to recognize more subcubes than the single GC strategy by using the binary reflected Gray code and inverse binary reflected Gray code, without increasing the execution time. Two algorithms for a complete subcube recognition system are also presented and shown to be more efficient and attractive than the sequential one currently used in the hypercube multiprocessor.

Original languageEnglish
Title of host publicationProceedings of 7th International Parallel Processing Symposium, IPPS 1993
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages105-112
Number of pages8
ISBN (Electronic)0818634421, 9780818634420
DOIs
Publication statusPublished - 1993 Jan 1
Event7th International Parallel Processing Symposium, IPPS 1993 - Newport, United States
Duration: 1993 Apr 131993 Apr 16

Publication series

NameProceedings of 7th International Parallel Processing Symposium, IPPS 1993

Conference

Conference7th International Parallel Processing Symposium, IPPS 1993
CountryUnited States
CityNewport
Period93-04-1393-04-16

Fingerprint

Parallel algorithms

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Hardware and Architecture
  • Software
  • Computational Theory and Mathematics
  • Computer Networks and Communications

Cite this

Chang, Y-K., & Bhuyan, L. N. (1993). Parallel algorithms for hypercube allocation. In Proceedings of 7th International Parallel Processing Symposium, IPPS 1993 (pp. 105-112). [262864] (Proceedings of 7th International Parallel Processing Symposium, IPPS 1993). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/IPPS.1993.262864
Chang, Yeim-Kuan ; Bhuyan, L. N. / Parallel algorithms for hypercube allocation. Proceedings of 7th International Parallel Processing Symposium, IPPS 1993. Institute of Electrical and Electronics Engineers Inc., 1993. pp. 105-112 (Proceedings of 7th International Parallel Processing Symposium, IPPS 1993).
@inproceedings{dcdb9e24c7e6444fad799349d2cf0700,
title = "Parallel algorithms for hypercube allocation",
abstract = "Parallel algorithms of the hypercube allocation strategies are considered. Although the sequential algorithms of various hypercube allocation strategies are easier to implement, their worst case time complexities exponentially increase as the dimension of the hypercube increases. The authors show that the free processors can be utilized to perform the allocation jobs in parallel to improve the efficiency of the hypercube allocation algorithms. A modified parallel algorithm for the single Gray-Code (GC) strategy is proposed and is shown to be able to recognize more subcubes than the single GC strategy by using the binary reflected Gray code and inverse binary reflected Gray code, without increasing the execution time. Two algorithms for a complete subcube recognition system are also presented and shown to be more efficient and attractive than the sequential one currently used in the hypercube multiprocessor.",
author = "Yeim-Kuan Chang and Bhuyan, {L. N.}",
year = "1993",
month = "1",
day = "1",
doi = "10.1109/IPPS.1993.262864",
language = "English",
series = "Proceedings of 7th International Parallel Processing Symposium, IPPS 1993",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "105--112",
booktitle = "Proceedings of 7th International Parallel Processing Symposium, IPPS 1993",
address = "United States",

}

Chang, Y-K & Bhuyan, LN 1993, Parallel algorithms for hypercube allocation. in Proceedings of 7th International Parallel Processing Symposium, IPPS 1993., 262864, Proceedings of 7th International Parallel Processing Symposium, IPPS 1993, Institute of Electrical and Electronics Engineers Inc., pp. 105-112, 7th International Parallel Processing Symposium, IPPS 1993, Newport, United States, 93-04-13. https://doi.org/10.1109/IPPS.1993.262864

Parallel algorithms for hypercube allocation. / Chang, Yeim-Kuan; Bhuyan, L. N.

Proceedings of 7th International Parallel Processing Symposium, IPPS 1993. Institute of Electrical and Electronics Engineers Inc., 1993. p. 105-112 262864 (Proceedings of 7th International Parallel Processing Symposium, IPPS 1993).

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

TY - GEN

T1 - Parallel algorithms for hypercube allocation

AU - Chang, Yeim-Kuan

AU - Bhuyan, L. N.

PY - 1993/1/1

Y1 - 1993/1/1

N2 - Parallel algorithms of the hypercube allocation strategies are considered. Although the sequential algorithms of various hypercube allocation strategies are easier to implement, their worst case time complexities exponentially increase as the dimension of the hypercube increases. The authors show that the free processors can be utilized to perform the allocation jobs in parallel to improve the efficiency of the hypercube allocation algorithms. A modified parallel algorithm for the single Gray-Code (GC) strategy is proposed and is shown to be able to recognize more subcubes than the single GC strategy by using the binary reflected Gray code and inverse binary reflected Gray code, without increasing the execution time. Two algorithms for a complete subcube recognition system are also presented and shown to be more efficient and attractive than the sequential one currently used in the hypercube multiprocessor.

AB - Parallel algorithms of the hypercube allocation strategies are considered. Although the sequential algorithms of various hypercube allocation strategies are easier to implement, their worst case time complexities exponentially increase as the dimension of the hypercube increases. The authors show that the free processors can be utilized to perform the allocation jobs in parallel to improve the efficiency of the hypercube allocation algorithms. A modified parallel algorithm for the single Gray-Code (GC) strategy is proposed and is shown to be able to recognize more subcubes than the single GC strategy by using the binary reflected Gray code and inverse binary reflected Gray code, without increasing the execution time. Two algorithms for a complete subcube recognition system are also presented and shown to be more efficient and attractive than the sequential one currently used in the hypercube multiprocessor.

UR - http://www.scopus.com/inward/record.url?scp=84938169375&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84938169375&partnerID=8YFLogxK

U2 - 10.1109/IPPS.1993.262864

DO - 10.1109/IPPS.1993.262864

M3 - Conference contribution

T3 - Proceedings of 7th International Parallel Processing Symposium, IPPS 1993

SP - 105

EP - 112

BT - Proceedings of 7th International Parallel Processing Symposium, IPPS 1993

PB - Institute of Electrical and Electronics Engineers Inc.

ER -

Chang Y-K, Bhuyan LN. Parallel algorithms for hypercube allocation. In Proceedings of 7th International Parallel Processing Symposium, IPPS 1993. Institute of Electrical and Electronics Engineers Inc. 1993. p. 105-112. 262864. (Proceedings of 7th International Parallel Processing Symposium, IPPS 1993). https://doi.org/10.1109/IPPS.1993.262864