Path-Based Partitioning Methods for 3D Networks-on-Chip with Minimal Adaptive Routing

Combining the benefits of 3D ICs and Networks-on-Chip (NoCs) schemes provides a significant performance gain in Chip Multiprocessors (CMPs) architectures. As multicast communication is commonly used in cache coherence protocols for CMPs and in various parallel applications, the performance of these...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on computers 2014-03, Vol.63 (3), p.718-733
Main Authors: Ebrahimi, Masoumeh, Daneshtalab, Masoud, Liljeberg, Pasi, Plosila, Juha, Flich, Jose, Tenhunen, Hannu
Format: Article
Language:English
Subjects:
3D Networks-on-Chip
adaptive routing algorithm
Algorithm design and analysis
Algorithms
analytical models
Multicast
Multicast communication
Networks
Partitioning
Partitioning algorithms
partitioning methods
Protocols
Routing
Switching theory
System recovery
Three dimensional
Traffic engineering
Traffic flow
Unicast
unicast and multicast communication
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Combining the benefits of 3D ICs and Networks-on-Chip (NoCs) schemes provides a significant performance gain in Chip Multiprocessors (CMPs) architectures. As multicast communication is commonly used in cache coherence protocols for CMPs and in various parallel applications, the performance of these systems can be significantly improved if multicast operations are supported at the hardware level. In this paper, we present several partitioning methods for the path-based multicast approach in 3D mesh-based NoCs, each with different levels of efficiency. In addition, we develop novel analytical models for unicast and multicast traffic to explore the efficiency of each approach. In order to distribute the unicast and multicast traffic more efficiently over the network, we propose the Minimal and Adaptive Routing (MAR) algorithm for the presented partitioning methods. The analytical and experimental results show that an advantageous method named Recursive Partitioning (RP) outperforms the other approaches. RP recursively partitions the network until all partitions contain a comparable number of switches and thus the multicast traffic is equally distributed among several subsets and the network latency is considerably decreased. The simulation results reveal that the RP method can achieve performance improvement across all workloads while performance can be further improved by utilizing the MAR algorithm. Nineteen percent average and 42 percent maximum latency reduction are obtained on SPLASH-2 and PARSEC benchmarks running on a 64-core CMP.
ISSN:0018-9340
1557-9956
1557-9956
DOI:10.1109/TC.2012.255