Application-Aware Deadlock-Free Oblivious Routing
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...
| Main Authors: | , , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery
2010
|
| Online Access: | http://hdl.handle.net/1721.1/51809 https://orcid.org/0000-0001-8253-7714 https://orcid.org/0000-0003-4301-1159 https://orcid.org/0000-0002-1224-0314 |
| _version_ | 1811083070005051392 |
|---|---|
| author | Kinsy, Michel A. Cho, Myong Hyon Wen, Tina Suh, Edward Van Dijk, Marten Devadas, Srinivas |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Kinsy, Michel A. Cho, Myong Hyon Wen, Tina Suh, Edward Van Dijk, Marten Devadas, Srinivas |
| author_sort | Kinsy, Michel A. |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T12:19:54Z |
| format | Article |
| id | mit-1721.1/51809 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T12:19:54Z |
| publishDate | 2010 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | mit-1721.1/518092022-10-01T08:59:16Z Application-Aware Deadlock-Free Oblivious Routing Kinsy, Michel A. Cho, Myong Hyon Wen, Tina Suh, Edward Van Dijk, Marten Devadas, Srinivas Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Devadas, Srinivas Kinsy, Michel A. Cho, Myong Hyon Wen, Tina Van Dijk, Marten Devadas, Srinivas 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. 2010-02-24T16:28:07Z 2010-02-24T16:28:07Z 2009 2009-06 Article http://purl.org/eprint/type/SubmittedJournalArticle 0163-5964 http://hdl.handle.net/1721.1/51809 Kinsy, Michel A. et al. “Application-aware deadlock-free oblivious routing.” SIGARCH Comput. Archit. News 37.3 (2009): 208-219. https://orcid.org/0000-0001-8253-7714 https://orcid.org/0000-0003-4301-1159 https://orcid.org/0000-0002-1224-0314 en_US http://doi.acm.org/10.1145/1555815.1555782 Computer Architecture News Attribution-Noncommercial-Share Alike 3.0 Unported http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Association for Computing Machinery author/dept web page |
| spellingShingle | Kinsy, Michel A. Cho, Myong Hyon Wen, Tina Suh, Edward Van Dijk, Marten Devadas, Srinivas Application-Aware Deadlock-Free Oblivious Routing |
| title | Application-Aware Deadlock-Free Oblivious Routing |
| title_full | Application-Aware Deadlock-Free Oblivious Routing |
| title_fullStr | Application-Aware Deadlock-Free Oblivious Routing |
| title_full_unstemmed | Application-Aware Deadlock-Free Oblivious Routing |
| title_short | Application-Aware Deadlock-Free Oblivious Routing |
| title_sort | application aware deadlock free oblivious routing |
| url | http://hdl.handle.net/1721.1/51809 https://orcid.org/0000-0001-8253-7714 https://orcid.org/0000-0003-4301-1159 https://orcid.org/0000-0002-1224-0314 |
| work_keys_str_mv | AT kinsymichela applicationawaredeadlockfreeobliviousrouting AT chomyonghyon applicationawaredeadlockfreeobliviousrouting AT wentina applicationawaredeadlockfreeobliviousrouting AT suhedward applicationawaredeadlockfreeobliviousrouting AT vandijkmarten applicationawaredeadlockfreeobliviousrouting AT devadassrinivas applicationawaredeadlockfreeobliviousrouting |