Changes between Version 6 and Version 7 of DataParallel/Vectorisation


Ignore:
Timestamp:
May 25, 2007 1:58:44 AM (8 years ago)
Author:
chak
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • DataParallel/Vectorisation

    v6 v7  
    44
    55This page describes our approach to implementing vectorisation by extending our earlier implementation of closure conversion.  A central aspect is the ability to mix modules compiled with vectorisation with modules compiled without vectorisation.
     6
    67
    78=== General strategy ===
     
    2223Let us assume that the functions `getArgs`, `print`, and `read` are defined in modules that have not been vectorised.  When vectorising `main`, we want to use the vectorised versions of the functions `sumP`, `mapP` (implied by the comprehension), and `enumFromToP` (implied by the array constructor).  However, all the rest of the code will remain largely unchanged.  (What ''largely unchanged'' means precisely, we still have to define.)  In fact, there will be two versions of `main`.  The original `main` function that, according to our policy, does not use any vectorised code and `main_v` that has all the array code properly vectorised and all the enclosing `IO` code largely unchanged.  In order to make use of vectorisation, the runtime system will have to invoke `main_v`, not `main`.  Moreover, the code calling `main_v` will have to first set up the thread gang and whatever other extra initialisation is needed.  Whether to execute `main` or `main_v` on program start up is determined by whether the `-fvect` option is present during linking or not.
    2324
     25
    2426=== Two array libraries ===
    2527
     
    2931Vectorisation transforms all uses of functions from `GHC.PArr` into uses of package ndp.  It can obviously only do that for computations manipulating values for whose type we have `PA` instances.
    3032
     33
    3134=== Basic data types ===
    3235
    33 In the generated code, we need closures, array families, array closure, and so forth.  We define closure as:
    34 {{{
    35 data a :-> b = forall e. !(e -> a -> b) :$ e
    36 }}}
    37 with basic closure cosntruction and application as
    38 {{{
    39 lam :: (a -> b) -> (a :-> b)
    40 lam f = const f :$ ()
     36The following data types are the basis for our representation of arrays and closure in vectorised code.
    4137
    42 ($:) :: (a :-> b) -> a -> b
    43 (f :$ e) $: x = f e x
    44 }}}
     38==== Indexed array family ====
    4539
    46 Moreover, we have a type class `PA` determining the types of values that may occur as array elements in flattened arrays.  The array type family `PArr` is associated with `PA`:
     40The type class `PA` has an instance for every type of values that may occur as elements in flattened arrays.  The array type family `PArr` is associated with `PA`:
    4741{{{
    4842class PA a where
     
    5347}}}
    5448
    55 A crucial element in the transformation is the representation of arrays of closures as ''array closures'':
     49==== Vectorised functions ====
     50
     51Vectorised functions use an explicit closure representation:
    5652{{{
    57 data a :=> b
     53data a :-> b
     54  = forall e.
     55      Cls { clsFun  :: !(e -> a -> b)
     56          , clsAFun :: !(PArr e -> PArr a -> PArr b)
     57          , clsEnv  :: e
     58          }
     59}}}
     60with basic closure construction and application as
     61{{{
     62lam :: (a -> b) -> (a :-> b)
     63lam f = Cls (const f) (const (mapP f)) ()
     64
     65($:) :: (a :-> b) -> a -> b
     66(Cls f _ e) $: x = f e x
     67}}}
     68
     69----
     70'''TODO:''' Can't we actually omit the explicit closure representation for ''scalar'' closures?  We need it for array closures, so that we can, e.g., pack them, but I think we don't really need it for scalar closures when we combine closure-conversion and vectorisation into one pass.  If that is correct, we can represent vectorised functions as
     71{{{
     72data a ->> b = Fun { fun  :: !(     a ->      b)
     73                   , afun :: !(PArr a -> PArr b)
     74                   }
     75
     76vect :: (a -> b) -> (a ->> b)
     77vect f = Fun f (mapP f)
     78}}}
     79----
     80
     81==== Lifted functions ====
     82
     83In lifted code, we represent functions by explicit closures combining scalar and lifted versions.  We do so using ''array closures'':
     84{{{
     85data a =>> b
    5886  = forall e. PA e =>
    59       !(PArr e -> PArr a -> PArr b) ::$ PArr e
     87      ACls { aclsFun  :: !(e -> a -> b)
     88           , aclsAFun :: !(PArr e -> PArr a -> PArr b)
     89           , aclsEnv  :: PArr e
     90           }
    6091}}}
    61 We apply array closures as follows:
     92We apply array closures using
    6293{{{
    63 ($::) :: (a :=> b) -> PArr a -> PArr b
    64 (fs ::$ es) $:: as = fs es as
     94($||) :: (a :=> b) -> PArr a -> PArr b
     95(ACls _ afun es) $:: as = afun es as
    6596}}}
     97
    6698
    6799=== Transformations ===