| Safe Haskell | None |
|---|---|
| Language | GHC2021 |
Futhark.Pass.Flatten.Incremental
Description
General definitions used for incremental flattening.
The idea behind incremental flattening is the observation that when flattening a program
map f xs
we have two options: (i) transform f to exploit any parallelism it may
contain, or (ii) turn f into sequential code and only exploit the
parallelism in map.
In some cases we do not have a choice, e.g. if f contains sufficiently
nonuniform operations that would result in nonuniform allocations. In other
cases the choice is obvious, such as when f is completely scalar. However,
in the general case either will work, and it depends on the workload which of
the options is optimal: if the outer map is big enough, it may be best to
efficiently sequentialise f (which can then also permit various locality
optimisations, such as tiling). But if the outer map does not have many
iterations, then we also need the parallelism in f to fully saturate the
machine.
The idea behind incremental flattening is to generate both versions, and select the appropriate one at run-time:
if predicate then sequentialise f...
else parallelise f...
The predicate is based on comparing the amount of exploitable parallelism with a threshold parameter. This threshold parameter is given a default value based on run-time hardware characteristics, but usually has to be auto-tuned in order to be optimal for a specific machine, program, and workload.
The multi-versioning approach is also used to generate more exotic versions,
such as one that parallelises f at a deeper hardware level
(Futhark.Pass.Flatten.Intrablock).
Synopsis
- worthIntrablock :: Lambda SOACS -> Bool
- worthSequentialising :: Lambda SOACS -> Bool
- isVersionableMap :: FunHasParallelism -> SegLevel -> DistInputs -> DistEnv -> SubExp -> [DistResult] -> Lambda SOACS -> Bool
- sufficientParallelism :: Name -> [SubExp] -> KernelPath -> Maybe Int64 -> FlattenM (SubExp, Name)
- isParallelFunInside :: FunHasParallelism -> Body SOACS -> Bool
- kernelAlternatives :: Name -> [Type] -> Body GPU -> [(SubExp, Body GPU)] -> FlattenM [VName]
- intraBlockAlternative :: IntrablockResult -> FlattenM (SubExp, Body GPU)
- mapAlternatives :: Name -> [Type] -> Attrs -> Bool -> Bool -> [SubExp] -> FlattenM (Body GPU) -> FlattenM (Body GPU) -> Maybe IntrablockResult -> FlattenM [VName]
- scanRedAlternatives :: Name -> [Type] -> Attrs -> Bool -> Bool -> [SubExp] -> FlattenM (Body GPU) -> FlattenM (Body GPU) -> FlattenM [VName]
- propagateVersioningAttrs :: Attrs -> Lambda SOACS -> Lambda SOACS
- imposeAttrs :: Attrs -> Stm SOACS -> Stm SOACS
- factorScremaForParallelism :: MonadBuilder m => FunHasParallelism -> Scope SOACS -> StmAux () -> Pat Type -> SubExp -> [VName] -> ScremaForm SOACS -> m (Maybe (Body SOACS))
- defaultSegLevel :: SegLevel
- inBlockSegLevel :: SegLevel
- allowVersioning :: SegLevel -> Bool
- bodyHasParallelism :: FunHasParallelism -> Body SOACS -> Bool
- lambdaHasParallelism :: FunHasParallelism -> Lambda SOACS -> Bool
- mayExploitOuter :: Attrs -> Bool
- onlyExploitIntra :: Attrs -> Bool
- mayExploitIntra :: Attrs -> Bool
Documentation
worthIntrablock :: Lambda SOACS -> Bool Source #
Intra-group parallelism is worthwhile if the lambda contains more than one instance of non-map nested parallelism, or any nested parallelism inside a loop.
worthSequentialising :: Lambda SOACS -> Bool Source #
A lambda is worth sequentialising if it contains enough nested parallelism of an interesting kind, or if distributing it would fragment sequential control flow - that is, if it contains meaningful parallelism nested inside a sequential loop or branch. Distribution must then split the loop or branch into separate kernel launches (and possibly host-evaluated control flow) per sequential step, so a version that instead sequentialises the nested parallelism is always worth offering.
isVersionableMap :: FunHasParallelism -> SegLevel -> DistInputs -> DistEnv -> SubExp -> [DistResult] -> Lambda SOACS -> Bool Source #
Should we generate multiple versions for this map? This requires both that
we are at a level where versioning is possible (allowVersioning) and that
the map itself produces only regular results (from an invariant width) and
does not call any parallel function (which force full flattening).
sufficientParallelism :: Name -> [SubExp] -> KernelPath -> Maybe Int64 -> FlattenM (SubExp, Name) Source #
isParallelFunInside :: FunHasParallelism -> Body SOACS -> Bool Source #
kernelAlternatives :: Name -> [Type] -> Body GPU -> [(SubExp, Body GPU)] -> FlattenM [VName] Source #
Arguments
| :: Name | Description for the result bindings. |
| -> [Type] | |
| -> Attrs | |
| -> Bool | Does the map body call a parallel function? If so we must fully flatten. |
| -> Bool | Is the body worth sequentialising (offering an outer-only version)? |
| -> [SubExp] | |
| -> FlattenM (Body GPU) | Construct the fully flattened body. |
| -> FlattenM (Body GPU) | Construct the outer-parallelism-only body. |
| -> Maybe IntrablockResult | |
| -> FlattenM [VName] |
Construct the multi-versioned alternatives for a map, given actions that
construct the fully-flattened body and the outer-parallel-only body, and an
optional intrablock result. This is the shared versioning policy used both
for top-level maps and for maps nested inside a map-nest; the only
differences between the two are which bodies are supplied and how their
results are consumed, both of which are handled by the caller. The ws are
the widths whose product bounds the outer parallelism (used for the threshold
comparison). Returns the names bound to the final results.
Arguments
| :: Name | |
| -> [Type] | |
| -> Attrs | |
| -> Bool | Does the operator body call a parallel function? If so we must fully flatten. |
| -> Bool | Does the seg level permit versioning at all (false in-block)? |
| -> [SubExp] | |
| -> FlattenM (Body GPU) | Construct the fully flattened body. |
| -> FlattenM (Body GPU) | Construct the outer-parallelism-only body. |
| -> FlattenM [VName] |
Construct the multi-versioned alternatives for a scan or reduce, given
actions that construct the fully-flattened body and the outer-parallel-only
body. Unlike mapAlternatives there is no intrablock version, and the
outer-only version is always offered (subject to attributes).
propagateVersioningAttrs :: Attrs -> Lambda SOACS -> Lambda SOACS Source #
Propagate incremental flattening attributes to the statements of a map lambda body. Statements that carry their own incremental flattening attributes are left alone.
imposeAttrs :: Attrs -> Stm SOACS -> Stm SOACS Source #
Impose outside flattening attributes on a statement. Only SOACs are affected, and only those that carry no flattening attributes of their own, as those are more specific.
Transforming code
factorScremaForParallelism :: MonadBuilder m => FunHasParallelism -> Scope SOACS -> StmAux () -> Pat Type -> SubExp -> [VName] -> ScremaForm SOACS -> m (Maybe (Body SOACS)) Source #
Produce a body suitable for full flattening from a Screma, or
Nothing if none of its lambdas contain meaningful parallelism, in
which case multi-versioning is not worthwhile. See Note
[Meaningful Parallelism] in Futhark.Pass.Flatten.Distribute.
Levels
allowVersioning :: SegLevel -> Bool Source #
Various queries
bodyHasParallelism :: FunHasParallelism -> Body SOACS -> Bool Source #
lambdaHasParallelism :: FunHasParallelism -> Lambda SOACS -> Bool Source #
mayExploitOuter :: Attrs -> Bool Source #
onlyExploitIntra :: Attrs -> Bool Source #
mayExploitIntra :: Attrs -> Bool Source #