Hackage :: [Package]

speculation: A framework for safe, programmable, speculative parallelism

[ bsd3, concurrency, library ] [ Propose Tags ] [ Report a vulnerability ]

A framework for safe, programmable, speculative parallelism, loosely based on http://research.microsoft.com/pubs/118795/pldi026-vaswani.pdf

spec g f a evaluates f g while forcing a, if g == a then f g is returned. Otherwise f a is evaluated.

Furthermore, if the argument has already been evaluated, we avoid sparking the parallel computation at all.

If a good guess at the value of a is available, this is one way to induce parallelism in an otherwise sequential task.

However, if the guess isn't available more cheaply than the actual answer, then this saves no work and if the guess is wrong, you risk evaluating the function twice.

spec a f a = f $! a

The best-case timeline looks like:

[---- f g ----]
   [----- a -----]
[-- spec g f a --]

The worst-case timeline looks like:

[---- f g ----]
   [----- a -----]
                 [---- f a ----]
[------- spec g f a -----------]

Compare these to the timeline of f $! a:

[---- a -----]
             [---- f a ----]

specSTM provides a similar time table for STM actions, but also rolls back side-effects.

Changes in 0.1.0:

  • Added Control.Concurrent.STM.Speculation with specSTM, and specSTM'

Changes in 0.0.2:

  • specFoldr1 bug fix

  • Added spec' combinator

Changes in 0.0.1:

  • Added WithoutSpeculation and WrappedFoldable

[Skip to Readme]

Downloads

Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees

Candidates

  • No Candidates
Versions [RSS] 0.0.0, 0.0.1, 0.0.2, 0.1.0, 0.2.0, 0.3.0, 0.4.0, 0.5.0, 0.5.1, 0.6.0, 0.7.0, 0.8.0, 0.8.0.1, 0.8.0.2, 0.8.1.0, 0.8.2.0, 0.9.0.0, 1.0.0.0, 1.1.0.0, 1.2.0.0, 1.2.0.1, 1.2.0.2, 1.3, 1.4, 1.4.1, 1.4.1.1, 1.4.1.2, 1.5, 1.5.0.1, 1.5.0.2, 1.5.0.3
Dependencies base (>=4 && <6), parallel (>=2.2 && <2.3), stm (>=2.1 && <2.2) [details]
Tested with ghc ==6.12.1
License BSD-3-Clause
Copyright (c) 2010 Edward A. Kmett
Author Edward A. Kmett
Maintainer Edward A. Kmett <ekmett@gmail.com>
Uploaded by EdwardKmett at 2010-06-27T11:26:05Z
Category Concurrency
Home page http://github.com/ekmett/speculation
Distributions
Reverse Dependencies 3 direct, 8598 indirect [details]
Downloads 25465 total (130 in the last 30 days)
Rating 2.0 (votes: 1) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs uploaded by user
Build status unknown [no reports yet]

Readme for speculation-0.2.0

[back to package description]

speculation

Speculative evaluation primitives for Haskell, very loosely based on the paper "Safe Programmable Speculative Parallelism" by Prabhu, Ramalingam, and Vaswani. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.19.4622

spec

spec :: Eq a => a -> (a -> b) -> a -> b

spec takes three arguments: An initial guess as to what the argument to the function will be when it is evaluated, a function to evaluate, and the actual argument to the function.

Spec checks to see if its actual argument has been evaluated, if so it just applies the function to the argument.

Otherwise, it begins evaluating the function with the guessed argument in parallel with evaluating the argument.

If you guessed right, then the result of applying the function to your guess is returned.

Otherwise, it then evaluates the function with the correct argument.

If a good guess is available, this permits us to increase parallelism in the resulting program.

It is subject to the following identity:

spec a f a = a `seq` f a

speculative folds

A number of speculative folds are also provided via the Speculative class.

These take an extra argument which is a function that guesses the result of of the fold up to a given point.

A minimal definition for Speculative can be derived automatically for any Foldable container.