Paper Info
Title
High-Performance, Low-Complexity Deadlock Avoidance for Arbitrary Topologies/Routings.
Abstract
Recently, the use of graph-based network topologies has been proposed as an alternative to traditional networks such as tori or fat-trees due to their very good topological characteristics. However they pose practical implementation challenges such as the lack of deadlock avoidance strategies. Previous proposals either lack flexibility, underutilise network resources or are exceedingly complex. We propose--and prove formally--three generic, low-complexity deadlock avoidance mechanisms that only require local information. Our methods are topology- and routing-independent and their virtual channel count is bounded by the length of the longest path. We evaluate our algorithms through an extensive simulation study to measure the impact on the performance using both synthetic and realistic traffic. First we compare against a well-known HPC mechanism for dragonfly and achieve similar performance level. Then we moved to Graph-based networks and show that our mechanisms can greatly outperform traditional, spanning-tree based mechanisms, even if these use a much larger number of virtual channels. Overall, our proposal provides a simple, flexible and high performance deadlock-avoidance solution.
Year
DOI
Venue
2018
10.1145/3205289.3205307
ICS
Keywords
Field
DocType
Deadlock avoidance, Arbitrary network topologies/routing policies, Virtual channels, Regular random graphs
Graph,Resource (disambiguation),Computer science,Deadlock,Parallel computing,Communication channel,Network topology,Longest path problem,Virtual channel,Bounded function,Distributed computing
Conference
ISBN
Citations 
PageRank 
978-1-4503-5783-8
2
0.42
References 
Authors
18
2
Name
Order
Citations
PageRank
Jose A. Pascual1425.03
Javier Navaridas220123.58