BibTeX entry:

     author={Sergei Gorlatch and Christian Lengauer},
     title={({D}e){C}omposition Rules for Parallel Scan and Reduction},
     booktitle = "Proc. 3rd Int. Working Conf. on
     Massively Parallel Programming Models (MPPM'97)",
     year = 	 "1998",
     publisher = {IEEE Computer Society Press},
     pages = "23--32"

  We study the use of well-defined building blocks for SPMD programming
  of machines with distributed memory. Our general framework is based on homomorphisms,
  functions that capture the idea of data-parallelism and have a close correspondence
  with collective operations of the MPI standard, e.g., scan and reduction.
  We prove two composition rules: under certain conditions, a composition of a scan
  and a reduction can be transformed into one reduction, and a composition of two scans
  into one scan. As an example of decomposition, we transform a segmented reduction into a
  composition of partial reduction and all-gather. The performance gain and
  overhead of the proposed composition and decomposition rules are assessed analytically
  for the hypercube and compared with the estimates for some other parallel models.

Paper itself (preliminary version, due to the copyright restrictions):

Cross links:

Sergei Gorlatch