Proc. IEEE Int. Conf. on Acoustics, Speech, and Signal Proc., Mar. 19-23, 2005, vol. 5, pp. 73-76, Philadelphia, PA USA.

Deadlock Detection for Distributed Process Networks

Alex G. Olson and Brian L. Evans

Embedded Signal Processing Laboratory, Wireless Networking and Communications Group, The University of Texas at Austin, Austin, TX 78712 USA -

Paper - Poster

Process Networks Research at UT Austin


The Process Network (PN) model, which consists of concurrent processes communicating over first-in first out unidirectional queues, is useful for modeling and exploiting functional parallelism in streaming data applications. The PN model maps easily onto multi-processor and/or multi-threaded targets. Since the PN model is Turing complete, memory requirements cannot be predicted statically. In general, any bounded memory scheduling algorithm for this model requires run-time deadlock detection. The few PN implementations that perform deadlock detection detect only global deadlocks. Not all local deadlocks, however, will cause a PN system to reach global deadlock. In this paper, we present the first local deadlock detection algorithm for PN models. The proposed algorithm is based on the Mitchell and Merritt algorithm and is suitable for both parallel and distributed PN implementations.

COPYRIGHT NOTICE: All the documents on this server have been submitted by their authors to scholarly journals or conferences as indicated, for the purpose of non-commercial dissemination of scientific work. The manuscripts are put on-line to facilitate this purpose. These manuscripts are copyrighted by the authors or the journals in which they were published. You may copy a manuscript for scholarly, non-commercial purposes, such as research or instruction, provided that you agree to respect these copyrights.

Last Updated 11/03/05.