Abstract. This paper is focused on designing two parallel dot product implementations for heterogeneous master-worker platforms. These implementations are based on the data allocation and dynamic load balancing strategies. The first implementation is the dynamic master - worker with allocation of vectors where the master distributes vectors (data) and computations to the workers whereas the second one is the dynamic master - worker with allocation of vector pointers where the vectors are supposed to be replicated among participating resources beforehand and the master distributes computations to the workers. We also report a set of numerical experiments on a heterogeneous platform where computational resources have different computing powers. Also, the workers are connected to the master by links of same capacities. The obtained experimental results demonstrate that the dynamic allocation of vector pointers achieve better performance than the original one for computing dot product computation.

The paper also presents and verifies an accurate timing model to predict the performance of the proposed implementations on clusters of heterogeneous workstations. Through this model the viability of the proposed implementations can be revealed without the extra effort that would be needed to carry out real testing.

Received: December 18, 2012

AMS Subject Classification: 65F30, 65Y05, 68M14, 68M20, 68W10

Key Words and Phrases: dot product, cluster of heterogeneous workstations, Message passing interface, parallel algorithms, performance prediction

Download paper from here.