Application-aware deadlock-free oblivious routing

Michel Kinsy, Myong Hyon Cho, Tina Wen, Edward Suh, Marten Van Dijk, Srinivas Devadas

Research output: Chapter in Book/Report/Conference proceedingConference contribution

57 Scopus citations


Conventional oblivious routing algorithms are either not application-aware or assume that each flow has its own private channel to ensure deadlock avoidance. We present a framework for application-aware routing that assures deadlock-freedom under one or more channels by forcing routes to conform to an acyclic channel dependence graph. Arbitrary minimal routes can be made deadlock-free through appropriate static channel allocation when two or more channels are available. Given bandwidth estimates for flows, we present a mixed integer-linear programming (MILP) approach and a heuristic approach for producing deadlock-free routes that minimize maximum channel load. The heuristic algorithm is calibrated using the MILP algorithm and evaluated on a number of benchmarks through detailed network simulation. Our framework can be used to produce application-aware routes that target the minimization of latency, number of flows through a link, bandwidth, or any combination thereof.

Original languageEnglish (US)
Title of host publicationISCA 2009 - 36th Annual International Symposium on Computer Architecture, Conference Proceedings
Number of pages12
StatePublished - 2009
Externally publishedYes
EventISCA 2009 - 36th Annual International Symposium on Computer Architecture - Austin, TX, United States
Duration: Jun 20 2009Jun 24 2009

Publication series

NameProceedings - International Symposium on Computer Architecture
ISSN (Print)1063-6897


OtherISCA 2009 - 36th Annual International Symposium on Computer Architecture
Country/TerritoryUnited States
CityAustin, TX


  • Oblivious routing
  • On-chip interconnection networks
  • Systems-on-chip

ASJC Scopus subject areas

  • Hardware and Architecture


Dive into the research topics of 'Application-aware deadlock-free oblivious routing'. Together they form a unique fingerprint.

Cite this