An efficient deadlock-free multicast routing algorithm for mesh-based networks-on-chip

Kuen Jong Lee, Chin Yao Chang, Hung Yang Yang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Citations (Scopus)

Abstract

Multicast communication has been commonly used in multiprocessor systems. Current multicast routing methods such as tree-based and path-based approaches may suffer from the problem of multicast deadlocks or long routing delay. In this work we propose a hybrid multicast routing algorithm that combines the advantages of both path-based and tree-based methods. The proposed algorithm together with a router design that requires no additional virtual channel can achieve deadlock-free multicast routing. Very high routing efficiency is achieved by the proposed algorithm due to an adaptive routing strategy according to the traffic load. Experimental results show that the saturation point (in terms of injection ratio) of our algorithm is significantly higher than those of the state-of-the-art tree-and path-based multicast routing algorithms, while at the saturation points of these two algorithms, our algorithm has a routing latency that is 21% and 43% smaller than those of the tree-and the path-based algorithms, respectively.

Original languageEnglish
Title of host publication2013 International Symposium on VLSI Design, Automation, and Test, VLSI-DAT 2013
DOIs
Publication statusPublished - 2013 Aug 15
Event2013 International Symposium on VLSI Design, Automation, and Test, VLSI-DAT 2013 - Hsinchu, Taiwan
Duration: 2013 Apr 222013 Apr 24

Publication series

Name2013 International Symposium on VLSI Design, Automation, and Test, VLSI-DAT 2013

Other

Other2013 International Symposium on VLSI Design, Automation, and Test, VLSI-DAT 2013
CountryTaiwan
CityHsinchu
Period13-04-2213-04-24

Fingerprint

Routing algorithms
Routers
Network-on-chip
Communication

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture
  • Electrical and Electronic Engineering

Cite this

Lee, K. J., Chang, C. Y., & Yang, H. Y. (2013). An efficient deadlock-free multicast routing algorithm for mesh-based networks-on-chip. In 2013 International Symposium on VLSI Design, Automation, and Test, VLSI-DAT 2013 [6533824] (2013 International Symposium on VLSI Design, Automation, and Test, VLSI-DAT 2013). https://doi.org/10.1109/VLDI-DAT.2013.6533824
Lee, Kuen Jong ; Chang, Chin Yao ; Yang, Hung Yang. / An efficient deadlock-free multicast routing algorithm for mesh-based networks-on-chip. 2013 International Symposium on VLSI Design, Automation, and Test, VLSI-DAT 2013. 2013. (2013 International Symposium on VLSI Design, Automation, and Test, VLSI-DAT 2013).
@inproceedings{7adcef0b716a4a16a4e0869d38284df0,
title = "An efficient deadlock-free multicast routing algorithm for mesh-based networks-on-chip",
abstract = "Multicast communication has been commonly used in multiprocessor systems. Current multicast routing methods such as tree-based and path-based approaches may suffer from the problem of multicast deadlocks or long routing delay. In this work we propose a hybrid multicast routing algorithm that combines the advantages of both path-based and tree-based methods. The proposed algorithm together with a router design that requires no additional virtual channel can achieve deadlock-free multicast routing. Very high routing efficiency is achieved by the proposed algorithm due to an adaptive routing strategy according to the traffic load. Experimental results show that the saturation point (in terms of injection ratio) of our algorithm is significantly higher than those of the state-of-the-art tree-and path-based multicast routing algorithms, while at the saturation points of these two algorithms, our algorithm has a routing latency that is 21{\%} and 43{\%} smaller than those of the tree-and the path-based algorithms, respectively.",
author = "Lee, {Kuen Jong} and Chang, {Chin Yao} and Yang, {Hung Yang}",
year = "2013",
month = "8",
day = "15",
doi = "10.1109/VLDI-DAT.2013.6533824",
language = "English",
isbn = "9781467344357",
series = "2013 International Symposium on VLSI Design, Automation, and Test, VLSI-DAT 2013",
booktitle = "2013 International Symposium on VLSI Design, Automation, and Test, VLSI-DAT 2013",

}

