Optimally Embedding 3-Ary n-Cubes into Grids

The 3-ary n-cube, denoted as Q_n³, 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³ into grids. We then propose a load balancing algorithm for embedding Q_n³ into a square grid with minimum dilation and congestion. Finally, we derive an O(N²) algorithm for embedding Q_n³ into a gird with balanced communication, where N is the number of nodes in Q_n³. Simulation experiments are performed to verify the total wirelength and evaluate the network cost of our proposed embedding algorithm.