Hello Parallel Programmers!
Whether you're a functional programmer or not you've probably noticed an increasing number of FP-related concepts circulating in this Age of Parallelism: immutability, implicit parallelism, dataflow, and so on. These ideas seem to be getting around and in fact are alive and well here at Intel. They play a major (though possibly non-obvious) role within Intel Concurrent Collections and we've decided to bring them out to the surface with a Haskell edition of that library.
As you may already know Intel Concurrent Collections (CnC) is a new library that captures a particular model of parallel computation. Specifically, CnC is used for graph-like computations that share immutable data in tables. It's a bit like stream processing, and a bit not. CnC is a better fit than streaming for applications that build and share data structures in parallel.
In CnC parlance the computation graph is made up of steps which read and write to item collections (tables) and produce unordered streams of tags that invoke other steps downstream.
Well, it happens that the CnC notion of a step is a pure function. A step does nothing but read its inputs and produce tags and items as output. This design was chosen to bring CnC to that elusive but wonderful place called deterministic parallelism. The decision had nothing to do with language preferences. (And indeed, the primary CnC implementations are for C++ and Java.)
Yet what a great match Haskell and CnC would make! Haskell is the only major language where we can (1) enforce that steps be pure, and (2) directly recognize (and leverage!) the fact that both steps and graph executions are pure.
Add to that the fact that Haskell is wonderfully extensible and thus the CnC "library" can feel almost like a domain-specific language. What, then, does Haskell CnC code look like? Let's see:
CnC meets Haskell
First, we will write specialized code blocks that perform the code for a step. These are "do" blocks in Haskell notation. Such a piece of code may do things like put or get items, for example:
This example gets one key-value pair and puts another. It could form a step that would execute in a CnC graph. (Syntax note: You'll notice that Haskell uses an indentation-based syntax (like Python) and that function application involves no parentheses or commas, only spaces (like a command shell). For example,
get is applied to two arguments above.)
In addition to step code, Haskell CnC also involves blocks of code for wiring together graphs. These look similar but are actually written in a different mini-language. In this mini-language the user can create nodes in the graph and connect tags to the steps that they "prescribe".
You may notice that there are no types in this code. Haskell is statically typed but uses type inference to determine what the types should be. (In fact, you could say that Haskell is more statically typed than virtually any other major language in that the type system is very rich and powerful.)
A complete program
Now we are almost ready to write a complete program that constructs and executes a graph. We need one final concept -- initialization/finalization. Whereas the "prescribe" operation above connects the edges of a graph, we still need a way to put data into the system from the outside and retrieve results when graph evaluation has completed. For this purpose, Haskell CnC allows the user to embed step code into the graph code. (Recall that the "step code" runs inside the graph, producing and consuming items.) In fact, the user embeds exactly two pieces of step code: one to initialize, another to finalize.
Below is a Hello World program that uses all of CnC's graph constructs. (You can find and run this program as hello_world.hs in the Haskell CnC distribution.)
This program will print "Hello World 99".
The initialize code puts two strings in the item collection. Item collections can be indexed by any (ordered) key type and in this example we use String keys. Graph execution consists of a single step that combines the words and writes the result. Execution of that step is triggered by
initialize putting out the tag 99. Put for tags ("put-Tag") is abbreviated
putt. Full apologies for the pun.
The "runGraph" function is needed to actually execute a graph object and return the result (that is, whatever was returned by the finalize step). One note for Haskellers is that because parallel graph evaluation is ultimately pure (whether or not it is implemented with IO), the runGraph returns a pure value (not one "tainted" with IO).
Give it a try! The source tarball is available here. The license is LGPL. The page on HackageDB contains the automatically generated documentation. If you have Haskell Platform installed you can get CnC with one line:
cabal install haskell-cnc
Note that with GHC 6.12.1 you will see parallel speedups, but for good parallel speedups you will currently need to build the latest GHC from source. It is a fast-moving target. Future posts will discuss some of the implementation details and performance.
Disclaimer: Note that Concurrent Collections for Haskell is not a supported product and comes with no implied or express warranty.