Communicating Operators - The Heart of PM

 

Communicating operators lie at the heart of the PM parallelisation model. They are designed to provide a compromise between the direct access to global data structures (particularly arrays) offered by approaches such as Partitioned Global Address Space and the straightforward synchronisation provided by Communicating Sequential Processes. In common with most data-parallel languages, PM contains a parallel version of the for statement which runs all invocations of its enclosed statement list concurrently:

      for element1 in array1, element2 in array2 do  
           element2=process_element(element1)  
      endfor  

Most real models will require some interaction between adjacent array elements. In PM this is achieved by using either a local or a global communicating operator. The global operator @v returns an array whose elements comprise the values of loop-local variable v in each invocation of the enclosing for statement. The neighbourhood operator v@{nbd} provides a more localised array view of v, containing only the local value and those of its neighbours, as defined by the array domain topology.

A very simple example is the implementation of a mean filter over a rectangular array. A 3x3 mean filter simply replaces each element of a grid by the mean of itself and its eight immediate neighbours. In PM this could be coded:

  for element in array do  
    element = sum(element@{-1..1,-1..1})/count(element@{-1..1,-1..1})  
  endfor  

Here sum and count are straightforward array operations. It is necessary to use count rather than simply dividing by nine since off-edge array elements are returned by @ as missing values. The communicating operators both request and supply values for the given variable, thus providing logical synchronisation between concurrent invocations.

There are also reduction versions of the communicating operators, which apply an operation globally or over a neighbourhood, rather than returning an array. The above example may be more efficiently coded as:

  for element in array do  
    element = sum::element@{-1..1,-1..1}/count::element@{-1..1,-1..1}  
  endfor  

The :: @ pair is the reduction version of the neighbourhood @ operator. The global reduction operator just uses ::. To normalise an array so that the sum of its elements sum to one:

 for element in array do  
  element = element/sum::element  
 endfor  

There is more to communicating operators, including their interaction with nested conditional/looping statements and their packaging into ‘loop procedures’. I will come back to this topic in later posts.