Comments and formatting to dph-prim-par
authorBen Lippmeier <benl@ouroborus.net>
Tue, 12 Apr 2011 09:47:42 +0000 (19:47 +1000)
committerBen Lippmeier <benl@ouroborus.net>
Tue, 12 Apr 2011 09:47:42 +0000 (19:47 +1000)
dph-prim-par/Data/Array/Parallel/Unlifted/Distributed/Arrays.hs
dph-prim-par/Data/Array/Parallel/Unlifted/Distributed/Basics.hs
dph-prim-par/Data/Array/Parallel/Unlifted/Distributed/Combinators.hs
dph-prim-par/Data/Array/Parallel/Unlifted/Distributed/DistST.hs
dph-prim-par/Data/Array/Parallel/Unlifted/Distributed/Scalars.hs
dph-prim-par/Data/Array/Parallel/Unlifted/Distributed/Types.hs

index 0dcd5c2..6f0822f 100644 (file)
@@ -26,7 +26,6 @@ module Data.Array.Parallel.Unlifted.Distributed.Arrays (
 
   Distribution, balanced, unbalanced
 ) where
-
 import Data.Array.Parallel.Base ( ST, runST)
 import Data.Array.Parallel.Unlifted.Sequential.Vector as Seq
 import Data.Array.Parallel.Unlifted.Sequential.Segmented
@@ -50,6 +49,11 @@ import GHC.Base ( quotInt, remInt )
 
 here s = "Data.Array.Parallel.Unlifted.Distributed.Arrays." Prelude.++ s
 
+
+-- Distribution ---------------------------------------------------------------
+-- | This is a phantom parameter used to record whether a distributed value
+--   is balanced evenly among the threads. It's used to signal this property
+--   between RULES, but the actual value is never used.
 data Distribution
 
 balanced :: Distribution
