Portal de Periódicos da CAPES

A progressive approach to handling message-dependent deadlock in parallel computer systems

2003; Institute of Electrical and Electronics Engineers; Volume: 14; Issue: 3 Linguagem: Inglês

10.1109/tpds.2003.1189584

2161-9883

Yong Ho Song, Timothy M. Pinkston,

Distributed systems and fault tolerance

Handling deadlocks is essential for providing reliable communication paths between processing nodes in parallel computer systems. The existence of multiple message types and associated inter-message dependencies may cause message-dependent deadlocks in networks that are designed to be free of routing deadlock. Most methods currently used for dealing with message-dependent deadlocks require more system resources than are necessary and/or do not use system resources efficiently. This may have an adverse effect on system performance if resources are scarce. In this paper, we characterize the frequency of message-dependent deadlocks in multiprocessor/multicomputer systems. We also propose a handling technique for message-dependent deadlocks based on progressive deadlock recovery and evaluate its performance with other approaches. Results show that message-dependent deadlocks occur very infrequently under typical circumstances thus, rendering approaches based on avoiding them overly restrictive in the common case. The proposed technique relaxes restrictions considerably, allowing the routing of packets and the handling of message-dependent deadlocks to be much more efficient-particularly when network resources are scarce.