| 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)) |