Debian Codegraph @

src/Futhark/Pass/ExtractKernels/BlockedKernel.hs

raw
1 {-# LANGUAGE TypeFamilies #-}
2
3 module Futhark.Pass.ExtractKernels.BlockedKernel
4 ( DistRep,
5 MkSegLevel,
6 ThreadRecommendation (..),
7 segRed,
8 nonSegRed,
9 segScan,
10 segHist,
11 segMap,
12 mapKernel,
13 KernelInput (..),
14 readKernelInput,
15 mkSegSpace,
16 dummyDim,
17 )
18 where
19
20 import Control.Monad
21 import Futhark.Analysis.PrimExp
22 import Futhark.IR
23 import Futhark.IR.Aliases (AliasableRep)
24 import Futhark.IR.GPU.Op (SegVirt (..))
25 import Futhark.IR.SegOp
26 import Futhark.MonadFreshNames
27 import Futhark.Tools
28 import Futhark.Transform.Rename
29 import Prelude hiding (quot)
30
31 -- | Constraints pertinent to performing distribution/flattening.
32 type DistRep rep =
33 ( Buildable rep,
34 HasSegOp rep,
35 BuilderOps rep,
36 LetDec rep ~ Type,
37 ExpDec rep ~ (),
38 BodyDec rep ~ (),
39 AliasableRep rep
40 )
41
42 data ThreadRecommendation = ManyThreads | NoRecommendation SegVirt
43
44 type MkSegLevel rep m =
45 [SubExp] -> String -> ThreadRecommendation -> BuilderT rep m (SegOpLevel rep)
46
47 mkSegSpace :: (MonadFreshNames m) => [(VName, SubExp)] -> m SegSpace
48 mkSegSpace dims = SegSpace <$> newVName "phys_tid" <*> pure dims
49
50 prepareRedOrScan ::
51 (MonadBuilder m, DistRep (Rep m)) =>
52 Certs ->
53 SubExp ->
54 Lambda (Rep m) ->
55 [VName] ->
56 [(VName, SubExp)] ->
57 [KernelInput] ->
58 m (SegSpace, KernelBody (Rep m))
59 prepareRedOrScan cs w map_lam arrs ispace inps = do
60 gtid <- newVName "gtid"
61 space <- mkSegSpace $ ispace ++ [(gtid, w)]
62 kbody <- fmap (uncurry (flip (KernelBody ()))) $
63 runBuilder $
64 localScope (scopeOfSegSpace space) $ do
65 mapM_ readKernelInput inps
66 certifying cs . mapM_ readKernelInput $ do
67 (p, arr) <- zip (lambdaParams map_lam) arrs
68 pure $ KernelInput (paramName p) (paramType p) arr [Var gtid]
69 res <- bodyBind (lambdaBody map_lam)
70 forM res $ \(SubExpRes res_cs se) -> pure $ Returns ResultMaySimplify res_cs se
71
72 pure (space, kbody)
73
74 segRed ::
75 (MonadFreshNames m, DistRep rep, HasScope rep m) =>
76 SegOpLevel rep ->
77 Pat (LetDec rep) ->
78 Certs ->
79 SubExp -> -- segment size
80 [SegBinOp rep] ->
81 Lambda rep ->
82 [VName] ->
83 [(VName, SubExp)] -> -- ispace = pair of (gtid, size) for the maps on "top" of this reduction
84 [KernelInput] -> -- inps = inputs that can be looked up by using the gtids from ispace
85 m (Stms rep)
86 segRed lvl pat cs w ops map_lam arrs ispace inps = runBuilder_ $ do
87 (kspace, kbody) <- prepareRedOrScan cs w map_lam arrs ispace inps
88 letBind pat $
89 Op $
90 segOp $
91 SegRed lvl kspace (lambdaReturnType map_lam) kbody ops
92
93 segScan ::
94 (MonadFreshNames m, DistRep rep, HasScope rep m) =>
95 SegOpLevel rep ->
96 Pat (LetDec rep) ->
97 Certs ->
98 SubExp -> -- segment size
99 [SegBinOp rep] ->
100 Lambda rep ->
101 [VName] ->
102 [(VName, SubExp)] -> -- ispace = pair of (gtid, size) for the maps on "top" of this scan
103 [KernelInput] -> -- inps = inputs that can be looked up by using the gtids from ispace
104 m (Stms rep)
105 segScan lvl pat cs w ops map_lam arrs ispace inps = runBuilder_ $ do
106 (kspace, kbody) <- prepareRedOrScan cs w map_lam arrs ispace inps
107 letBind pat $
108 Op $
109 segOp $
110 SegScan lvl kspace (lambdaReturnType map_lam) kbody ops
111
112 segMap ::
113 (MonadFreshNames m, DistRep rep, HasScope rep m) =>
114 SegOpLevel rep ->
115 Pat (LetDec rep) ->
116 SubExp -> -- segment size
117 Lambda rep ->
118 [VName] ->
119 [(VName, SubExp)] -> -- ispace = pair of (gtid, size) for the maps on "top" of this map
120 [KernelInput] -> -- inps = inputs that can be looked up by using the gtids from ispace
121 m (Stms rep)
122 segMap lvl pat w map_lam arrs ispace inps = runBuilder_ $ do
123 (kspace, kbody) <- prepareRedOrScan mempty w map_lam arrs ispace inps
124 letBind pat $
125 Op $
126 segOp $
127 SegMap lvl kspace (lambdaReturnType map_lam) kbody
128
129 dummyDim ::
130 (MonadBuilder m) =>
131 Pat Type ->
132 m (Pat Type, [(VName, SubExp)], m ())
133 dummyDim pat = do
134 -- We add a unit-size segment on top to ensure that the result
135 -- of the SegRed is an array, which we then immediately index.
136 -- This is useful in the case that the value is used on the
137 -- device afterwards, as this may save an expensive
138 -- host-device copy (scalars are kept on the host, but arrays
139 -- may be on the device).
140 let addDummyDim t = t `arrayOfRow` intConst Int64 1
141 pat' <- fmap addDummyDim <$> renamePat pat
142 dummy <- newVName "dummy"
143 let ispace = [(dummy, intConst Int64 1)]
144
145 pure
146 ( pat',
147 ispace,
148 forM_ (zip (patNames pat') (patNames pat)) $ \(from, to) -> do
149 from_t <- lookupType from
150 letBindNames [to] . BasicOp $
151 case from_t of
152 Acc {} -> SubExp $ Var from
153 _ -> Index from $ fullSlice from_t [DimFix $ intConst Int64 0]
154 )
155
156 nonSegRed ::
157 (MonadFreshNames m, DistRep rep, HasScope rep m) =>
158 SegOpLevel rep ->
159 Pat Type ->
160 SubExp ->
161 [SegBinOp rep] ->
162 Lambda rep ->
163 [VName] ->
164 m (Stms rep)
165 nonSegRed lvl pat w ops map_lam arrs = runBuilder_ $ do
166 (pat', ispace, read_dummy) <- dummyDim pat
167 addStms =<< segRed lvl pat' mempty w ops map_lam arrs ispace []
168 read_dummy
169
170 segHist ::
171 (DistRep rep, MonadFreshNames m, HasScope rep m) =>
172 SegOpLevel rep ->
173 Pat Type ->
174 SubExp ->
175 -- | Segment indexes and sizes.
176 [(VName, SubExp)] ->
177 [KernelInput] ->
178 [HistOp rep] ->
179 Lambda rep ->
180 [VName] ->
181 m (Stms rep)
182 segHist lvl pat arr_w ispace inps ops lam arrs = runBuilder_ $ do
183 gtid <- newVName "gtid"
184 space <- mkSegSpace $ ispace ++ [(gtid, arr_w)]
185
186 kbody <- fmap (uncurry (flip $ KernelBody ())) $
187 runBuilder $
188 localScope (scopeOfSegSpace space) $ do
189 mapM_ readKernelInput inps
190 forM_ (zip (lambdaParams lam) arrs) $ \(p, arr) -> do
191 arr_t <- lookupType arr
192 letBindNames [paramName p] $
193 BasicOp $
194 Index arr $
195 fullSlice arr_t [DimFix $ Var gtid]
196 res <- bodyBind (lambdaBody lam)
197 forM res $ \(SubExpRes cs se) ->
198 pure $ Returns ResultMaySimplify cs se
199
200 letBind pat $ Op $ segOp $ SegHist lvl space (lambdaReturnType lam) kbody ops
201
202 mapKernelSkeleton ::
203 (DistRep rep, HasScope rep m, MonadFreshNames m) =>
204 [(VName, SubExp)] ->
205 [KernelInput] ->
206 m (SegSpace, Stms rep)
207 mapKernelSkeleton ispace inputs = do
208 read_input_stms <- runBuilder_ $ mapM readKernelInput inputs
209
210 space <- mkSegSpace ispace
211 pure (space, read_input_stms)
212
213 mapKernel ::
214 (DistRep rep, HasScope rep m, MonadFreshNames m) =>
215 MkSegLevel rep m ->
216 [(VName, SubExp)] ->
217 [KernelInput] ->
218 [Type] ->
219 KernelBody rep ->
220 m (SegOp (SegOpLevel rep) rep, Stms rep)
221 mapKernel mk_lvl ispace inputs rts (KernelBody () kstms krets) = runBuilderT' $ do
222 (space, read_input_stms) <- mapKernelSkeleton ispace inputs
223
224 let kbody' = KernelBody () (read_input_stms <> kstms) krets
225
226 -- If the kernel creates arrays (meaning it will require memory
227 -- expansion), we want to truncate the amount of threads.
228 -- Otherwise, have at it! This is a bit of a hack - in principle,
229 -- we should make this decision later, when we have a clearer idea
230 -- of what is happening inside the kernel.
231 let r = if all primType rts then ManyThreads else NoRecommendation SegVirt
232
233 lvl <- mk_lvl (map snd ispace) "segmap" r
234
235 pure $ SegMap lvl space rts kbody'
236
237 data KernelInput = KernelInput
238 { kernelInputName :: VName,
239 kernelInputType :: Type,
240 kernelInputArray :: VName,
241 kernelInputIndices :: [SubExp]
242 }
243 deriving (Show)
244
245 readKernelInput ::
246 (DistRep (Rep m), MonadBuilder m) =>
247 KernelInput ->
248 m ()
249 readKernelInput inp = do
250 let pe = PatElem (kernelInputName inp) $ kernelInputType inp
251 letBind (Pat [pe]) . BasicOp $
252 case kernelInputType inp of
253 Acc {} ->
254 SubExp $ Var $ kernelInputArray inp
255 _ ->
256 Index (kernelInputArray inp) . Slice $
257 map DimFix (kernelInputIndices inp)
258 ++ map sliceDim (arrayDims (kernelInputType inp))