Data partitioning with a realistic performance model of networks of heterogeneous computers with task size limits

Author

Lastovetsky, Alexey ; Reddy, Ravi

fYear

2004

fDate

5-7 July 2004

Firstpage

133

Lastpage

140

Abstract

The paper presents a performance model that can be used to optimally schedule arbitrary tasks on a network of heterogeneous computers when there is an upper bound on the size of the task that can be solved by each computer. We formulate a problem of partitioning of an n-element set over p heterogeneous processors using this advanced performance model and give its efficient solution of the complexity O(p³ × log₂ n).

Keywords

computational complexity; data handling; distributed programming; processor scheduling; task analysis; workstation clusters; complexity; data partitioning; heterogeneous computers; heterogeneous processors; heterogeneous systems; hybrid systems; load balancing; n-element set; network performance model; optimal scheduling; task assignment; task partitioning; task scheduling; task size limits; Application software; Computer networks; Concurrent computing; Distributed computing; Grid computing; Parallel programming; Pervasive computing; Processor scheduling; Signal processing algorithms; Upper bound; Heterogeneous (hybrid) systems; Load balancing and task; Scheduling and task partitioning;

fLanguage

English

Publisher

ieee

Conference_Titel

Parallel and Distributed Computing, 2004. Third International Symposium on/Algorithms, Models and Tools for Parallel Computing on Heterogeneous Networks, 2004. Third International Workshop on

Print_ISBN

0-7695-2210-6

Type

conf

DOI

10.1109/ISPDC.2004.17

Filename

1372059