Deadlock avoidance for systolic communication

DOI10.1016/0885-064X(88)90023-4MaRDI QIDQ1104743zbMATH OpenFDO

Authors H. T. Kung

Publication date 1988

Published in Journal of Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0885-064X(88)90023-4

zbMATH Keywords

deadlock avoidanceparallel processing systemqueue bufferingsystolic communication model

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Theory of operating systems (68N25) Grammars and rewriting systems (68Q42)

Review text

Under the systolic communication model, each cell (or processor) in a parallel processing system can operate directly on data residing at the cell's input queues and move computed results directly to the cell's output queues. Incoming and outgoing data need not be stored in the cell's local memory, if not required by the computation. By avoiding these local memory accesses, systolic communication can achieve high efficiency when executing many systolic algorithms. Though efficient, systolic communication may lead to deadlocks at run time if data arriving at a cell's input queues are improperly ordered. This paper describes the nature of this deadlock problem, gives an abstract formulation of the problem, and provides a deadlock avoidance strategy.

Recommendations

• Deadlock-freeness of hexagonal systolic arrays
• Optimal centralized algorithms for store-and-forward deadlock avoidance
• Deadlock-free message routing in multicomputer networks
• scientific article; zbMATH DE number 3926230
• Prevention of deadlocks in parallel programs of multiprocessor machines

Cited in

(5)

• A deadlock-free communication kernel for loop architecture
• Dealing with final state sensitivity for synchronous communication
• scientific article; zbMATH DE number 3949689 (Why is no real title available?)
• scientific article; zbMATH DE number 7314999 (Why is no real title available?)
• Deadlock-freeness of hexagonal systolic arrays

This page was built for publication: Deadlock avoidance for systolic communication

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1104743)