Skil: an imperative language with algorithmic skeletons for efficient distributed programming

Abstract

We present Skil, an imperative language enhanced with higher order functions and currying, as well as with a polymorphic type system. The high level of Skil allows the integration of algorithmic skeletons, i.e. of higher order functions representing parallel computation patterns. At the same time, the language can be efficiently implemented. After describing a series of skeletons which work with distributed arrays, we give two examples of parallel programs implemented on the basis of skeletons, namely shortest paths in graphs and Gaussian elimination. Run time measurements show that we approach the efficiency of message passing C up to a factor between 1 and 2.5.