Title

Space Efficient List Merging On A Multiprocessor Ring

Abstract

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.

Publication Date

1-1-1990

Number of Pages

188-194

Document Type

Article; Proceedings Paper

Personal Identifier

scopus

Socpus ID

0025229815 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/0025229815

This document is currently not available here.

Share

COinS