Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/69825
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Type: | Journal article |
Title: | Embedding meshes and tori on double-loop networks of the same size |
Author: | Chen, Y. Shen, H. |
Citation: | IEEE Transactions on Computers, 2011; 60(8):1157-1168 |
Publisher: | IEEE Computer Soc |
Issue Date: | 2011 |
ISSN: | 0018-9340 1557-9956 |
Statement of Responsibility: | Yawen Chen and Hong Shen |
Abstract: | Double-loop networks are extensions of ring networks and are widely used in the design and implementation of local area networks and parallel processing architectures. However, embedding of other types of networks on double-loop networks has not been well studied due to the topological complexity of double-loop networks. The traditional L-shape, designed to compute the diameter of double-loop networks, is not effective to solve the embedding problem. We propose a novel tessellation approach to partition the geometric plane of double-loop networks into a set of parallelogram tiles, called P-shape. Based on the characteristics of P-shape, we design a simple embedding scheme, namely, P-shape embedding, that embeds meshes and tori on double-loop networks in a systematic way. Under P-shape embedding, we evaluate the embedding metrics of dilation, average dilation, and congestion, which depend heavily on the parameters of P-shape. A main merit of P-shape embedding is that a large fraction of embedded mesh/torus edges have edge dilation 1, resulting in a low average dilation. These are the first results, to our knowledge, for embedding meshes and tori on double-loop networks which is of great significance due to the popularity of these architectures. Our P-shape construction bridges between regular graphs and double-loop networks, and provides a powerful tool for studying double-loop networks. |
Keywords: | Double-loop networks mesh torus graph embedding dilation. |
Rights: | © 2011 IEEE |
DOI: | 10.1109/TC.2010.275 |
Grant ID: | http://purl.org/au-research/grants/arc/DP0985063 http://purl.org/au-research/grants/arc/DP0985063 |
Published version: | http://dx.doi.org/10.1109/tc.2010.275 |
Appears in Collections: | Aurora harvest Computer Science publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
RA_hdl_69825.pdf Restricted Access | Restricted Access | 1.05 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.