J.B. Pedersen (USA) and A. Brodsky (Canada)
Resource Allocation, Parallel Program ming, Message Passing Systems
: The correctness of applications that perform asynchronous message passing typically relies on the un derlying hardware having a sufficient amount of memory (message buffers) to hold all undelivered messages—such applications may deadlock when executed on a system with an insufficient number of message buffers. Thus, deter mining the minimum number of buffers that an application needs to prevent deadlock is an important task when writ ing or porting parallel applications. Unfortunately, both this problem (called the Buffer Allocation Problem) and the simpler problem of determining whether an applica tion may deadlock for a given number of available message buffers are intractable [1]. We present a new epoch-based polynomial-time ap proach for approximating the Buffer Allocation Problem. Our approach partitions application executions into epochs and intersperses barrier synchronizations between them, thus limiting the number of message buffers necessary to ensure deadlock-freedom. This approach produces near op timal solutions for many common cases and can be adapted to guide application modifications that ensure deadlock freedom when the application is ported. Lastly, we de scribe a space-time trade-off between the number of avail able message buffers and the number of barrier synchro nizations, and describe how this trade-off can be used to fine-tune application performance.
Important Links:
Go Back
