Debian Codegraph @

src/Futhark/Pass/ExtractKernels/Intrablock.hs

raw
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