%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% %
% Eden Porting Project, Philipps-Universität Marburg %
% %
% Exercise version, workpool incomplete %
% %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{code}
{-# OPTIONS -cpp #-}
module EdenSkel (parMap,
farm,
dm,
eagerInstList,
shuffle, unshuffleN
) where
import Eden
import List
\end{code}
\section{Eden Skeletons}
This module contains essential Eden Skeletons described in
research papers: ParMap, Farm, Direct Mapping.
\begin{code}
-- The skeletons
----------------
-- basic: parMap
parMap :: (Trans a, Trans b) =>
Process a b -> [a] -> [b]
parMap p xs =
eagerInstList (repeat p) xs
-- process farm
farm :: (Trans a, Trans b) =>
Int -> (Int -> [a] -> [[a]]) -- n, distribute
-> ([[b]] -> [b]) -- combine
-> Process [a] [b] -- worker process
-> [a] -> [b] -- what to do
farm np distr combine p inputs =
combine (parMap p (distr np inputs))
-- direct mapping
dm :: (Trans a, Trans b) =>
Int -> (Int -> [a] -> [[a]]) -> ([[b]] -> [b])
-> ([a] -> Process () [b])
-> [a] -> [b]
dm np split combine proc inputs = combine results
where
results = eagerInstList proclist (repeat void)
proclist = [ proc (extract i np inputs)| i <- [0..(np-1)] ]
extract i n inputs = (split n inputs)!!i
\end{code}
\section{Eager Process Instantiation}
These are the functions to create eagerly instantiated processes in programs
(a very common task in Eden programs). Lists are eagerly instantiated by
evaluating each element to WHNF.
This function uses the internals createProcess and Lift to avoid waiting
for a result after process creation (core transformation not implemented).
%------------------------------
\begin{code}
cpTL :: (Trans a, Trans b) => Process a b -> a -> Lift b
cpTL = createProcess
-- Front End Function:
----------------------
{- eagerInstList zips a list of processes and their input.
All processes are instantiated on the way.-}
eagerInstList :: (Trans a, Trans b) =>
[Process a b ] -> [a] -> [b]
eagerInstList ps xs = let insts = zipWith (cpTL) ps xs
in tlList insts
-- Helpers:
-----------
-- tlList: force the instantiation of the element processes and return the list of results
tlList :: [Lift a] -> [a]
-- tlList insts = foldr1 (seq) insts
tlList insts = forceWHNFSpine insts
`seq` (map deLift insts)
-- forceWHNFSpine: evaluate all elements of the list to WHNF
forceWHNFSpine :: [a] -> ()
forceWHNFSpine [] = ()
forceWHNFSpine (x:xs) = x `seq` forceWHNFSpine xs
-- tlLList: the same for an list of lists
tlLList :: [[Lift a]] -> [[a]]
-- tlLList insts = foldr1 (seq) (foldr1 (seq) insts)
tlLList insts = forceWHNFSpine (map forceWHNFSpine insts)
`seq` (map (map deLift) insts)
\end{code}
\section{Helpers}
Some functions to distribute and combine a list.
\begin{code}
{- unshuffleN splits a list into n lists
[takeEach n (drop i xs) | i <- [0..(n-1)]] -}
unshuffleN :: Int -> [a] -> [[a]]
unshuffleN n xs = unshuffle xs
where unshuffle xs = map (f xs) [0..n-1]
where f xs i = g (drop i xs)
g [] = []
g xs = head xs : (g (drop n xs))
-- simple shuffling (not incremental!)
shuffle :: [[a]] -> [a]
shuffle = concat . transpose
void = ()
\end{code}