| 1 |
{-# LANGUAGE LambdaCase #-} |
| 2 |
{-# LANGUAGE TypeFamilies #-} |
| 3 |
{-# OPTIONS_GHC -Wno-overlapping-patterns -Wno-incomplete-patterns -Wno-incomplete-uni-patterns -Wno-incomplete-record-updates #-} |
| 4 |
|
| 5 |
module Futhark.Pass.ExtractKernels.DistributeNests |
| 6 |
( MapLoop (..), |
| 7 |
mapLoopStm, |
| 8 |
bodyContainsParallelism, |
| 9 |
lambdaContainsParallelism, |
| 10 |
determineReduceOp, |
| 11 |
histKernel, |
| 12 |
DistEnv (..), |
| 13 |
DistAcc (..), |
| 14 |
runDistNestT, |
| 15 |
DistNestT, |
| 16 |
liftInner, |
| 17 |
distributeMap, |
| 18 |
distribute, |
| 19 |
distributeSingleStm, |
| 20 |
distributeMapBodyStms, |
| 21 |
addStmsToAcc, |
| 22 |
addStmToAcc, |
| 23 |
permutationAndMissing, |
| 24 |
addPostStms, |
| 25 |
postStm, |
| 26 |
inNesting, |
| 27 |
) |
| 28 |
where |
| 29 |
|
| 30 |
import Control.Arrow (first) |
| 31 |
import Control.Monad |
| 32 |
import Control.Monad.RWS.Strict |
| 33 |
import Control.Monad.Reader |
| 34 |
import Control.Monad.Trans.Maybe |
| 35 |
import Control.Monad.Writer.Strict |
| 36 |
import Data.List (find, partition, tails) |
| 37 |
import Data.List.NonEmpty (NonEmpty (..)) |
| 38 |
import Data.Map qualified as M |
| 39 |
import Data.Maybe |
| 40 |
import Futhark.IR |
| 41 |
import Futhark.IR.GPU.Op (SegVirt (..)) |
| 42 |
import Futhark.IR.SOACS (SOACS) |
| 43 |
import Futhark.IR.SOACS qualified as SOACS |
| 44 |
import Futhark.IR.SOACS.SOAC hiding (HistOp, histDest) |
| 45 |
import Futhark.IR.SOACS.Simplify (simpleSOACS, simplifyStms) |
| 46 |
import Futhark.IR.SegOp |
| 47 |
import Futhark.MonadFreshNames |
| 48 |
import Futhark.Pass.ExtractKernels.BlockedKernel |
| 49 |
import Futhark.Pass.ExtractKernels.Distribution |
| 50 |
import Futhark.Pass.ExtractKernels.ISRWIM |
| 51 |
import Futhark.Pass.ExtractKernels.Interchange |
| 52 |
import Futhark.Tools |
| 53 |
import Futhark.Transform.CopyPropagate |
| 54 |
import Futhark.Transform.FirstOrderTransform qualified as FOT |
| 55 |
import Futhark.Transform.Rename |
| 56 |
import Futhark.Util.Log |
| 57 |
|
| 58 |
scopeForSOACs :: (SameScope rep SOACS) => Scope rep -> Scope SOACS |
| 59 |
scopeForSOACs = castScope |
| 60 |
|
| 61 |
data MapLoop = MapLoop (Pat Type) (StmAux ()) SubExp (Lambda SOACS) [VName] |
| 62 |
|
| 63 |
mapLoopStm :: MapLoop -> Stm SOACS |
| 64 |
mapLoopStm (MapLoop pat aux w lam arrs) = |
| 65 |
Let pat aux $ Op $ Screma w arrs $ mapSOAC lam |
| 66 |
|
| 67 |
data DistEnv rep m = DistEnv |
| 68 |
{ distNest :: Nestings, |
| 69 |
distScope :: Scope rep, |
| 70 |
distOnTopLevelStms :: Stms SOACS -> DistNestT rep m (Stms rep), |
| 71 |
distOnInnerMap :: |
| 72 |
MapLoop -> |
| 73 |
DistAcc rep -> |
| 74 |
DistNestT rep m (DistAcc rep), |
| 75 |
distOnSOACSStms :: Stm SOACS -> Builder rep (Stms rep), |
| 76 |
distOnSOACSLambda :: Lambda SOACS -> Builder rep (Lambda rep), |
| 77 |
distSegLevel :: MkSegLevel rep m |
| 78 |
} |
| 79 |
|
| 80 |
data DistAcc rep = DistAcc |
| 81 |
{ distTargets :: Targets, |
| 82 |
distStms :: Stms rep |
| 83 |
} |
| 84 |
|
| 85 |
data DistRes rep = DistRes |
| 86 |
{ accPostStms :: PostStms rep, |
| 87 |
accLog :: Log |
| 88 |
} |
| 89 |
|
| 90 |
instance Semigroup (DistRes rep) where |
| 91 |
DistRes ks1 log1 <> DistRes ks2 log2 = |
| 92 |
DistRes (ks1 <> ks2) (log1 <> log2) |
| 93 |
|
| 94 |
instance Monoid (DistRes rep) where |
| 95 |
mempty = DistRes mempty mempty |
| 96 |
|
| 97 |
newtype PostStms rep = PostStms {unPostStms :: Stms rep} |
| 98 |
|
| 99 |
instance Semigroup (PostStms rep) where |
| 100 |
PostStms xs <> PostStms ys = PostStms $ ys <> xs |
| 101 |
|
| 102 |
instance Monoid (PostStms rep) where |
| 103 |
mempty = PostStms mempty |
| 104 |
|
| 105 |
typeEnvFromDistAcc :: (DistRep rep) => DistAcc rep -> Scope rep |
| 106 |
typeEnvFromDistAcc = scopeOfPat . fst . outerTarget . distTargets |
| 107 |
|
| 108 |
addStmsToAcc :: Stms rep -> DistAcc rep -> DistAcc rep |
| 109 |
addStmsToAcc stms acc = |
| 110 |
acc {distStms = stms <> distStms acc} |
| 111 |
|
| 112 |
addStmToAcc :: |
| 113 |
(MonadFreshNames m, DistRep rep) => |
| 114 |
Stm SOACS -> |
| 115 |
DistAcc rep -> |
| 116 |
DistNestT rep m (DistAcc rep) |
| 117 |
addStmToAcc stm acc = do |
| 118 |
onSoacs <- asks distOnSOACSStms |
| 119 |
(stm', _) <- runBuilder $ onSoacs stm |
| 120 |
pure acc {distStms = stm' <> distStms acc} |
| 121 |
|
| 122 |
soacsLambda :: |
| 123 |
(MonadFreshNames m, DistRep rep) => |
| 124 |
Lambda SOACS -> |
| 125 |
DistNestT rep m (Lambda rep) |
| 126 |
soacsLambda lam = do |
| 127 |
onLambda <- asks distOnSOACSLambda |
| 128 |
fst <$> runBuilder (onLambda lam) |
| 129 |
|
| 130 |
newtype DistNestT rep m a |
| 131 |
= DistNestT (ReaderT (DistEnv rep m) (WriterT (DistRes rep) m) a) |
| 132 |
deriving |
| 133 |
( Functor, |
| 134 |
Applicative, |
| 135 |
Monad, |
| 136 |
MonadReader (DistEnv rep m), |
| 137 |
MonadWriter (DistRes rep) |
| 138 |
) |
| 139 |
|
| 140 |
liftInner :: (LocalScope rep m, DistRep rep) => m a -> DistNestT rep m a |
| 141 |
liftInner m = do |
| 142 |
outer_scope <- askScope |
| 143 |
DistNestT $ |
| 144 |
lift $ |
| 145 |
lift $ do |
| 146 |
inner_scope <- askScope |
| 147 |
localScope (outer_scope `M.difference` inner_scope) m |
| 148 |
|
| 149 |
instance (MonadFreshNames m) => MonadFreshNames (DistNestT rep m) where |
| 150 |
getNameSource = DistNestT $ lift getNameSource |
| 151 |
putNameSource = DistNestT . lift . putNameSource |
| 152 |
|
| 153 |
instance (Monad m, ASTRep rep) => HasScope rep (DistNestT rep m) where |
| 154 |
askScope = asks distScope |
| 155 |
|
| 156 |
instance (Monad m, ASTRep rep) => LocalScope rep (DistNestT rep m) where |
| 157 |
localScope types = local $ \env -> |
| 158 |
env {distScope = types <> distScope env} |
| 159 |
|
| 160 |
instance (Monad m) => MonadLogger (DistNestT rep m) where |
| 161 |
addLog msgs = tell mempty {accLog = msgs} |
| 162 |
|
| 163 |
runDistNestT :: |
| 164 |
(MonadLogger m, DistRep rep) => |
| 165 |
DistEnv rep m -> |
| 166 |
DistNestT rep m (DistAcc rep) -> |
| 167 |
m (Stms rep) |
| 168 |
runDistNestT env (DistNestT m) = do |
| 169 |
(acc, res) <- runWriterT $ runReaderT m env |
| 170 |
addLog $ accLog res |
| 171 |
-- There may be a few final targets remaining - these correspond to |
| 172 |
-- arrays that are identity mapped, and must have statements |
| 173 |
-- inserted here. |
| 174 |
pure $ |
| 175 |
unPostStms (accPostStms res) <> identityStms (outerTarget $ distTargets acc) |
| 176 |
where |
| 177 |
outermost = nestingLoop $ |
| 178 |
case distNest env of |
| 179 |
(nest, []) -> nest |
| 180 |
(_, nest : _) -> nest |
| 181 |
params_to_arrs = |
| 182 |
map (first paramName) $ |
| 183 |
loopNestingParamsAndArrs outermost |
| 184 |
|
| 185 |
identityStms (rem_pat, res) = |
| 186 |
stmsFromList $ zipWith identityStm (patElems rem_pat) res |
| 187 |
identityStm pe (SubExpRes cs (Var v)) |
| 188 |
| Just arr <- lookup v params_to_arrs = |
| 189 |
certify cs . Let (Pat [pe]) (defAux ()) . BasicOp $ |
| 190 |
Replicate mempty (Var arr) |
| 191 |
identityStm pe (SubExpRes cs se) = |
| 192 |
certify cs . Let (Pat [pe]) (defAux ()) . BasicOp $ |
| 193 |
Replicate (Shape [loopNestingWidth outermost]) se |
| 194 |
|
| 195 |
addPostStms :: (Monad m) => PostStms rep -> DistNestT rep m () |
| 196 |
addPostStms ks = tell $ mempty {accPostStms = ks} |
| 197 |
|
| 198 |
postStm :: (Monad m) => Stms rep -> DistNestT rep m () |
| 199 |
postStm stms = addPostStms $ PostStms stms |
| 200 |
|
| 201 |
withStm :: |
| 202 |
(Monad m, DistRep rep) => |
| 203 |
Stm SOACS -> |
| 204 |
DistNestT rep m a -> |
| 205 |
DistNestT rep m a |
| 206 |
withStm stm = local $ \env -> |
| 207 |
env |
| 208 |
{ distScope = |
| 209 |
castScope (scopeOf stm) <> distScope env, |
| 210 |
distNest = |
| 211 |
letBindInInnerNesting provided $ |
| 212 |
distNest env |
| 213 |
} |
| 214 |
where |
| 215 |
provided = namesFromList $ patNames $ stmPat stm |
| 216 |
|
| 217 |
leavingNesting :: |
| 218 |
(MonadFreshNames m, DistRep rep) => |
| 219 |
DistAcc rep -> |
| 220 |
DistNestT rep m (DistAcc rep) |
| 221 |
leavingNesting acc = |
| 222 |
case popInnerTarget $ distTargets acc of |
| 223 |
Nothing -> |
| 224 |
error "The kernel targets list is unexpectedly small" |
| 225 |
Just ((pat, res), newtargets) |
| 226 |
| not $ null $ distStms acc -> do |
| 227 |
-- Any statements left over correspond to something that |
| 228 |
-- could not be distributed because it would cause irregular |
| 229 |
-- arrays. These must be reconstructed into a a Map SOAC |
| 230 |
-- that will be sequentialised. XXX: life would be better if |
| 231 |
-- we were able to distribute irregular parallelism. |
| 232 |
(Nesting _ inner, _) <- asks distNest |
| 233 |
let MapNesting _ aux w params_and_arrs = inner |
| 234 |
body = Body () (distStms acc) res |
| 235 |
used_in_body = freeIn body |
| 236 |
(used_params, used_arrs) = |
| 237 |
unzip $ |
| 238 |
filter ((`nameIn` used_in_body) . paramName . fst) params_and_arrs |
| 239 |
lam' = |
| 240 |
Lambda |
| 241 |
{ lambdaParams = used_params, |
| 242 |
lambdaBody = body, |
| 243 |
lambdaReturnType = map rowType $ patTypes pat |
| 244 |
} |
| 245 |
stms <- |
| 246 |
runBuilder_ . auxing aux . FOT.transformSOAC pat $ |
| 247 |
Screma w used_arrs $ |
| 248 |
mapSOAC lam' |
| 249 |
|
| 250 |
pure $ acc {distTargets = newtargets, distStms = stms} |
| 251 |
| otherwise -> do |
| 252 |
-- Any results left over correspond to a Replicate or a Copy in |
| 253 |
-- the parent nesting, depending on whether the argument is a |
| 254 |
-- parameter of the innermost nesting. |
| 255 |
(Nesting _ inner_nesting, _) <- asks distNest |
| 256 |
let w = loopNestingWidth inner_nesting |
| 257 |
aux = loopNestingAux inner_nesting |
| 258 |
inps = loopNestingParamsAndArrs inner_nesting |
| 259 |
|
| 260 |
remnantStm pe (SubExpRes cs (Var v)) |
| 261 |
| Just (_, arr) <- find ((== v) . paramName . fst) inps = |
| 262 |
certify cs . Let (Pat [pe]) aux . BasicOp $ |
| 263 |
Replicate mempty (Var arr) |
| 264 |
remnantStm pe (SubExpRes cs se) = |
| 265 |
certify cs . Let (Pat [pe]) aux . BasicOp $ |
| 266 |
Replicate (Shape [w]) se |
| 267 |
|
| 268 |
stms = |
| 269 |
stmsFromList $ zipWith remnantStm (patElems pat) res |
| 270 |
|
| 271 |
pure $ acc {distTargets = newtargets, distStms = stms} |
| 272 |
|
| 273 |
mapNesting :: |
| 274 |
(MonadFreshNames m, DistRep rep) => |
| 275 |
Pat Type -> |
| 276 |
StmAux () -> |
| 277 |
SubExp -> |
| 278 |
Lambda SOACS -> |
| 279 |
[VName] -> |
| 280 |
DistNestT rep m (DistAcc rep) -> |
| 281 |
DistNestT rep m (DistAcc rep) |
| 282 |
mapNesting pat aux w lam arrs m = |
| 283 |
local extend $ leavingNesting =<< m |
| 284 |
where |
| 285 |
nest = |
| 286 |
Nesting mempty $ |
| 287 |
MapNesting pat aux w $ |
| 288 |
zip (lambdaParams lam) arrs |
| 289 |
extend env = |
| 290 |
env |
| 291 |
{ distNest = pushInnerNesting nest $ distNest env, |
| 292 |
distScope = castScope (scopeOf lam) <> distScope env |
| 293 |
} |
| 294 |
|
| 295 |
inNesting :: |
| 296 |
(Monad m, DistRep rep) => |
| 297 |
KernelNest -> |
| 298 |
DistNestT rep m a -> |
| 299 |
DistNestT rep m a |
| 300 |
inNesting (outer, nests) = local $ \env -> |
| 301 |
env |
| 302 |
{ distNest = (inner, nests'), |
| 303 |
distScope = foldMap scopeOfLoopNesting (outer : nests) <> distScope env |
| 304 |
} |
| 305 |
where |
| 306 |
(inner, nests') = |
| 307 |
case reverse nests of |
| 308 |
[] -> (asNesting outer, []) |
| 309 |
(inner' : ns) -> (asNesting inner', map asNesting $ outer : reverse ns) |
| 310 |
asNesting = Nesting mempty |
| 311 |
|
| 312 |
bodyContainsParallelism :: Body SOACS -> Bool |
| 313 |
bodyContainsParallelism = any isParallelStm . bodyStms |
| 314 |
where |
| 315 |
isParallelStm stm = |
| 316 |
isMap (stmExp stm) |
| 317 |
&& not ("sequential" `inAttrs` stmAuxAttrs (stmAux stm)) |
| 318 |
isMap BasicOp {} = False |
| 319 |
isMap Apply {} = False |
| 320 |
isMap Match {} = False |
| 321 |
isMap (Loop _ ForLoop {} body) = bodyContainsParallelism body |
| 322 |
isMap (Loop _ WhileLoop {} _) = False |
| 323 |
isMap (WithAcc _ lam) = bodyContainsParallelism $ lambdaBody lam |
| 324 |
isMap Op {} = True |
| 325 |
|
| 326 |
lambdaContainsParallelism :: Lambda SOACS -> Bool |
| 327 |
lambdaContainsParallelism = bodyContainsParallelism . lambdaBody |
| 328 |
|
| 329 |
distributeMapBodyStms :: |
| 330 |
(MonadFreshNames m, LocalScope rep m, DistRep rep) => |
| 331 |
DistAcc rep -> |
| 332 |
Stms SOACS -> |
| 333 |
DistNestT rep m (DistAcc rep) |
| 334 |
distributeMapBodyStms orig_acc = distribute <=< onStms orig_acc . stmsToList |
| 335 |
where |
| 336 |
onStms acc [] = pure acc |
| 337 |
onStms acc (Let pat aux (Op (Stream w arrs accs lam)) : stms) = do |
| 338 |
types <- asksScope scopeForSOACs |
| 339 |
stream_stms <- |
| 340 |
snd <$> runBuilderT (sequentialStreamWholeArray pat w accs lam arrs) types |
| 341 |
stream_stms' <- |
| 342 |
runReaderT (copyPropagateInStms simpleSOACS types stream_stms) types |
| 343 |
onStms acc $ stmsToList (fmap (certify (stmAuxCerts aux)) stream_stms') ++ stms |
| 344 |
onStms acc (stm : stms) = |
| 345 |
-- It is important that stm is in scope if 'maybeDistributeStm' |
| 346 |
-- wants to distribute, even if this causes the slightly silly |
| 347 |
-- situation that stm is in scope of itself. |
| 348 |
withStm stm $ maybeDistributeStm stm =<< onStms acc stms |
| 349 |
|
| 350 |
onInnerMap :: (Monad m) => MapLoop -> DistAcc rep -> DistNestT rep m (DistAcc rep) |
| 351 |
onInnerMap loop acc = do |
| 352 |
f <- asks distOnInnerMap |
| 353 |
f loop acc |
| 354 |
|
| 355 |
onTopLevelStms :: (Monad m) => Stms SOACS -> DistNestT rep m () |
| 356 |
onTopLevelStms stms = do |
| 357 |
f <- asks distOnTopLevelStms |
| 358 |
postStm =<< f stms |
| 359 |
|
| 360 |
maybeDistributeStm :: |
| 361 |
(MonadFreshNames m, LocalScope rep m, DistRep rep) => |
| 362 |
Stm SOACS -> |
| 363 |
DistAcc rep -> |
| 364 |
DistNestT rep m (DistAcc rep) |
| 365 |
maybeDistributeStm stm acc |
| 366 |
| "sequential" `inAttrs` stmAuxAttrs (stmAux stm) = |
| 367 |
addStmToAcc stm acc |
| 368 |
maybeDistributeStm (Let pat aux (Op soac)) acc |
| 369 |
| "sequential_outer" `inAttrs` stmAuxAttrs aux = |
| 370 |
distributeMapBodyStms acc . fmap (certify (stmAuxCerts aux)) |
| 371 |
=<< runBuilder_ (FOT.transformSOAC pat soac) |
| 372 |
maybeDistributeStm stm@(Let pat _ (Op (Screma w arrs form))) acc |
| 373 |
| Just lam <- isMapSOAC form = |
| 374 |
-- Only distribute inside the map if we can distribute everything |
| 375 |
-- following the map. |
| 376 |
distributeIfPossible acc >>= \case |
| 377 |
Nothing -> addStmToAcc stm acc |
| 378 |
Just acc' -> distribute =<< onInnerMap (MapLoop pat (stmAux stm) w lam arrs) acc' |
| 379 |
maybeDistributeStm stm@(Let pat aux (Loop merge form@ForLoop {} body)) acc |
| 380 |
| all (`notNameIn` freeIn (patTypes pat)) (patNames pat), |
| 381 |
bodyContainsParallelism body = |
| 382 |
distributeSingleStm acc stm >>= \case |
| 383 |
Just (kernels, res, nest, acc') |
| 384 |
| -- XXX: We cannot distribute if this loop depends on |
| 385 |
-- certificates bound within the loop nest (well, we could, |
| 386 |
-- but interchange would not be valid). This is not a |
| 387 |
-- fundamental restriction, but an artifact of our |
| 388 |
-- certificate representation, which we should probably |
| 389 |
-- rethink. |
| 390 |
not $ |
| 391 |
(freeIn form <> freeIn aux) |
| 392 |
`namesIntersect` boundInKernelNest nest, |
| 393 |
Just (perm, pat_unused) <- permutationAndMissing pat res -> |
| 394 |
-- We need to pretend pat_unused was used anyway, by adding |
| 395 |
-- it to the kernel nest. |
| 396 |
localScope (typeEnvFromDistAcc acc') $ do |
| 397 |
addPostStms kernels |
| 398 |
nest' <- expandKernelNest pat_unused nest |
| 399 |
types <- asksScope scopeForSOACs |
| 400 |
|
| 401 |
-- Simplification is key to hoisting out statements that |
| 402 |
-- were variant to the loop, but invariant to the outer maps |
| 403 |
-- (which are now innermost). |
| 404 |
stms <- |
| 405 |
(`runReaderT` types) $ |
| 406 |
simplifyStms =<< interchangeLoops nest' (SeqLoop perm pat merge form body) |
| 407 |
onTopLevelStms stms |
| 408 |
pure acc' |
| 409 |
_ -> |
| 410 |
addStmToAcc stm acc |
| 411 |
maybeDistributeStm stm@(Let pat _ (Match cond cases defbody ret)) acc |
| 412 |
| all (`notNameIn` freeIn pat) (patNames pat), |
| 413 |
any bodyContainsParallelism (defbody : map caseBody cases) |
| 414 |
|| not (all primType (matchReturns ret)) = |
| 415 |
distributeSingleStm acc stm >>= \case |
| 416 |
Just (kernels, res, nest, acc') |
| 417 |
| not $ |
| 418 |
(freeIn cond <> freeIn ret) `namesIntersect` boundInKernelNest nest, |
| 419 |
Just (perm, pat_unused) <- permutationAndMissing pat res -> |
| 420 |
-- We need to pretend pat_unused was used anyway, by adding |
| 421 |
-- it to the kernel nest. |
| 422 |
localScope (typeEnvFromDistAcc acc') $ do |
| 423 |
nest' <- expandKernelNest pat_unused nest |
| 424 |
addPostStms kernels |
| 425 |
types <- asksScope scopeForSOACs |
| 426 |
let branch = Branch perm pat cond cases defbody ret |
| 427 |
stms <- |
| 428 |
(`runReaderT` types) $ |
| 429 |
simplifyStms . oneStm =<< interchangeBranch nest' branch |
| 430 |
onTopLevelStms stms |
| 431 |
pure acc' |
| 432 |
_ -> |
| 433 |
addStmToAcc stm acc |
| 434 |
maybeDistributeStm stm@(Let pat _ (WithAcc inputs lam)) acc |
| 435 |
| lambdaContainsParallelism lam = |
| 436 |
distributeSingleStm acc stm >>= \case |
| 437 |
Just (kernels, res, nest, acc') |
| 438 |
| not $ |
| 439 |
freeIn (drop num_accs (lambdaReturnType lam)) |
| 440 |
`namesIntersect` boundInKernelNest nest, |
| 441 |
Just (perm, pat_unused) <- permutationAndMissing pat res -> |
| 442 |
-- We need to pretend pat_unused was used anyway, by adding |
| 443 |
-- it to the kernel nest. |
| 444 |
localScope (typeEnvFromDistAcc acc') $ do |
| 445 |
nest' <- expandKernelNest pat_unused nest |
| 446 |
types <- asksScope scopeForSOACs |
| 447 |
addPostStms kernels |
| 448 |
let withacc = WithAccStm perm pat inputs lam |
| 449 |
stms <- |
| 450 |
(`runReaderT` types) $ |
| 451 |
simplifyStms . oneStm =<< interchangeWithAcc nest' withacc |
| 452 |
onTopLevelStms stms |
| 453 |
pure acc' |
| 454 |
_ -> |
| 455 |
addStmToAcc stm acc |
| 456 |
where |
| 457 |
num_accs = length inputs |
| 458 |
maybeDistributeStm (Let pat aux (Op (Screma w arrs form))) acc |
| 459 |
| Just [Reduce comm lam nes] <- isReduceSOAC form, |
| 460 |
Just m <- irwim pat w comm lam $ zip nes arrs = do |
| 461 |
types <- asksScope scopeForSOACs |
| 462 |
(_, stms) <- runBuilderT (auxing aux m) types |
| 463 |
distributeMapBodyStms acc stms |
| 464 |
|
| 465 |
-- Parallelise segmented scatters. |
| 466 |
maybeDistributeStm stm@(Let pat aux (Op (Scatter w ivs as lam))) acc = |
| 467 |
distributeSingleStm acc stm >>= \case |
| 468 |
Just (kernels, res, nest, acc') |
| 469 |
| Just (perm, pat_unused) <- permutationAndMissing pat res -> |
| 470 |
localScope (typeEnvFromDistAcc acc') $ do |
| 471 |
nest' <- expandKernelNest pat_unused nest |
| 472 |
lam' <- soacsLambda lam |
| 473 |
addPostStms kernels |
| 474 |
postStm =<< segmentedScatterKernel nest' perm pat (stmAuxCerts aux) w lam' ivs as |
| 475 |
pure acc' |
| 476 |
_ -> |
| 477 |
addStmToAcc stm acc |
| 478 |
-- Parallelise segmented Hist. |
| 479 |
maybeDistributeStm stm@(Let pat aux (Op (Hist w as ops lam))) acc = |
| 480 |
distributeSingleStm acc stm >>= \case |
| 481 |
Just (kernels, res, nest, acc') |
| 482 |
| Just (perm, pat_unused) <- permutationAndMissing pat res -> |
| 483 |
localScope (typeEnvFromDistAcc acc') $ do |
| 484 |
lam' <- soacsLambda lam |
| 485 |
nest' <- expandKernelNest pat_unused nest |
| 486 |
addPostStms kernels |
| 487 |
postStm =<< segmentedHistKernel nest' perm (stmAuxCerts aux) w ops lam' as |
| 488 |
pure acc' |
| 489 |
_ -> |
| 490 |
addStmToAcc stm acc |
| 491 |
-- Parallelise Index slices if the result is going to be returned |
| 492 |
-- directly from the kernel. This is because we would otherwise have |
| 493 |
-- to sequentialise writing the result, which may be costly. |
| 494 |
maybeDistributeStm stm@(Let (Pat [pe]) aux (BasicOp (Index arr slice))) acc |
| 495 |
| not $ null $ sliceDims slice, |
| 496 |
Var (patElemName pe) `elem` map resSubExp (snd (innerTarget (distTargets acc))) = |
| 497 |
distributeSingleStm acc stm >>= \case |
| 498 |
Just (kernels, _res, nest, acc') -> |
| 499 |
localScope (typeEnvFromDistAcc acc') $ do |
| 500 |
addPostStms kernels |
| 501 |
postStm =<< segmentedGatherKernel nest (stmAuxCerts aux) arr slice |
| 502 |
pure acc' |
| 503 |
_ -> |
| 504 |
addStmToAcc stm acc |
| 505 |
-- If the scan can be distributed by itself, we will turn it into a |
| 506 |
-- segmented scan. |
| 507 |
-- |
| 508 |
-- If the scan cannot be distributed by itself, it will be |
| 509 |
-- sequentialised in the default case for this function. |
| 510 |
maybeDistributeStm stm@(Let pat aux (Op (Screma w arrs form))) acc |
| 511 |
| Just (scans, map_lam) <- isScanomapSOAC form, |
| 512 |
Scan lam nes <- singleScan scans = |
| 513 |
distributeSingleStm acc stm >>= \case |
| 514 |
Just (kernels, res, nest, acc') |
| 515 |
| Just (perm, pat_unused) <- permutationAndMissing pat res -> |
| 516 |
-- We need to pretend pat_unused was used anyway, by adding |
| 517 |
-- it to the kernel nest. |
| 518 |
localScope (typeEnvFromDistAcc acc') $ do |
| 519 |
nest' <- expandKernelNest pat_unused nest |
| 520 |
map_lam' <- soacsLambda map_lam |
| 521 |
localScope (typeEnvFromDistAcc acc') $ |
| 522 |
segmentedScanomapKernel nest' perm (stmAuxCerts aux) w lam map_lam' nes arrs |
| 523 |
>>= kernelOrNot mempty stm acc kernels acc' |
| 524 |
_ -> |
| 525 |
addStmToAcc stm acc |
| 526 |
-- If the map function of the reduction contains parallelism we split |
| 527 |
-- it, so that the parallelism can be exploited. |
| 528 |
maybeDistributeStm (Let pat aux (Op (Screma w arrs form))) acc |
| 529 |
| Just (reds, map_lam) <- isRedomapSOAC form, |
| 530 |
lambdaContainsParallelism map_lam = do |
| 531 |
(mapstm, redstm) <- |
| 532 |
redomapToMapAndReduce pat (w, reds, map_lam, arrs) |
| 533 |
distributeMapBodyStms acc $ oneStm mapstm {stmAux = aux} <> oneStm redstm |
| 534 |
-- if the reduction can be distributed by itself, we will turn it into a |
| 535 |
-- segmented reduce. |
| 536 |
-- |
| 537 |
-- If the reduction cannot be distributed by itself, it will be |
| 538 |
-- sequentialised in the default case for this function. |
| 539 |
maybeDistributeStm stm@(Let pat aux (Op (Screma w arrs form))) acc |
| 540 |
| Just (reds, map_lam) <- isRedomapSOAC form, |
| 541 |
Reduce comm lam nes <- singleReduce reds = |
| 542 |
distributeSingleStm acc stm >>= \case |
| 543 |
Just (kernels, res, nest, acc') |
| 544 |
| Just (perm, pat_unused) <- permutationAndMissing pat res -> |
| 545 |
-- We need to pretend pat_unused was used anyway, by adding |
| 546 |
-- it to the kernel nest. |
| 547 |
localScope (typeEnvFromDistAcc acc') $ do |
| 548 |
nest' <- expandKernelNest pat_unused nest |
| 549 |
|
| 550 |
lam' <- soacsLambda lam |
| 551 |
map_lam' <- soacsLambda map_lam |
| 552 |
|
| 553 |
let comm' |
| 554 |
| commutativeLambda lam = Commutative |
| 555 |
| otherwise = comm |
| 556 |
|
| 557 |
regularSegmentedRedomapKernel nest' perm (stmAuxCerts aux) w comm' lam' map_lam' nes arrs |
| 558 |
>>= kernelOrNot mempty stm acc kernels acc' |
| 559 |
_ -> |
| 560 |
addStmToAcc stm acc |
| 561 |
maybeDistributeStm (Let pat aux (Op (Screma w arrs form))) acc = do |
| 562 |
-- This Screma is too complicated for us to immediately do |
| 563 |
-- anything, so split it up and try again. |
| 564 |
scope <- asksScope scopeForSOACs |
| 565 |
distributeMapBodyStms acc . fmap (certify (stmAuxCerts aux)) . snd |
| 566 |
=<< runBuilderT (dissectScrema pat w form arrs) scope |
| 567 |
maybeDistributeStm stm@(Let _ aux (BasicOp (Replicate shape (Var stm_arr)))) acc = do |
| 568 |
distributeSingleUnaryStm acc stm stm_arr $ \nest outerpat arr -> |
| 569 |
if shape == mempty |
| 570 |
then pure $ oneStm $ Let outerpat aux $ BasicOp $ Replicate mempty $ Var arr |
| 571 |
else runBuilder_ $ auxing aux $ do |
| 572 |
arr_t <- lookupType arr |
| 573 |
let arr_r = arrayRank arr_t |
| 574 |
nest_r = length (snd nest) + 1 |
| 575 |
res_r = arr_r + shapeRank shape |
| 576 |
-- Move the to-be-replicated dimensions outermost. |
| 577 |
arr_tr <- |
| 578 |
letExp (baseString arr <> "_tr") . BasicOp $ |
| 579 |
Rearrange arr ([nest_r .. arr_r - 1] ++ [0 .. nest_r - 1]) |
| 580 |
-- Replicate the now-outermost dimensions appropriately. |
| 581 |
arr_tr_rep <- |
| 582 |
letExp (baseString arr <> "_tr_rep") . BasicOp $ |
| 583 |
Replicate shape (Var arr_tr) |
| 584 |
-- Move the replicated dimensions back where they belong. |
| 585 |
letBind outerpat . BasicOp $ |
| 586 |
Rearrange arr_tr_rep ([res_r - nest_r .. res_r - 1] ++ [0 .. res_r - nest_r - 1]) |
| 587 |
maybeDistributeStm stm@(Let _ aux (BasicOp (Replicate shape v))) acc = do |
| 588 |
distributeSingleStm acc stm >>= \case |
| 589 |
Just (kernels, _, nest, acc') |
| 590 |
| boundInKernelNest nest == mempty -> do |
| 591 |
addPostStms kernels |
| 592 |
let outerpat = loopNestingPat $ fst nest |
| 593 |
nest_shape = Shape $ kernelNestWidths nest |
| 594 |
localScope (typeEnvFromDistAcc acc') $ do |
| 595 |
postStm <=< runBuilder_ . auxing aux . letBind outerpat $ |
| 596 |
BasicOp (Replicate (nest_shape <> shape) v) |
| 597 |
pure acc' |
| 598 |
_ -> addStmToAcc stm acc |
| 599 |
-- Opaques are applied to the full array, because otherwise they can |
| 600 |
-- drastically inhibit parallelisation in some cases. |
| 601 |
maybeDistributeStm stm@(Let (Pat [pe]) aux (BasicOp (Opaque _ (Var stm_arr)))) acc |
| 602 |
| not $ primType $ typeOf pe = |
| 603 |
distributeSingleUnaryStm acc stm stm_arr $ \_ outerpat arr -> |
| 604 |
pure $ oneStm $ Let outerpat aux $ BasicOp $ Replicate mempty $ Var arr |
| 605 |
maybeDistributeStm stm@(Let _ aux (BasicOp (Rearrange stm_arr perm))) acc = |
| 606 |
distributeSingleUnaryStm acc stm stm_arr $ \nest outerpat arr -> do |
| 607 |
let r = length (snd nest) + 1 |
| 608 |
perm' = [0 .. r - 1] ++ map (+ r) perm |
| 609 |
-- We need to add a copy, because the original map nest |
| 610 |
-- will have produced an array without aliases, and so must we. |
| 611 |
arr' <- newVName $ baseString arr |
| 612 |
arr_t <- lookupType arr |
| 613 |
pure $ |
| 614 |
stmsFromList |
| 615 |
[ Let (Pat [PatElem arr' arr_t]) aux $ BasicOp $ Replicate mempty $ Var arr, |
| 616 |
Let outerpat aux $ BasicOp $ Rearrange arr' perm' |
| 617 |
] |
| 618 |
maybeDistributeStm stm@(Let _ aux (BasicOp (Reshape stm_arr reshape))) acc = |
| 619 |
distributeSingleUnaryStm acc stm stm_arr $ \nest outerpat arr -> do |
| 620 |
let outer = Shape (kernelNestWidths nest) |
| 621 |
reshape' = reshapeCoerce outer <> newshapeInner outer reshape |
| 622 |
pure $ oneStm $ Let outerpat aux $ BasicOp $ Reshape arr reshape' |
| 623 |
maybeDistributeStm stm@(Let pat aux (BasicOp (Update _ arr slice (Var v)))) acc |
| 624 |
| not $ null $ sliceDims slice = |
| 625 |
distributeSingleStm acc stm >>= \case |
| 626 |
Just (kernels, res, nest, acc') |
| 627 |
| map resSubExp res == map Var (patNames $ stmPat stm), |
| 628 |
Just (perm, pat_unused) <- permutationAndMissing pat res -> do |
| 629 |
addPostStms kernels |
| 630 |
localScope (typeEnvFromDistAcc acc') $ do |
| 631 |
nest' <- expandKernelNest pat_unused nest |
| 632 |
postStm |
| 633 |
=<< segmentedUpdateKernel nest' perm (stmAuxCerts aux) arr slice v |
| 634 |
pure acc' |
| 635 |
_ -> addStmToAcc stm acc |
| 636 |
maybeDistributeStm stm@(Let _ aux (BasicOp (Concat d (x :| xs) w))) acc = |
| 637 |
distributeSingleStm acc stm >>= \case |
| 638 |
Just (kernels, _, nest, acc') -> |
| 639 |
localScope (typeEnvFromDistAcc acc') $ |
| 640 |
segmentedConcat nest |
| 641 |
>>= kernelOrNot (stmAuxCerts aux) stm acc kernels acc' |
| 642 |
_ -> |
| 643 |
addStmToAcc stm acc |
| 644 |
where |
| 645 |
segmentedConcat nest = |
| 646 |
isSegmentedOp nest [0] mempty mempty [] (x : xs) $ |
| 647 |
\pat _ _ _ (x' : xs') -> |
| 648 |
let d' = d + length (snd nest) + 1 |
| 649 |
in addStm $ Let pat aux $ BasicOp $ Concat d' (x' :| xs') w |
| 650 |
maybeDistributeStm stm acc = |
| 651 |
addStmToAcc stm acc |
| 652 |
|
| 653 |
distributeSingleUnaryStm :: |
| 654 |
(MonadFreshNames m, LocalScope rep m, DistRep rep) => |
| 655 |
DistAcc rep -> |
| 656 |
Stm SOACS -> |
| 657 |
VName -> |
| 658 |
(KernelNest -> Pat Type -> VName -> DistNestT rep m (Stms rep)) -> |
| 659 |
DistNestT rep m (DistAcc rep) |
| 660 |
distributeSingleUnaryStm acc stm stm_arr f = |
| 661 |
distributeSingleStm acc stm >>= \case |
| 662 |
Just (kernels, res, nest, acc') |
| 663 |
| map resSubExp res == map Var (patNames $ stmPat stm), |
| 664 |
(outer, _) <- nest, |
| 665 |
[(_, arr)] <- loopNestingParamsAndArrs outer, |
| 666 |
boundInKernelNest nest `namesIntersection` freeIn stm |
| 667 |
== oneName stm_arr, |
| 668 |
perfectlyMapped arr nest -> do |
| 669 |
addPostStms kernels |
| 670 |
let outerpat = loopNestingPat $ fst nest |
| 671 |
localScope (typeEnvFromDistAcc acc') $ do |
| 672 |
postStm =<< f nest outerpat arr |
| 673 |
pure acc' |
| 674 |
_ -> addStmToAcc stm acc |
| 675 |
where |
| 676 |
perfectlyMapped arr (outer, nest) |
| 677 |
| [(p, arr')] <- loopNestingParamsAndArrs outer, |
| 678 |
arr == arr' = |
| 679 |
case nest of |
| 680 |
[] -> paramName p == stm_arr |
| 681 |
x : xs -> perfectlyMapped (paramName p) (x, xs) |
| 682 |
| otherwise = |
| 683 |
False |
| 684 |
|
| 685 |
distribute :: |
| 686 |
(MonadFreshNames m, LocalScope rep m, DistRep rep) => |
| 687 |
DistAcc rep -> |
| 688 |
DistNestT rep m (DistAcc rep) |
| 689 |
distribute acc = |
| 690 |
fromMaybe acc <$> distributeIfPossible acc |
| 691 |
|
| 692 |
mkSegLevel :: |
| 693 |
(MonadFreshNames m, LocalScope rep m, DistRep rep) => |
| 694 |
DistNestT rep m (MkSegLevel rep (DistNestT rep m)) |
| 695 |
mkSegLevel = do |
| 696 |
mk_lvl <- asks distSegLevel |
| 697 |
pure $ \w desc r -> do |
| 698 |
(lvl, stms) <- lift $ liftInner $ runBuilderT' $ mk_lvl w desc r |
| 699 |
addStms stms |
| 700 |
pure lvl |
| 701 |
|
| 702 |
distributeIfPossible :: |
| 703 |
(MonadFreshNames m, LocalScope rep m, DistRep rep) => |
| 704 |
DistAcc rep -> |
| 705 |
DistNestT rep m (Maybe (DistAcc rep)) |
| 706 |
distributeIfPossible acc = do |
| 707 |
nest <- asks distNest |
| 708 |
mk_lvl <- mkSegLevel |
| 709 |
tryDistribute mk_lvl nest (distTargets acc) (distStms acc) >>= \case |
| 710 |
Nothing -> pure Nothing |
| 711 |
Just (targets, kernel) -> do |
| 712 |
postStm kernel |
| 713 |
pure $ |
| 714 |
Just |
| 715 |
DistAcc |
| 716 |
{ distTargets = targets, |
| 717 |
distStms = mempty |
| 718 |
} |
| 719 |
|
| 720 |
distributeSingleStm :: |
| 721 |
(MonadFreshNames m, LocalScope rep m, DistRep rep) => |
| 722 |
DistAcc rep -> |
| 723 |
Stm SOACS -> |
| 724 |
DistNestT |
| 725 |
rep |
| 726 |
m |
| 727 |
( Maybe |
| 728 |
( PostStms rep, |
| 729 |
Result, |
| 730 |
KernelNest, |
| 731 |
DistAcc rep |
| 732 |
) |
| 733 |
) |
| 734 |
distributeSingleStm acc stm = do |
| 735 |
nest <- asks distNest |
| 736 |
mk_lvl <- mkSegLevel |
| 737 |
tryDistribute mk_lvl nest (distTargets acc) (distStms acc) >>= \case |
| 738 |
Nothing -> pure Nothing |
| 739 |
Just (targets, distributed_stms) -> |
| 740 |
tryDistributeStm nest targets stm >>= \case |
| 741 |
Nothing -> pure Nothing |
| 742 |
Just (res, targets', new_kernel_nest) -> |
| 743 |
pure $ |
| 744 |
Just |
| 745 |
( PostStms distributed_stms, |
| 746 |
res, |
| 747 |
new_kernel_nest, |
| 748 |
DistAcc |
| 749 |
{ distTargets = targets', |
| 750 |
distStms = mempty |
| 751 |
} |
| 752 |
) |
| 753 |
|
| 754 |
segmentedScatterKernel :: |
| 755 |
(MonadFreshNames m, LocalScope rep m, DistRep rep) => |
| 756 |
KernelNest -> |
| 757 |
[Int] -> |
| 758 |
Pat Type -> |
| 759 |
Certs -> |
| 760 |
SubExp -> |
| 761 |
Lambda rep -> |
| 762 |
[VName] -> |
| 763 |
[(Shape, Int, VName)] -> |
| 764 |
DistNestT rep m (Stms rep) |
| 765 |
segmentedScatterKernel nest perm scatter_pat cs scatter_w lam ivs dests = do |
| 766 |
-- We replicate some of the checking done by 'isSegmentedOp', but |
| 767 |
-- things are different because a scatter is not a reduction or |
| 768 |
-- scan. |
| 769 |
-- |
| 770 |
-- First, pretend that the scatter is also part of the nesting. The |
| 771 |
-- KernelNest we produce here is technically not sensible, but it's |
| 772 |
-- good enough for flatKernel to work. |
| 773 |
let nesting = |
| 774 |
MapNesting scatter_pat (StmAux cs mempty mempty ()) scatter_w $ zip (lambdaParams lam) ivs |
| 775 |
nest' = |
| 776 |
pushInnerKernelNesting (scatter_pat, bodyResult $ lambdaBody lam) nesting nest |
| 777 |
(ispace, kernel_inps) <- flatKernel nest' |
| 778 |
|
| 779 |
let (as_ws, as_ns, as) = unzip3 dests |
| 780 |
indexes = zipWith (*) as_ns $ map length as_ws |
| 781 |
|
| 782 |
-- The input/output arrays ('as') _must_ correspond to some kernel |
| 783 |
-- input, or else the original nested scatter would have been |
| 784 |
-- ill-typed. Find them. |
| 785 |
as_inps <- mapM (findInput kernel_inps) as |
| 786 |
|
| 787 |
mk_lvl <- mkSegLevel |
| 788 |
|
| 789 |
let (is, vs) = splitAt (sum indexes) $ bodyResult $ lambdaBody lam |
| 790 |
(is', k_body_stms) <- runBuilder $ do |
| 791 |
addStms $ bodyStms $ lambdaBody lam |
| 792 |
pure is |
| 793 |
|
| 794 |
let grouped = groupScatterResults (zip3 as_ws as_ns as_inps) (is' ++ vs) |
| 795 |
(_, dest_arrs, _) = unzip3 grouped |
| 796 |
|
| 797 |
dest_arrs_ts <- mapM (lookupType . kernelInputArray) dest_arrs |
| 798 |
|
| 799 |
let k_body = |
| 800 |
KernelBody () k_body_stms $ |
| 801 |
zipWith (inPlaceReturn ispace) dest_arrs_ts grouped |
| 802 |
-- Remove unused kernel inputs, since some of these might |
| 803 |
-- reference the array we are scattering into. |
| 804 |
kernel_inps' = |
| 805 |
filter ((`nameIn` freeIn k_body) . kernelInputName) kernel_inps |
| 806 |
|
| 807 |
(k, k_stms) <- mapKernel mk_lvl ispace kernel_inps' dest_arrs_ts k_body |
| 808 |
|
| 809 |
traverse renameStm <=< runBuilder_ $ do |
| 810 |
addStms k_stms |
| 811 |
|
| 812 |
let pat = Pat . rearrangeShape perm $ patElems $ loopNestingPat $ fst nest |
| 813 |
letBind pat $ Op $ segOp k |
| 814 |
where |
| 815 |
findInput kernel_inps a = |
| 816 |
maybe bad pure $ find ((== a) . kernelInputName) kernel_inps |
| 817 |
bad = error "Ill-typed nested scatter encountered." |
| 818 |
|
| 819 |
inPlaceReturn ispace arr_t (_, inp, is_vs) = |
| 820 |
WriteReturns write_cs (kernelInputArray inp) $ do |
| 821 |
(is, v) <- is_vs |
| 822 |
pure |
| 823 |
( fullSlice arr_t . map DimFix $ |
| 824 |
map Var (init gtids) ++ map resSubExp is, |
| 825 |
resSubExp v |
| 826 |
) |
| 827 |
where |
| 828 |
write_cs = |
| 829 |
foldMap (foldMap resCerts . fst) is_vs |
| 830 |
<> foldMap (resCerts . snd) is_vs |
| 831 |
(gtids, _ws) = unzip ispace |
| 832 |
|
| 833 |
segmentedUpdateKernel :: |
| 834 |
(MonadFreshNames m, LocalScope rep m, DistRep rep) => |
| 835 |
KernelNest -> |
| 836 |
[Int] -> |
| 837 |
Certs -> |
| 838 |
VName -> |
| 839 |
Slice SubExp -> |
| 840 |
VName -> |
| 841 |
DistNestT rep m (Stms rep) |
| 842 |
segmentedUpdateKernel nest perm cs arr slice v = do |
| 843 |
(base_ispace, kernel_inps) <- flatKernel nest |
| 844 |
let slice_dims = sliceDims slice |
| 845 |
slice_gtids <- replicateM (length slice_dims) (newVName "gtid_slice") |
| 846 |
|
| 847 |
let ispace = base_ispace ++ zip slice_gtids slice_dims |
| 848 |
|
| 849 |
((dest_t, res), kstms) <- runBuilder $ do |
| 850 |
-- Compute indexes into full array. |
| 851 |
v' <- |
| 852 |
certifying cs . letSubExp "v" . BasicOp . Index v $ |
| 853 |
Slice (map (DimFix . Var) slice_gtids) |
| 854 |
slice_is <- |
| 855 |
traverse (toSubExp "index") $ |
| 856 |
fixSlice (fmap pe64 slice) $ |
| 857 |
map (pe64 . Var) slice_gtids |
| 858 |
|
| 859 |
let write_is = map (Var . fst) base_ispace ++ slice_is |
| 860 |
arr' = |
| 861 |
maybe (error "incorrectly typed Update") kernelInputArray $ |
| 862 |
find ((== arr) . kernelInputName) kernel_inps |
| 863 |
arr_t <- lookupType arr' |
| 864 |
pure |
| 865 |
( arr_t, |
| 866 |
WriteReturns mempty arr' [(Slice $ map DimFix write_is, v')] |
| 867 |
) |
| 868 |
|
| 869 |
-- Remove unused kernel inputs, since some of these might |
| 870 |
-- reference the array we are scattering into. |
| 871 |
let kernel_inps' = |
| 872 |
filter ((`nameIn` (freeIn kstms <> freeIn res)) . kernelInputName) kernel_inps |
| 873 |
|
| 874 |
mk_lvl <- mkSegLevel |
| 875 |
(k, prestms) <- |
| 876 |
mapKernel mk_lvl ispace kernel_inps' [dest_t] $ |
| 877 |
KernelBody () kstms [res] |
| 878 |
|
| 879 |
traverse renameStm <=< runBuilder_ $ do |
| 880 |
addStms prestms |
| 881 |
let pat = Pat . rearrangeShape perm $ patElems $ loopNestingPat $ fst nest |
| 882 |
letBind pat $ Op $ segOp k |
| 883 |
|
| 884 |
segmentedGatherKernel :: |
| 885 |
(MonadFreshNames m, LocalScope rep m, DistRep rep) => |
| 886 |
KernelNest -> |
| 887 |
Certs -> |
| 888 |
VName -> |
| 889 |
Slice SubExp -> |
| 890 |
DistNestT rep m (Stms rep) |
| 891 |
segmentedGatherKernel nest cs arr slice = do |
| 892 |
let slice_dims = sliceDims slice |
| 893 |
slice_gtids <- replicateM (length slice_dims) (newVName "gtid_slice") |
| 894 |
|
| 895 |
(base_ispace, kernel_inps) <- flatKernel nest |
| 896 |
let ispace = base_ispace ++ zip slice_gtids slice_dims |
| 897 |
|
| 898 |
((res_t, res), kstms) <- runBuilder $ do |
| 899 |
-- Compute indexes into full array. |
| 900 |
slice'' <- |
| 901 |
subExpSlice . sliceSlice (primExpSlice slice) $ |
| 902 |
primExpSlice $ |
| 903 |
Slice $ |
| 904 |
map (DimFix . Var) slice_gtids |
| 905 |
v' <- certifying cs $ letSubExp "v" $ BasicOp $ Index arr slice'' |
| 906 |
v_t <- subExpType v' |
| 907 |
pure (v_t, Returns ResultMaySimplify mempty v') |
| 908 |
|
| 909 |
mk_lvl <- mkSegLevel |
| 910 |
(k, prestms) <- |
| 911 |
mapKernel mk_lvl ispace kernel_inps [res_t] $ |
| 912 |
KernelBody () kstms [res] |
| 913 |
|
| 914 |
traverse renameStm <=< runBuilder_ $ do |
| 915 |
addStms prestms |
| 916 |
|
| 917 |
let pat = Pat $ patElems $ loopNestingPat $ fst nest |
| 918 |
|
| 919 |
letBind pat $ Op $ segOp k |
| 920 |
|
| 921 |
segmentedHistKernel :: |
| 922 |
(MonadFreshNames m, LocalScope rep m, DistRep rep) => |
| 923 |
KernelNest -> |
| 924 |
[Int] -> |
| 925 |
Certs -> |
| 926 |
SubExp -> |
| 927 |
[SOACS.HistOp SOACS] -> |
| 928 |
Lambda rep -> |
| 929 |
[VName] -> |
| 930 |
DistNestT rep m (Stms rep) |
| 931 |
segmentedHistKernel nest perm cs hist_w ops lam arrs = do |
| 932 |
-- We replicate some of the checking done by 'isSegmentedOp', but |
| 933 |
-- things are different because a Hist is not a reduction or |
| 934 |
-- scan. |
| 935 |
(ispace, inputs) <- flatKernel nest |
| 936 |
let orig_pat = |
| 937 |
Pat . rearrangeShape perm $ |
| 938 |
patElems $ |
| 939 |
loopNestingPat $ |
| 940 |
fst nest |
| 941 |
|
| 942 |
-- The input/output arrays _must_ correspond to some kernel input, |
| 943 |
-- or else the original nested Hist would have been ill-typed. |
| 944 |
-- Find them. |
| 945 |
ops' <- forM ops $ \(SOACS.HistOp num_bins rf dests nes op) -> |
| 946 |
SOACS.HistOp num_bins rf |
| 947 |
<$> mapM (fmap kernelInputArray . findInput inputs) dests |
| 948 |
<*> pure nes |
| 949 |
<*> pure op |
| 950 |
|
| 951 |
mk_lvl <- asks distSegLevel |
| 952 |
onLambda <- asks distOnSOACSLambda |
| 953 |
let onLambda' = fmap fst . runBuilder . onLambda |
| 954 |
liftInner $ |
| 955 |
runBuilderT'_ $ do |
| 956 |
-- It is important not to launch unnecessarily many threads for |
| 957 |
-- histograms, because it may mean we unnecessarily need to reduce |
| 958 |
-- subhistograms as well. |
| 959 |
lvl <- mk_lvl (hist_w : map snd ispace) "seghist" $ NoRecommendation SegNoVirt |
| 960 |
addStms |
| 961 |
=<< histKernel onLambda' lvl orig_pat ispace inputs cs hist_w ops' lam arrs |
| 962 |
where |
| 963 |
findInput kernel_inps a = |
| 964 |
maybe bad pure $ find ((== a) . kernelInputName) kernel_inps |
| 965 |
bad = error "Ill-typed nested Hist encountered." |
| 966 |
|
| 967 |
histKernel :: |
| 968 |
(MonadBuilder m, DistRep (Rep m)) => |
| 969 |
(Lambda SOACS -> m (Lambda (Rep m))) -> |
| 970 |
SegOpLevel (Rep m) -> |
| 971 |
Pat Type -> |
| 972 |
[(VName, SubExp)] -> |
| 973 |
[KernelInput] -> |
| 974 |
Certs -> |
| 975 |
SubExp -> |
| 976 |
[SOACS.HistOp SOACS] -> |
| 977 |
Lambda (Rep m) -> |
| 978 |
[VName] -> |
| 979 |
m (Stms (Rep m)) |
| 980 |
histKernel onLambda lvl orig_pat ispace inputs cs hist_w ops lam arrs = runBuilderT'_ $ do |
| 981 |
ops' <- forM ops $ \(SOACS.HistOp dest_shape rf dests nes op) -> do |
| 982 |
(op', nes', shape) <- determineReduceOp op nes |
| 983 |
op'' <- lift $ onLambda op' |
| 984 |
pure $ HistOp dest_shape rf dests nes' shape op'' |
| 985 |
|
| 986 |
let isDest = flip elem $ concatMap histDest ops' |
| 987 |
inputs' = filter (not . isDest . kernelInputArray) inputs |
| 988 |
|
| 989 |
certifying cs $ |
| 990 |
addStms |
| 991 |
=<< traverse renameStm |
| 992 |
=<< segHist lvl orig_pat hist_w ispace inputs' ops' lam arrs |
| 993 |
|
| 994 |
determineReduceOp :: |
| 995 |
(MonadBuilder m) => |
| 996 |
Lambda SOACS -> |
| 997 |
[SubExp] -> |
| 998 |
m (Lambda SOACS, [SubExp], Shape) |
| 999 |
determineReduceOp lam nes = |
| 1000 |
-- FIXME? We are assuming that the accumulator is a replicate, and |
| 1001 |
-- we fish out its value in a gross way. |
| 1002 |
case mapM subExpVar nes of |
| 1003 |
Just ne_vs' -> do |
| 1004 |
let (shape, lam') = isVectorMap lam |
| 1005 |
nes' <- forM ne_vs' $ \ne_v -> do |
| 1006 |
ne_v_t <- lookupType ne_v |
| 1007 |
letSubExp "hist_ne" $ |
| 1008 |
BasicOp $ |
| 1009 |
Index ne_v $ |
| 1010 |
fullSlice ne_v_t $ |
| 1011 |
replicate (shapeRank shape) $ |
| 1012 |
DimFix $ |
| 1013 |
intConst Int64 0 |
| 1014 |
pure (lam', nes', shape) |
| 1015 |
Nothing -> |
| 1016 |
pure (lam, nes, mempty) |
| 1017 |
|
| 1018 |
isVectorMap :: Lambda SOACS -> (Shape, Lambda SOACS) |
| 1019 |
isVectorMap lam |
| 1020 |
| [Let (Pat pes) _ (Op (Screma w arrs form))] <- |
| 1021 |
stmsToList $ bodyStms $ lambdaBody lam, |
| 1022 |
map resSubExp (bodyResult (lambdaBody lam)) == map (Var . patElemName) pes, |
| 1023 |
Just map_lam <- isMapSOAC form, |
| 1024 |
arrs == map paramName (lambdaParams lam) = |
| 1025 |
let (shape, lam') = isVectorMap map_lam |
| 1026 |
in (Shape [w] <> shape, lam') |
| 1027 |
| otherwise = (mempty, lam) |
| 1028 |
|
| 1029 |
segmentedScanomapKernel :: |
| 1030 |
(MonadFreshNames m, LocalScope rep m, DistRep rep) => |
| 1031 |
KernelNest -> |
| 1032 |
[Int] -> |
| 1033 |
Certs -> |
| 1034 |
SubExp -> |
| 1035 |
Lambda SOACS -> |
| 1036 |
Lambda rep -> |
| 1037 |
[SubExp] -> |
| 1038 |
[VName] -> |
| 1039 |
DistNestT rep m (Maybe (Stms rep)) |
| 1040 |
segmentedScanomapKernel nest perm cs segment_size lam map_lam nes arrs = do |
| 1041 |
mk_lvl <- asks distSegLevel |
| 1042 |
onLambda <- asks distOnSOACSLambda |
| 1043 |
let onLambda' = fmap fst . runBuilder . onLambda |
| 1044 |
isSegmentedOp nest perm (freeIn lam) (freeIn map_lam) nes [] $ |
| 1045 |
\pat ispace inps nes' _ -> do |
| 1046 |
(lam', nes'', shape) <- determineReduceOp lam nes' |
| 1047 |
lam'' <- onLambda' lam' |
| 1048 |
let scan_op = SegBinOp Noncommutative lam'' nes'' shape |
| 1049 |
lvl <- mk_lvl (segment_size : map snd ispace) "segscan" $ NoRecommendation SegNoVirt |
| 1050 |
addStms |
| 1051 |
=<< traverse renameStm |
| 1052 |
=<< segScan lvl pat cs segment_size [scan_op] map_lam arrs ispace inps |
| 1053 |
|
| 1054 |
regularSegmentedRedomapKernel :: |
| 1055 |
(MonadFreshNames m, LocalScope rep m, DistRep rep) => |
| 1056 |
KernelNest -> |
| 1057 |
[Int] -> |
| 1058 |
Certs -> |
| 1059 |
SubExp -> |
| 1060 |
Commutativity -> |
| 1061 |
Lambda rep -> |
| 1062 |
Lambda rep -> |
| 1063 |
[SubExp] -> |
| 1064 |
[VName] -> |
| 1065 |
DistNestT rep m (Maybe (Stms rep)) |
| 1066 |
regularSegmentedRedomapKernel nest perm cs segment_size comm lam map_lam nes arrs = do |
| 1067 |
mk_lvl <- asks distSegLevel |
| 1068 |
isSegmentedOp nest perm (freeIn lam) (freeIn map_lam) nes [] $ |
| 1069 |
\pat ispace inps nes' _ -> do |
| 1070 |
let red_op = SegBinOp comm lam nes' mempty |
| 1071 |
lvl <- mk_lvl (segment_size : map snd ispace) "segred" $ NoRecommendation SegNoVirt |
| 1072 |
addStms |
| 1073 |
=<< traverse renameStm |
| 1074 |
=<< segRed lvl pat cs segment_size [red_op] map_lam arrs ispace inps |
| 1075 |
|
| 1076 |
isSegmentedOp :: |
| 1077 |
(MonadFreshNames m, LocalScope rep m, DistRep rep) => |
| 1078 |
KernelNest -> |
| 1079 |
[Int] -> |
| 1080 |
Names -> |
| 1081 |
Names -> |
| 1082 |
[SubExp] -> |
| 1083 |
[VName] -> |
| 1084 |
( Pat Type -> |
| 1085 |
[(VName, SubExp)] -> |
| 1086 |
[KernelInput] -> |
| 1087 |
[SubExp] -> |
| 1088 |
[VName] -> |
| 1089 |
BuilderT rep m () |
| 1090 |
) -> |
| 1091 |
DistNestT rep m (Maybe (Stms rep)) |
| 1092 |
isSegmentedOp nest perm free_in_op _free_in_fold_op nes arrs m = runMaybeT $ do |
| 1093 |
-- We must verify that array inputs to the operation are inputs to |
| 1094 |
-- the outermost loop nesting or free in the loop nest. Nothing |
| 1095 |
-- free in the op may be bound by the nest. Furthermore, the |
| 1096 |
-- neutral elements must be free in the loop nest. |
| 1097 |
-- |
| 1098 |
-- We must summarise any names from free_in_op that are bound in the |
| 1099 |
-- nest, and describe how to obtain them given segment indices. |
| 1100 |
|
| 1101 |
let bound_by_nest = boundInKernelNest nest |
| 1102 |
|
| 1103 |
(ispace, kernel_inps) <- flatKernel nest |
| 1104 |
|
| 1105 |
when (free_in_op `namesIntersect` bound_by_nest) $ |
| 1106 |
fail "Non-fold lambda uses nest-bound parameters." |
| 1107 |
|
| 1108 |
let indices = map fst ispace |
| 1109 |
|
| 1110 |
prepareNe (Var v) |
| 1111 |
| v `nameIn` bound_by_nest = |
| 1112 |
fail "Neutral element bound in nest" |
| 1113 |
prepareNe ne = pure ne |
| 1114 |
|
| 1115 |
prepareArr arr = |
| 1116 |
case find ((== arr) . kernelInputName) kernel_inps of |
| 1117 |
Just inp |
| 1118 |
| kernelInputIndices inp == map Var indices -> |
| 1119 |
pure $ pure $ kernelInputArray inp |
| 1120 |
Nothing |
| 1121 |
| arr `notNameIn` bound_by_nest -> |
| 1122 |
-- This input is something that is free inside |
| 1123 |
-- the loop nesting. We will have to replicate |
| 1124 |
-- it. |
| 1125 |
pure $ |
| 1126 |
letExp |
| 1127 |
(baseString arr ++ "_repd") |
| 1128 |
(BasicOp $ Replicate (Shape $ map snd ispace) $ Var arr) |
| 1129 |
_ -> |
| 1130 |
fail "Input not free, perfectly mapped, or outermost." |
| 1131 |
|
| 1132 |
nes' <- mapM prepareNe nes |
| 1133 |
|
| 1134 |
mk_arrs <- mapM prepareArr arrs |
| 1135 |
|
| 1136 |
lift $ |
| 1137 |
liftInner $ |
| 1138 |
runBuilderT'_ $ do |
| 1139 |
nested_arrs <- sequence mk_arrs |
| 1140 |
|
| 1141 |
let pat = |
| 1142 |
Pat . rearrangeShape perm $ |
| 1143 |
patElems $ |
| 1144 |
loopNestingPat $ |
| 1145 |
fst nest |
| 1146 |
|
| 1147 |
m pat ispace kernel_inps nes' nested_arrs |
| 1148 |
|
| 1149 |
permutationAndMissing :: Pat Type -> Result -> Maybe ([Int], [PatElem Type]) |
| 1150 |
permutationAndMissing (Pat pes) res = do |
| 1151 |
let (_used, unused) = |
| 1152 |
partition ((`nameIn` freeIn res) . patElemName) pes |
| 1153 |
res' = map resSubExp res |
| 1154 |
res_expanded = res' ++ map (Var . patElemName) unused |
| 1155 |
perm <- map (Var . patElemName) pes `isPermutationOf` res_expanded |
| 1156 |
pure (perm, unused) |
| 1157 |
|
| 1158 |
-- Add extra pattern elements to every kernel nesting level. |
| 1159 |
expandKernelNest :: |
| 1160 |
(MonadFreshNames m) => [PatElem Type] -> KernelNest -> m KernelNest |
| 1161 |
expandKernelNest pes (outer_nest, inner_nests) = do |
| 1162 |
let outer_size = |
| 1163 |
loopNestingWidth outer_nest |
| 1164 |
: map loopNestingWidth inner_nests |
| 1165 |
inner_sizes = tails $ map loopNestingWidth inner_nests |
| 1166 |
outer_nest' <- expandWith outer_nest outer_size |
| 1167 |
inner_nests' <- zipWithM expandWith inner_nests inner_sizes |
| 1168 |
pure (outer_nest', inner_nests') |
| 1169 |
where |
| 1170 |
expandWith nest dims = do |
| 1171 |
pes' <- mapM (expandPatElemWith dims) pes |
| 1172 |
pure |
| 1173 |
nest |
| 1174 |
{ loopNestingPat = |
| 1175 |
Pat $ patElems (loopNestingPat nest) <> pes' |
| 1176 |
} |
| 1177 |
|
| 1178 |
expandPatElemWith dims pe = do |
| 1179 |
name <- newVName $ baseString $ patElemName pe |
| 1180 |
pure |
| 1181 |
pe |
| 1182 |
{ patElemName = name, |
| 1183 |
patElemDec = patElemType pe `arrayOfShape` Shape dims |
| 1184 |
} |
| 1185 |
|
| 1186 |
kernelOrNot :: |
| 1187 |
(MonadFreshNames m, DistRep rep) => |
| 1188 |
Certs -> |
| 1189 |
Stm SOACS -> |
| 1190 |
DistAcc rep -> |
| 1191 |
PostStms rep -> |
| 1192 |
DistAcc rep -> |
| 1193 |
Maybe (Stms rep) -> |
| 1194 |
DistNestT rep m (DistAcc rep) |
| 1195 |
kernelOrNot cs stm acc _ _ Nothing = |
| 1196 |
addStmToAcc (certify cs stm) acc |
| 1197 |
kernelOrNot cs _ _ kernels acc' (Just stms) = do |
| 1198 |
addPostStms kernels |
| 1199 |
postStm $ fmap (certify cs) stms |
| 1200 |
pure acc' |
| 1201 |
|
| 1202 |
distributeMap :: |
| 1203 |
(MonadFreshNames m, LocalScope rep m, DistRep rep) => |
| 1204 |
MapLoop -> |
| 1205 |
DistAcc rep -> |
| 1206 |
DistNestT rep m (DistAcc rep) |
| 1207 |
distributeMap (MapLoop pat aux w lam arrs) acc = |
| 1208 |
distribute |
| 1209 |
=<< mapNesting |
| 1210 |
pat |
| 1211 |
aux |
| 1212 |
w |
| 1213 |
lam |
| 1214 |
arrs |
| 1215 |
(distribute =<< distributeMapBodyStms acc' lam_stms) |
| 1216 |
where |
| 1217 |
acc' = |
| 1218 |
DistAcc |
| 1219 |
{ distTargets = |
| 1220 |
pushInnerTarget |
| 1221 |
(pat, bodyResult $ lambdaBody lam) |
| 1222 |
$ distTargets acc, |
| 1223 |
distStms = mempty |
| 1224 |
} |
| 1225 |
|
| 1226 |
lam_stms = bodyStms $ lambdaBody lam |