Embedding cycles and meshes onto incomplete hypercubes

Jywe Fei Fang, Ju Yuan Hsiao, Chuan Yi Tang

Research output: Contribution to journalArticle

6 Citations (Scopus)

Abstract

An incomplete hypercube is a generalization of the hypercube in the sense that the number of nodes can be an arbitrary integer number. Moreover, we can enlarge its system size without reconfiguring the links. In this paper, we study the incomplete hypercube's ability to execute parallel algorithms using embedding technique. Since many algorithms have been proposed for linear arrays, cycles and meshes, the issues of embedding these interconnection networks are addressed. On the other hand, a multiprogramming system may only allocate part of the whole system for a task. Hence, we are motivated to study the problem of how to embed these interconnection networks of an arbitrary size into the incomplete hypercubes. For these embedding issues, we have proposed algorithms to enumerate these interconnection networks on the incomplete hypercubes optimally and definitely, except only to prove the existence of these optimal embeddings.

Original languageEnglish
Pages (from-to)1-19
Number of pages19
JournalInternational Journal of Computer Mathematics
Volume75
Issue number1
DOIs
Publication statusPublished - 2000 Jan 1

Fingerprint

Hypercube
Multiprogramming
Mesh
Interconnection Networks
Cycle
Parallel algorithms
Linear Array
Arbitrary
Parallel Algorithms
Integer
Vertex of a graph

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Computational Theory and Mathematics
  • Applied Mathematics

Cite this

@article{72f0fe25596a4353aeca194517da5d19,
title = "Embedding cycles and meshes onto incomplete hypercubes",
abstract = "An incomplete hypercube is a generalization of the hypercube in the sense that the number of nodes can be an arbitrary integer number. Moreover, we can enlarge its system size without reconfiguring the links. In this paper, we study the incomplete hypercube's ability to execute parallel algorithms using embedding technique. Since many algorithms have been proposed for linear arrays, cycles and meshes, the issues of embedding these interconnection networks are addressed. On the other hand, a multiprogramming system may only allocate part of the whole system for a task. Hence, we are motivated to study the problem of how to embed these interconnection networks of an arbitrary size into the incomplete hypercubes. For these embedding issues, we have proposed algorithms to enumerate these interconnection networks on the incomplete hypercubes optimally and definitely, except only to prove the existence of these optimal embeddings.",
author = "Fang, {Jywe Fei} and Hsiao, {Ju Yuan} and Tang, {Chuan Yi}",
year = "2000",
month = "1",
day = "1",
doi = "10.1080/00207160008804962",
language = "English",
volume = "75",
pages = "1--19",
journal = "International Journal of Computer Mathematics",
issn = "0020-7160",
publisher = "Taylor and Francis Ltd.",
number = "1",

}

Embedding cycles and meshes onto incomplete hypercubes. / Fang, Jywe Fei; Hsiao, Ju Yuan; Tang, Chuan Yi.

In: International Journal of Computer Mathematics, Vol. 75, No. 1, 01.01.2000, p. 1-19.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Embedding cycles and meshes onto incomplete hypercubes

AU - Fang, Jywe Fei

AU - Hsiao, Ju Yuan

AU - Tang, Chuan Yi

PY - 2000/1/1

Y1 - 2000/1/1

N2 - An incomplete hypercube is a generalization of the hypercube in the sense that the number of nodes can be an arbitrary integer number. Moreover, we can enlarge its system size without reconfiguring the links. In this paper, we study the incomplete hypercube's ability to execute parallel algorithms using embedding technique. Since many algorithms have been proposed for linear arrays, cycles and meshes, the issues of embedding these interconnection networks are addressed. On the other hand, a multiprogramming system may only allocate part of the whole system for a task. Hence, we are motivated to study the problem of how to embed these interconnection networks of an arbitrary size into the incomplete hypercubes. For these embedding issues, we have proposed algorithms to enumerate these interconnection networks on the incomplete hypercubes optimally and definitely, except only to prove the existence of these optimal embeddings.

AB - An incomplete hypercube is a generalization of the hypercube in the sense that the number of nodes can be an arbitrary integer number. Moreover, we can enlarge its system size without reconfiguring the links. In this paper, we study the incomplete hypercube's ability to execute parallel algorithms using embedding technique. Since many algorithms have been proposed for linear arrays, cycles and meshes, the issues of embedding these interconnection networks are addressed. On the other hand, a multiprogramming system may only allocate part of the whole system for a task. Hence, we are motivated to study the problem of how to embed these interconnection networks of an arbitrary size into the incomplete hypercubes. For these embedding issues, we have proposed algorithms to enumerate these interconnection networks on the incomplete hypercubes optimally and definitely, except only to prove the existence of these optimal embeddings.

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

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

U2 - 10.1080/00207160008804962

DO - 10.1080/00207160008804962

M3 - Article

AN - SCOPUS:0033646188

VL - 75

SP - 1

EP - 19

JO - International Journal of Computer Mathematics

JF - International Journal of Computer Mathematics

SN - 0020-7160

IS - 1

ER -