diff options
| author | Simon Marlow <simonmar@microsoft.com> | 2006-04-07 02:05:11 +0000 |
|---|---|---|
| committer | Simon Marlow <simonmar@microsoft.com> | 2006-04-07 02:05:11 +0000 |
| commit | 0065d5ab628975892cea1ec7303f968c3338cbe1 (patch) | |
| tree | 8e2afe0ab48ee33cf95009809d67c9649573ef92 /docs/comm/exts/ndp.html | |
| parent | 28a464a75e14cece5db40f2765a29348273ff2d2 (diff) | |
| download | haskell-0065d5ab628975892cea1ec7303f968c3338cbe1.tar.gz | |
Reorganisation of the source tree
Most of the other users of the fptools build system have migrated to
Cabal, and with the move to darcs we can now flatten the source tree
without losing history, so here goes.
The main change is that the ghc/ subdir is gone, and most of what it
contained is now at the top level. The build system now makes no
pretense at being multi-project, it is just the GHC build system.
No doubt this will break many things, and there will be a period of
instability while we fix the dependencies. A straightforward build
should work, but I haven't yet fixed binary/source distributions.
Changes to the Building Guide will follow, too.
Diffstat (limited to 'docs/comm/exts/ndp.html')
| -rw-r--r-- | docs/comm/exts/ndp.html | 360 |
1 files changed, 360 insertions, 0 deletions
diff --git a/docs/comm/exts/ndp.html b/docs/comm/exts/ndp.html new file mode 100644 index 0000000000..0c94c3960b --- /dev/null +++ b/docs/comm/exts/ndp.html @@ -0,0 +1,360 @@ +<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN"> +<html> + <head> + <META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=ISO-8859-1"> + <title>The GHC Commentary - Parallel Arrays</title> + </head> + + <body BGCOLOR="FFFFFF"> + <h1>The GHC Commentary - Parallel Arrays</h1> + <p> + This section describes an experimental extension by high-performance + arrays, which comprises special syntax for array types and array + comprehensions, a set of optimising program transformations, and a set + of special purpose libraries. The extension is currently only partially + implemented, but the development will be tracked here. + <p> + Parallel arrays originally got their name from the aim to provide an + architecture-independent programming model for a range of parallel + computers. However, since experiments showed that the approach is also + worthwhile for sequential array code, the emphasis has shifted to their + parallel evaluation semantics: As soon as any element in a parallel + array is demanded, all the other elements are evaluated, too. This + makes parallel arrays more strict than <a + href="http://haskell.org/onlinelibrary/array.html">standard Haskell 98 + arrays</a>, but also opens the door for a loop-based implementation + strategy that leads to significantly more efficient code. + <p> + The programming model as well as the use of the <em>flattening + transformation</em>, which is central to the approach, has its origin in + the programming language <a + href="http://www.cs.cmu.edu/~scandal/nesl.html">Nesl</a>. + + <h2>More Sugar: Special Syntax for Array Comprehensions</h2> + <p> + The option <code>-fparr</code>, which is a dynamic hsc option that can + be reversed with <code>-fno-parr</code>, enables special syntax for + parallel arrays, which is not essential to using parallel arrays, but + makes for significantly more concise programs. The switch works by + making the lexical analyser (located in <a + href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/parser/Lex.lhs"><code>Lex.lhs</code></a>) + recognise the tokens <code>[:</code> and <code>:]</code>. Given that + the additional productions in the parser (located in <a + href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/parser/Parser.y"><code>Parser.y</code></a>) + cannot be triggered without the lexer generating the necessary tokens, + there is no need to alter the behaviour of the parser. + <p> + The following additional syntax is accepted (the non-terminals are those + from the <a href="http://haskell.org/onlinereport/">Haskell 98 language + definition</a>): + <p> + <blockquote><pre> +atype -> '[:' type ':] (parallel array type) + +aexp -> '[:' exp1 ',' ... ',' expk ':]' (explicit array, k >= 0) + | '[:' exp1 [',' exp2] '..' exp3 ':]' (arithmetic array sequence) + | '[:' exp '|' quals1 '|' ... '|' qualsn ':]' (array comprehension, n >= 1) + +quals -> qual1 ',' ... ',' qualn (qualifier list, n >= 1) + +apat -> '[:' pat1 ',' ... ',' patk ':]' (array pattern, k >= 0) +</pre> + </blockquote> + <p> + Moreover, the extended comprehension syntax that allows for <em>parallel + qualifiers</em> (i.e., qualifiers separated by "<code>|</code>") is also + supported in list comprehensions. In general, the similarity to the + special syntax for list is obvious. The two main differences are that + (a) arithmetic array sequences are always finite and (b) + <code>[::]</code> is not treated as a constructor in expressions and + patterns, but rather as a special case of the explicit array syntax. + The former is a simple consequence of the parallel evaluation semantics + of parallel arrays and the latter is due to arrays not being a + constructor-based data type. + <p> + As a naming convention, types and functions that are concerned with + parallel arrays usually contain the string <code>parr</code> or + <code>PArr</code> (often as a prefix), and where corresponding types or + functions for handling lists exist, the name is identical, except for + containing the substring <code>parr</code> instead of <code>list</code> + (possibly in caps). + <p> + The following implications are worth noting explicitly: + <ul> + <li>As the value and pattern <code>[::]</code> is an empty explicit + parallel array (i.e., something of the form <code>ExplicitPArr ty + []</code> in the AST). This is in contrast to lists, which use the + nil-constructor instead. In the case of parallel arrays, using a + constructor would be rather awkward, as it is not a constructor-based + type. (This becomes rather clear in the desugarer.) + <li>As a consequence, array patterns have the general form <code>[:p1, + p2, ..., pn:]</code>, where <code>n</code> >= 0. Thus, two array + patterns overlap iff they have the same length -- an important property + for the pattern matching compiler. + </ul> + + <h2>Prelude Support for Parallel Arrays</h2> + <p> + The Prelude module <a + href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/lib/std/PrelPArr.lhs"><code>PrelPArr</code></a> + defines the standard operations and their types on parallel arrays and + provides a basic implementation based on boxed arrays. The interface of + <code>PrelPArr</code> is oriented by H98's <code>PrelList</code>, but + leaving out all functions that require infinite structures and adding + frequently needed array operations, such as permutations. Parallel + arrays are quite unqiue in that they use an entirely different + representation as soon as the flattening transformation is activated, + which is described further below. In particular, <code>PrelPArr</code> + defines the type <code>[::]</code> and operations to create, process, + and inspect parallel arrays. The type as well as the names of some of + the operations are also hardwired in <a + href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/prelude/TysWiredIn.lhs"><code>TysWiredIn</code></a> + (see the definition of <code>parrTyCon</code> in this module) and <a + href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/prelude/PrelNames.lhs"><code>PrelNames</code></a>. + This is again very much like the case of lists, where the type is + defined in <a + href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/lib/std/PrelBase.lhs"><code>PrelBase</code></a> + and similarly wired in; however, for lists the entirely + constructor-based definition is exposed to user programs, which is not + the case for parallel arrays. + + <h2>Desugaring Parallel Arrays</h2> + <p> + The parallel array extension requires the desugarer to replace all + occurrences of (1) explicit parallel arrays, (2) array patterns, and (3) + array comprehensions by a suitable combination of invocations of + operations defined in <code>PrelPArr</code>. + + <h4>Explicit Parallel Arrays</h4> + <p> + These are by far the simplest to remove. We simply replace every + occurrence of <code>[:<i>e<sub>1</sub></i>, ..., + <i>e<sub>n</sub></i>:]</code> by + <blockquote> + <code> + toP [<i>e<sub>1</sub></i>, ..., <i>e<sub>n</sub></i>] + </code> + </blockquote> + <p> + i.e., we build a list of the array elements, which is, then, converted + into a parallel array. + + <h4>Parallel Array Patterns</h4> + <p> + Array patterns are much more tricky as element positions may contain + further patterns and the <a + href="../the-beast/desugar.html#patmat">pattern matching compiler</a> + requires us to flatten all those out. But before we turn to the gory + details, here first the basic idea: A flat array pattern matches exactly + iff it's length corresponds to the length of the matched array. Hence, + if we have a set of flat array patterns matching an array value + <code>a</code>, it suffices to generate a Core <code>case</code> + expression that scrutinises <code>lengthP a</code> and has one + alternative for every length of array occuring in one of the patterns. + Moreover, there needs to be a default case catching all other array + lengths. In each alternative, array indexing (i.e., the functions + <code>!:</code>) is used to bind array elements to the corresponding + pattern variables. This sounds easy enough and is essentially what the + parallel array equation of the function <a + href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/deSugar/DsUtils.lhs"><code>DsUtils</code></a><code>.mkCoAlgCaseMatchResult</code> + does. + <p> + Unfortunately, however, the pattern matching compiler expects that it + can turn (almost) any pattern into variable patterns, literals, or + constructor applications by way of the functions <a + href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/deSugar/Match.lhs"><code>Match</code></a><code>.tidy1</code>. + And to make matters worse, some weird machinery in the module <a + href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/deSugar/Check.lhs"><code>Check</code></a> + insists on being able to reverse the process (essentially to pretty + print patterns in warnings for incomplete or overlapping patterns). + <p> + The solution to this is an (unlimited) set of <em>fake</em> constructors + for parallel arrays, courtesy of <a + href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/prelude/TysWiredIn.lhs"><code>TysWiredIn</code></a><code>.parrFakeCon</code>. + In other words, any pattern of the form <code>[:<i>p<sub>1</sub></i>, + ..., <i>p<sub>n</sub></i>:]</code> is transformed into + <blockquote> + <code> + MkPArray<i>n</i> <i>p<sub>1</sub></i> ... <i>p<sub>n</sub></i> + </code> + </blockquote> + <p> + by <code>Match.tidy1</code>, then, run through the rest of the pattern + matching compiler, and finally, picked up by + <code>DsUtils.mkCoAlgCaseMatchResult</code>, which converts it into a + <code>case</code> expression as outlined above. + <p> + As an example consider the source expression + <blockquote><pre> +case v of + [:x1:] -> e1 + [:x2, x3, x4:] -> e2 + _ -> e3</pre> + </blockquote> + <p> + <code>Match.tidy1</code> converts it into a form that is equivalent to + <blockquote><pre> +case v of { + MkPArr1 x1 -> e1; + MkPArr2 x2 x3 x4 -> e2; + _ -> e3; +}</pre> + </blockquote> + <p> + which <code>DsUtils.mkCoAlgCaseMatchResult</code> turns into the + following Core code: + <blockquote><pre> + case lengthP v of + Int# i# -> + case i# of l { + DFT -> e3 + 1 -> let x1 = v!:0 in e1 + 3 -> let x2 = v!:0; x2 = v!:1; x3 = v!:2 in e2 + }</pre> + </blockquote> + + <h4>Parallel Array Comprehensions</h4> + <p> + The most challenging construct of the three are array comprehensions. + In principle, it would be possible to transform them in essentially the + same way as list comprehensions, but this would lead to abysmally slow + code as desugaring of list comprehensions generates code that is + optimised for sequential, constructor-based structures. In contrast, + array comprehensions need to be transformed into code that solely relies + on collective operations and avoids the creation of many small + intermediate arrays. + <p> + The transformation is implemented by the function <a + href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/deSugar/DsListComp.lhs"><code>DsListComp</code></a><code>.dsPArrComp</code>. + In the following, we denote this transformation function by the form + <code><<<i>e</i>>> pa ea</code>, where <code><i>e</i></code> + is the comprehension to be compiled and the arguments <code>pa</code> + and <code>ea</code> denote a pattern and the currently processed array + expression, respectively. The invariant constraining these two + arguments is that all elements in the array produced by <code>ea</code> + will <em>successfully</em> match against <code>pa</code>. + <p> + Given a source-level comprehensions <code>[:e | qss:]</code>, we compile + it with <code><<[:e | qss:]>> () [:():]</code> using the + rules + <blockquote><pre> +<<[:e' | :]>> pa ea = mapP (\pa -> e') ea +<<[:e' | b , qs:]>> pa ea = <<[:e' | qs:]>> pa (filterP (\pa -> b) ea) +<<[:e' | p <- e, qs:]>> pa ea = + let ef = filterP (\x -> case x of {p -> True; _ -> False}) e + in + <<[:e' | qs:]>> (pa, p) (crossP ea ef) +<<[:e' | let ds, qs:]>> pa ea = + <<[:e' | qs:]>> (pa, (x_1, ..., x_n)) + (mapP (\v@pa -> (v, let ds in (x_1, ..., x_n))) ea) +where + {x_1, ..., x_n} = DV (ds) -- Defined Variables +<<[:e' | qs | qss:]>> pa ea = + <<[:e' | qss:]>> (pa, (x_1, ..., x_n)) + (zipP ea <<[:(x_1, ..., x_n) | qs:]>>) +where + {x_1, ..., x_n} = DV (qs)</pre> + </blockquote> + <p> + We assume the denotation of <code>crossP</code> to be given by + <blockquote><pre> +crossP :: [:a:] -> [:b:] -> [:(a, b):] +crossP a1 a2 = let + len1 = lengthP a1 + len2 = lengthP a2 + x1 = concatP $ mapP (replicateP len2) a1 + x2 = concatP $ replicateP len1 a2 + in + zipP x1 x2</pre> + </blockquote> + <p> + For a more efficient implementation of <code>crossP</code>, see + <a + href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/lib/std/PrelPArr.lhs"><code>PrelPArr</code></a>. + <p> + Moreover, the following optimisations are important: + <ul> + <li>In the <code>p <- e</code> rule, if <code>pa == ()</code>, drop + it and simplify the <code>crossP ea e</code> to <code>e</code>. + <li>We assume that fusion will optimise sequences of array processing + combinators. + <li>FIXME: Do we want to have the following function? + <blockquote><pre> +mapFilterP :: (a -> Maybe b) -> [:a:] -> [:b:]</pre> + </blockquote> + <p> + Even with fusion <code>(mapP (\p -> e) . filterP (\p -> + b))</code> may still result in redundant pattern matching + operations. (Let's wait with this until we have seen what the + Simplifier does to the generated code.) + </ul> + + <h2>Doing Away With Nested Arrays: The Flattening Transformation</h2> + <p> + On the quest towards an entirely unboxed representation of parallel + arrays, the flattening transformation is the essential ingredient. GHC + uses a <a + href="http://www.cse.unsw.edu.au/~chak/papers/CK00.html">substantially + improved version</a> of the transformation whose original form was + described by Blelloch & Sabot. The flattening transformation + replaces values of type <code>[:a:]</code> as well as functions + operating on these values by alternative, more efficient data structures + and functions. + <p> + The flattening machinery is activated by the option + <code>-fflatten</code>, which is a static hsc option. It consists of + two steps: function vectorisation and array specialisation. Only the + first of those is implemented so far. If selected, the transformation + is applied to a module in Core form immediately after the <a + href="../the-beast/desugar.html">desugarer,</a> before the <a + href="../the-beast/simplifier.html">Mighty Simplifier</a> gets to do its + job. After vectorisation, the Core program can be dumped using the + option <code>-ddump-vect</code>. The is a good reason for us to perform + flattening immediately after the desugarer. In <a + href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/main/HscMain.lhs"><code>HscMain</code></a><code>.hscRecomp</code> + the so-called <em>persistent compiler state</em> is maintained, which + contains all the information about imported interface files needed to + lookup the details of imported names (e.g., during renaming and type + checking). However, all this information is zapped before the + simplifier is invoked (supposedly to reduce the space-consumption of + GHC). As flattening has to get at all kinds of identifiers from Prelude + modules, we need to do it before the relevant information in the + persistent compiler state is gone. + + <p> + As flattening generally requires all libraries to be compiled for + flattening (just like profiling does), there is a <em>compiler way</em> + <code>"ndp"</code>, which can be selected using the way option code + <code>-ndp</code>. This option will automagically select + <code>-fparr</code> and <code>-fflatten</code>. + + <h4><code>FlattenMonad</code></h4> + <p> + The module <a + href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/ndpFlatten/FlattenMonad.lhs"><code>FlattenMonad</code></a> + implements the monad <code>Flatten</code> that is used during + vectorisation to keep track of various sets of bound variables and a + variable substitution map; moreover, it provides a supply of new uniques + and allows us to look up names in the persistent compiler state (i.e., + imported identifiers). + <p> + In order to be able to look up imported identifiers in the persistent + compiler state, it is important that these identifies are included into + the free variable lists computed by the renamer. More precisely, all + names needed by flattening are included in the names produced by + <code>RnEnv.getImplicitModuleFVs</code>. To avoid putting + flattening-dependent lists of names into the renamer, the module + <code>FlattenInfo</code> exports <code>namesNeededForFlattening</code>. + + [FIXME: It might be worthwhile to document in the non-Flattening part of + the Commentary that the persistent compiler state is zapped after + desugaring and how the free variables determined by the renamer imply + which names are imported.] + + <p><small> +<!-- hhmts start --> +Last modified: Tue Feb 12 01:44:21 EST 2002 +<!-- hhmts end --> + </small> + </body> +</html> |