Lee, KJ, Chang, CY & Yang, HY 2013, An efficient deadlock-free multicast routing algorithm for mesh-based networks-on-chip. in 2013 International Symposium on VLSI Design, Automation, and Test, VLSI-DAT 2013., 6533824, 2013 International Symposium on VLSI Design, Automation, and Test, VLSI-DAT 2013, 2013 International Symposium on VLSI Design, Automation, and Test, VLSI-DAT 2013, Hsinchu, Taiwan, 13-04-22. https://doi.org/10.1109/VLDI-DAT.2013.6533824

An efficient deadlock-free multicast routing algorithm for mesh-based networks-on-chip. / Lee, Kuen Jong; Chang, Chin Yao; Yang, Hung Yang.

2013 International Symposium on VLSI Design, Automation, and Test, VLSI-DAT 2013. 2013. 6533824 (2013 International Symposium on VLSI Design, Automation, and Test, VLSI-DAT 2013).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - An efficient deadlock-free multicast routing algorithm for mesh-based networks-on-chip

AU - Lee, Kuen Jong

AU - Chang, Chin Yao

AU - Yang, Hung Yang

PY - 2013/8/15

Y1 - 2013/8/15

N2 - Multicast communication has been commonly used in multiprocessor systems. Current multicast routing methods such as tree-based and path-based approaches may suffer from the problem of multicast deadlocks or long routing delay. In this work we propose a hybrid multicast routing algorithm that combines the advantages of both path-based and tree-based methods. The proposed algorithm together with a router design that requires no additional virtual channel can achieve deadlock-free multicast routing. Very high routing efficiency is achieved by the proposed algorithm due to an adaptive routing strategy according to the traffic load. Experimental results show that the saturation point (in terms of injection ratio) of our algorithm is significantly higher than those of the state-of-the-art tree-and path-based multicast routing algorithms, while at the saturation points of these two algorithms, our algorithm has a routing latency that is 21% and 43% smaller than those of the tree-and the path-based algorithms, respectively.

AB - Multicast communication has been commonly used in multiprocessor systems. Current multicast routing methods such as tree-based and path-based approaches may suffer from the problem of multicast deadlocks or long routing delay. In this work we propose a hybrid multicast routing algorithm that combines the advantages of both path-based and tree-based methods. The proposed algorithm together with a router design that requires no additional virtual channel can achieve deadlock-free multicast routing. Very high routing efficiency is achieved by the proposed algorithm due to an adaptive routing strategy according to the traffic load. Experimental results show that the saturation point (in terms of injection ratio) of our algorithm is significantly higher than those of the state-of-the-art tree-and path-based multicast routing algorithms, while at the saturation points of these two algorithms, our algorithm has a routing latency that is 21% and 43% smaller than those of the tree-and the path-based algorithms, respectively.

UR - http://www.scopus.com/inward/record.url?scp=84881354242&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84881354242&partnerID=8YFLogxK

U2 - 10.1109/VLDI-DAT.2013.6533824

DO - 10.1109/VLDI-DAT.2013.6533824

M3 - Conference contribution

AN - SCOPUS:84881354242

SN - 9781467344357

T3 - 2013 International Symposium on VLSI Design, Automation, and Test, VLSI-DAT 2013

BT - 2013 International Symposium on VLSI Design, Automation, and Test, VLSI-DAT 2013

ER -

Lee KJ, Chang CY, Yang HY. An efficient deadlock-free multicast routing algorithm for mesh-based networks-on-chip. In 2013 International Symposium on VLSI Design, Automation, and Test, VLSI-DAT 2013. 2013. 6533824. (2013 International Symposium on VLSI Design, Automation, and Test, VLSI-DAT 2013). https://doi.org/10.1109/VLDI-DAT.2013.6533824