Changes between Version 6 and Version 7 of DataParallel/Vectorisation


Ignore:
Timestamp:
May 25, 2007 1:58:44 AM (7 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 ===