From: quixoticsycophant@...
Date: 2008-09-09T16:03:45+09:00
Subject: [ANN] CompTree: Parallel Computation Tree

= CompTree: Parallel Computation Tree

== Synopsis

  require 'comp_tree'

  CompTree::Driver.new { |driver|

    # Define a function named 'area' taking these three arguments.
    driver.define_area(:width, :height, :offset) { |width, height,
offset|
      width*height - offset
    }

    # Define a function 'width' which takes a 'border' argument.
    driver.define_width(:border) { |border|
      2 + border
    }

    # Ditto for 'height'.
    driver.define_height(:border) { |border|
      3 + border
    }

    # Define a constant function 'border'.
    driver.define_border {
      5
    }

    # Ditto for 'offset'.
    driver.define_offset {
      7
    }

    # Compute the area using four parallel threads.
    area = driver.compute(:area, :threads => 4)

    # We've done this computation.
    if area == (2 + 5)*(3 + 5) - 7
      puts "It worked!"
    else
      puts "Send bug report to ..."
    end
  }

=== Alternative Forms for Function Definitions

This form evals a lambda, saving you the repeat parameter list:

  driver.define_area :width, :height, :offset, %{
    width*height - offset
  }

  driver.define_width :border, %{
    2 + border
  }

Notice the '%' before the brace.  The lambda is created just once,
during the time of definition.

Finally there is the raw form which uses no +eval+ or
+method_missing+ tricks:

  driver.define(:area, :width, :height, :offset) { |width, height,
offset|
    width*height - offset
  }

  driver.define(:width, :border) { |border|
    2 + border
  }

== Important Notes

The user should have a basic understanding of functional programming
(see for example http://en.wikipedia.org/wiki/Functional_programming)
and the meaning of side effects.

CompTree requires the user to adopt a functional style.  Every
function you define must explicitly depend on the data it uses.

  #
  # BAD example: depending on state -- offset not listed as a
parameter
  #
  driver.define_area(:width, :height) { |width, height|
    width*height - offset
  }

Unless offset is really a constant, the result of
driver.compute(:area, :num_threads => n) is not well-defined for n>1.

Just as depending on some changeable state is bad, it is likewise bad
to affect a state (to produce a side effect).

  #
  # BAD example: affecting state
  #
  driver.define_area(:width, :height, :offset) { |width, height,
offset|
    ACCUMULATOR.add "more data"
    width*height - offset
  }

Given a tree where nodes are modifying _ACCUMULATOR_, the end state of
_ACCUMULATOR_ is not well-defined.  Moreover if _ACCUMULATOR_ is not
thread-safe, the result will be even worse.

Note however it is OK affect a state as long as no other function
depends on that state.  This is the principle under which +comp_tree+
parallelizes Rake tasks (http://drake.rubyforge.org).

== Install

  % gem install comp_tree

Or for the regular (non-gem) .tgz package,

  % ruby install.rb [--uninstall]

== Links

* Download: http://rubyforge.org/frs/?group_id=6917
* Rubyforge home: http://rubyforge.org/projects/comptree
* Repository: http://github.com/quix/comp_tree

== Author

* James M. Lawrence <quixoticsycophant@gmail.com>