Free Web Hosting by Netfirms
 Web Hosting by Netfirms | Free Domain Names by Netfirms

The Parallel Programming Language V

V is a new parallel programming language based on C.

V extends C with a new type constructor for vectors and introduces parallelism using an apply-to-each construct and some built-in primitives. The apply-to-each allows the simultaneous application of built-in and user-defined functions at all or some elements of a vector.

V is pursuing a novel approach to data parallel computing that is expected to lead to a larger range of applications than High Performance Fortran (HPF). Specifically the large class of divide-and-conquer algorithms offers possibilities for parallelization that are difficult to express in HPF. So far, applications of that kind must be transformed by hand to fit the paradigm of "flat" parallelism. New research results in the area of functional languages have shown that this task can be automated, i.e., dynamically nested parallelism can be transformed by the compiler into flat parallelism.

Programming Model

V inherits its vectors from the functional language NESL designed in the Scandal project at the Carnegie Mellon University.

NESL is based on the Scan Vector Model developed by Guy E. Blelloch. This approach is characterized by

bullet The ability to deal with nested parallelism
bullet Simple description and efficient implementation of irregular data structures (e.g. sparse matrices) and divide-and-conquer algorithms (e.g. quicksort)
bullet Implicit data distribution
bullet Automatic load balancing
bullet Architecture independence
bullet Easy to use cost model (step/work-complexity)

V makes the approach available for imperative programming:

Parallel computations can be programmed in a procedural style as long as they have no global effects, they may be used in sequential imperative code.

The C programmer can use the environment he or she is familiar with, existing software, interfaces, and tools can be used.

Elements of V

V is an extension of ANSI C that integrates the following elements:
bullet Declarations of Vectors 
  int vector[*], (*ptr_to_vector)[*];
  int matrix[*][*];

  int foo () [*] {...}
bullet Values: Sequences of varying lengths of elements of the same type 
  vector = [1, 2, 3];
bullet Apply-to-each: Parallel computation of vector elements 
  squares = [ x*x : x in xs ];
'squares' becomes a vector whose elements are given by 'x*x' for each 'x' in 'xs'. 
  less    = [x : x in xs : x <  pivot];
'less' becomes the vector of those 'x' from 'xs' that are less than 'pivot'.

bullet Element access 
  x = v[1];
bullet Concatenation of two vectors 
  w = v >< [1];
bullet Range 
  [a::b]

  [a::b::c]
bullet Size 
  $ v
bullet Pure Functions: checked to have no global side effect and can be used in apply-to-each constructs. 
  pure int double (int x)
  {
    return 2 * x;
  }

  pure void divmod
     (int a, int b, int *c, int *d)
  {
    *c = a / b;
    *d = a % b;
  }
bullet Other operations and builtin functions

Example

Divide And Conquer: Parallel Quicksort 
  pure int qsort (int xs[*]) [*]
  {
    int pivot;
    int less[*], equal[*], greater[*];
    int sorted[*][*];

    if ($xs <= 1) return xs;
  
    pivot   = xs[$xs / 2];

    less    = [x : x in xs : x <  pivot];
    equal   = [x : x in xs : x == pivot];
    greater = [x : x in xs : x >  pivot];

    sorted  = [qsort (subseq) :
	       subseq in [less, greater]];

    return sorted[0] >< equal >< sorted[1];
  }
Using the apply-to-each construct the initial input vector `xs' is split into three vectors containing the elements `less', `equal', and `greater' than the `pivot'. This is done in parallel with constant step complexity. The function then is recursively invoked on `less' and `greater', in order to sort these smaller vectors. By placing both recursive calls within an apply-to-each construct the recursive calls are not only parallel within each call, but are also executed in parallel to each other. This leads, in the average case, to a logarithmic step complexity. The result of the recursive calls (`sorted') and the elements `equal' to the `pivot' are, finally, concatenated to form the result---this concatenation requires constant step complexity.

Implementation

Each pure function is translated in two ways. First, the `normal' scalar code is generated, then it is lifted to work on vectors of arguments and to return a vector of results. This lifted version of a function is used if the function is invoked in the context of an apply-to-each. 
     int square (int x)
     {
	return x*x;
     }
becomes 
     int vector_square (int x[*]) [*]
     {
	return [y*y : y in x];
     }
Whenever a pure function is called in the body of an apply-to-each or in the vectorized version of a pure function, its lifted version is used. 
     v = [ square(x) : x in v ];
becomes 
     v = vector_square(v);
The system provides vectorized versions for all primitive functions which are allowed within apply-to-each and pure functions. This way, the vectorized version of user-defined pure functions is mapped to the parallel primitives of the system. Vectorization is applied to all C constructs appearing in pure functions, including loops. Thus, nested parallelism is completely flattened at compile time.

V was implemented with the GENTLE Compiler Construction System.

Papers

M.M.T. Chakravarty, F.W. Schröer, M. Simons:
V Reference Manual
GMD FIRST, Technical Report, 1994

M.M.T. Chakravarty, F.W. Schröer, M. Simons:
V User's Manual
TU Berlin, Technical Report, 1994

M.M.T. Chakravarty, F.W. Schröer, M. Simons:
V - Nested Parallelism in C
In W.K. Giloi, S. Jähnichen, B. Shriver (eds.):
Proceedings Programming Models for Massively Parallel Computers 1995,
IEEE Computer Society Press, 1995

W. Pfannenstiel, M. Dahm, M.M.T. Chakravarty, S.Jähnichen,
G. Keller, F.W. Schröer, M. Simons:
Aspects of the Compilation of Nested Parallel Imperative Languages
In J. Darlington, ed.:
International Conference on Massively Parallel Programming Models 1997,
IEEE Computer Society Press, 1997

V is developed in a joint project at the Institute for Computer Architecture and Software Technology (FIRST) of the German National Research Center for Information Technology (GMD) and at the Software Engineering Research Group of the TU Berlin.