begin of spawn documentation

1 files changed, 57 insertions, 0 deletions

diff --git a/doc/spawn.txt b/doc/spawn.txt
new file mode 100644
index 000000000..19560ebf5
--- /dev/null
+++ b/doc/spawn.txt
@@ -0,0 +1,57 @@
+==========================================================
+                  Parallel & Spawn
+==========================================================
+
+Nimrod has two flavors of parallelism: 
+1) `Structured`:idx parallelism via the ``parallel`` statement.
+2) `Unstructured`:idx: parallelism via the standalone ``spawn`` statement.
+
+Somewhat confusingly, ``spawn`` is also used in the ``parallel`` statement
+with slightly different semantics. ``spawn`` always takes a call expression of
+the form ``f(a, ...)``. Let ``T`` be ``f``'s return type. If ``T`` is ``void``
+then ``spawn``'s return type is also ``void``. Within a ``parallel`` section
+``spawn``'s return type is ``T``, otherwise it is ``FlowVar[T]``.
+
+The compiler can ensure the location in ``location = spawn f(...)`` is not
+read prematurely within a ``parallel`` section and so there is no need for
+the overhead of an indirection via ``FlowVar[T]`` to ensure correctness.
+
+
+Parallel statement
+==================
+
+The parallel statement is the preferred mechanism to introduce parallelism
+in a Nimrod program. A subset of the Nimrod language is valid within a
+``parallel`` section. This subset is checked to be free of data races at
+compile time. A sophisticated `disjoint checker`:idx: ensures that no data
+races are possible even though shared memory is extensively supported!
+
+The subset is in fact the full language with the following
+restrictions / changes:
+
+* ``spawn`` within a ``parallel`` section has special semantics.
+* Every location of the form ``a[i]`` and ``a[i..j]`` and ``dest`` where 
+  ``dest`` is part of the pattern ``dest = spawn f(...)`` has to be
+  provable disjoint. This is called the *disjoint check*.
+* Every other complex location ``loc`` that is used in a spawned 
+  proc (``spawn f(loc)``) has to immutable for the duration of
+  the ``parallel``. This is called the *immutability check*. Currently it
+  is not specified what exactly "complex location" means. We need to make that
+  an optimization!
+* Every array access has to be provable within bounds.
+* Slices are optimized so that no copy is performed. This optimization is not
+  yet performed for ordinary slices outside of a ``parallel`` section.
+
+
+Spawn statement
+===============
+
+A standalone ``spawn`` statement is a simple construct. It executes
+the passed expression on the thread pool and returns a `data flow variable`:idx:
+``FlowVar[T]`` that can be read from. The reading with the ``^`` operator is
+**blocking**. However, one can use ``awaitAny`` to wait on multiple flow variables
+at the same time.
+
+Like the ``parallel`` statement data flow variables ensure that no data races
+are possible.
+