Changes between Version 37 and Version 38 of DataParallel/Replicate


Ignore:
Timestamp:
Aug 22, 2011 3:28:59 AM (4 years ago)
Author:
chak
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • DataParallel/Replicate

    v37 v38  
    163163Arrays with virtual segments can not always be combined without duplicating the data corresponding to repeated segments (after all, a disjoint segment may be inserted into a sequence of repeated segments).  For simplicity, we may want to expand all repeated segments and remove all not used physical segments in `combinePA`.  (It seems that this should not lead to unexpected blow-ups as the repeated data now is part of a functions result and should be accounted for in its complexity estimate.) 
    164164 
     165Some examples: 
     166{{{ 
     167desire:dph-common-vseg benl$ ghc --interactive examples/Test.hs -package dph-par -package dph-prim-par -Iinclude 
     168 
     169 
     170-- pprv : pretty print virtual array 
     171*Test> pprv arrN3 
     172[[0],[1,2,3],[5,6,7,8,9]] 
     173 
     174 
     175-- pprp : pretty print physical array 
     176*Test> pprp arrN3 
     177PArray  3 
     178   PNested 
     179       vsegids:    [0,1,2] 
     180       pseglens:   [1,3,5] 
     181       psegstarts: [0,1,4] 
     182       psegsrcs:   [0,0,0] 
     183       PInt [0,1,2,3,5,6,7,8,9] 
     184 
     185 
     186-- With segmented replicate we only replicate the vsegs fields 
     187--  The functions ending PA' take lists for some arguments, and are just for experimentation. 
     188--  Functions ending in plain PA take real arrays. 
     189 
     190*Test> pprv $ replicatesPA' [2, 4, 3] arrN3 
     191[[0],[0],[1,2,3],[1,2,3],[1,2,3],[1,2,3],[5,6,7,8,9],[5,6,7,8,9],[5,6,7,8,9]] 
     192 
     193*Test> pprp $ replicatesPA' [2, 4, 3] arrN3 
     194PArray  9 
     195   PNested 
     196       vsegids:    [0,0,1,1,1,1,2,2,2] 
     197       pseglens:   [1,3,5] 
     198       psegstarts: [0,1,4] 
     199       psegsrcs:   [0,0,0] 
     200       PInt [0,1,2,3,5,6,7,8,9] 
     201 
     202 
     203-- To pack an array, we pack the vsegs then drop out the psegs that  
     204-- aren't referenced by any vseg. 
     205 
     206*Test> pprv $ packByTagPA' (replicatesPA' [2, 4, 3] arrN3) [1, 0, 0, 0, 0, 0, 1, 0, 1] 1 
     207[[0],[5,6,7,8,9],[5,6,7,8,9]] 
     208 
     209*Test> pprp $ packByTagPA' (replicatesPA' [2, 4, 3] arrN3) [1, 0, 0, 0, 0, 0, 1, 0, 1] 1 
     210PArray  0 
     211   PNested 
     212       vsegids:    [0,1,1] 
     213       pseglens:   [1,5] 
     214       psegstarts: [0,4] 
     215       psegsrcs:   [0,0] 
     216       PInt [0,1,2,3,5,6,7,8,9] 
     217 
     218 
     219-- Applying concatPA merges the two outermost layers. 
     220 
     221*Test> pprv $ concatPA $ packByTagPA' (replicatesPA' [2, 4, 3] arrN3) [1, 0, 0, 0, 0, 0, 1, 0, 1] 1 
     222[0,5,6,7,8,9,5,6,7,8,9] 
     223 
     224*Test> pprp $ concatPA $ packByTagPA' (replicatesPA' [2, 4, 3] arrN3) [1, 0, 0, 0, 0, 0, 1, 0, 1] 1 
     225PArray  11 
     226   PInt [0,5,6,7,8,9,5,6,7,8,9] 
     227}}} 
     228 
    165229=== Reduction === 
    166230 
     
    176240 
    177241As we saw in the previous subsection, some physical segments may not appear as virtual segments at all (if a replicated array shrunk by applying a pack operation).  Hence, we need to be careful that `sumP^` only reduces those physical segments of the array that are used by one or more virtual segments. 
     242 
     243=== Append === 
     244 
     245{{{ 
     246*Test> :type arrN3 
     247arrN3 :: PArray (PArray Int) 
     248 
     249*Test> pprv arrN3 
     250[[0],[1,2,3],[5,6,7,8,9]] 
     251 
     252*Test> pprp arrN3 
     253PArray  3 
     254   PNested 
     255       vsegids:    [0,1,2] 
     256       pseglens:   [1,3,5] 
     257       psegstarts: [0,1,4] 
     258       psegsrcs:   [0,0,0] 
     259       PInt [0,1,2,3,5,6,7,8,9] 
     260 
     261 
     262*Test> pprv arrN4 
     263[[7,8,9,10,11,12,13],[0],[1,2,3],[0]] 
     264 
     265*Test> pprp arrN4 
     266PArray  4 
     267   PNested 
     268       vsegids:    [0,1,2,3] 
     269       pseglens:   [7,1,3,1] 
     270       psegstarts: [0,7,8,11] 
     271       psegsrcs:   [0,0,0,0] 
     272       PInt [7,8,9,10,11,12,13,0,1,2,3,0] 
     273 
     274 
     275-- Append is also an index space transform. When we append two arrays 
     276-- we append the segmentation information, but just put both flat arrays 
     277-- into the result, without copying their data. Note how the result 
     278-- contains both PInt arrays from the source. 
     279 
     280*Test> pprv $ arrN3 `appPA` arrN4 
     281[[0],[1,2,3],[5,6,7,8,9],[7,8,9,10,11,12,13],[0],[1,2,3],[0]] 
     282 
     283 
     284*Test> pprp $ arrN3 `appPA` arrN4 
     285PArray  7 
     286   PNested 
     287       vsegids:    [0,1,2,3,4,5,6] 
     288       pseglens:   [1,3,5,7,1,3,1] 
     289       psegstarts: [0,1,4,0,7,8,11] 
     290       psegsrcs:   [0,0,0,1,1,1,1] 
     291       PInt [0,1,2,3,5,6,7,8,9] 
     292       PInt [7,8,9,10,11,12,13,0,1,2,3,0] 
     293}}} 
    178294 
    179295=== Splitting and joining (for distribution across threads) ===