A fast and verified algorithm for proving store-and-forward networks deadlock-free

F. Verbeek, J. Schmaltz

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    5 Citations (Scopus)


    Deadlocks are an important issue in the design of interconnection networks. A successful approach is to restrict the routing function such that it satisfies a necessary and sufficient condition for deadlock-free routing. Typically, such a condition states that some (extended) dependency graph must be a cyclic. Defining and proving such a condition is complex. Proving that a routing function satisfies a condition can be complex as well. In this paper we present the first algorithm that automatically proves routing functions deadlock-free for store-and-forward networks. The time complexity of our algorithm is linear in the size of the resource dependency graph. The algorithm checks a variation of Duato's condition for adaptive routing. The condition and the algorithm have been formalized in the logic of the ACL2 interactive theorem prover. The correctness of our algorithm w.r.t. the condition is formally checked using ACL2.
    Original languageEnglish
    Title of host publicationProceedings of the 19th International Euromicro Conference on Parallel, Distributed and Network-based Processing (PDP 2011, Ayia Napa, Cyprus, February 9-11, 2011)
    EditorsY. Cotronis, M. Danelutto, G.A. Papadopoulos
    PublisherIEEE Computer Society
    ISBN (Print)978-0-7695-4328-4
    Publication statusPublished - 2011

    Cite this