Skeletons

In the course of the SPICA project multiple skeletons were developed. We can divide them into few classes. All the code linked from here is shown in pretty-printed HTML. The original source files are, of course, also available. Just replace ".html" with ".lhs" or ".hs".

All the code on this page is released unter the GNU GPL licence.

Divide and Conquer

Originally developed for parallel FFT, these skeletons are suitable for other divide and conquer tasks. In this project they are used for Karatsuba multiplication and Strassen multiplication. DC with depth control and distributed transition to a further skeleton is in work.

All-to-all

map-and-transpose, the original.
This skeleton was also developed for parallel FFT. It implements distributable homomorphisms in a special twodimensional case. The skeleton consists of map, transpose and map phases. Transpose needs to perform on distributed data. The first implementation was complicated. However it leads to the concept of "remote data". With it, a more generic all-to-all skeleton is easily possible.
map-and-traspose, with the remote data is now
```
parMapRD . transpose . parMapRD
```
where RD suffix indicated the remote data version.
all-to-all skeleton

Using map

Not necessarily a new skeleton, a map-like parallelism is used in our implementation of several instances of multiple-residue arithmetic. The several residues are independent and can be computed separately. Gauss elimination serves as an example.

Parallel Iteration

iterUntil
Originated from a port of an iteration skeleton to modern Eden, this topic captures the skeletons for parallel do-while loop. The check of the predicate in while is relaxed to happen only once in a few iterations, enabling parallelism.
map+reduce
However, a detailed study of a specific subclass of this skeleton showed that for parallel primality test a weaker result suffies. It is captured in the map+reduce family of skeletons. Inthere, map can be an arbitrary parallel map: parMap, farm, workpool, etc. The reduce function, however, is special. It is required to have some specific properties to be able to abort the parallel computation is the predicate in while is false.

We have implemented two primality tests: Rabin-Miller and APRCL with the above skeletons.