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

F. Verbeek, J. Schmaltz

    Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

    5 Citaten (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.
    Originele taal-2Engels
    TitelProceedings of the 19th International Euromicro Conference on Parallel, Distributed and Network-based Processing (PDP 2011, Ayia Napa, Cyprus, February 9-11, 2011)
    RedacteurenY. Cotronis, M. Danelutto, G.A. Papadopoulos
    UitgeverijIEEE Computer Society
    ISBN van geprinte versie978-0-7695-4328-4
    StatusGepubliceerd - 2011

    Citeer dit