Data partitioning for multiprocessors with memory heterogeneity and memory constraints

Issue title: International Symposium of Parallel and Distributed Computing & International Workshop on Algorithms, Models and Tools for Parallel Computing on Heterogenous Networks

Article type: Research Article

Authors: Lastovetsky, Alexey | Reddy, Ravi

Affiliations: Department of Computer Science University College Dublin, Belfield Dublin 4, Ireland. E-mail: {Alexey.Lastovetsky, Manumachu.Reddy}@ucd.ie

Abstract: The paper presents a performance model that can be used to optimally distribute computations over heterogeneous computers. This model is application-centric representing the speed of each computer by a function of the problem size. This way it takes into account the processor heterogeneity, the heterogeneity of memory structure, and the memory limitations at each level of memory hierarchy. A problem of optimal partitioning of an n-element set over p heterogeneous processors using this performance model is formulated, and its efficient solution of the complexity O(p^{3}× log_{2} n) is given.

Keywords: Heterogeneous (hybrid) systems, scheduling and task partitioning, load balancing and task assignment

Journal: Scientific Programming, vol. 13, no. 2, pp. 93-112, 2005