Data Partitioning with a Functional Performance Model of Heterogeneous Processors

Abstract

In this paper, we address the problem of optimal distribution of computational tasks on a network of heterogeneous computers when one or more tasks do not fit into the main memory of the processors and when relative speeds vary with the problem size. We propose a functional performance model of heterogeneous processors that integrates many essential features of a network of heterogeneous computers having a major impact on its performance such as the processor heterogeneity, the heterogeneity of memory structure, and the effects of paging. Under this model, the speed of each processor is represented by a continuous function of the size of the problem whereas traditional models use single numbers to represent the speeds of the processors. We formulate a problem of partitioning of an n-element set over p heterogeneous processors using this model and design an algorithm of the complexity O(p × log₂n) solving the problem.

Keywords

heterogeneous systems scheduling and task partitioning load balancing and task assignment high performance computing

Get full access to this article

View all access options for this article.

References

Beaumont, O. , Boudet, V. , Petitet, A. , Rastello, F. and Robert, Y. (2001a). A proposal for a heterogeneous cluster ScaLAPACK (dense linear solvers) , IEEE Transactions on Computers, 50: 1052-1070 .

Beaumont, O. , Boudet, V. , Rastello, F. and Robert, Y. (2001b). Matrix multiplication on heterogeneous platforms , IEEE Transactions on Parallel and Distributed Systems, 12: 1033-1051 .

Bharadwaj, V. , Ghose, D. , Mani, V. and Robertazzi, T. G. (1996). Scheduling Divisible Loads in Parallel and Distributed Systems, IEEE Computer Society Press and John Wiley & Sons, Los Alamitos, CA .

Cierniak, M. , Li, W. and Zaki, M. J. (1997). Compile-time scheduling algorithms for heterogeneous network of workstations , Computer Journal, Special Issue on Automatic Loop Parallelization, 40(6): 356-372 .

Crandall, P. and Quinn, M. (1993). Block data decomposition for data-parallel programming on a heterogeneous workstation network , in Proceedings of the Second International Symposium on High Performance Distributed Computing (HPDC ’93), 20-23 July, Spokane, WA, USA, pp. 42-49 , IEEE Computer Society.

Crandall, P. and Quinn, M. (1995). Problem decomposition for non-uniformity and processor heterogeneity , Journal of the Brazilian Computer Society, 2: 13-23 .

Dongarra, J. , Croz, J. D. , Duff, I. S. and Hammarling, S. (1990). A set of level-3 basic linear algebra subprograms , ACM Transactions on Mathematical Software, 16: 1-17 .

Drozdowski, M. and Wolniewicz, P. (2003a). Out-of-core divisible load processing , IEEE Transactions on Parallel and Distributed Systems, 14: 1048-1056 .

Drozdowski, M. and Wolniewicz, P. (2003b). Divisible load scheduling in systems with limited memory , Cluster Computing, 6: 19-29 .

10.

Iverson, M. and Ozguner, F. (1998). Dynamic, competitive scheduling of multiple DAGs in a distributed heterogeneous environment , in Proceedings of the Seventh Heterogeneous Computing Workshop (HCW ’98), Orlando, FL, IEEE Computer Society Press, pp. 70-78 , March.

11.

Kalinov, A. and Lastovetsky, A. (2001). Heterogeneous distribution of computations solving linear algebra problems on networks of heterogeneous computers , Journal of Parallel and Distributed Computing, 61: 520-535 .

12.

Kumar, V. , Grama, A. , Gupta, A. and Karypis, G. (1994). Introduction to Parallel Computing: Design and Analysis of Algorithms, Benjamin-Cummings, Addison-Wesley, Reading, MA .

13.

Lastovetsky, A. and Reddy, R. (2004). Data partitioning with a realistic performance model of networks of heterogeneous computers , in Proceedings of the 18th International Parallel and Distributed Processing Symposium (IPDPS 2004), 26-30 April 2004, Santa Fe, New Mexico, USA, CDROM/Abstracts Proceedings, IEEE Computer Society.

14.

Lastovetsky, A. and Reddy, R. (2005). Data partitioning for multiprocessors with memory heterogeneity and memory constraints , Scientific Programming, 13: 93-112 , IOS Press .

15.

Lastovetsky, A. , Reddy, R. and Higgins, R. (2006). Building the functional performance model of a processor , in Proceedings of the 21st Annual ACM Symposium on Applied Computing (SAC’06), 23-27 April 2006, Dijon, France, pp. 746-753 , ACM Press.

16.

Lastovetsky, A. and Twamley, J. (2005). Towards a realistic performance model for networks of heterogeneous computers , in High Performance Computational Science and Engineering: Proceedings of IFIP TC5 Workshop, World Computer Congress, 22-27 August 2004, Toulouse, France, eds M. K. Ng , A. Doncescu , L. T. Yang , T. Leng , pp. 39-58 , Springer.

17.

Maheswaran, M. and Siegel, H. J. (1998). A dynamic matching and scheduling algorithm for heterogeneous computing systems , in Proceedings of the Seventh Heterogeneous Computing Workshop (HCW 1998), Orlando, FL, pp. 57-69 , IEEE Computer Society Press, March.

18.

Petitet, A. and Dongarra, J. (1999). Algorithmic redistribution methods for block-cyclic decompositions , IEEE Transactions on Parallel and Distributed Systems, 10: 1201-1216 .

19.

Tan, M. , Siegel, H. J. , Antonio, J. K. and Li, Y. A. (1997). Minimizing the application execution time through scheduling of subtasks and communication traffic in a heterogeneous computing system , IEEE Transactions on Parallel and Distributed Systems, 8: 857-871 .

20.

Yan, Y. , Zhang, X. , and Song, Y. (1996). An effective and practical performance prediction model for parallel computing on non-dedicated heterogeneous NOW , Journal of Parallel and Distributed Computing, 38: 63-80 .

21.

Whaley, R. C. , Petitet, A. and Dongarra, J. (2000). Automated empirical optimizations of software and the atlas project, Technical report, Department of Computer Sciences, University of Tennessee, Knoxville , March.