edenskel-2.1.0.0: Semi-explicit parallel programming skeleton library

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

Control.Parallel.Eden.DivConq

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

Sequential Version.

# Distributed expansion divide-and-conquer skeletons

## Straightforward implementation for arbitrary DC problems

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

Arguments

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

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

Arguments

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

offline distributed-expansion divide-and-conquer skeleton.

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).

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

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).

Arguments

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

Deprecated: better use parDC instead

Like `parDC` but uses simple DC Interface.

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

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.

Arguments

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

Deprecated: better use disDCdepth instead

Tutorial version, same as `disDCdepth`

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.

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`.

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.

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

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.

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`.