C³: An architecture-independent model for coarse-grained parallel machines

We propose an architecture-independent parallel model, the C³-model. The C³-model evaluates, for a given parallel algorithm and target architecture, the complexity of computation, the pattern of communication, and the potential congestion arising in communication operations. A metric for estimating the effect of link and processor congestion on the performance of an arbitrary communication operation is developed. We describe how the C³-model can serve as a platform for the development of coarse-grained algorithms sensitive to the parameters of a parallel machine. The initial validation of the C³-model is discussed through different implementations of communication operations on the Intel Touchstone Delta