Load analysis and cost estimation of parallel constrained producer-consumer algorithms
Tariq Kamal, Keith Bisset, Ali Raza Butt, MADHAV V. MARATHE · 2014
Cost estimation is crucial for optimizing the performance of parallel algorithms on distributed systems. This paper performs load analysis and cost estimation of constrained producer-consumer (CPC) parallel algorithms. In CPC algorithms, the computation is performed by classes of nodes (tasks), separated in time. For any given CPC problem, the cost can be modelled as a linear combination of computational imbalance components and a communication load. These components can be determined from analysis of the inter-task communication of the algorithm.