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
aolson@ece.utexas.edu -
bevans@ece.utexas.edu
Paper -
Poster
Process Networks Research
at UT Austin
Abstract
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.