Space Efficient List Merging On A Multiprocessor Ring

Algorithms are considered for a multiprocessor ring consisting of a moderate number of processors, each with a large private memory. The data in the lists are distributed equally among the processor memories, with each processor holding a contiguous segment of the list. The process of merging the two lists is described in terms of lattice paths. Addition of symbolic polynomials is used as the prototypical merging application. Two algorithms are described for merging. Both move the list elements so that a standard sequential algorithm can be applied locally. The first shifts both lists simultaneously so as to achieve alignment. The second uses a variant of odd-even merging. The time complexity of the alignment operation is shown to be linear in the length of the smaller list