dph-prim-par-0.6.1.1: Data Parallel Haskell segmented arrays. (production version)

Safe HaskellSafe-Infered

Data.Array.Parallel.Unlifted.Parallel.UPVSegd

Contents

Description

Parallel virtual segment descriptors.

See Data.Array.Parallel.Unlifted for how this works.

Synopsis

Types

data UPVSegd Source

Parallel Virtual Segment descriptor.

Instances

Show UPVSegd 
PprPhysical UPVSegd

Pretty print the physical representation of a UVSegd

Consistency check

valid :: UPVSegd -> BoolSource

O(1). Check the internal consistency of a virutal segmentation descriptor.

Constructors

mkUPVSegdSource

Arguments

:: Vector Int

Array saying which physical segment to use for each virtual segment.

-> UPSSegd

Scattered segment descriptor defining the physical segments.

-> UPVSegd 

O(1). Construct a new virtual segment descriptor.

fromUPSegd :: UPSegd -> UPVSegdSource

O(segs). Promote a UPSegd to a UPVSegd. All segments are assumed to come from a flat array with sourceid 0. The result contains one virtual segment for every physical segment the provided UPSegd.

fromUPSSegd :: UPSSegd -> UPVSegdSource

O(segs). Promote a UPSSegd to a UPVSegd. The result contains one virtual segment for every physical segment defined by the UPSSegd.

empty :: UPVSegdSource

O(1). Construct an empty segment descriptor, with no elements or segments.

singleton :: Int -> UPVSegdSource

O(1). Construct a singleton segment descriptor. The single segment covers the given number of elements in a flat array with sourceid 0.

replicatedSource

Arguments

:: Int

Length of segment.

-> Int

Number of times replicated.

-> UPVSegd 

O(1). Construct a UPVSegd that describes an array created by replicating a single segment several times.

Predicates

isManifest :: UPVSegd -> BoolSource

O(1). Checks whether all the segments are manifest (unshared / non-virtual). If this is the case, then the vsegids field will be [0..len-1].

Consumers can check this field, avoid demanding the vsegids field. This can avoid the need for it to be constructed in the first place, due to lazy evaluation.

isContiguous :: UPVSegd -> BoolSource

O(1). True when the starts are identical to the usegd indices field and the sources are all 0's.

In this case all the data elements are in one contiguous flat array, and consumers can avoid looking at the real starts and sources fields.

Projections

length :: UPVSegd -> IntSource

O(1). Yield the overall number of segments.

takeVSegids :: UPVSegd -> Vector IntSource

O(1). Yield the virtual segment ids of UPVSegd.

takeVSegidsRedundant :: UPVSegd -> Vector IntSource

O(1). Take the vsegids of a UPVSegd, but don't require that every physical segment is referenced by some virtual segment.

If you're just performing indexing and don't need the invariant that all physical segments are reachable from some virtual segment, then use this version as it's faster. This sidesteps the code that maintains the invariant.

The stated O(1) complexity assumes that the array has already been fully evalauted. If this is not the case then we can avoid demanding the result of a prior computation on the vsegids, thus reducing the cost attributed to that prior computation.

takeUPSSegd :: UPVSegd -> UPSSegdSource

O(1). Yield the UPSSegd of UPVSegd.

takeUPSSegdRedundant :: UPVSegd -> UPSSegdSource

O(1). Take the UPSSegd of a UPVSegd, but don't require that every physical segment is referenced by some virtual segment.

See the note in takeVSegidsRedundant.

takeLengths :: UPVSegd -> Vector IntSource

O(segs). Yield the lengths of the segments described by a UPVSegd.

getSeg :: UPVSegd -> Int -> (Int, Int, Int)Source

O(1). Get the length, starting index, and source id of a segment.

Demotion

unsafeDemoteToUPSSegd :: UPVSegd -> UPSSegdSource

O(segs). Yield a UPSSegd that describes each segment of a UPVSegd individually.

By doing this we lose information about which virtual segments correspond to the same physical segments.

WARNING: Trying to take the UPSegd of a nested array that has been constructed with replication can cause index space overflow. This is because the virtual size of the corresponding flat data can be larger than physical memory. If this happens then indices fields and element count in the result will be invalid.

unsafeDemoteToUPSegd :: UPVSegd -> UPSegdSource

O(segs). Yield a UPSegd that describes each segment of a UPVSegd individually, assuming all segments have been concatenated to remove scattering.

Operators

updateVSegs :: (Vector Int -> Vector Int) -> UPVSegd -> UPVSegdSource

Update the vsegids of a UPVSegd, and then cull the physical segment descriptor so that all physical segments are reachable from some virtual segment.

This function lets you perform filtering operations on the virtual segments, while maintaining the invariant that all physical segments are referenced by some virtual segment.

updateVSegsReachable :: (Vector Int -> Vector Int) -> UPVSegd -> UPVSegdSource

Update the vsegids of UPVSegd, where the result is guaranteed to cover all physical segments.

Using this version saves performing the cull operation which discards unreachable physical segments.

  • The resulting vsegids must cover all physical segments. If they do not then there will be physical segments that are not reachable from some virtual segment, and subsequent operations like segmented fold will have the wrong work complexity.

appendWithSource

Arguments

:: UPVSegd

Descriptor of first array.

-> Int

Number of flat physical arrays for first descriptor.

-> UPVSegd

Descriptor of second array.

-> Int

Number of flat physical arrays for second descriptor.

-> UPVSegd 

Produce a segment descriptor that describes the result of appending two arrays.

combine2Source

Arguments

:: UPSel2

Selector for the combine operation.

-> UPVSegd

Descriptor of first array.

-> Int

Number of flat physical arrays for first descriptor.

-> UPVSegd

Descriptor of second array.

-> Int

Number of flat physical arrays for second descriptor.

-> UPVSegd 

Combine two virtual segment descriptors.