Optimization

Functional algorithmic skeletons promise a high-level pro-gramming interface for distributed-memory clusters that free developers from concerns of task decomposition, schedul-ing, and communication. Unfortunately, prior distributed functional skeleton frameworks do not deliver performance comparable to that achievable in a low-level distributed pro-gramming model such as C with MPI and OpenMP, even when used in concert with high-performance array libraries. There are several causes: they do not take advantage of shared memory on each cluster node; they impose a xed partitioning strategy on input data; and they have limited ability to fuse loops involving skeletons that produce a vari-able number of outputs per input. We address these shortcomings in the Triolet program-ming language through a modular library design that sep-arates concerns of parallelism, loop nesting, and data par-titioning. We show how Triolet substantially improves the parallel performance of algorithms involving array traver-sals and nested, variable-size loops over what is achievable in Eden, a distributed variant of Haskell. We further demon-strate how Triolet can substantially simplify parallel pro-gramming relative to C with MPI and OpenMP while achiev-ing 23100 % of its performance on a 128-core cluster