Study on parallel merging of arrays using PVM

Abstract

The algorithm for merging is inspired by the method proposed in [1]. In the algorithm we partition the two arrays in subpartitions, and we sent each subpartition (Ai,Bi) to be merged by the child processes created on other hosts of  the virtual machine. Then with the merged subpartitions received from the child processes we directly assemble in the parent process the merge of the two primary sequences.

For partitioning there the following alternatives:

1.      We compute the partitions in the master process and we send only the two partitions for merging to a slave process. In this case the disadvantage is that the master performs a greater effort to compute the partitions but sends less data to the children (sends only the partitions).

2.      We send at least one of the sets in its entirety to the child for computing the partitioning. In this case more data is sent but the parent does not have to compute

In the implementation of the algorithm we chose the first alternative, because in a real application the chosen variant varies in each case with the speed of the processors or the speed of data transmission.