Advice wanted on parallel processing

[Daniel Fischer]

Am Mittwoch, 18. März 2009 15:28 schrieb Colin Paul Adams:
> I've just managed to build ghc 6.11 (Thanks Simon).
>
> I did this for two reasons, one of which is I want to try to improve
> the speed of the AI for the Chu Shogi program I am writing by making
> use of parallel processing. I have a 4-core Xeon runing Fedora Linux
> 10 (AMD64).
>
> I have a repeatable scenario for timings. With ghc 6.10.1, no threaded
> runtime, the computer takes 51 or 52 seconds to move (experimental
> variation up to 1.2 seconds).
>
> With ghc 6.11, it takes the same time.
>
> If I switch on the threaded runtime, then it rises slightly (perhaps
> not significantly - I measure 53-54 seconds). With 2, 3 or 4
> processors, I measured (one-off, so not reliable) 65, 55 and 58
> seconds respectively.
>
> Well, that doesn't really matter, provided I can get the time back
> with interest by exploiting parallelism. My first thought for an
> "easy" win is the move generator. At present I have this code:
>
> -- | Generate all legal moves from state.
> --
> -- The best moves (according to some heuristic) should come first
> generate_moves :: (Non_interactive_state, Maybe Move) ->
> [(Non_interactive_state, Maybe Move)] generate_moves (state, _) =
>     let colour = case is_black_to_play state of
>                    True -> Black
>                    False -> White
>         pieces' = all_pieces_of_colour (board state) colour
>         unsorted = concatMap (generate_moves_for_piece state) pieces'
>         sorted = sortBy best_move unsorted
>         moves = mapMaybe new_move sorted
>     in {-trace (concat (intersperse "\n" (map (print_move . fromJust . snd)
> moves)))-} moves where new_move mv =
>                   case update_from_move (state, Nothing) mv of
>                     Nothing -> Nothing
>                     Just (st', Nothing) -> Just (st', Just mv)
>
>
> and my idea was to run the call to generate_moves_for_piece in
> parallel over the pieces' list. I thought I could do that simply by
> replacing concatMap with parFlatMap, but discovered I need to supply
> an extra argument - a Strategy. Not knowing what this should be
> (where's the best place to read up on this?) I tried specifying rwhnf.

Control.Parallel.Strategies, docs and source?

generate_moves_for_piece produces a list. rwhnf forces this list enough to see 
if it's [] or (_:_)
(rwhnf x = x `seq` ()), that doesn't get enough work done in each thread to 
compensate the overhead. Try using rnf after writing an NFData instance for 
Move.

If e.g.

data Move = Move {from :: Position, to :: Position}

, the instance would be

instance NFData Move where
	rnf (Move f t) = rnf f `seq` rnf t `seq` ()

That might require NFData instances for Position and its components, but 
specifying these should be automatic.

>
> My timings then are:
>
> -N1 83 seconds
> -N2 57 seconds
> -N3 58 seconds
> -N4 60 seconds
>
> so a complete failure.
>
> Where should I go from here?

HTH,
Daniel