NESL (thing)

NESL is a parallel functional language developed at the Carnegie Mellon University. It is described as a "nested data parallel language". Recall that data parallelism simply means that we can apply a function to an list (or collection) of elements in parallel, like the array operations in High Performance Fortran.

NESL, however distinguishes itself from HPF and many other data parallel languages in that the functions applied to the collection may itself be implemented in parallel. Hence the term nested data parallelism. NESL is a purely implicit parallel language, exploiting the inherent parallelism offered by pure functional languages. This is in conjunction with the goal of the language: "being able to write parallel code as concisely and clearly as sequential code, while achieving close to peak performance."

Here is an example code from the NESL webpage for parallel quicksort:

function QUICKSORT(S) =
    if (#S <= 1) then S
    else
        let a = S[rand(#S)];
        S_1 = {e in S | e < a};
        S_2 = {e in S | e == a};
        S_3 = {e in S | e > a};
    R = {QUICKSORT(v): v in [S_1, S_3]};
    in R[0] ++ S_2 ++ R[1];

In NESL, data parallelism is denoted by the curly braces. {e in S | e < a} can be read as: "return a list of elements e in the list S such that e is less than a." The equivalent parallel quicksort algorithm using MPI consists of 1,700 lines of code.

Clearly, from NESL, we can see that functional programming has its advantages in the expression of concise code. However, does this concise code translate to fast running times? The jury, it seems, is still out. Sisal, another functional language, claims to be faster than Fortran code that goes through automatic vectorizing and parallelizing, and comparable to explicitly parallel Fortran code, while still being more concise. Sisal, however is implemented only for shared memory machines.