@@ -60,7 +64,10 @@ unbalanced :: Distribution
 {-# NOINLINE unbalanced #-}
 unbalanced = error $ here "unbalanced: touched"
 
--- | Distribute the given array length over a 'Gang'.
+
+-- Splitting and Joining array lengths ----------------------------------------
+-- | Distribute an array length over a 'Gang'.
+--   Each thread holds the number of elements it's reponsible for.
 splitLenD :: Gang -> Int -> Dist Int
 {-# INLINE splitLenD #-}
 splitLenD g n = generateD_cheap g len
@@ -73,6 +80,9 @@ splitLenD g n = generateD_cheap g len
     len i | i < m     = l+1
           | otherwise = l
 
+-- | Distribute an array length over a 'Gang'.
+--   Each thread holds the number of elements it's responsible for, 
+--   and the index of the start of its chunk.
 splitLenIdxD :: Gang -> Int -> Dist (Int,Int)
 {-# INLINE splitLenIdxD #-}
 splitLenIdxD g n = generateD_cheap g len_idx
@@ -84,28 +94,33 @@ splitLenIdxD g n = generateD_cheap g len_idx
     {-# INLINE [0] len_idx #-}
     len_idx i | i < m     = (l+1, i*(l+1))
               | otherwise = (l,   i*l + m)
+
+
+-- | Get the overall length of a distributed array.
+--   We ask each thread for its chunk length, and sum them all up.
+joinLengthD :: Unbox a => Gang -> Dist (Vector a) -> Int
+{-# INLINE joinLengthD #-}
+joinLengthD g = sumD g . lengthD
                                                
 
+-- Splitting and Joining arrays -----------------------------------------------
 -- | Distribute an array over a 'Gang' such that each threads gets the given
--- number of elements.
+--   number of elements.
 splitAsD :: Unbox a => Gang -> Dist Int -> Vector a -> Dist (Vector a)
 {-# INLINE_DIST splitAsD #-}
 splitAsD g dlen !arr = zipWithD (seqGang g) (Seq.slice arr) is dlen
   where
     is = fst $ scanD g (+) 0 dlen
 
--- lengthD reexported from types
-
--- | Overall length of a distributed array.
-joinLengthD :: Unbox a => Gang -> Dist (Vector a) -> Int
-{-# INLINE joinLengthD #-}
-joinLengthD g = sumD g . lengthD
-
-
--- NOTE: We need splitD_impl and joinD_impl to avoid introducing loops through
--- rules. Without them, splitJoinD would be a loop breaker.
 
 -- | Distribute an array over a 'Gang'.
+--
+--   NOTE: This is defined in terms of splitD_impl to avoid introducing loops
+--         through RULES. Without it, splitJoinD would be a loop breaker.
+splitD :: Unbox a => Gang -> Distribution -> Vector a -> Dist (Vector a)
+{-# INLINE_DIST splitD #-}
+splitD g _ arr = splitD_impl g arr
+
 splitD_impl :: Unbox a => Gang -> Vector a -> Dist (Vector a)
 {-# INLINE_DIST splitD_impl #-}
 splitD_impl g !arr = generateD_cheap g (\i -> Seq.slice arr (idx i) (len i))
@@ -123,19 +138,14 @@ splitD_impl g !arr = generateD_cheap g (\i -> Seq.slice arr (idx i) (len i))
     len i | i < m     = l+1
           | otherwise = l
 
-    -- slice i | i < m     = Seq.slice arr ((l+1)*i) (l+1)
-    --         | otherwise = Seq.slice arr ((l+1)*m + l*(i-m)) l
-{-
-splitD_impl g !arr = zipWithD (seqGang g) (Seq.slice arr) is dlen
-  where
-    dlen = splitLengthD (seqGang g) arr
-    is   = fstS $ scanD (seqGang g) (+) 0 dlen
--}
 
--- | Distribute an array over a 'Gang'.
-splitD :: Unbox a => Gang -> Distribution -> Vector a -> Dist (Vector a)
-{-# INLINE_DIST splitD #-}
-splitD g _ arr = splitD_impl g arr
+-- | Join a distributed array.
+--
+--   NOTE: This is defined in terms of joinD_impl to avoid introducing loops
+--         through RULES. Without it, splitJoinD would be a loop breaker.
+joinD :: Unbox a => Gang -> Distribution -> Dist (Vector a) -> Vector a
+{-# INLINE CONLIKE [1] joinD #-}
+joinD g _ darr  = joinD_impl g darr
 
 joinD_impl :: forall a. Unbox a => Gang -> Dist (Vector a) -> Vector a
 {-# INLINE_DIST joinD_impl #-}
@@ -146,16 +156,20 @@ joinD_impl g !darr = checkGangD (here "joinD") g darr $
     copy :: forall s. MVector s a -> Int -> Vector a -> DistST s ()
     copy ma i arr = stToDistST (Seq.copy (mslice i (Seq.length arr) ma) arr)
 
--- | Join a distributed array.
-joinD :: Unbox a => Gang -> Distribution -> Dist (Vector a) -> Vector a
-{-# INLINE CONLIKE [1] joinD #-}
-joinD g _ darr  = joinD_impl g darr
 
-splitJoinD :: (Unbox a, Unbox b)
-           => Gang -> (Dist (Vector a) -> Dist (Vector b)) -> Vector a -> Vector b
+-- | Split a vector over a gang, run a distributed computation, then
+--   join the pieces together again.
+splitJoinD
+        :: (Unbox a, Unbox b)
+        => Gang
+        -> (Dist (Vector a) -> Dist (Vector b))
+        -> Vector a
+        -> Vector b
 {-# INLINE_DIST splitJoinD #-}
 splitJoinD g f !xs = joinD_impl g (f (splitD_impl g xs))
 
+
+
 -- | Join a distributed array, yielding a mutable global array
 joinDM :: Unbox a => Gang -> Dist (Vector a) -> ST s (MVector s a)
 {-# INLINE joinDM #-}
@@ -169,6 +183,7 @@ joinDM g darr = checkGangD (here "joinDM") g darr $
     --
     copy ma i arr = stToDistST (Seq.copy (mslice i (Seq.length arr) ma) arr)
 
+
 {-# RULES
 
 "splitD[unbalanced]/joinD" forall g b da.
@@ -236,6 +251,8 @@ joinDM g darr = checkGangD (here "joinDM") g darr $
 
   #-}
 
+
+-- Permutation ----------------------------------------------------------------
 -- | Permute for distributed arrays.
 permuteD :: forall a. Unbox a => Gang -> Dist (Vector a) -> Dist (Vector Int) -> Vector a
 {-# INLINE_DIST permuteD #-}
@@ -252,6 +269,8 @@ bpermuteD :: Unbox a => Gang -> Vector a -> Dist (Vector Int) -> Dist (Vector a)
 {-# INLINE bpermuteD #-}
 bpermuteD g !as ds = mapD g (Seq.bpermute as) ds
 
+
+-- Update ---------------------------------------------------------------------
 -- NB: This does not (and cannot) try to prevent two threads from writing to
 -- the same position. We probably want to consider this an (unchecked) user
 -- error.
@@ -268,6 +287,8 @@ atomicUpdateD g darr upd = runST (
     update :: forall s. MVector s a -> Vector (Int,a) -> DistST s ()
     update marr arr = stToDistST (Seq.mupdate marr arr)
 
+
+--- Splitting and Joining segment descriptors ---------------------------------
 splitSegdD :: Gang -> USegd -> Dist USegd
 {-# NOINLINE splitSegdD #-}
 splitSegdD g !segd = mapD g lengthsToUSegd
@@ -278,7 +299,7 @@ splitSegdD g !segd = mapD g lengthsToUSegd
        . splitLenD g
        $ elementsUSegd segd
 
-    n = lengthUSegd segd
+    n    = lengthUSegd segd
     lens = lengthsUSegd segd
 
     chunk !i !k = let !j = go i k
index 80e867c..afcb99b 100644 (file)
@@ -10,8 +10,6 @@
 --
 -- Basic operations on distributed types.
 --
-
-
 module Data.Array.Parallel.Unlifted.Distributed.Basics (
   eqD, neqD, toD, fromD
 ) where
@@ -30,27 +28,30 @@ import Control.Monad ( zipWithM_ )
 
 here s = "Data.Array.Parallel.Unlifted.Distributed.Basics." ++ s
 
--- | Test whether to distributed values are equal. This requires a 'Gang'
--- and hence can't be defined in terms of 'Eq'.
+-- | Test whether to distributed values are equal. 
+--   This requires a 'Gang' and hence can't be defined in terms of 'Eq'.
 --
 eqD :: (Eq a, DT a) => Gang -> Dist a -> Dist a -> Bool
 eqD g dx dy = andD g (zipWithD g (==) dx dy)
 
--- | Test whether to distributed values are not equal. This requires a 'Gang'
--- and hence can't be defined in terms of 'Eq'.
+
+-- | Test whether to distributed values are not equal.
+--   This requires a 'Gang' and hence can't be defined in terms of 'Eq'.
 --
 neqD :: (Eq a, DT a) => Gang -> Dist a -> Dist a -> Bool
 neqD g dx dy = orD g (zipWithD g (/=) dx dy)
 
+
 -- | Generate a distributed value from the first @p@ elements of a list.
 -- 
--- /NOTE:/ Debugging only.
+--   /NOTE:/ For debugging only.
 toD :: DT a => Gang -> [a] -> Dist a
 toD g xs = newD g (\md -> zipWithM_ (writeMD md) [0 .. gangSize g - 1] xs)
 
+
 -- | Yield all elements of a distributed value.
 --
--- /NOTE:/ Debugging only.
+--   /NOTE:/ For debugging only.
 fromD :: DT a => Gang -> Dist a -> [a]
 fromD g dt = checkGangD (here "fromDT") g dt $
              map (indexD dt) [0 .. gangSize g - 1]
index 4330e6c..2a70e6d 100644 (file)
@@ -1,4 +1,5 @@
 {-# LANGUAGE ScopedTypeVariables #-}
+{-# LANGUAGE CPP #-}
 -----------------------------------------------------------------------------
 -- |
 -- Module      :  Data.Array.Parallel.Unlifted.Distributed.Basics
@@ -12,8 +13,6 @@
 -- Standard combinators for distributed types.
 --
 
-{-# LANGUAGE CPP #-}
-
 #include "fusion-phases.h"
 
 module Data.Array.Parallel.Unlifted.Distributed.Combinators (
@@ -38,18 +37,34 @@ import Debug.Trace
 
 here s = "Data.Array.Parallel.Unlifted.Distributed.Combinators." ++ s
 
+-- | Create a distributed value, given a function that makes the value in each thread.
 generateD :: DT a => Gang -> (Int -> a) -> Dist a
 {-# NOINLINE generateD #-}
-generateD g f = runDistST g (myIndex >>= return . f)
+generateD g f 
+       = trace "generate full")
+       $ runDistST g (myIndex >>= return . f)
 
+
+-- | Create a distributed value, but run it sequentially (I think?)
 generateD_cheap :: DT a => Gang -> (Int -> a) -> Dist a
 {-# NOINLINE generateD_cheap #-}
-generateD_cheap g f = runDistST_seq g (myIndex >>= return . f)
+generateD_cheap g f 
+       = trace "generate cheap"
+       $ runDistST_seq g (myIndex >>= return . f)
+
 
+-- Mapping --------------------------------------------------------------------
+-- | Map a function across all elements of a distributed value.
+--   The worker function also gets the current thread index.
+--   As opposed to `imapD'` this version also deepSeqs each element before
+--   passing it to the function.
 imapD :: (DT a, DT b) => Gang -> (Int -> a -> b) -> Dist a -> Dist b
 {-# INLINE [0] imapD #-}
 imapD g f d = imapD' g (\i x -> x `deepSeqD` f i x) d
 
+
+-- | Map a function across all elements of a distributed value.
+--   The worker function also gets the current thread index.
 imapD' :: (DT a, DT b) => Gang -> (Int -> a -> b) -> Dist a -> Dist b
 {-# NOINLINE imapD' #-}
 imapD' g f !d = checkGangD (here "imapD") g d
@@ -58,18 +73,11 @@ imapD' g f !d = checkGangD (here "imapD") g d
                                 x <- myD d
                                 return (f i x)))
 
+
 -- | Map a function over a distributed value.
 mapD :: (DT a, DT b) => Gang -> (a -> b) -> Dist a -> Dist b
 {-# INLINE mapD #-}
 mapD g = imapD g . const
-{-
-mapD g f !d = checkGangD (here "mapD") g d
-              {- (runDistST g (do
-                              x <- myD d
-                              traceDistST ("mapD <" ++ measureD x ++ ">")
-                              return (f x))) -}
-             (runDistST g (myD d >>= return . f))
--}
 
 {-# RULES
 
@@ -82,22 +90,6 @@ mapD g f !d = checkGangD (here "mapD") g d
 "imapD/imapD" forall gang f g d.
   imapD gang f (imapD gang g d) = imapD gang (\i x -> f i (g i x)) d
 
-"zipD/imapD[1]" forall gang f xs ys.
-  zipD (imapD gang f xs) ys
-    = imapD gang (\i (x,y) -> (f i x,y)) (zipD xs ys)
-
-"zipD/imapD[2]" forall gang f xs ys.
-  zipD xs (imapD gang f ys)
-    = imapD gang (\i (x,y) -> (x, f i y)) (zipD xs ys)
-
-"zipD/generateD[1]" forall gang f xs.
-  zipD (generateD gang f) xs
-    = imapD gang (\i x -> (f i, x)) xs
-
-"zipD/generateD[2]" forall gang f xs.
-  zipD xs (generateD gang f)
-    = imapD gang (\i x -> (x, f i)) xs
-
   #-}
 
 {- RULES
@@ -117,22 +109,45 @@ mapD g f !d = checkGangD (here "mapD") g d
   zipD xs (mapD gang f ys)
     = mapD gang (unsafe_pairS . (\(xs, ys) -> (xs, f ys)) . unsafe_unpairS)
                 (zipD xs ys)
-
   -}
 
--- zipD, unzipD, fstD, sndD reexported from Types
 
+-- Zipping --------------------------------------------------------------------
 -- | Combine two distributed values with the given function.
 zipWithD :: (DT a, DT b, DT c)
          => Gang -> (a -> b -> c) -> Dist a -> Dist b -> Dist c
 {-# INLINE zipWithD #-}
 zipWithD g f dx dy = mapD g (uncurry f) (zipD dx dy)
 
+
+-- | Combine two distributed values with the given function.
+--   The worker function also gets the index of the current thread.
 izipWithD :: (DT a, DT b, DT c)
           => Gang -> (Int -> a -> b -> c) -> Dist a -> Dist b -> Dist c
 {-# INLINE izipWithD #-}
 izipWithD g f dx dy = imapD g (\i -> uncurry (f i)) (zipD dx dy)
 
+{-# RULES
+"zipD/imapD[1]" forall gang f xs ys.
+  zipD (imapD gang f xs) ys
+    = imapD gang (\i (x,y) -> (f i x,y)) (zipD xs ys)
+
+"zipD/imapD[2]" forall gang f xs ys.
+  zipD xs (imapD gang f ys)
+    = imapD gang (\i (x,y) -> (x, f i y)) (zipD xs ys)
+
+"zipD/generateD[1]" forall gang f xs.
+  zipD (generateD gang f) xs
+    = imapD gang (\i x -> (f i, x)) xs
+
+"zipD/generateD[2]" forall gang f xs.
+  zipD xs (generateD gang f)
+    = imapD gang (\i x -> (x, f i)) xs
+
+  #-}
+
+
+-- Folding --------------------------------------------------------------------
 -- | Fold a distributed value.
 foldD :: DT a => Gang -> (a -> a -> a) -> Dist a -> a
 -- {-# INLINE_DIST foldD #-}
@@ -145,6 +160,7 @@ foldD g f !d = checkGangD ("here foldD") g d $
     fold i x | i == n    = x
              | otherwise = fold (i+1) (f x $ d `indexD` i)
 
+
 -- | Prefix sum of a distributed value.
 scanD :: forall a. DT a => Gang -> (a -> a -> a) -> a -> Dist a -> (Dist a, a)
 {-# NOINLINE scanD #-}
@@ -162,6 +178,7 @@ scanD g f z !d = checkGangD (here "scanD") g d $
                                  writeMD md i x
                                  scan md (i+1) (f x $ d `indexD` i)
 
+-- | Combination of map and fold.
 mapAccumLD :: forall a b acc. (DT a, DT b)
            => Gang -> (acc -> a -> (acc,b))
                    -> acc -> Dist a -> (acc,Dist b)
@@ -181,6 +198,8 @@ mapAccumLD g f acc !d = checkGangD (here "mapAccumLD") g d $
                                               writeMD md i b
                                               go md (i+1) acc'
                                 
+
+-- Versions that work on DistST -----------------------------------------------
 -- NOTE: The following combinators must be strict in the Dists because if they
 -- are not, the Dist might be evaluated (in parallel) when it is requested in
 -- the current computation which, again, is parallel. This would break our
index 8f7e51d..baf9d98 100644 (file)
 --
 -- /TODO:/ Add facilities for implementing parallel scans etc.
 --
-
 module Data.Array.Parallel.Unlifted.Distributed.DistST (
   DistST, stToDistST, distST_, distST, runDistST, runDistST_seq, traceDistST,
-
   myIndex, myD, readMyMD, writeMyMD
 ) where
 
@@ -33,7 +31,11 @@ import Data.Array.Parallel.Unlifted.Distributed.Types (
 
 import Control.Monad (liftM)
 
+
 -- | Data-parallel computations.
+--   When applied to a thread gang, the computation implicitly knows the index
+--   of the thread it's working on. Alternatively, if we know the thread index
+--   then we can make a regular ST computation.
 newtype DistST s a = DistST { unDistST :: Int -> ST s a }
 
 instance Monad (DistST s) where
@@ -45,52 +47,60 @@ instance Monad (DistST s) where
                                     x <- p i
                                     unDistST (f x) i
 
+
 -- | Yields the index of the current thread within its gang.
 myIndex :: DistST s Int
 {-# INLINE myIndex #-}
 myIndex = DistST return
 
--- | Lifts an 'ST' computation into the 'DistST' monad. The lifted computation
--- should be data parallel.
+
+-- | Lifts an 'ST' computation into the 'DistST' monad.
+--   The lifted computation should be data parallel.
 stToDistST :: ST s a -> DistST s a
 {-# INLINE stToDistST #-}
 stToDistST p = DistST $ \i -> p
 
+
 -- | Yields the 'Dist' element owned by the current thread.
 myD :: DT a => Dist a -> DistST s a
 {-# NOINLINE myD #-}
 myD dt = liftM (indexD dt) myIndex
 
+
 -- | Yields the 'MDist' element owned by the current thread.
 readMyMD :: DT a => MDist a s -> DistST s a
 {-# NOINLINE readMyMD #-}
-readMyMD mdt = do
-                 i <- myIndex
-                 stToDistST $ readMD mdt i
+readMyMD mdt 
+ = do  i <- myIndex
+       stToDistST $ readMD mdt i
+
 
 -- | Writes the 'MDist' element owned by the current thread.
 writeMyMD :: DT a => MDist a s -> a -> DistST s ()
 {-# NOINLINE writeMyMD #-}
-writeMyMD mdt x = do
-                    i <- myIndex
-                    stToDistST $ writeMD mdt i x
+writeMyMD mdt x 
+ = do  i <- myIndex
+       stToDistST $ writeMD mdt i x
+
 
 -- | Execute a data-parallel computation on a 'Gang'.
+--   The same DistST comutation runs on each thread.
 distST_ :: Gang -> DistST s () -> ST s ()
 {-# INLINE distST_ #-}
 distST_ g = gangST g . unDistST
 
+
 -- | Execute a data-parallel computation, yielding the distributed result.
 distST :: DT a => Gang -> DistST s a -> ST s (Dist a)
 {-# INLINE distST #-}
-distST g p = do
-               md <- newMD g
-               distST_ g $ writeMyMD md =<< p
-               unsafeFreezeMD md
+distST g p 
+ = do  md <- newMD g
+        distST_ g $ writeMyMD md =<< p
+        unsafeFreezeMD md
+
 
 -- | Run a data-parallel computation, yielding the distributed result.
 runDistST :: DT a => Gang -> (forall s. DistST s a) -> Dist a
--- {-# INLINE runDistST #-}
 {-# NOINLINE runDistST #-}
 runDistST g p = runST (distST g p)
 
index c73ef58..fd4cab9 100644 (file)
@@ -9,11 +9,11 @@
 -- Portability :  non-portable (GHC Extensions)
 --
 -- Distributed scalars.
+-- With a distributed value like (Dist Int), each thread has its own integer, 
+-- which may or may not have the same values as the ones on other threads.
 --
-
 module Data.Array.Parallel.Unlifted.Distributed.Scalars (
   unitD, scalarD,
-
   orD, andD, sumD
 ) where
 
@@ -24,24 +24,27 @@ import Data.Array.Parallel.Unlifted.Distributed.Types (
 import Data.Array.Parallel.Unlifted.Distributed.Combinators (
   mapD, foldD)
 
+
 -- unitD reexported from Types
 
+
 -- | Distribute a scalar.
+--   Each thread gets its own copy of the same value.
 scalarD :: DT a => Gang -> a -> Dist a
 scalarD g x = mapD g (const x) (unitD g)
 
--- |
---
+
+-- | OR together all instances of a distributed 'Bool'.
 orD :: Gang -> Dist Bool -> Bool
 orD g = foldD g (||)
 
--- |
---
+
+-- | AND together all instances of a distributed 'Bool'.
 andD :: Gang -> Dist Bool -> Bool
 andD g = foldD g (&&)
 
--- |
---
+
+-- | Sum all instances of a distributed number.
 sumD :: (Num a, DT a) => Gang -> Dist a -> a
 sumD g = foldD g (+)
 
index 0ff4de4..b76926a 100644 (file)
@@ -59,13 +59,12 @@ infixl 9 `indexD`
 
 here s = "Data.Array.Parallel.Unlifted.Distributed.Types." ++ s
 
--- |Distributed types
--- ----------------------------
 
+-- Distributed Types ----------------------------------------------------------
 -- | Class of distributable types. Instances of 'DT' can be
--- distributed across all workers of a 'Gang'. All such types
--- must be hyperstrict as we do not want to pass thunks into distributed
--- computations.
+--   distributed across all workers of a 'Gang'. 
+--   All such types must be hyperstrict as we do not want to pass thunks
+--   into distributed computations.
 class DT a where
   data Dist  a
   data MDist a :: * -> *
@@ -74,8 +73,8 @@ class DT a where
   indexD         :: Dist a -> Int -> a
 
   -- | Create an unitialised distributed value for the given 'Gang'.
-  -- The gang is used (only) to know how many elements are needed
-  -- in the distributed value.
+  --   The gang is used (only) to know how many elements are needed
+  --   in the distributed value.
   newMD          :: Gang                  -> ST s (MDist a s)
 
   -- | Extract an element from a mutable distributed value.
@@ -90,83 +89,137 @@ class DT a where
   deepSeqD       :: a -> b -> b
   deepSeqD = seq
 
-  -- | Number of elements in the distributed value. This is for debugging
-  -- only.
+
+  -- Debugging ------------------------
+  -- | Number of elements in the distributed value.
+  --   For debugging only, as we shouldn't depend on the size of the gang.
   sizeD :: Dist a -> Int
 
-  -- | Number of elements in the mutable distributed value. This is for
-  -- debugging only.
+  -- | Number of elements in the mutable distributed value.
+  --   For debugging only, as we shouldn't care about the actual number.
   sizeMD :: MDist a s -> Int
 
+  -- | Show a distributed value.
+  --   For debugging only.
   measureD :: a -> String
   measureD _ = "None"
 
--- Distributed values must always be hyperstrict.
--- instance DT a => HS (Dist a)
+-- Show instance (for debugging only)
+instance (Show a, DT a) => Show (Dist a) where
+  show d = show (Prelude.map (indexD d) [0 .. sizeD d - 1])
+
 
+
+-- Checking -------------------------------------------------------------------
 -- | Check that the sizes of the 'Gang' and of the distributed value match.
 checkGangD :: DT a => String -> Gang -> Dist a -> b -> b
 checkGangD loc g d v = checkEq loc "Wrong gang" (gangSize g) (sizeD d) v
 
--- | Check that the sizes of the 'Gang' and of the mutable distributed value
--- match.
+
+-- | Check that the sizes of the 'Gang' and of the mutable distributed value match.
 checkGangMD :: DT a => String -> Gang -> MDist a s -> b -> b
 checkGangMD loc g d v = checkEq loc "Wrong gang" (gangSize g) (sizeMD d) v
 
--- Show instance (for debugging only)
-instance (Show a, DT a) => Show (Dist a) where
-  show d = show (Prelude.map (indexD d) [0 .. sizeD d - 1])
 
--- | 'DT' instances
--- ----------------
+-- Operations -----------------------------------------------------------------
+-- | Given a computation that can write its result to a mutable distributed value, 
+--   run the computation to generate an immutable distributed value.
+newD :: DT a => Gang -> (forall s . MDist a s -> ST s ()) -> Dist a
+newD g init =
+  runST (do
+           mdt <- newMD g
+           init mdt
+           unsafeFreezeMD mdt)
 
-instance DT () where
-  data Dist ()    = DUnit  !Int
-  data MDist () s = MDUnit !Int
+-- | Show all members of a distributed value.
+debugD :: DT a => Dist a -> String
+debugD d = "["
+         ++ intercalate "," [measureD (indexD d i) | i <- [0 .. sizeD d-1]]
+         ++ "]"
 
-  indexD  (DUnit n) i       = check (here "indexD[()]") n i $ ()
-  newMD                     = return . MDUnit . gangSize
-  readMD   (MDUnit n) i     = check (here "readMD[()]")  n i $
-                               return ()
-  writeMD  (MDUnit n) i ()  = check (here "writeMD[()]") n i $
-                               return ()
-  unsafeFreezeMD (MDUnit n) = return $ DUnit n
 
+-- DPrim ----------------------------------------------------------------------
+-- | For distributed primitive values, we can just store all the members in
+--   a vector. The vector has the same length as the number of threads in the gang.
+--
 class Unbox e => DPrim e where
+
+  -- | Make an immutable distributed value.
   mkDPrim :: V.Vector e -> Dist  e
+
+  -- | Unpack an immutable distributed value back into a vector.
   unDPrim :: Dist  e -> V.Vector e
 
+  -- | Make a mutable distributed value.
   mkMDPrim :: MV.STVector s e -> MDist  e s
+
+  -- | Unpack a mutable distributed value back into a vector.
   unMDPrim :: MDist  e s -> MV.STVector s e
 
+
+-- | Get the member corresponding to a thread index.
 primIndexD :: DPrim a => Dist a -> Int -> a
 {-# INLINE primIndexD #-}
 primIndexD = (V.!) . unDPrim
 
+
+-- | Create a new distributed value, having as many members as threads
+--   in the given 'Gang'.
 primNewMD :: DPrim a => Gang -> ST s (MDist a s)
 {-# INLINE primNewMD #-}
 primNewMD = liftM mkMDPrim . MV.new . gangSize
 
+
+-- | Read the member of a distributed value corresponding to the given thread index.
 primReadMD :: DPrim a => MDist a s -> Int -> ST s a
 {-# INLINE primReadMD #-}
 primReadMD = MV.read . unMDPrim
 
+-- | Write the member of a distributed value corresponding to the given thread index.
 primWriteMD :: DPrim a => MDist a s -> Int -> a -> ST s ()
 {-# INLINE primWriteMD #-}
 primWriteMD = MV.write . unMDPrim
 
+-- | Freeze a mutable distributed value to an immutable one.
+--   You promise not to update the mutable one any further.
 primUnsafeFreezeMD :: DPrim a => MDist a s -> ST s (Dist a)
 {-# INLINE primUnsafeFreezeMD #-}
 primUnsafeFreezeMD = liftM mkDPrim . V.unsafeFreeze . unMDPrim
 
+
+-- | Get the size of a distributed value, that is, the number of threads
+--   in the gang that it was created for.
 primSizeD :: DPrim a => Dist a -> Int
 {-# INLINE primSizeD #-}
 primSizeD = V.length . unDPrim
 
+-- | Get the size of a distributed mutable value, that is, the number of threads
+--   in the gang it was created for.
 primSizeMD :: DPrim a => MDist a s -> Int
 {-# INLINE primSizeMD #-}
 primSizeMD = MV.length . unMDPrim
 
+
+-- Unit -----------------------------------------------------------------------
+instance DT () where
+  data Dist ()    = DUnit  !Int
+  data MDist () s = MDUnit !Int
+
+  indexD  (DUnit n) i       = check (here "indexD[()]") n i $ ()
+  newMD                     = return . MDUnit . gangSize
+  readMD   (MDUnit n) i     = check (here "readMD[()]")  n i $
+                               return ()
+  writeMD  (MDUnit n) i ()  = check (here "writeMD[()]") n i $
+                               return ()
+  unsafeFreezeMD (MDUnit n) = return $ DUnit n
+
+-- | Yield a distributed unit.
+unitD :: Gang -> Dist ()
+{-# INLINE_DIST unitD #-}
+unitD = DUnit . gangSize
+
+
+-- Bool -----------------------------------------------------------------------
 instance DPrim Bool where
   mkDPrim           = DBool
   unDPrim (DBool a) = a
@@ -186,6 +239,8 @@ instance DT Bool where
   sizeD          = primSizeD
   sizeMD         = primSizeMD
 
+
+-- Char -----------------------------------------------------------------------
 instance DPrim Char where
   mkDPrim           = DChar
   unDPrim (DChar a) = a
@@ -205,6 +260,8 @@ instance DT Char where
   sizeD          = primSizeD
   sizeMD         = primSizeMD
 
+
+-- Int ------------------------------------------------------------------------
 instance DPrim Int where
   mkDPrim          = DInt
   unDPrim (DInt a) = a
@@ -226,6 +283,8 @@ instance DT Int where
 
   measureD n = "Int " ++ show n
 
+
+-- Word8 ----------------------------------------------------------------------
 instance DPrim Word8 where
   mkDPrim            = DWord8
   unDPrim (DWord8 a) = a
@@ -245,6 +304,8 @@ instance DT Word8 where
   sizeD          = primSizeD
   sizeMD         = primSizeMD
 
+
+-- Float ----------------------------------------------------------------------
 instance DPrim Float where
   mkDPrim            = DFloat
   unDPrim (DFloat a) = a
@@ -264,6 +325,8 @@ instance DT Float where
   sizeD          = primSizeD
   sizeMD         = primSizeMD
 
+
+-- Double ---------------------------------------------------------------------
 instance DPrim Double where
   mkDPrim             = DDouble
   unDPrim (DDouble a) = a
@@ -283,6 +346,8 @@ instance DT Double where
   sizeD          = primSizeD
   sizeMD         = primSizeMD
 
+
+-- Pairs ----------------------------------------------------------------------
 instance (DT a, DT b) => DT (a,b) where
   data Dist  (a,b)   = DProd  !(Dist a)    !(Dist b)
   data MDist (a,b) s = MDProd !(MDist a s) !(MDist b s)
@@ -304,6 +369,31 @@ instance (DT a, DT b) => DT (a,b) where
 
   measureD (x,y) = "Pair " ++ "(" ++ measureD x ++ ") (" ++  measureD y ++ ")"
 
+
+-- | Pairing of distributed values.
+-- /The two values must belong to the same/ 'Gang'.
+zipD :: (DT a, DT b) => Dist a -> Dist b -> Dist (a,b)
+{-# INLINE [0] zipD #-}
+zipD !x !y = checkEq (here "zipDT") "Size mismatch" (sizeD x) (sizeD y) $
+             DProd x y
+
+-- | Unpairing of distributed values.
+unzipD :: (DT a, DT b) => Dist (a,b) -> (Dist a, Dist b)
+{-# INLINE_DIST unzipD #-}
+unzipD (DProd dx dy) = (dx,dy)
+
+-- | Extract the first elements of a distributed pair.
+fstD :: (DT a, DT b) => Dist (a,b) -> Dist a
+{-# INLINE_DIST fstD #-}
+fstD = fst . unzipD
+
+-- | Extract the second elements of a distributed pair.
+sndD :: (DT a, DT b) => Dist (a,b) -> Dist b
+{-# INLINE_DIST sndD #-}
+sndD = snd . unzipD
+
+
+-- Maybe ----------------------------------------------------------------------
 instance DT a => DT (Maybe a) where
   data Dist  (Maybe a)   = DMaybe  !(Dist  Bool)   !(Dist  a)
   data MDist (Maybe a) s = MDMaybe !(MDist Bool s) !(MDist a s)
@@ -333,32 +423,8 @@ instance DT a => DT (Maybe a) where
   measureD Nothing = "Nothing"
   measureD (Just x) = "Just (" ++ measureD x ++ ")"
 
-{-
-instance DT a => DT (MaybeS a) where
-  data Dist  (MaybeS a)   = DMaybe  !(Dist  Bool)   !(Dist  a)
-  data MDist (MaybeS a) s = MDMaybe !(MDist Bool s) !(MDist a s)
-
-  indexD (DMaybe bs as) i
-    | bs `indexD` i       = JustS $ as `indexD` i
-    | otherwise           = NothingS
-  newMD g = liftM2 MDMaybe (newMD g) (newMD g)
-  readMD (MDMaybe bs as) i =
-    do
-      b <- readMD bs i
-      if b then liftM JustS $ readMD as i
-           else return NothingS
-  writeMD (MDMaybe bs as) i NothingS  = writeMD bs i False
-  writeMD (MDMaybe bs as) i (JustS x) = writeMD bs i True
-                                     >> writeMD as i x
-  unsafeFreezeMD (MDMaybe bs as) = liftM2 DMaybe (unsafeFreezeMD bs)
-                                                 (unsafeFreezeMD as)
-  sizeD  (DMaybe  b _) = sizeD  b
-  sizeMD (MDMaybe b _) = sizeMD b
-
-  measureD NothingS = "Nothing"
-  measureD (JustS x) = "Just (" ++ measureD x ++ ")"
--}
 
+-- Vector ---------------------------------------------------------------------
 instance Unbox a => DT (V.Vector a) where
   data Dist  (Vector a)   = DVector  !(Dist  Int)   !(BV.Vector      (Vector a))
   data MDist (Vector a) s = MDVector !(MDist Int s) !(MBV.STVector s (Vector a))
@@ -378,6 +444,13 @@ instance Unbox a => DT (V.Vector a) where
 
   measureD xs = "Vector " ++ show (V.length xs)
 
+
+-- | Yield the distributed length of a distributed array.
+lengthD :: Unbox a => Dist (Vector a) -> Dist Int
+lengthD (DVector l _) = l
+
+
+-- USegd ----------------------------------------------------------------------
 instance DT USegd where
   data Dist  USegd   = DUSegd  !(Dist (Vector Int))
                                !(Dist (Vector Int))
@@ -426,74 +499,3 @@ elementsUSegdD :: Dist USegd -> Dist Int
 {-# INLINE_DIST elementsUSegdD #-}
 elementsUSegdD (DUSegd _ _ dns) = dns
 
--- |Basic operations on immutable distributed types
--- -------------------------------------------
-
-newD :: DT a => Gang -> (forall s . MDist a s -> ST s ()) -> Dist a
-newD g init =
-  runST (do
-           mdt <- newMD g
-           init mdt
-           unsafeFreezeMD mdt)
-                    
-
--- | Yield a distributed unit.
-unitD :: Gang -> Dist ()
-{-# INLINE_DIST unitD #-}
-unitD = DUnit . gangSize
-
--- | Pairing of distributed values.
--- /The two values must belong to the same/ 'Gang'.
-zipD :: (DT a, DT b) => Dist a -> Dist b -> Dist (a,b)
-{-# INLINE [0] zipD #-}
-zipD !x !y = checkEq (here "zipDT") "Size mismatch" (sizeD x) (sizeD y) $
-             DProd x y
-
--- | Unpairing of distributed values.
-unzipD :: (DT a, DT b) => Dist (a,b) -> (Dist a, Dist b)
-{-# INLINE_DIST unzipD #-}
-unzipD (DProd dx dy) = (dx,dy)
-
--- | Extract the first elements of a distributed pair.
-fstD :: (DT a, DT b) => Dist (a,b) -> Dist a
-{-# INLINE_DIST fstD #-}
-fstD = fst . unzipD
-
--- | Extract the second elements of a distributed pair.
-sndD :: (DT a, DT b) => Dist (a,b) -> Dist b
-{-# INLINE_DIST sndD #-}
-sndD = snd . unzipD
-
-{-
--- | Pairing of distributed values.
--- /The two values must belong to the same/ 'Gang'.
-zipSD :: (DT a, DT b) => Dist a -> Dist b -> Dist (a,b)
-{-# INLINE [0] zipSD #-}
-zipSD !x !y = checkEq (here "zipSD") "Size mismatch" (sizeD x) (sizeD y) $
-              SDProd x y
-
--- | Unpairing of distributed values.
-unzipSD :: (DT a, DT b) => Dist (a,b) -> (Dist a, Dist b)
-{-# INLINE_DIST unzipSD #-}
-unzipSD (SDProd dx dy) = (dx,dy)
-
--- | Extract the first elements of a distributed pair.
-fstSD :: (DT a, DT b) => Dist (a,b) -> Dist a
-{-# INLINE_DIST fstSD #-}
-fstSD = fst . unzipSD
-
--- | Extract the second elements of a distributed pair.
-sndSD :: (DT a, DT b) => Dist (a,b) -> Dist b
-{-# INLINE_DIST sndSD #-}
-sndSD = snd . unzipSD
--}
-
--- | Yield the distributed length of a distributed array.
-lengthD :: Unbox a => Dist (Vector a) -> Dist Int
-lengthD (DVector l _) = l
-
-debugD :: DT a => Dist a -> String
-debugD d = "["
-         ++ intercalate "," [measureD (indexD d i) | i <- [0 .. sizeD d-1]]
-         ++ "]"
-