Derivation of Efficient Parallel Algorithms on a Ring of Processors.
Ali E. Abdallah, T. Theoharis · 1997
A binary operator which takes two lists os arguments is colled, multiscon if eaery element of the first list must be considered, in conjunction with euery element of the second list in order to produce the result. Seuerol problems such as the relat'i,onal databose operators join, intersection, and, difference can be expressed as specific instances of rnultiscan. In this paper we consider a generic functional definition of multiscan ond show how it can be implemented as a network of communicating sequential processes (CSP) with a ring configuration. We eaomine issues which affect the perlonnance ol the parallel implementation and, identily two properties which, if possessed by a multiscan operator, allow the d,eriuation of an efficient scalable parallel im9tlernentation on a ring of processors. A practical illustration from the field of relational data bases is giuen.