Optimally Embedding 3-Ary n-Cubes into Grids
WB Fan, JX Fan, CK Lin, Y Wang, YJ Han… - Journal of Computer …, 2019 - Springer
WB Fan, JX Fan, CK Lin, Y Wang, YJ Han, RC Wang
Journal of Computer Science and Technology, 2019•SpringerAbstract The 3-ary n-cube, denoted as Q n 3 Q _n^ 3, is an important interconnection
network topology proposed for parallel computers, owing to its many desirable properties
such as regular and symmetrical structure, and strong scalability, among others. In this
paper, we first obtain an exact formula for the minimum wirelength to embed Q n 3 Q _n^ 3
into grids. We then propose a load balancing algorithm for embedding Q n 3 Q _n^ 3 into a
square grid with minimum dilation and congestion. Finally, we derive an O (N 2) algorithm …
network topology proposed for parallel computers, owing to its many desirable properties
such as regular and symmetrical structure, and strong scalability, among others. In this
paper, we first obtain an exact formula for the minimum wirelength to embed Q n 3 Q _n^ 3
into grids. We then propose a load balancing algorithm for embedding Q n 3 Q _n^ 3 into a
square grid with minimum dilation and congestion. Finally, we derive an O (N 2) algorithm …
Abstract
The 3-ary n-cube, denoted as , is an important interconnection network topology proposed for parallel computers, owing to its many desirable properties such as regular and symmetrical structure, and strong scalability, among others. In this paper, we first obtain an exact formula for the minimum wirelength to embed into grids. We then propose a load balancing algorithm for embedding into a square grid with minimum dilation and congestion. Finally, we derive an O(N2) algorithm for embedding into a gird with balanced communication, where N is the number of nodes in . Simulation experiments are performed to verify the total wirelength and evaluate the network cost of our proposed embedding algorithm.
Springer