A Dilation-Improved Embedding of Pyramids into 3-Dimensional Meshes


The KIPS Transactions:PartA, Vol. 10, No. 6, pp. 627-634, Dec. 2003
10.3745/KIPSTA.2003.10.6.627,   PDF Download:

Abstract

In this paper, we consider a graph-theoretic problem, the so-called “graph embedding problem” that maps the vertices and edges of the given guest graph model into the corresponding vertices and paths of the host graph under the condition of maintaining better performance parameters such as dilation, congestion, and expansion. We firstly propose a new mapping function which can embed the pyramid model with height N into the 3-dimensional mesh massively parallel processor system with the height (4(N 1)/3 2)/3 and the regular 2-dimensional mesh of one side 2(2N-1)/3, and analyze the performance of the embedding in terms of the dilation parameter that reflects the number of communication steps between two adjacent vertices under the embedding. We prove that the dilation of the embedding is (2*4(N-2)/3 4)/3. This is superior to the previous result of 4(N-2)/3 under the same condition.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
J. J. Hwan, "A Dilation-Improved Embedding of Pyramids into 3-Dimensional Meshes," The KIPS Transactions:PartA, vol. 10, no. 6, pp. 627-634, 2003. DOI: 10.3745/KIPSTA.2003.10.6.627.

[ACM Style]
Jang Jeong Hwan. 2003. A Dilation-Improved Embedding of Pyramids into 3-Dimensional Meshes. The KIPS Transactions:PartA, 10, 6, (2003), 627-634. DOI: 10.3745/KIPSTA.2003.10.6.627.