Paper Details

On the Complexity of Buffer Allocation in Message Passing Systems

Authors: Brodsky, Alex, Pedersen, Jan Bækgaard, Wagner, Alan

Abstract:

In modern cluster systems message passing functionality is often off-loaded to the network interface card for efficiency reasons. However, this limits the amount of memory available for message buffers. Unfortunately, buffer insufficiency can cause an otherwise correct program to deadlock, or at least slow down. Hence, given a program trace from an execution in an unrestricted environment, determining the minimum number of buffers needed for a safe execution is an important problem. We present three related problems, all concerned with buffer allocation for safe and efficient execution. We prove intractability results for the first two problems and present a polynomial time algorithm for the third.

Proceedings:

Communicating Process Architectures 2002, James S. Pascoe, Roger J. Loader, Vaidy S. Sunderam, 2002, pp 79 - 96 published by IOS Press, Amsterdam

Files: PS, PDF

This record in other formats:

Web page: BibTEX, Refer
Plain text: BibTEX, Refer

If you have any comments on this database, including inaccuracies, requests to remove or add information, or suggestions for improvement, the WoTUG web team are happy to hear of them. We will do our best to resolve problems to everyone's satisfaction.

Copyright for the papers presented in this database normally resides with the authors; please contact them directly for more information. Addresses are normally presented in the full paper.