A decision procedure for deadlock-free routing in wormhole networks

F. Verbeek, J. Schmaltz

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

10 Citaten (Scopus)
254 Downloads (Pure)

Samenvatting

Deadlock freedom is a key challenge in the design of communication networks. Wormhole switching is a popular switching technique, which is also prone to deadlocks. Deadlock analysis of routing functions is a manual and complex task. We propose an algorithm that automatically proves routing functions deadlock-free or outputs a minimal counter-example explaining the source of the deadlock. Our algorithm is the first to automatically check a necessary and sufficient condition for deadlock-free routing. We illustrate its efficiency in a complex adaptive routing function for torus topologies. Results are encouraging. Deciding deadlock freedom is co-NP-Complete for wormhole networks. Nevertheless, our tool proves a 13 × 13 torus deadlock-free within seconds. Finding minimal deadlocks is more difficult. Our tool needs four minutes to find a minimal deadlock in a 11 × 11 torus while it needs nine hours for a 12 × 12 network.
Originele taal-2Engels
Pagina's (van-tot)1935-1944
TijdschriftIEEE Transactions on Parallel and Distributed Systems
Volume25
Nummer van het tijdschrift8
DOI's
StatusGepubliceerd - 2014

Vingerafdruk Duik in de onderzoeksthema's van 'A decision procedure for deadlock-free routing in wormhole networks'. Samen vormen ze een unieke vingerafdruk.

Citeer dit