Sample Chapel Exercises (SIGCSE 2014 Workshop 28)

Feel free to follow your interests in exploring Chapel, but here are some suggestions. For examples of Chapel syntax, refer to the cheat sheet and to examples.chpl. You can also refer to our tutorials:

• http://faculty.knox.edu/dbunde/teaching/chapel/
• http://cs.colby.edu/kgburke/?resource=chapelTutorial

Remember that to compile and run, you can do the following:

  chpl myFile.chpl
  ./a.out

Suggestions for hands-on session one:

1. Write a parallel function to compute the dot product of two vectors. One possible signature for the method is

        proc getDotProduct(v : [] real, w : [] real) : real {
   

   This signature, and a testing program, is in dotProduct.chpl.
2. Define a function for matrix-vector products. A possible signature:

        proc matrixVectorProduct(matrix : [] real, vector : [] real) : [] real {
   

   If you want to use your dot product routine, you can get the range of row values using matrix.domain.dim(1) and you can extract a single row of the matrix by accessing it with only one coordinate: matrix[index].
3. Use scans and reductions to sum a Taylor series such as

   ex=1+x+x2/2! + x3/3! + ... + xi/i! + ...
   

   (Recall the factorials and powersOf3 arrays created using scans in the slides.)
4. Use a reduction to compute the index where the pivot of quicksort will be placed, i.e. the number of values smaller than the pivot value.
5. Write a function to split a one-dimensional range, e.g. rangeToSplit, into two equal pieces. There are many things to consider/recall here!
   • You could write a function that splits only stridable ranges. Then your function header will look like:

              proc splitRange(rangeToSplit : range(stridable = true)) : [0..1] range(stridable = true) {
     

   • rangeToSplit.size - the number of elements, if it's finite (bounded).
   • rangeToSplit.low, rangeToSplit.high - the low and high bounds of the range (if they exist).
   • rangeToSplit.stride - the stride (distance between consecutive elements) of the range, if it's stridable.
   • More range properties are listed in the Chapel language spec, starting on page 155.
6. See if you can implement the Game of Life. Some neat things to try:
   • Use inherent parallelism in array assignment/operators.
   • Use parallel loops to determine the new life-value at each cell.
   • Use domain slicing to reduce code needed to check for boundary conditions.
   • Use dynamic array domains to implement an unbounded lifescape without doing explicit array copying when you go over the current boundaries.

Suggestions for hands-on session two:

(You can also continue with the session one problems...)

1. Write a parallel version of bubble sort: Repeatedly compare each even-indexed element with its successor and then each odd-indexed element with its successor. After n repetitions of this, the array should be sorted.
2. Define a node class and use it to make a linked list. (nil is the name of a null reference in Chapel.) Write functions for inserting, removing, printing the list, etc.
3. Write a custom reduction to identify the 2nd smallest value. (The sample custom reduction is in sampleReduction.chpl.) What about the k^th smallest?
4. Write a custom reduction to compute a histogram from an array of 0s, 1s, and 2s.
5. Implement binary search. You can do this in a C-style way by passing indices denoting the part of the array being searched or by changing the domain at each level.
6. Implement parallel merge sort.