Safe Haskell | None |
---|---|
Language | Haskell2010 |
Segmented operations. These correspond to perfect map
nests on
top of something, except that the map
s are conceptually only
over iota
s (so there will be explicit indexing inside them).
Synopsis
- data SegOp lvl rep
- = SegMap lvl SegSpace [Type] (KernelBody rep)
- | SegRed lvl SegSpace [SegBinOp rep] [Type] (KernelBody rep)
- | SegScan lvl SegSpace [SegBinOp rep] [Type] (KernelBody rep)
- | SegHist lvl SegSpace [HistOp rep] [Type] (KernelBody rep)
- data SegVirt
- segLevel :: SegOp lvl rep -> lvl
- segBody :: SegOp lvl rep -> KernelBody rep
- segSpace :: SegOp lvl rep -> SegSpace
- typeCheckSegOp :: Checkable rep => (lvl -> TypeM rep ()) -> SegOp lvl (Aliases rep) -> TypeM rep ()
- data SegSpace = SegSpace {
- segFlat :: VName
- unSegSpace :: [(VName, SubExp)]
- scopeOfSegSpace :: SegSpace -> Scope rep
- segSpaceDims :: SegSpace -> [SubExp]
- data HistOp rep = HistOp {}
- histType :: HistOp rep -> [Type]
- data SegBinOp rep = SegBinOp {
- segBinOpComm :: Commutativity
- segBinOpLambda :: Lambda rep
- segBinOpNeutral :: [SubExp]
- segBinOpShape :: Shape
- segBinOpResults :: [SegBinOp rep] -> Int
- segBinOpChunks :: [SegBinOp rep] -> [a] -> [[a]]
- data KernelBody rep = KernelBody {
- kernelBodyDec :: BodyDec rep
- kernelBodyStms :: Stms rep
- kernelBodyResult :: [KernelResult]
- aliasAnalyseKernelBody :: (ASTRep rep, CanBeAliased (Op rep)) => AliasTable -> KernelBody rep -> KernelBody (Aliases rep)
- consumedInKernelBody :: Aliased rep => KernelBody rep -> Names
- data ResultManifest
- data KernelResult
- = Returns ResultManifest SubExp
- | WriteReturns Shape VName [(Slice SubExp, SubExp)]
- | ConcatReturns SplitOrdering SubExp SubExp VName
- | TileReturns [(SubExp, SubExp)] VName
- | RegTileReturns [(SubExp, SubExp, SubExp)] VName
- kernelResultSubExp :: KernelResult -> SubExp
- data SplitOrdering
- data SegOpMapper lvl frep trep m = SegOpMapper {
- mapOnSegOpSubExp :: SubExp -> m SubExp
- mapOnSegOpLambda :: Lambda frep -> m (Lambda trep)
- mapOnSegOpBody :: KernelBody frep -> m (KernelBody trep)
- mapOnSegOpVName :: VName -> m VName
- mapOnSegOpLevel :: lvl -> m lvl
- identitySegOpMapper :: Monad m => SegOpMapper lvl rep rep m
- mapSegOpM :: (Applicative m, Monad m) => SegOpMapper lvl frep trep m -> SegOp lvl frep -> m (SegOp lvl trep)
- simplifySegOp :: (SimplifiableRep rep, BodyDec rep ~ (), Simplifiable lvl) => SegOp lvl rep -> SimpleM rep (SegOp lvl (Wise rep), Stms (Wise rep))
- class HasSegOp rep where
- type SegOpLevel rep
- asSegOp :: Op rep -> Maybe (SegOp (SegOpLevel rep) rep)
- segOp :: SegOp (SegOpLevel rep) rep -> Op rep
- segOpRules :: (HasSegOp rep, BinderOps rep, Bindable rep) => RuleBook rep
- segOpReturns :: (Mem rep, Monad m, HasScope rep m) => SegOp lvl rep -> m [ExpReturns]
Documentation
A SegOp
is semantically a perfectly nested stack of maps, on
top of some bottommost computation (scalar computation, reduction,
scan, or histogram). The SegSpace
encodes the original map
structure.
All SegOp
s are parameterised by the representation of their body,
as well as a *level*. The *level* is a representation-specific bit
of information. For example, in GPU backends, it is used to
indicate whether the SegOp
is expected to run at the thread-level
or the group-level.
SegMap lvl SegSpace [Type] (KernelBody rep) | |
SegRed lvl SegSpace [SegBinOp rep] [Type] (KernelBody rep) | The KernelSpace must always have at least two dimensions, implying that the result of a SegRed is always an array. |
SegScan lvl SegSpace [SegBinOp rep] [Type] (KernelBody rep) | |
SegHist lvl SegSpace [HistOp rep] [Type] (KernelBody rep) |
Instances
Do we need group-virtualisation when generating code for the
segmented operation? In most cases, we do, but for some simple
kernels, we compute the full number of groups in advance, and then
virtualisation is an unnecessary (but generally very small)
overhead. This only really matters for fairly trivial but very
wide map
kernels where each thread performs constant-time work on
scalars.
SegVirt | |
SegNoVirt | |
SegNoVirtFull | Not only do we not need virtualisation, but we _guarantee_ that all physical threads participate in the work. This can save some checks in code generation. |
typeCheckSegOp :: Checkable rep => (lvl -> TypeM rep ()) -> SegOp lvl (Aliases rep) -> TypeM rep () Source #
Type check a SegOp
, given a checker for its level.
Index space of a SegOp
.
SegSpace | |
|
scopeOfSegSpace :: SegSpace -> Scope rep Source #
Details
An operator for SegHist
.
HistOp | |
|
Instances
RepTypes rep => Eq (HistOp rep) Source # | |
RepTypes rep => Ord (HistOp rep) Source # | |
RepTypes rep => Show (HistOp rep) Source # | |
SegBinOp | |
|
Instances
RepTypes rep => Eq (SegBinOp rep) Source # | |
RepTypes rep => Ord (SegBinOp rep) Source # | |
Defined in Futhark.IR.SegOp | |
RepTypes rep => Show (SegBinOp rep) Source # | |
PrettyRep rep => Pretty (SegBinOp rep) Source # | |
segBinOpResults :: [SegBinOp rep] -> Int Source #
How many reduction results are produced by these SegBinOp
s?
segBinOpChunks :: [SegBinOp rep] -> [a] -> [[a]] Source #
Split some list into chunks equal to the number of values
returned by each SegBinOp
data KernelBody rep Source #
The body of a SegOp
.
KernelBody | |
|
Instances
aliasAnalyseKernelBody :: (ASTRep rep, CanBeAliased (Op rep)) => AliasTable -> KernelBody rep -> KernelBody (Aliases rep) Source #
Perform alias analysis on a KernelBody
.
consumedInKernelBody :: Aliased rep => KernelBody rep -> Names Source #
The variables consumed in the kernel body.
data ResultManifest Source #
Metadata about whether there is a subtle point to this
KernelResult
. This is used to protect things like tiling, which
might otherwise be removed by the simplifier because they're
semantically redundant. This has no semantic effect and can be
ignored at code generation.
ResultNoSimplify | Don't simplify this one! |
ResultMaySimplify | Go nuts. |
ResultPrivate | The results produced are only used within the same physical thread later on, and can thus be kept in registers. |
Instances
Eq ResultManifest Source # | |
Defined in Futhark.IR.SegOp (==) :: ResultManifest -> ResultManifest -> Bool # (/=) :: ResultManifest -> ResultManifest -> Bool # | |
Ord ResultManifest Source # | |
Defined in Futhark.IR.SegOp compare :: ResultManifest -> ResultManifest -> Ordering # (<) :: ResultManifest -> ResultManifest -> Bool # (<=) :: ResultManifest -> ResultManifest -> Bool # (>) :: ResultManifest -> ResultManifest -> Bool # (>=) :: ResultManifest -> ResultManifest -> Bool # max :: ResultManifest -> ResultManifest -> ResultManifest # min :: ResultManifest -> ResultManifest -> ResultManifest # | |
Show ResultManifest Source # | |
Defined in Futhark.IR.SegOp showsPrec :: Int -> ResultManifest -> ShowS # show :: ResultManifest -> String # showList :: [ResultManifest] -> ShowS # |
data KernelResult Source #
A KernelBody
does not return an ordinary Result
. Instead, it
returns a list of these.
Returns ResultManifest SubExp | Each "worker" in the kernel returns this.
Whether this is a result-per-thread or a
result-per-group depends on where the |
WriteReturns Shape VName [(Slice SubExp, SubExp)] | |
ConcatReturns SplitOrdering SubExp SubExp VName | |
TileReturns [(SubExp, SubExp)] VName | |
RegTileReturns [(SubExp, SubExp, SubExp)] VName |
Instances
kernelResultSubExp :: KernelResult -> SubExp Source #
Get the root SubExp
corresponding values for a KernelResult
.
data SplitOrdering Source #
How an array is split into chunks.
Instances
Generic traversal
data SegOpMapper lvl frep trep m Source #
SegOpMapper | |
|
identitySegOpMapper :: Monad m => SegOpMapper lvl rep rep m Source #
A mapper that simply returns the SegOp
verbatim.
mapSegOpM :: (Applicative m, Monad m) => SegOpMapper lvl frep trep m -> SegOp lvl frep -> m (SegOp lvl trep) Source #
Apply a SegOpMapper
to the given SegOp
.
Simplification
simplifySegOp :: (SimplifiableRep rep, BodyDec rep ~ (), Simplifiable lvl) => SegOp lvl rep -> SimpleM rep (SegOp lvl (Wise rep), Stms (Wise rep)) Source #
Simplify the given SegOp
.
class HasSegOp rep where Source #
Does this rep contain SegOp
s in its Op
s? A rep must be an
instance of this class for the simplification rules to work.
type SegOpLevel rep Source #
segOpRules :: (HasSegOp rep, BinderOps rep, Bindable rep) => RuleBook rep Source #
Simplification rules for simplifying SegOp
s.
Memory
segOpReturns :: (Mem rep, Monad m, HasScope rep m) => SegOp lvl rep -> m [ExpReturns] Source #
Like segOpType
, but for memory representations.