Control.Parallel.Eden.DivConq

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 )

Divide-and-conquer scheme

type DivideConquer a b

Arguments

 = (a -> Bool)

trivial?

-> (a -> b)

solve

-> (a -> [a])

split

-> (a -> [b] -> b)

combine

-> a

input

-> b

result

type DivideConquerSimple a b

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

Sequential Version.

Distributed expansion divide-and-conquer skeletons

Straightforward implementation for arbitrary DC problems

parDC

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

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

Arguments

:: Trans b

=> Int

branching degree

-> [Int]

tickets

-> DivideConquer a b

offline distributed-expansion divide-and-conquer skeleton.

disDCdepth

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

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

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

Deprecated: better use dc instead

Like dc but uses simple DC Interface.

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

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

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

Deprecated: better use parDC instead

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

divConD

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

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

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

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'

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'

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

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

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

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

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.