Changes between Version 6 and Version 7 of DataParallel/Vectorisation
 Timestamp:
 May 25, 2007 1:58:44 AM (9 years ago)
Legend:
 Unmodified
 Added
 Removed
 Modified

DataParallel/Vectorisation
v6 v7 4 4 5 5 This 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 6 7 7 8 === General strategy === … … 22 23 Let 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. 23 24 25 24 26 === Two array libraries === 25 27 … … 29 31 Vectorisation 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. 30 32 33 31 34 === Basic data types === 32 35 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 :$ () 36 The following data types are the basis for our representation of arrays and closure in vectorised code. 41 37 42 ($:) :: (a :> b) > a > b 43 (f :$ e) $: x = f e x 44 }}} 38 ==== Indexed array family ==== 45 39 46 Moreover, we have a type class `PA` determining the types of values that may occur as arrayelements in flattened arrays. The array type family `PArr` is associated with `PA`:40 The 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`: 47 41 {{{ 48 42 class PA a where … … 53 47 }}} 54 48 55 A crucial element in the transformation is the representation of arrays of closures as ''array closures'': 49 ==== Vectorised functions ==== 50 51 Vectorised functions use an explicit closure representation: 56 52 {{{ 57 data a :=> b 53 data a :> b 54 = forall e. 55 Cls { clsFun :: !(e > a > b) 56 , clsAFun :: !(PArr e > PArr a > PArr b) 57 , clsEnv :: e 58 } 59 }}} 60 with basic closure construction and application as 61 {{{ 62 lam :: (a > b) > (a :> b) 63 lam 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 closureconversion and vectorisation into one pass. If that is correct, we can represent vectorised functions as 71 {{{ 72 data a >> b = Fun { fun :: !( a > b) 73 , afun :: !(PArr a > PArr b) 74 } 75 76 vect :: (a > b) > (a >> b) 77 vect f = Fun f (mapP f) 78 }}} 79  80 81 ==== Lifted functions ==== 82 83 In lifted code, we represent functions by explicit closures combining scalar and lifted versions. We do so using ''array closures'': 84 {{{ 85 data a =>> b 58 86 = 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 } 60 91 }}} 61 We apply array closures as follows:92 We apply array closures using 62 93 {{{ 63 ($ ::) :: (a :=> b) > PArr a > PArr b64 ( fs ::$ es) $:: as = fses as94 ($) :: (a :=> b) > PArr a > PArr b 95 (ACls _ afun es) $:: as = afun es as 65 96 }}} 97 66 98 67 99 === Transformations ===