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) ===