Copyright	(c) Philipps Universitaet Marburg 2009-2014
License	BSD-style (see the file LICENSE)
Maintainer	eden@mathematik.uni-marburg.de
Stability	beta
Portability	not portable
Safe Haskell	None
Language	Haskell98

Control.Parallel.Eden.DivConq

Contents

Divide-and-conquer scheme
Sequential divide-and-conquer
Distributed expansion divide-and-conquer skeletons
- Straightforward implementation for arbitrary DC problems
- Divide-and-conquer skeleton for regular n-ary trees
Flat expansion divide-and-conquer skeletons
Deprecated divide-and-conquer skeletons (legacy code)

Description

This Haskell module defines divide-and-conquer skeletons for the parallel functional language Eden.

All divide-and-conquer algorithms are parameterised with control functions which decide if a problem is trivial, how to solve a trivial problem, how to split a non-trivial problem into smaller problems and how to combine solutions of subproblems into a solution of the problem.

Depends on GHC. Using standard GHC, you will get a threaded simulation of Eden. Use the forked GHC-Eden compiler from http://www.mathematik.uni-marburg.de/~eden for a parallel build.

Eden Group ( http://www.mathematik.uni-marburg.de/~eden )

Synopsis

Divide-and-conquer scheme

type DivideConquer a b Source

Arguments

= (a -> Bool)	trivial?
-> (a -> b)	solve
-> (a -> [a])	split
-> (a -> [b] -> b)	combine
-> a	input
-> b	result

type DivideConquerSimple a b Source

Arguments

= (a -> Bool)	trivial?
-> (a -> b)	solve
-> (a -> [a])	split
-> ([b] -> b)	combine (only uses sub-results, not the input)
-> a	input
-> b	result

The simple interface (deprecated): combine function without input

Sequential divide-and-conquer

dc :: DivideConquer a b Source

Sequential Version.

Distributed expansion divide-and-conquer skeletons

Straightforward implementation for arbitrary DC problems

parDC Source

Arguments

:: (Trans a, Trans b)
=> Int	parallel depth
-> DivideConquer a b

Simple parMap parallelisation with depth control but no placement control. This variant allows to give an additional depth parameter for the recursion, proceeding in a sequential manner when depth=0. The process scheme unfolds the call tree on processors chosen by the runtime environment. Round-Robin distribution is unfavourable for this skeleton, better use RTS option +RTS -qrnd when using it.

Divide-and-conquer skeleton for regular n-ary trees

disDC Source

Arguments

:: (Trans a, Trans b)
=> Int	branching degree
-> Places	tickets
-> DivideConquer a b

Distributed-expansion divide-and-conquer skeleton (tutorial version, similar to dcNTickets).

offline_disDC Source

Arguments

:: Trans b
=> Int	branching degree
-> [Int]	tickets
-> DivideConquer a b

offline distributed-expansion divide-and-conquer skeleton.

disDCdepth Source

Arguments

:: (Trans a, Trans b)
=> Int	branching degree
-> Int	parallel depth
-> DivideConquer a b

DC skeleton with fixed branching degree, parallel depth control and explicit process placement (tree-shaped process creation, one task in each recursive step stays local).

disDCn Source

Arguments

:: (Trans a, Trans b)
=> Int	branching degree
-> Int	number of processes
-> DivideConquer a b

Like disDCdepth, but controls parallelism by limiting the number of processes instead of the parallel depth.

Flat expansion divide-and-conquer skeletons

flatDC Source

Arguments

:: (Trans a, Trans b)
=> ((a -> b) -> [a] -> [b])	custom map implementation
-> Int	depth
-> DivideConquer a b

DC Skeleton with flat expansion of upper DC-tree levels, takes custom map skeletons to solve expanded tasks (a sequential map skeleton leads to a sequential DC-skeleton).

Deprecated divide-and-conquer skeletons (legacy code)

Deprecated sequential divide-and-conquer

divConSeq :: (Trans a, Trans b) => DivideConquerSimple a b Source

Deprecated: better use dc instead

Like dc but uses simple DC Interface.

divConSeq_c :: (Trans a, Trans b) => DivideConquer a b Source

Deprecated: better use dc instead

Tutorial version, same as dc

Deprecated straightforward implementations for arbitrary DC problems

divCon :: (Trans a, Trans b) => DivideConquerSimple a b Source

Deprecated: better use parDC instead

Straightforward implementation.

The straightforward method to parallelise divide-and-conquer algorithms is to unfold the call tree onto different processors. The process scheme unfolds the call tree on processors chosen by the runtime environment. Round-Robin distribution is unfavourable for this skeleton, better use runtime option -qrnd when using it.

divCon_c :: (Trans a, Trans b) => DivideConquer a b Source

Deprecated: better use parDC instead

Like divCon but with different combine signature (takes the original problem as additional input).

divConD Source

Arguments

:: (Trans a, Trans b)
=> Int	parallel depth
-> DivideConquerSimple a b

Deprecated: better use parDC instead

Like parDC but uses simple DC Interface.

divConD_c Source

Arguments

:: (Trans a, Trans b)
=> Int	parallel depth
-> DivideConquer a b

Deprecated: better use parDC instead

Tutorial version, same as parDC.

Deprecated divide-and-conquer skeleton for regular n-ary trees

dcN Source

Arguments

:: (Trans a, Trans b)
=> Int	branching degree
-> Int	parallel depth
-> DivideConquerSimple a b

Deprecated: better use disDCdepth instead

Like disDCdepth but uses simple DC Interface.

dcN_c Source

Arguments

:: (Trans a, Trans b)
=> Int	branching degree
-> Int	parallel depth
-> DivideConquer a b

Deprecated: better use disDCdepth instead

Tutorial version, same as disDCdepth

dcN' Source

Arguments

:: (Trans a, Trans b)
=> Int	branching degree
-> Int	number of processes
-> DivideConquerSimple a b

Deprecated: better use disDCn instead

Like disDCn but uses simple DC Interface.

dcN_c' Source

Arguments

:: (Trans a, Trans b)
=> Int	branching degree
-> Int	number of processes
-> DivideConquer a b

Deprecated: better use disDCn instead

Tutorial version, same as disDCn.

dcNTickets Source

Arguments

:: (Trans a, Trans b)
=> Int	branching degree
-> Places	tickets (places to use)
-> DivideConquerSimple a b

Deprecated: better use disDC instead

Like disDC, but differs in demand control and uses simple DC Interface.

dcNTickets_c Source

Arguments

:: (Trans a, Trans b)
=> Int	branching degree
-> Places	Tickets (places to use)
-> DivideConquer a b

Deprecated: better use disDC instead

Like disDC, but differs in demand control.

Deprecated flat expansion divide-and-conquer skeletons

divConFlat Source

Arguments

:: (Trans a, Trans b)
=> ((a -> b) -> [a] -> [b])	custom map implementation
-> Int	depth
-> DivideConquerSimple a b

Deprecated: better use flatDC instead

Like as flatDC but uses simple DC Interface.

divConFlat_c Source

Arguments

:: (Trans a, Trans b)
=> ((a -> b) -> [a] -> [b])	custom map implementation
-> Int	parallel depth
-> DivideConquer a b

Deprecated: better use flatDC instead

Tutorial version, same as flatDC.