Design space

Design issue notes for Haskell MPI bindings.

Design goals

1. Support for dynamic sized types (eg recursively defined algebraic data types, such as lists, whose size could not be known by receiving side without constructing the same value).
   • Emphasises convenience and safety over absolute performance. This includes run-time checks for things that would definitely break MPI (negative counts in alltoall, etc)
   • May support a subset of all of the MPI communication functions.
2. Support for static sized data types (eg primitive types, and fixed size compounds, such as tuples with fixed size elements. Any use case where receiving side could either know the size at compile time or compute it "cheaply" falls into this category).
   • Emphasises performance over convenience and safety. For example, by avoiding data copying where possible.
   • Emphasises update-in-place where possible via mutable collections.
   • Tries to support all of the MPI communication functions, especially the collective ones.
3. Encourage idiomatic Haskell style.
   • May diverge from C API where necessary (break collectives into send and recv parts).
   • May have different arguments to functions, and in different order to maximise currying opportunity.
   • Try to use Haskell type system features where possible, such as distinguishing Rank and Tag from Int.
   • Try to be as general as possible with message types by overloading.
   • Try to hide the internals (so that users would not be forced to deal with functions from Foreign.*)
4. Keep up decent speed
   • Overhead for supporting the static sized data types should be kept at minimum

Note

The interface for dynamic sized types can also include types of static size (eg Ints). So a user may have to choose which approach is best for their needs.

Key implementation questions

1. What are the right collection types to use for collective communication functions (in Serializable.hs)?

   Current candidate: lists

   Rationale: We could not foresee all possible use-cases for collective operations. Users can decide to scatter/gather/otherwise collect a single element to each processor, or group of elements comprising some "strided/stiped" pattern inside a container, or group of elements satisfying some predicate, or ... Classic MPI tries to solve this by providing "*v" functions (scatterv, gatherv, alltoallv) that allows to specify sizes and displacements withing C-style memory mapped arrays.

   Since Serializable.hs does not operate on values that have the same immediate representation, it make little sense trying to port this approach to Haskell (remember that we are talking about exposed API, not the internals of the implementation of the collective functions in Serializable.hs). We can not reasonably expect users to calculcate sizes and displacements into List, Sequence, Map or any other container type, especially taking into account that index-based access is not the preferred mode of operation on them.

   The other approach proposed in MPI is custom datatype declarations. For example, user can declare a type that describes a column or row of two-dimensional array of given size, and value of such type is the number of row or column. This approach also would look unnatural when ported to Haskell verbatim.

   Proposal is for users to make use of high-order functions to re-shape their container however they like and produce a list that has one element for each process (or, a single value in case of functions like "gather").

   Otherwise we would have to device some kind of overloadable Streams-like interface for various containers that would allow API to extract "next chunk" or "chunk for N-th processor" from the container, and provide users with the ability to parametrize this interface for their liking ("select first two elements out of every three", "select using this predicate" or ....).

2. What is the right way to overload message types?

Proposed technical solutions

1. Use Serializable class for message type representing dynamic sized types.
   • Use a persistent sequence type for collections of values (such as a list, or Data.Sequence or something overloaded).
2. Use Storable class for message type representing static sized types.
   • Use an array type for collections of values.

Open questions

1. What is the right way to overload the collection type for static sized types?
2. If we are using array types, do we want to support both mutable and immutable arrays?
   • Mutable arrays allow us to reuse previously allocated memory and are likely to be the most efficient solution, especially for tight numeric computation loops, so they must be supported.
   • Destructive update is only needed for data being received. Send data is read only.
   • There could be three types of message collections: read only sent data, mutable received data, and immutable received data(?!).
3. We might loose precision somewhere in the Int<->CInt conversion. Need more tests to test this
4. We have no API to compute the size of the MPI datatypes. sizeOf is of no help, since in OpenMPI all "datatypes" are pointers to something, hence sizeOf of them will always be equal 4.
5. We transfer StorableArrays and IOArrays as byte buffers. What would happen when sender and receiver have the different endianness?
6. How to implement Reduce-like operations, especially for Serializable API? Lets start with Storable API: reduce-like operations expect to operate on values of the known type, which means that our trick of treating Storable as byte buffer would not cut it. We need to know how to project the type of array elements into MPI datatypes, and need to know what to do with the elements that could not be thusly mapped. Maybe we could make do with Haskell HOFs for reduce-like functionality? Perl's Parallel-MPI-Simple has a nice example of userland Reduce implementation.