Skip to main content

On the edge

One of the more difficult aspects of coding stencils or other neighbourhood-based operations is working out what should happen at the edge of the grid. Parallel array languages such as ZPL have expended significant effort to provide mechanism to make coding edge effects easier.

PM handles edge effects by making use of optional data types - containers that can hold either a value (e.g.: an integer) or null. Optional types have many uses, including the representation of unbounded data structures in a pointerless language. A number of operators are defined for optional types, most usefully |.  x|y returns the value contained in x if that value is not null. Otherwise y is returned. 

Binary communicating operators (x@[neighbourhood] or x@{neighbourhood}) always return optionally-typed values, with off-edge cells set to null. Combined with the | operator, this makes dealing with edge-effects straightforward.

The following code fragment demonstrates how PM handles edge effects in practice. It solves the 2D steady-state heat transfer problem for a rectangular box whose four walls are maintained at temperatures boundary1..boundary4. A simple solution to this problem involves repeatedly replacing the temperature in each grid cell with the average of its four immediate neighbours until no further change occurs (Jacobi Iteration).

 for cell in [1..N,1..M] do  
      temp := 0.0  
      repeat   
           newtemp := (  
               temp@[-1, 0]|boundary1  
              +temp@[ 1, 0]|boundary2  
              +temp@[ 0,-1]|boundary3  
              +temp@[ 0, 1]|boundary4  
           )/4.0  
         diff := abs(newtemp-temp)  
         temp = newtemp  
      until max::diff < tolerance  
 endfor

This algorithm is a popular example used for discussing and benchmarking parallel systems. Example code is available online for ZPL, MPI and Chapel (amongst others.)

Comments

Post a Comment

Popular posts from this blog

Data in, data out

When a program is running over multiple processors or processing cores then it is important to be able to map where data are flowing. One way in which data flows can be translated into programming language semantics is though argument passing to subroutines. In the absence of global variables, data transfer to and from a subroutine straightforwardly can be directly related to communication to and from another processor. In PM, the emphasis is on data parallelism through the for statement. for index in array do index=process(index) endfor      So what are the rules governing data flow into and out of this statement? These are primarily based around variable locality. x:= 1 for index in array do y:=func(index) index=process(x,y) endfor Here x is relatively global to the for statement and y is local to it (a variables scope only extends to the end of the statement block in which it is defined).  There are two ways t...
Post a Comment
Read more

Compile time, run time, coffee time

[ Please note that in the following discussion I will be using PM 0.5 notation, which is slightly different to PM 0.4 and also in some flux as PM 0.5 is still in development. ]   Many programming languages (and most newly developed ones) include some form of compile-time programming, ranging from simple preprocessors ( #define , #if in C) to fully blown macro systems capable of re-writing the abstract syntax tree during compilation (Rust, Julia, etc .). In line with its philosophy of keeping things as simple as possible, but not simpler, PM takes a middle road with compile-time programming supported primarily through the type system. There is nothing too radical here – this is not an area where the language aims to break new ground.  The PM approach centres around the use of compile-time types. Many languages use special types to denote literal values and PM follows this trend. Literal integers, reals, strings and Booleans each have their own types: literal(int) , litera...
Post a Comment
Read more

The PM Type System

In common with other aspects of PM design, the type system is designed to facilitate the use of flexible programming constructs, such as polymorphism and dynamic dispatch, while emphasising the generation of fast, static, code.  In common with many other modern languages, PM also attempts to combine the safety of static typing with the expressivity of dynamically typed languages such as Python . The type of any PM expression may usually be determined by a static examination of the code. Variables take their types from an initialising expression using the ‘:=’ declaration syntax popularised by Go . a:= 100 ! Declare ‘a’ as an integer (int) variable Variables do not change type during the course of their lifetime – polymorphic programming requires the use of special values, described later. Composite values such as structures are generated using specialised expressions rather than through the invocation of type-specific creator functions: b:= struct var_descriptor...
Post a Comment
Read more