liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
Deadlock Free Routing inMesh Networks on Chip with Regions
Linköping University, Department of Computer and Information Science. Linköping University, The Institute of Technology.
2009 (English)Licentiate thesis, monograph (Other academic)
Abstract [en]

There is a seemingly endless miniaturization of electronic components, which has enabled designers to build sophisticated computing structureson silicon chips. Consequently, electronic systems are continuously improving with new and more advanced functionalities. Design complexity ofthese Systems on Chip (SoC) is reduced by the use of pre-designed cores. However, several problems related to the interconnection of coresremain. Network on Chip (NoC) is a new SoC design paradigm, which targets the interconnect problems using classical network concepts. Still,SoC cores show large variance in size and functionality, whereas several NoC benefits relate to regularity and homogeneity.

This thesis studies some network aspects which are characteristic to NoC systems. One is the issue of area wastage in NoC due to cores of varioussizes. We elaborate on using oversized regions in regular mesh NoC and identify several new design possibilities. Adverse effects of regions oncommunication are outlined and evaluated by simulation.

Deadlock freedom is an important region issue, since it affects both the usability and performance of routing algorithms. The concept of faultyblocks, used in deadlock free fault-tolerant routing algorithms has similarities with rectangular regions. We have improved and adopted one suchalgorithm to provide deadlock free routing in NoC with regions. This work also offers a methodology for designing topology agnostic, deadlockfree, highly adaptive application specific routing algorithms. The methodology exploits information about communication among tasks of anapplication. This is used in the analysis of deadlock freedom, such that fewer deadlock preventing routing restrictions are required.

A comparative study of the two proposed routing algorithms shows that the application specific algorithm gives significantly higher performance.But, the fault-tolerant algorithm may be preferred for systems requiring support for general communication. Several extensions to our work areproposed, for example in areas such as core mapping and efficient routing algorithms. The region concept can be extended for supporting reuse ofa pre-designed NoC as a component in a larger hierarchical NoC.

Place, publisher, year, edition, pages
Linköping: Linköping University Electronic Press , 2009. , 127 p.
Linköping Studies in Science and Technology. Thesis, ISSN 0280-7971 ; 1410
Keyword [en]
Networks on Chip, Mesh Topology, Routing Algorithms, Wormhole Switching, Deadlock, Application Specific Routing
National Category
Engineering and Technology
URN: urn:nbn:se:liu:diva-20284Local ID: LiU-Tek-Lic-2009:18ISBN: 978-91-7393-559-3OAI: diva2:233717
2009-09-14, E1405, hus E, Campus Valla, Linköpings universitet, Linköping, 14:00 (English)
Available from: 2009-09-02 Created: 2009-09-02 Last updated: 2009-09-02Bibliographically approved

Open Access in DiVA

Deadlock Free Routing in Mesh Networks on Chip with Regions(1330 kB)1924 downloads
File information
File name FULLTEXT01.pdfFile size 1330 kBChecksum SHA-512
Type fulltextMimetype application/pdf
Cover(53 kB)26 downloads
File information
File name COVER01.pdfFile size 53 kBChecksum SHA-512
Type coverMimetype application/pdf

By organisation
Department of Computer and Information ScienceThe Institute of Technology
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
Total: 1924 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 299 hits
ReferencesLink to record
Permanent link

Direct link