We use cookies to improve your experience with our site.
Wei-Bei Fan, Jian-Xi Fan, Cheng-Kuan Lin, Yan Wang, Yue-Juan Han, Ru-Chuan Wang. Optimally Embedding 3-Ary n-Cubes into Grids[J]. Journal of Computer Science and Technology, 2019, 34(2): 372-387. DOI: 10.1007/s11390-019-1893-0
Citation: Wei-Bei Fan, Jian-Xi Fan, Cheng-Kuan Lin, Yan Wang, Yue-Juan Han, Ru-Chuan Wang. Optimally Embedding 3-Ary n-Cubes into Grids[J]. Journal of Computer Science and Technology, 2019, 34(2): 372-387. DOI: 10.1007/s11390-019-1893-0

Optimally Embedding 3-Ary n-Cubes into Grids

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

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return