A Hybrid Multicast Routing Approach with Enhanced Methods for Mesh-Based Networks-on-Chip

Chun Wei Wu, Kuen-Jong Lee, Alan P. Su

Research output: Contribution to journalArticle

2 Citations (Scopus)

Abstract

Multicast communication can greatly enhance the performance of Networks-on-Chip. Currently most multicast routing algorithms are either tree-based or path-based. The former has low latency but needs to solve multicast deadlocks through additional hardware resources. The latter can avoid deadlocks easily but may require long routing paths. In this paper we propose a hybrid multicast routing approach that combines the advantages of both path- A nd tree-based methods. The proposed approach ensures deadlock-free multicast routing without requiring additional virtual channels or large buffers to hold large packets. High routing performance is achieved using an adaptive routing strategy considering the traffic load in nearby routers. Two techniques, namely node balancing and path balancing, are further developed to enhance this hybrid routing algorithm. Extensive experiments with different buffer sizes, packet sizes and numbers of destinations per packet under random and Rent's rule traffic at various traffic injection rates have been conducted. The results show that the average latency of our approach is lower than previous multicast routing algorithms in most cases, and the saturation points of our approach are always at much higher injection rates.

Original languageEnglish
Article number8309347
Pages (from-to)1231-1245
Number of pages15
JournalIEEE Transactions on Computers
Volume67
Issue number9
DOIs
Publication statusPublished - 2018 Sep 1

Fingerprint

Multicast Routing
Routing algorithms
Deadlock
Routing Algorithm
Mesh
Path
Traffic
Multicast
Balancing
Latency
Buffer
Injection
Routing
Virtual Channel
Adaptive Routing
Routers
Hybrid Algorithm
Router
Hardware
Saturation

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics

Cite this

@article{e6c1bf46b7cc49b88a105265a3a10f1e,
title = "A Hybrid Multicast Routing Approach with Enhanced Methods for Mesh-Based Networks-on-Chip",
abstract = "Multicast communication can greatly enhance the performance of Networks-on-Chip. Currently most multicast routing algorithms are either tree-based or path-based. The former has low latency but needs to solve multicast deadlocks through additional hardware resources. The latter can avoid deadlocks easily but may require long routing paths. In this paper we propose a hybrid multicast routing approach that combines the advantages of both path- A nd tree-based methods. The proposed approach ensures deadlock-free multicast routing without requiring additional virtual channels or large buffers to hold large packets. High routing performance is achieved using an adaptive routing strategy considering the traffic load in nearby routers. Two techniques, namely node balancing and path balancing, are further developed to enhance this hybrid routing algorithm. Extensive experiments with different buffer sizes, packet sizes and numbers of destinations per packet under random and Rent's rule traffic at various traffic injection rates have been conducted. The results show that the average latency of our approach is lower than previous multicast routing algorithms in most cases, and the saturation points of our approach are always at much higher injection rates.",
author = "Wu, {Chun Wei} and Kuen-Jong Lee and Su, {Alan P.}",
year = "2018",
month = "9",
day = "1",
doi = "10.1109/TC.2018.2813394",
language = "English",
volume = "67",
pages = "1231--1245",
journal = "IEEE Transactions on Computers",
issn = "0018-9340",
publisher = "IEEE Computer Society",
number = "9",

}

A Hybrid Multicast Routing Approach with Enhanced Methods for Mesh-Based Networks-on-Chip. / Wu, Chun Wei; Lee, Kuen-Jong; Su, Alan P.

In: IEEE Transactions on Computers, Vol. 67, No. 9, 8309347, 01.09.2018, p. 1231-1245.

Research output: Contribution to journalArticle

TY - JOUR

T1 - A Hybrid Multicast Routing Approach with Enhanced Methods for Mesh-Based Networks-on-Chip

AU - Wu, Chun Wei

AU - Lee, Kuen-Jong

AU - Su, Alan P.

PY - 2018/9/1

Y1 - 2018/9/1

N2 - Multicast communication can greatly enhance the performance of Networks-on-Chip. Currently most multicast routing algorithms are either tree-based or path-based. The former has low latency but needs to solve multicast deadlocks through additional hardware resources. The latter can avoid deadlocks easily but may require long routing paths. In this paper we propose a hybrid multicast routing approach that combines the advantages of both path- A nd tree-based methods. The proposed approach ensures deadlock-free multicast routing without requiring additional virtual channels or large buffers to hold large packets. High routing performance is achieved using an adaptive routing strategy considering the traffic load in nearby routers. Two techniques, namely node balancing and path balancing, are further developed to enhance this hybrid routing algorithm. Extensive experiments with different buffer sizes, packet sizes and numbers of destinations per packet under random and Rent's rule traffic at various traffic injection rates have been conducted. The results show that the average latency of our approach is lower than previous multicast routing algorithms in most cases, and the saturation points of our approach are always at much higher injection rates.

AB - Multicast communication can greatly enhance the performance of Networks-on-Chip. Currently most multicast routing algorithms are either tree-based or path-based. The former has low latency but needs to solve multicast deadlocks through additional hardware resources. The latter can avoid deadlocks easily but may require long routing paths. In this paper we propose a hybrid multicast routing approach that combines the advantages of both path- A nd tree-based methods. The proposed approach ensures deadlock-free multicast routing without requiring additional virtual channels or large buffers to hold large packets. High routing performance is achieved using an adaptive routing strategy considering the traffic load in nearby routers. Two techniques, namely node balancing and path balancing, are further developed to enhance this hybrid routing algorithm. Extensive experiments with different buffer sizes, packet sizes and numbers of destinations per packet under random and Rent's rule traffic at various traffic injection rates have been conducted. The results show that the average latency of our approach is lower than previous multicast routing algorithms in most cases, and the saturation points of our approach are always at much higher injection rates.

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

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

U2 - 10.1109/TC.2018.2813394

DO - 10.1109/TC.2018.2813394

M3 - Article

AN - SCOPUS:85043400562

VL - 67

SP - 1231

EP - 1245

JO - IEEE Transactions on Computers

JF - IEEE Transactions on Computers

SN - 0018-9340

IS - 9

M1 - 8309347

ER -