Realistic communication model for parallel computing on cluster

Abstract

We present a model for parallel computation on commodity cluster. Our cluster model is targeted as a tool for performance analysis and algorithm design. We abstract the communication event by means of local and remote data movements, and explicitly expose the contention problems by capturing them in our parameters. To validate our model, we compare the prediction accuracy of our model with the Postal model for the popular tree-based broadcast algorithm. Our model provides good prediction accuracy and answers to some performance issues that are missing in existing models. We examine the gather collective operation, in which contention delay dominates its overall execution time. Based on the model, we design a communication schedule for the gather operation that is based on the upper and lower bounds, in which the congestion behavior could be under our control and achieve optimal results by avoiding data loss.