76 COMPUTING APPLICATIONS DATA PARTITIONING WITH A FUNCTIONAL PERFORMANCE MODEL OF HETEROGENEOUS PROCESSORS

In this paper, we address the problem of optimal distribu-tion 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 perform-ance 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 mem-ory structure, and the effects of paging. Under this model, the speed of each processor is represented by a continu-ous 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 × log2n) solving the problem. Key words: heterogeneous systems, scheduling and task partitioning, load balancing and task assignment, high performance computing.