| 1 |
{-# LANGUAGE TypeFamilies #-} |
| 2 |
|
| 3 |
-- | Extract limited nested parallelism for execution inside |
| 4 |
-- individual kernel threadblocks. |
| 5 |
module Futhark.Pass.ExtractKernels.Intrablock (intrablockParallelise) where |
| 6 |
|
| 7 |
import Control.Monad |
| 8 |
import Control.Monad.RWS |
| 9 |
import Control.Monad.Trans.Maybe |
| 10 |
import Data.Map.Strict qualified as M |
| 11 |
import Data.Set qualified as S |
| 12 |
import Futhark.Analysis.PrimExp.Convert |
| 13 |
import Futhark.IR.GPU hiding (HistOp) |
| 14 |
import Futhark.IR.GPU.Op qualified as GPU |
| 15 |
import Futhark.IR.SOACS |
| 16 |
import Futhark.MonadFreshNames |
| 17 |
import Futhark.Pass.ExtractKernels.BlockedKernel |
| 18 |
import Futhark.Pass.ExtractKernels.DistributeNests |
| 19 |
import Futhark.Pass.ExtractKernels.Distribution |
| 20 |
import Futhark.Pass.ExtractKernels.ToGPU |
| 21 |
import Futhark.Tools |
| 22 |
import Futhark.Transform.FirstOrderTransform qualified as FOT |
| 23 |
import Futhark.Util.Log |
| 24 |
import Prelude hiding (log) |
| 25 |
|
| 26 |
-- | Convert the statements inside a map nest to kernel statements, |
| 27 |
-- attempting to parallelise any remaining (top-level) parallel |
| 28 |
-- statements. Anything that is not a map, scan or reduction will |
| 29 |
-- simply be sequentialised. This includes sequential loops that |
| 30 |
-- contain maps, scans or reduction. In the future, we could probably |
| 31 |
-- do something more clever. Make sure that the amount of parallelism |
| 32 |
-- to be exploited does not exceed the group size. Further, as a hack |
| 33 |
-- we also consider the size of all intermediate arrays as |
| 34 |
-- "parallelism to be exploited" to avoid exploding shared memory. |
| 35 |
-- |
| 36 |
-- We distinguish between "minimum group size" and "maximum |
| 37 |
-- exploitable parallelism". |
| 38 |
intrablockParallelise :: |
| 39 |
(MonadFreshNames m, LocalScope GPU m) => |
| 40 |
KernelNest -> |
| 41 |
Lambda SOACS -> |
| 42 |
m |
| 43 |
( Maybe |
| 44 |
( (SubExp, SubExp), |
| 45 |
SubExp, |
| 46 |
Log, |
| 47 |
Stms GPU, |
| 48 |
Stms GPU |
| 49 |
) |
| 50 |
) |
| 51 |
intrablockParallelise knest lam = runMaybeT $ do |
| 52 |
(ispace, inps) <- lift $ flatKernel knest |
| 53 |
|
| 54 |
(num_tblocks, w_stms) <- |
| 55 |
lift $ |
| 56 |
runBuilder $ |
| 57 |
letSubExp "intra_num_tblocks" |
| 58 |
=<< foldBinOp (Mul Int64 OverflowUndef) (intConst Int64 1) (map snd ispace) |
| 59 |
|
| 60 |
let body = lambdaBody lam |
| 61 |
|
| 62 |
tblock_size <- newVName "computed_tblock_size" |
| 63 |
(wss_min, wss_avail, log, kbody) <- |
| 64 |
lift . localScope (scopeOfLParams $ lambdaParams lam) $ |
| 65 |
intrablockParalleliseBody body |
| 66 |
|
| 67 |
outside_scope <- lift askScope |
| 68 |
-- outside_scope may also contain the inputs, even though those are |
| 69 |
-- not actually available outside the kernel. |
| 70 |
let available v = |
| 71 |
v `M.member` outside_scope |
| 72 |
&& v `notElem` map kernelInputName inps |
| 73 |
unless (all available $ namesToList $ freeIn (wss_min ++ wss_avail)) $ |
| 74 |
fail "Irregular parallelism" |
| 75 |
|
| 76 |
((intra_avail_par, kspace, read_input_stms), prelude_stms) <- lift $ |
| 77 |
runBuilder $ do |
| 78 |
let foldBinOp' _ [] = eSubExp $ intConst Int64 1 |
| 79 |
foldBinOp' bop (x : xs) = foldBinOp bop x xs |
| 80 |
ws_min <- |
| 81 |
mapM (letSubExp "one_intra_par_min" <=< foldBinOp' (Mul Int64 OverflowUndef)) $ |
| 82 |
filter (not . null) wss_min |
| 83 |
ws_avail <- |
| 84 |
mapM (letSubExp "one_intra_par_avail" <=< foldBinOp' (Mul Int64 OverflowUndef)) $ |
| 85 |
filter (not . null) wss_avail |
| 86 |
|
| 87 |
-- The amount of parallelism available *in the worst case* is |
| 88 |
-- equal to the smallest parallel loop, or *at least* 1. |
| 89 |
intra_avail_par <- |
| 90 |
letSubExp "intra_avail_par" =<< foldBinOp' (SMin Int64) ws_avail |
| 91 |
|
| 92 |
-- The group size is either the maximum of the minimum parallelism |
| 93 |
-- exploited, or the desired parallelism (bounded by the max group |
| 94 |
-- size) in case there is no minimum. |
| 95 |
letBindNames [tblock_size] |
| 96 |
=<< if null ws_min |
| 97 |
then |
| 98 |
eBinOp |
| 99 |
(SMin Int64) |
| 100 |
(eSubExp =<< letSubExp "max_tblock_size" (Op $ SizeOp $ GetSizeMax SizeThreadBlock)) |
| 101 |
(eSubExp intra_avail_par) |
| 102 |
else foldBinOp' (SMax Int64) ws_min |
| 103 |
|
| 104 |
let inputIsUsed input = kernelInputName input `nameIn` freeIn body |
| 105 |
used_inps = filter inputIsUsed inps |
| 106 |
|
| 107 |
addStms w_stms |
| 108 |
read_input_stms <- runBuilder_ $ mapM readGroupKernelInput used_inps |
| 109 |
space <- SegSpace <$> newVName "phys_tblock_id" <*> pure ispace |
| 110 |
pure (intra_avail_par, space, read_input_stms) |
| 111 |
|
| 112 |
let kbody' = kbody {kernelBodyStms = read_input_stms <> kernelBodyStms kbody} |
| 113 |
|
| 114 |
let nested_pat = loopNestingPat first_nest |
| 115 |
rts = map (length ispace `stripArray`) $ patTypes nested_pat |
| 116 |
grid = KernelGrid (Count num_tblocks) (Count $ Var tblock_size) |
| 117 |
lvl = SegBlock SegNoVirt (Just grid) |
| 118 |
kstm = |
| 119 |
Let nested_pat aux $ Op $ SegOp $ SegMap lvl kspace rts kbody' |
| 120 |
|
| 121 |
let intra_min_par = intra_avail_par |
| 122 |
pure |
| 123 |
( (intra_min_par, intra_avail_par), |
| 124 |
Var tblock_size, |
| 125 |
log, |
| 126 |
prelude_stms, |
| 127 |
oneStm kstm |
| 128 |
) |
| 129 |
where |
| 130 |
first_nest = fst knest |
| 131 |
aux = loopNestingAux first_nest |
| 132 |
|
| 133 |
readGroupKernelInput :: |
| 134 |
(DistRep (Rep m), MonadBuilder m) => |
| 135 |
KernelInput -> |
| 136 |
m () |
| 137 |
readGroupKernelInput inp |
| 138 |
| Array {} <- kernelInputType inp = do |
| 139 |
v <- newVName $ baseString $ kernelInputName inp |
| 140 |
readKernelInput inp {kernelInputName = v} |
| 141 |
letBindNames [kernelInputName inp] $ BasicOp $ Replicate mempty $ Var v |
| 142 |
| otherwise = |
| 143 |
readKernelInput inp |
| 144 |
|
| 145 |
data IntraAcc = IntraAcc |
| 146 |
{ accMinPar :: S.Set [SubExp], |
| 147 |
accAvailPar :: S.Set [SubExp], |
| 148 |
accLog :: Log |
| 149 |
} |
| 150 |
|
| 151 |
instance Semigroup IntraAcc where |
| 152 |
IntraAcc min_x avail_x log_x <> IntraAcc min_y avail_y log_y = |
| 153 |
IntraAcc (min_x <> min_y) (avail_x <> avail_y) (log_x <> log_y) |
| 154 |
|
| 155 |
instance Monoid IntraAcc where |
| 156 |
mempty = IntraAcc mempty mempty mempty |
| 157 |
|
| 158 |
type IntrablockM = |
| 159 |
BuilderT GPU (RWS () IntraAcc VNameSource) |
| 160 |
|
| 161 |
instance MonadLogger IntrablockM where |
| 162 |
addLog log = tell mempty {accLog = log} |
| 163 |
|
| 164 |
runIntrablockM :: |
| 165 |
(MonadFreshNames m, HasScope GPU m) => |
| 166 |
IntrablockM () -> |
| 167 |
m (IntraAcc, Stms GPU) |
| 168 |
runIntrablockM m = do |
| 169 |
scope <- castScope <$> askScope |
| 170 |
modifyNameSource $ \src -> |
| 171 |
let (((), kstms), src', acc) = runRWS (runBuilderT m scope) () src |
| 172 |
in ((acc, kstms), src') |
| 173 |
|
| 174 |
parallelMin :: [SubExp] -> IntrablockM () |
| 175 |
parallelMin ws = |
| 176 |
tell |
| 177 |
mempty |
| 178 |
{ accMinPar = S.singleton ws, |
| 179 |
accAvailPar = S.singleton ws |
| 180 |
} |
| 181 |
|
| 182 |
intrablockBody :: Body SOACS -> IntrablockM (Body GPU) |
| 183 |
intrablockBody body = do |
| 184 |
stms <- collectStms_ $ intrablockStms $ bodyStms body |
| 185 |
pure $ mkBody stms $ bodyResult body |
| 186 |
|
| 187 |
intrablockLambda :: Lambda SOACS -> IntrablockM (Lambda GPU) |
| 188 |
intrablockLambda lam = |
| 189 |
mkLambda (lambdaParams lam) $ |
| 190 |
bodyBind =<< intrablockBody (lambdaBody lam) |
| 191 |
|
| 192 |
intrablockWithAccInput :: WithAccInput SOACS -> IntrablockM (WithAccInput GPU) |
| 193 |
intrablockWithAccInput (shape, arrs, Nothing) = |
| 194 |
pure (shape, arrs, Nothing) |
| 195 |
intrablockWithAccInput (shape, arrs, Just (lam, nes)) = do |
| 196 |
lam' <- intrablockLambda lam |
| 197 |
pure (shape, arrs, Just (lam', nes)) |
| 198 |
|
| 199 |
intrablockStm :: Stm SOACS -> IntrablockM () |
| 200 |
intrablockStm stm@(Let pat aux e) = do |
| 201 |
scope <- askScope |
| 202 |
let lvl = SegThreadInBlock SegNoVirt |
| 203 |
|
| 204 |
case e of |
| 205 |
Loop merge form loopbody -> |
| 206 |
localScope (scopeOfLoopForm form <> scopeOfFParams (map fst merge)) $ do |
| 207 |
loopbody' <- intrablockBody loopbody |
| 208 |
certifying (stmAuxCerts aux) . letBind pat $ |
| 209 |
Loop merge form loopbody' |
| 210 |
Match cond cases defbody ifdec -> do |
| 211 |
cases' <- mapM (traverse intrablockBody) cases |
| 212 |
defbody' <- intrablockBody defbody |
| 213 |
certifying (stmAuxCerts aux) . letBind pat $ |
| 214 |
Match cond cases' defbody' ifdec |
| 215 |
WithAcc inputs lam -> do |
| 216 |
inputs' <- mapM intrablockWithAccInput inputs |
| 217 |
lam' <- intrablockLambda lam |
| 218 |
certifying (stmAuxCerts aux) . letBind pat $ WithAcc inputs' lam' |
| 219 |
Op soac |
| 220 |
| "sequential_outer" `inAttrs` stmAuxAttrs aux -> |
| 221 |
intrablockStms . fmap (certify (stmAuxCerts aux)) |
| 222 |
=<< runBuilder_ (FOT.transformSOAC pat soac) |
| 223 |
Op (Screma w arrs form) |
| 224 |
| Just lam <- isMapSOAC form -> do |
| 225 |
let loopnest = MapNesting pat aux w $ zip (lambdaParams lam) arrs |
| 226 |
env = |
| 227 |
DistEnv |
| 228 |
{ distNest = |
| 229 |
singleNesting $ Nesting mempty loopnest, |
| 230 |
distScope = |
| 231 |
scopeOfPat pat |
| 232 |
<> scopeForGPU (scopeOf lam) |
| 233 |
<> scope, |
| 234 |
distOnInnerMap = |
| 235 |
distributeMap, |
| 236 |
distOnTopLevelStms = |
| 237 |
liftInner . collectStms_ . intrablockStms, |
| 238 |
distSegLevel = \minw _ _ -> do |
| 239 |
lift $ parallelMin minw |
| 240 |
pure lvl, |
| 241 |
distOnSOACSStms = |
| 242 |
pure . oneStm . soacsStmToGPU, |
| 243 |
distOnSOACSLambda = |
| 244 |
pure . soacsLambdaToGPU |
| 245 |
} |
| 246 |
acc = |
| 247 |
DistAcc |
| 248 |
{ distTargets = singleTarget (pat, bodyResult $ lambdaBody lam), |
| 249 |
distStms = mempty |
| 250 |
} |
| 251 |
|
| 252 |
addStms |
| 253 |
=<< runDistNestT env (distributeMapBodyStms acc (bodyStms $ lambdaBody lam)) |
| 254 |
Op (Screma w arrs form) |
| 255 |
| Just (scans, mapfun) <- isScanomapSOAC form, |
| 256 |
-- FIXME: Futhark.CodeGen.ImpGen.GPU.Block.compileGroupOp |
| 257 |
-- cannot handle multiple scan operators yet. |
| 258 |
Scan scanfun nes <- singleScan scans -> do |
| 259 |
let scanfun' = soacsLambdaToGPU scanfun |
| 260 |
mapfun' = soacsLambdaToGPU mapfun |
| 261 |
certifying (stmAuxCerts aux) $ |
| 262 |
addStms =<< segScan lvl pat mempty w [SegBinOp Noncommutative scanfun' nes mempty] mapfun' arrs [] [] |
| 263 |
parallelMin [w] |
| 264 |
Op (Screma w arrs form) |
| 265 |
| Just (reds, map_lam) <- isRedomapSOAC form -> do |
| 266 |
let onReduce (Reduce comm red_lam nes) = |
| 267 |
SegBinOp comm (soacsLambdaToGPU red_lam) nes mempty |
| 268 |
reds' = map onReduce reds |
| 269 |
map_lam' = soacsLambdaToGPU map_lam |
| 270 |
certifying (stmAuxCerts aux) $ |
| 271 |
addStms =<< segRed lvl pat mempty w reds' map_lam' arrs [] [] |
| 272 |
parallelMin [w] |
| 273 |
Op (Screma w arrs form) -> |
| 274 |
-- This screma is too complicated for us to immediately do |
| 275 |
-- anything, so split it up and try again. |
| 276 |
mapM_ intrablockStm . fmap (certify (stmAuxCerts aux)) . snd |
| 277 |
=<< runBuilderT (dissectScrema pat w form arrs) (scopeForSOACs scope) |
| 278 |
Op (Hist w arrs ops bucket_fun) -> do |
| 279 |
ops' <- forM ops $ \(HistOp num_bins rf dests nes op) -> do |
| 280 |
(op', nes', shape) <- determineReduceOp op nes |
| 281 |
let op'' = soacsLambdaToGPU op' |
| 282 |
pure $ GPU.HistOp num_bins rf dests nes' shape op'' |
| 283 |
|
| 284 |
let bucket_fun' = soacsLambdaToGPU bucket_fun |
| 285 |
certifying (stmAuxCerts aux) $ |
| 286 |
addStms =<< segHist lvl pat w [] [] ops' bucket_fun' arrs |
| 287 |
parallelMin [w] |
| 288 |
Op (Stream w arrs accs lam) |
| 289 |
| chunk_size_param : _ <- lambdaParams lam -> do |
| 290 |
types <- asksScope castScope |
| 291 |
((), stream_stms) <- |
| 292 |
runBuilderT (sequentialStreamWholeArray pat w accs lam arrs) types |
| 293 |
let replace (Var v) | v == paramName chunk_size_param = w |
| 294 |
replace se = se |
| 295 |
replaceSets (IntraAcc x y log) = |
| 296 |
IntraAcc (S.map (map replace) x) (S.map (map replace) y) log |
| 297 |
censor replaceSets $ intrablockStms stream_stms |
| 298 |
Op (Scatter w ivs dests lam) -> do |
| 299 |
write_i <- newVName "write_i" |
| 300 |
space <- mkSegSpace [(write_i, w)] |
| 301 |
|
| 302 |
let lam' = soacsLambdaToGPU lam |
| 303 |
grouped = groupScatterResults dests $ bodyResult $ lambdaBody lam' |
| 304 |
(_, dest_arrs, _) = unzip3 grouped |
| 305 |
|
| 306 |
dest_ts <- mapM lookupType dest_arrs |
| 307 |
|
| 308 |
let krets = do |
| 309 |
(a_t, (_a_w, a, is_vs)) <- zip dest_ts grouped |
| 310 |
let cs = |
| 311 |
foldMap (foldMap resCerts . fst) is_vs |
| 312 |
<> foldMap (resCerts . snd) is_vs |
| 313 |
is_vs' = do |
| 314 |
(is, v) <- is_vs |
| 315 |
pure |
| 316 |
( fullSlice a_t $ map (DimFix . resSubExp) is, |
| 317 |
resSubExp v |
| 318 |
) |
| 319 |
pure $ WriteReturns cs a is_vs' |
| 320 |
inputs = do |
| 321 |
(p, p_a) <- zip (lambdaParams lam') ivs |
| 322 |
pure $ KernelInput (paramName p) (paramType p) p_a [Var write_i] |
| 323 |
|
| 324 |
kstms <- runBuilder_ $ |
| 325 |
localScope (scopeOfSegSpace space) $ do |
| 326 |
mapM_ readKernelInput inputs |
| 327 |
addStms $ bodyStms $ lambdaBody lam' |
| 328 |
|
| 329 |
certifying (stmAuxCerts aux) $ do |
| 330 |
let body = KernelBody () kstms krets |
| 331 |
letBind pat $ Op $ SegOp $ SegMap lvl space (patTypes pat) body |
| 332 |
|
| 333 |
parallelMin [w] |
| 334 |
_ -> |
| 335 |
addStm $ soacsStmToGPU stm |
| 336 |
|
| 337 |
intrablockStms :: Stms SOACS -> IntrablockM () |
| 338 |
intrablockStms = mapM_ intrablockStm |
| 339 |
|
| 340 |
intrablockParalleliseBody :: |
| 341 |
(MonadFreshNames m, HasScope GPU m) => |
| 342 |
Body SOACS -> |
| 343 |
m ([[SubExp]], [[SubExp]], Log, KernelBody GPU) |
| 344 |
intrablockParalleliseBody body = do |
| 345 |
(IntraAcc min_ws avail_ws log, kstms) <- |
| 346 |
runIntrablockM $ intrablockStms $ bodyStms body |
| 347 |
pure |
| 348 |
( S.toList min_ws, |
| 349 |
S.toList avail_ws, |
| 350 |
log, |
| 351 |
KernelBody () kstms $ map ret $ bodyResult body |
| 352 |
) |
| 353 |
where |
| 354 |
ret (SubExpRes cs se) = Returns ResultMaySimplify cs se |