Linear optimization of multi-path routing in network on chips

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

Warianty tytułu

PL

Liniowa optymalizacja wielościeżkowego routingu w sieciach wewnątrzukładowych

• Języki publikacji: EN

Abstrakty

EN

In this paper, a technique for determining required link band-width of a multi-path routing algorithm dedicated to Network on Chip (NoC) is presented. The proposed algorithm is based on the linear programming and allows us to avoid deadlocks and contentions in case of Tapeworm routing used for data-dominated streaming multimedia applications realized in Multi Processor Systems on Chip. The proposed approach is illustrated with an example of features extraction module for the Automatic Speech Recognition (ASR) system.

PL

W artykule opisano technikę określania wymaganej przepustowości łączy sieci wewnątrzukładowej z routingiem wielościeżkowym. Zaproponowany algorytm bazuje na programowaniu liniowym i umożliwia unikanie blokad w routingu typu Tapeworm, wykorzystywanego dla multimedialnych aplikacji zdominowanych przez dane realizowanych w układach typu MPSoC. Autorski algorytm routingu Tapeworm dla niektórych aplikacji multimedialnych okazuje się być wydajniejszy od XY, powszechnie używanego algorytmu routingu w NoC. Zaproponowane podejście zostało zilustrowane przykładem modułu ekstrakcji cech w systemie automatycznego rozpoznawania mowy. Klasyczny diagram takiego modułu został przedstawiony na rys. 1. W celu określenia marszrut pomiędzy rdzeniami realizującymi funkcjonalności poszczególnych bloków tego modułu została zaadaptowana technika znana z tradycyjnych sieci komputerowych, opisana m.in. w [8]. W artykule zaproponowano sposób wyboru ścieżek między rdzeniem źródłowym i docelowym, opisano sposób określania ograniczeń, a także zaproponowano funkcję celu uwzględniającą długość ścieżki. Do wyszukiwania optymalnej przepustowości łączy wykorzystano algorytm przypominający wyszukiwanie binarne. Badania eksperymentalne, w ramach których zaimplementowano opisany moduł w języku SystemC, a także wykorzystano komercyjne narzędzie do rozwiązywania problemu programowania liniowego, potwierdzają skuteczność i efektywność opisywanego podejścia.

Słowa kluczowe

EN

Network on Chip (NoC); multipath routing; features extraction

PL

sieci wewnątrzukładowe; routing wielościeżkowy; ekstrakcja cech

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2012
• Tom: R. 58, nr 7
• Strony: 659--661
• Opis fizyczny: Bibliogr. 8 poz., rys.

Twórcy

autor

Dziurzański P.

autor

Mąka T.

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

Bibliografia

• [1] Anusuya M., Katti S.: Front end analysis of speech recognition: a review, International Journal of Speech Technology, vol. 14, pp. 99-145, December 2010.
• [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] Chojnacki B., Maka T., Dziurzanski P.: Virtual path implementation of multi-stream routing in network on chip, 11th international conference on Parallel computing technologies (PaCT’11), LNCS vol. 6783, pp. 431-436, 2011.
• [4] 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.
• [5] Gold B., Morgan N.: Speech and Audio Signal Processing: Processing and Perception of Speech and Music, John Wiley & Sons, Inc., 2000.
• [6] Jurafsky D. and Martin J. H.: Speech and Language Processing: An Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition, Pearson Education Ltd., London, 2009.
• [7] 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.
• [8] Pioro M., Medhi D.: Routing, Flow, and Capacity Design in Communication and Computer Networks, Morgan Kaufmann, 2004.