Heterogeneity Considered Harmful to Algorithm Designers

In this paper, we deal with algorithmic issues on heterogeneous platforms. We show that static schedul- ing and load-balancing strategies are absolutely needed to achieve good performances, in contrast to situa- tion for homogeneous parallel machines where dynamic schemes often turn out to be very satisfactory. However, we also show that static strategies targeted to heteroge- neous platforms are difficult to design and implement: intuitively, data distribution must obey a much more re- fined model than standard block-cyclic distributions to equally balance the load between processors of different speeds. Technically, we state several NP-completeness results that demonstrate the intrinsic difficulty of static load-balancing on heterogeneous platforms.