Enhancing functional and irregular parallelism: stateful functions and their semantics

Abstract

We describe an approach in which stateful computations can be expressed within the framework of a functional language. We consider algorithms with nondeterministic intermediate results and a deterministic final result which is obtained for any series of intermediate values of some variable shared among parallel tasks or, in other words, the ordering of updates to the variable does not matter. Functional languages normally abstract away from explicit syn- chronization and exploit parallelism between separate uses of a variable. But in some cases we can relax that requirement with both parallelism and determinate computation. To increase its expressiveness and efficiency for this important class of problems, we propose to extend the Sisal language with state variables encapsulated within stateful functions. We have used Centaur to specify and construct a semantic-based environment. We illustrate the proposed language extension with analysis of several examples, and comparison with other languages.