On the complexity of buffer allocation in message passing systems

DOI10.1016/J.JPDC.2004.10.009zbMATH Open1075.68554arXivcs/0301035OpenAlexW2114767021MaRDI QIDQ557643FDOQ557643

Authors: Alex Brodsky, Jan Pedersen, A. S. Wagner 

Publication date: 30 June 2005

Published in: Journal of Parallel and Distributed Computing (Search for Journal in Brave)

Abstract: Message passing programs commonly use buffers to avoid unnecessary synchronizations and to improve performance by overlapping communication with computation. Unfortunately, using buffers makes the program no longer portable, potentially unable to complete on systems without a sufficient number of buffers. Effective buffer use entails that the minimum number needed for a safe execution be allocated. We explore a variety of problems related to buffer allocation for safe and efficient execution of message passing programs. We show that determining the minimum number of buffers or verifying a buffer assignment are intractable problems. However, we give a polynomial time algorithm to determine the minimum number of buffers needed to allow for asynchronous execution. We extend these results to several different buffering schemes, which in some cases make the problems tractable.

Full work available at URL: https://arxiv.org/abs/cs/0301035

Recommendations

• Approximating the buffer allocation problem using epochs
• Bounds on the Efficiency of Message-Passing Protocols for Parallel Computers
• Scheduling time-constrained communication in linear networks
• Can message buffers be axiomatized in linear temporal logic?
• On the completeness of verifying message passing programs under bounded asynchrony

zbMATH Keywords

Buffer allocationComplexityMessage passing systemsParallel and distributed programming

Mathematics Subject Classification ID

Distributed systems (68M14)

Cited In (6)

• Approximating the buffer allocation problem using epochs
• Buffered Resource Constraint: Algorithms and Complexity
• Model Checking Software
• Mathematical programming models for joint simulation-optimization applied to closed queueing networks
• Buffered Communication Analysis in Distributed Multiparty Sessions
• Resource allocation via message passing

Uses Software

• LAM-MPI

This page was built for publication: On the complexity of buffer allocation in message passing systems

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