Adaptive tree-based multicast routing in network on chip architecture

• Autorzy: Czarnecki Ł. , Dziużański P.

Warianty tytułu

PL

Adaptacyjny routing jeden-do-wielu oparty na konstruowaniu drzewa w sieciach wewnątrzukładowych

• Języki publikacji: EN

Abstrakty

EN

The majority of the contemporary implementations of multicast in on-chip networks rely on multiple unicast communication pattern. The drawbacks of such an approach are inefficient network resources utilization and information redundancy, which results with the performance degradation and high message latencies. In the paper, we propose an adaptive tree-based multicast routing algorithm for an interconnection networks. The presented algorithm is based on the network traffic analysis and adapts the routing decisions to the current network conditions. We receive message delay improvement by 85-200% incomparison to the unicast communication pattern.

PL

Większość współczesnych implementacji routingu jeden-do-wielu w sieciach wewnątrzukładowych opiera się o wielokrotne wysyłanie przez źródło tych samych pakietów do różnych węzłów. Wadą takiego podejścia jest nieefektywne wykorzystanie zasobów sieciowych i redundancja informacji, która przekłada się na obniżenie wydajności i opóźnienia przy przesyłania pakietów. W artykule zaproponowany został adaptacyjny algorytm typu multicast oparty na konstrukcji drzew rozpinających. Zaprezentowany algorytm dokonuje analizy ruchu sieciowego i adaptacyjnie podejmuje decyzje w zależności od aktualnego stanu sieci. Badania eksperymentalne wykazały zmniejszenie opóźnienia o 85. ..200% w porównaniu z wielokrotną transmisją typu unicast.

Słowa kluczowe

EN

network on chip; NoC; multicast routing; adaptive routing

PL

sieci wewnątrzukładowe; routing jeden do wielu; routing adaptacyjny

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Elektronika : konstrukcje, technologie, zastosowania
• Rocznik: 2010
• Tom: Vol. 51, nr 4
• Strony: 33--37
• Opis fizyczny: Bibliogr. 10 poz., wykr.

Twórcy

autor

Czarnecki Ł.

autor

Dziużański P.

• Zachodniopomorski Uniwersytet Technologiczny w Szczecinie, Wydział Informatyki

Bibliografia

• [1] Anjan K., Pinkston Т., Duato J., Generalized Theory for Deadlock-Free Adaptive Wormhole Routing and its Applicationto Disha Concurrent, Proceedings of the10th International Parallel Processing Symposium, 1996.
• [2] Anjan K., Pinkston T., Duato J., A General Theory for Deadlock-Free Adaptive Routing Using a Mixed Set of Resources, IEEE Transactions on Parallel and Distributed Systems, Vol. 12,2001.
• [3] Benini L., de Micheli G., Networks on Chips: Technology and Tools, Morgan Kaufman, 2006.
• [4] Dally W., Towles В., Principles and Practices of Interconnection Networks, Morgan Kaufmann, 2004.
• [5] Duato J., Yalamanehili S., Ni L., Interconnection Networks-an Engineering Approach, Morgan Kaufman, 2003.
• [6] Kumar D., Najjar W., Srimani P., A New Adaptive Hardware Tree-Based Multicast Routing in K-Ary N-Cubes, IEEE Transactions on Computers, Vol. 50, No. 7, 2001.
• [7] Kumar D., Najjar W., Srimani P., Performance Evaluation of a New Hardware Supported Multicast Scheme for K-ary N-cubes, Proceedings of the 15th International Symposium on Parallel and Distributed Processing, 2001.
• [8] Lin X., McKinlev P., Ni L., Performance evaluation of multicast wormhole routing in 2D-mesh multicomputers, Proceedings of the 1991 International Conference on Parallel Processing, vol. 1, 1991.
• [9] Malumbres M., Duato J., Torrellas J., An Efficient Implementation of Tree-Based Multicast Routing for Distributed Shared-Memory Multiprocessors, Proceedings of the the 8th IEEE Symposium on Parallel and Distributed Processing, 1996.
• [10] Xi L.: Should Scalable Parallel Computers Support Efficient Hardware Multicast. Proceedings of the International Conference on Parallel Processing, 1995.