Formal analysis of destination reachability under given restrictions for multi-path routing in Network on Chip

• Autorzy: Dziurzański P.

Warianty tytułu

PL

Analiza formalna osiągalności celu przy zadanych ograniczeniach routingu wielościeżkowego w sieciach wewnątrzukładowych

• Języki publikacji: EN

Abstrakty

EN

In this paper, a technique for selecting proper restrictions in multi-path routing guarantying deadlock-freedom dedicated to Network on Chip (NoC) is presented. The proposed algorithm is based on the model checking utilizing computation tree temporal logic. This approach is illustrated with an example of features extraction module for the Automatic Speech Recognition (ASR) system. It is shown that even for this simple, 7-core MPSoC, selecting a wrong restriction may result in obtaining an unroutable on-chip network.

PL

W niniejszym artykule została przedstawiona technika wyboru odpowiednich ograniczeń wielościeżkowego routingu w sieciach wewnątrzukładowych, gwarantujących brak występowania blokad. Proponowany algorytm wykorzystuje sprawdzanie modeli z logiką temporalną drzew obliczeń CTL. Podejście zilustrowano przykładem ekstrakcji cech dla automatycznego rozpoznawania mowy. Pokazano, iż nawet dla tego prostego 7-rdzenowego układu typu MPSoC, wybór nieprawidłowego ograniczenia może skutkować uzyskaniem nierutowalnej sieci.

Słowa kluczowe

EN

network on chip; NoC; temporal logic; computation tree; state reachability

PL

sieci wewnątrzukładowe; logika temporalna; drzewo obliczeń; osiągalność stanu

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Elektronika : konstrukcje, technologie, zastosowania
• Rocznik: 2012
• Tom: Vol. 53, nr 12
• Strony: 127--129
• Opis fizyczny: Bibliogr. 12 poz., wykr., rys.

Twórcy

autor

Dziurzański P.

• Zachodniopomorski Uniwersytet Technologiczny w Szczecinie, Wydział Informatyki

Bibliografia

• [1] Anusuya M., Katti S.: Front end analysis of speech recognition: a review. International Journal of Speech Technology, vol. 14, 2010, pp. 99-145.
• [2] Benini L., Micheli G. de: Networks on Chips: Technology and Tools, Morgan Kaufman, 2006.
• [3] Bjerregaard T., Mahadevan S.: A Survey of Research and Practices of Network-on-Chip. ACM Computing Surveys (CSUR), vol. 38, 2006, Article 1.
• [4] Cimatti A., et al.: NuSMV 2: An OpenSource Tool for Symbolic Model Checking. Proceeding of International Conference on Computer-Aided Verification (CAV 2002). Copenhagen, Denmark, July 27-31, 2002.
• [5] Chojnacki B., Maka T., Dziurzanski P.: Virtual path implementation of multi-stream routing in network. 11th International Conference on Parallel Computing Technologies (PaCT'11), LNCS vol. 6783, 2011, pp. 431-436.
• [6] Dziurzanski P., Maka T.: Stream Transfer Balancing Scheme Utilizing Multi-path Routing in Networks. Chip, 4th International Workshop ARC 2008, London, UK, 2008, pp. 294-299.
• [7] Dziurzanski P., Maka T.: Features extraction system for automatic speech recognition core mapping into an irregular Network on Chip. Elektronika, no. 9, 2012, pp. 154-156
• [8] Clarke E. M., Emerson E. A., Sistla A. P.: Automatic verification of finite-state concurrent systems using temporal logic specifications. ACM Transactions on Programming Languages and Systems (TOPLAS), vol. 8, no. 2, 1986, pp. 244-263.
• [9] Glass C. J., Ni L. M.: The turn model for adaptive routing. Proc. 19th International Symposium on Computer Architecture, 1992, pp. 278-287.
• [10] Murali S., Atienza D., Benini L., Micheli G. De: A Method for Routing Packets Across Multiple Paths in NoCs with In-Order Delivery and Fault-Tolerance Guarantees. VLSI Design, vol. 2007, Article ID 37627, 11 pages, 2007.
• [11] Rodrigo S., et al.: Cost-Efficient On-Chip Routing Implementations for CMP and MPSoC Systems. IEEE Trans, on Computer-Aided Design of Integrated Circuits and Systems, vol. 30, no. 4, 2011, pp. 534-547.
• [12] Stefan R., Goossens K.: ATOM slot allocation based on multi-path routing in NoCs. Microprocessors and Microsystems, vol. 35, 2011, pp. 130-138.