The emergence of grid and a new class of data-driven applications is making a new form of parallelism desirable, which we refer to as coarse-grained pipelined parallelism. In this paper, we focus on the problem of choosing packet size, i.e., the unit of transfer between the pipeline units, in exploiting this form of parallelism.

We develop an analytical model for this purpose. Because the pipeline includes both communication and computation phases, the frequency and/or volume of communication between different phases can be different. We consider two models, fixed-frequency and fixed-size, and derive mathematical expressions for both.

We have carried out detailed evaluation of our models using three applications, executed with different parameters and datasets. Our experiments show that the choice of packet size makes a significant difference in the execution time, and the packet sizes suggested by the model result in the lowest or very close to the lowest possible execution time.