Multi-Stream Routing in Network on Chip for Data-dominated Algorithms

• Autorzy: Chojnacki B. , Dziurzański P. , Mąka T.

Warianty tytułu

PL

Routing wielościeżkowy w sieciach wewnątrzukładowych dla algorytmów

• Języki publikacji: EN

Abstrakty

EN

In this paper a multi-path routing algorithm dedicated to Network on Chip (NoC) together with its implementation is presented. The proposed algorithm is based on the Ford-Fulkerson method and is aimed at data-dominated multimedia applications realized in Multi Processor Systems on Chip. The efficiency of the proposed technique is compared with the state-of-the-art NoC routing. Our implementation utilizing virtual channels allows us to obtain promising results in some popular multimedia codecs.

PL

W artykule został przedstawiony wielościeżkowy routing przeznaczony do sieci wewnątrzukładowych (ang. Network on Chip, NoC) wraz z jego implementacją. Proponowany algorytm został oparty na metodzie Forda-Fulkersona i jest przeznaczony do multimedialnych aplikacji strumieniowych zdominowanych przez dane, realizowanych w wieloprocesorowych systemach jednoukładowych (ang. Multi Processor Systems on Chip, MPSoC). Efektywność prezentowanej techniki została porównana z najpopularniejszym algorytmem routingu używanym w NoC - XY. Badania eksperymentalne wykazały, że w niektórych przypadkach uzyskano znaczącą poprawę czasu transmisji. Przedstawiona implementacja algorytmu wykorzystuje kanały wirtualne i, chociaż wymaga wykonania dodatkowych obliczeń, umożliwiła otrzymanie obiecujących wyników dla niektórych popularnych kodeków Multimedialnych, natomiast dla innych uzyskano nieco gorsze wyniki. Stąd trudno jednoznacznie wnioskować o wyższości wielościeżkowych mechanizmów routingu nad tradycyjnymi jednościeżkowymi. Routing typu tapeworm należy zatem postrzegać jako alternatywną propozycję routingu przeznaczoną dla strumieniowych algorytmów realizowanych w NoC, która poszerza przestrzeń poszukiwań korzystnej realizacji układowej. W niektórych przypadkach jej stosowanie znacznie polepsza wyniki, czasami zaś lepiej zastosować tradycyjne podejście. W chwili obecnej autorzy nie są w stanie zidentyfikować cech wspólnych algorytmów, które są korzystnie realizowalne z wykorzystaniem proponowanej techniki.

Słowa kluczowe

EN

Network on Chip (NoC); multipath routing; Ford-Fulkerson method

PL

sieci wewnątrzukładowe; trasowanie wielościeżkowe; metoda Forda-Fulkersona

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2011
• Tom: R. 57, nr 8
• Strony: 920--922
• Opis fizyczny: Bibliogr. 12 poz., rys., tab., wykr.

Twórcy

autor

Chojnacki B.

autor

Dziurzański P.

autor

Mąka T.

• Zachodniopomorski UniwersytetTtechnologiczny w Szczecinie, ul. Żołnierska 49, 71-210 Szczecin,

Bibliografia

• [1] Andersen S. V. et al.: iLBC - a linear predictive coder, IEEE Workshop on Speech Coding, 2002.
• [2] Bjerregaard T., Mahadevan S.: A Survey of Research and Practices of Network-on-Chip, ACM Computing Surveys (CSUR), vol. 38, 2006, Article 1.
• [3] Brandenburg K.: MP3 and AAC Explained, 17th International Conference: High-Quality Audio Coding, 1999.
• [4] Duato J., Yalamanchili S., Ni L.: Interconnection Networks. An Engineering Approach, Morgan Kaufmann Publishers, 2003.
• [5] Dziurzanski P., Maka T.: Stream-based Multi-path Routing Scheme in On-chip Networks, 16th EUROMICRO Conference on Parallel, Distributed and Network-based Processing PDP, 13-15 February, Toulouse, France, ss. 15-16, 2008.
• [6] Dziurzanski P., Maka T.: Stream Transfer Balancing Scheme Utilizing Multi-Path Routing in Networks on Chip, 4th International Workshop ARC 2008, 26-28 March, London, UK, ss. 294-299, 2008.
• [7] Ford L. R., Jr. and Fulkerson D. R.: Flows in Networks. Princeton University Press, Princeton, NJ, 1962.
• [8] Greenberg H. J.: Ford-Fulkerson Max Flow Labeling Algorithm, University of Colorado, at Denver, 1998.
• [9] Kavaldjiev N. et al.: Routing of guaranteed throughput traffic in a network-on-chip, Technical Report TR CTIT-05-42 Centre for Telematics and Information Technology, University of Twente, Enschede, 2005.
• [10] Li M., Zeng Q. A., Jone W. B.: DyXY: a proximity congestion-aware deadlock-free dynamic routing method for network on chip. 43rd ACM IEEE Design Automation Conference (DAC), 2006, pp. 849-852.
• [11] Richardson I. E. G.: H.264 and MPEG-4 Video Compression: Video Coding for Next Generation Multimedia, Wiley, 2003.
• [12] Smit G. J. M., et al.: Efficient Architectures for Streaming DSP Applications, Dynamically Reconfigurable Architectures, Internationales Begegnungs- und Forschungszentrum fuer Informatik (IBFI), Schloss Dagstuhl, Germany, 2006.