Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
EbDa: A New Theory on Design and Verification of Deadlock-free Interconnection Networks
KTH, School of Information and Communication Technology (ICT), Electronics, Electronic and embedded systems.
MDH.
2017 (English)In: In Proceedings of ISCA ’17, ACM Press, 2017, 1-13 p.Conference paper, Published paper (Refereed)
Abstract [en]

Freedom from deadlock is one of the most important issues whendesigning routing algorithms in on-chip/off-chip networks. Manyworks have been developed upon Dally’s theory proving that a networkis deadlock-free if there is no cyclic dependency on the channeldependency graph. However, finding such acyclic graph has beenvery challenging, which limits Dally’s theory to networks with a lownumber of channels. In this paper, we introduce three theorems thatdirectly lead to routing algorithms with an acyclic channel dependencygraph.We also propose the partitioning methodology, enablinga design to reach the maximum adaptiveness for the n-dimensionalmesh and k-ary n-cube topologies with any given number of channels.In addition, deadlock-free routing algorithms can be derivedranging from maximally fully adaptive routing down to deterministicrouting. The proposed theorems can drastically remove thedifficulties of designing deadlock-free routing algorithms.

Place, publisher, year, edition, pages
ACM Press, 2017. 1-13 p.
Keyword [en]
Cyclic Dependencies, Deadlock-free Routing Algorithms, Interconnection Networks
National Category
Computer Systems
Identifiers
URN: urn:nbn:se:kth:diva-206968DOI: 10.1145/3079856.3080253OAI: oai:DiVA.org:kth-206968DiVA: diva2:1094681
Conference
ISCA
Note

QC 20170515

Available from: 2017-05-10 Created: 2017-05-10 Last updated: 2017-05-15Bibliographically approved

Open Access in DiVA

EbDa-ISCA17(7383 kB)134 downloads
File information
File name FULLTEXT01.pdfFile size 7383 kBChecksum SHA-512
6294efe3d1030eac6257efb7aa819d10097aaabde57976dfe755c7431a19c88fcea8d6fe1cb18e208a264fb8ecc4928b98e073e525866c1ac1748770c7209783
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Search in DiVA

By author/editor
Ebrahimi, Masoumeh
By organisation
Electronic and embedded systems
Computer Systems

Search outside of DiVA

GoogleGoogle Scholar
Total: 134 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

Altmetric score

Total: 634 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf