| 1 | //===- ShardingInterfaceImpl.cpp - Linalg sharding models -----------------===// |
| 2 | // |
| 3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| 4 | // See https://llvm.org/LICENSE.txt for license information. |
| 5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| 6 | // |
| 7 | //===----------------------------------------------------------------------===// |
| 8 | |
| 9 | #include "mlir/Dialect/Linalg/Extensions/ShardingInterfaceImpl.h" |
| 10 | |
| 11 | #include "mlir/Analysis/SliceAnalysis.h" |
| 12 | #include "mlir/Dialect/Affine/IR/AffineDialect.h" |
| 13 | #include "mlir/Dialect/Arith/IR/Arith.h" |
| 14 | #include "mlir/Dialect/Linalg/IR/Linalg.h" |
| 15 | #include "mlir/Dialect/Linalg/IR/LinalgInterfaces.h" |
| 16 | #include "mlir/Dialect/SCF/IR/SCF.h" |
| 17 | #include "mlir/Dialect/Shard/IR/ShardOps.h" |
| 18 | #include "mlir/Dialect/Shard/Interfaces/ShardingInterface.h" |
| 19 | #include "mlir/Dialect/Shard/Interfaces/ShardingInterfaceImpl.h" |
| 20 | #include "mlir/Dialect/Shard/Transforms/Transforms.h" |
| 21 | #include "mlir/Dialect/Tensor/IR/Tensor.h" |
| 22 | #include "mlir/Dialect/Utils/StructuredOpsUtils.h" |
| 23 | #include "mlir/IR/AffineExpr.h" |
| 24 | #include "mlir/IR/DialectRegistry.h" |
| 25 | #include "mlir/IR/IRMapping.h" |
| 26 | #include "mlir/IR/MLIRContext.h" |
| 27 | #include "mlir/IR/OpDefinition.h" |
| 28 | #include "mlir/IR/Operation.h" |
| 29 | #include "mlir/IR/SymbolTable.h" |
| 30 | #include "mlir/IR/Value.h" |
| 31 | #include "llvm/ADT/STLExtras.h" |
| 32 | #include "llvm/ADT/SmallVector.h" |
| 33 | #include "llvm/ADT/TypeSwitch.h" |
| 34 | #include <numeric> |
| 35 | #include <optional> |
| 36 | |
| 37 | namespace mlir::linalg { |
| 38 | using GridAxis = shard::GridAxis; |
| 39 | using ReductionKind = shard::ReductionKind; |
| 40 | using Sharding = shard::Sharding; |
| 41 | using ShardingArray = shard::ShardingArray; |
| 42 | using GridOp = shard::GridOp; |
| 43 | |
| 44 | // Returns the corresponding grid reduction kind for the given arith op. |
| 45 | static ReductionKind getReductionKind(Operation *op) { |
| 46 | return llvm::TypeSwitch<Operation *, ReductionKind>(op) |
| 47 | // Floating-point operations. |
| 48 | .Case(caseFn: [](arith::AddFOp op) { return ReductionKind::Sum; }) |
| 49 | .Case(caseFn: [](arith::MulFOp op) { return ReductionKind::Product; }) |
| 50 | // TODO: handle maxnumf and minnumf. |
| 51 | .Case(caseFn: [](arith::MaximumFOp op) { return ReductionKind::Max; }) |
| 52 | .Case(caseFn: [](arith::MinimumFOp op) { return ReductionKind::Min; }) |
| 53 | // Integer operations. |
| 54 | .Case(caseFn: [](arith::AddIOp op) { return ReductionKind::Sum; }) |
| 55 | .Case(caseFn: [](arith::OrIOp op) { return ReductionKind::BitwiseOr; }) |
| 56 | .Case(caseFn: [](arith::XOrIOp op) { return ReductionKind::BitwiseXor; }) |
| 57 | .Case(caseFn: [](arith::AndIOp op) { return ReductionKind::BitwiseAnd; }) |
| 58 | // TODO: handle signless, signed and unsigned types properly. |
| 59 | // It is assumed that the element type of the collective operands and |
| 60 | // result drive the meaning of the reduction kind, whether it is signed |
| 61 | // or unsigned. |
| 62 | // The reduction op inside the linalg op may have different result type |
| 63 | // from the element type of the linalg op's result. |
| 64 | // Also signed and unsigned Arith dialect ops may accept signed, unsigned |
| 65 | // or signless operands. |
| 66 | // Maybe expand the reduction kinds. |
| 67 | .Case(caseFn: [](arith::MaxUIOp op) { return ReductionKind::Max; }) |
| 68 | .Case(caseFn: [](arith::MinUIOp op) { return ReductionKind::Min; }) |
| 69 | .Case(caseFn: [](arith::MaxSIOp op) { return ReductionKind::Max; }) |
| 70 | .Case(caseFn: [](arith::MinSIOp op) { return ReductionKind::Min; }) |
| 71 | .Case(caseFn: [](arith::MulIOp op) { return ReductionKind::Product; }) |
| 72 | .Default(defaultFn: [](Operation *op) { return ReductionKind::Generic; }); |
| 73 | } |
| 74 | |
| 75 | static std::optional<Operation *> getCombinerOp(LinalgOp op) { |
| 76 | SmallVector<Operation *> combinerOps; |
| 77 | Value reducedValue = matchReduction(iterCarriedArgs: op.getRegionOutputArgs(), redPos: 0, combinerOps); |
| 78 | if (!reducedValue || combinerOps.size() != 1) { |
| 79 | return std::nullopt; |
| 80 | } |
| 81 | |
| 82 | return combinerOps[0]; |
| 83 | } |
| 84 | |
| 85 | static ReductionKind getReductionKindOfLinalgOp(LinalgOp op) { |
| 86 | std::optional<Operation *> reductionOp = getCombinerOp(op); |
| 87 | if (!reductionOp) { |
| 88 | return ReductionKind::Generic; |
| 89 | } |
| 90 | [[maybe_unused]] Type resultElementType = |
| 91 | llvm::cast<RankedTensorType>(Val: op->getResult(idx: 0).getType()).getElementType(); |
| 92 | // TODO: handle case when result type of the reduction op does not match the |
| 93 | // element type of the result tensor. |
| 94 | // Would it makes sense at all? |
| 95 | assert(resultElementType == reductionOp.value()->getResult(0).getType()); |
| 96 | return getReductionKind(op: reductionOp.value()); |
| 97 | } |
| 98 | |
| 99 | static GridOp getGrid(Operation *op, ArrayRef<Sharding> operandShardings, |
| 100 | ArrayRef<Sharding> resultShardings, |
| 101 | SymbolTableCollection &symbolTable) { |
| 102 | for (const Sharding &sharding : operandShardings) { |
| 103 | if (sharding) { |
| 104 | return shard::getGrid(op, gridSymbol: sharding.getGridAttr(), symbolTableCollection&: symbolTable); |
| 105 | } |
| 106 | } |
| 107 | |
| 108 | for (const Sharding &sharding : resultShardings) { |
| 109 | if (sharding) { |
| 110 | return shard::getGrid(op, gridSymbol: sharding.getGridAttr(), symbolTableCollection&: symbolTable); |
| 111 | } |
| 112 | } |
| 113 | |
| 114 | assert(false); |
| 115 | return nullptr; |
| 116 | } |
| 117 | |
| 118 | // Choose the operand based on the current process index along the reduction |
| 119 | // grid axes. |
| 120 | // We need to use the initial value only once to avoid including it in the |
| 121 | // reduction multiple times. |
| 122 | // In each process group only the leading process with linear index 0 would use |
| 123 | // the original operand. |
| 124 | // The other processes would use the reduction operation neutral tensor. |
| 125 | static Value createDestinationPassingStyleInitOperand( |
| 126 | LinalgOp op, int operandNumber, Value partitionedOperand, |
| 127 | ArrayRef<GridAxis> reductionGridAxes, GridOp gridOp, |
| 128 | ImplicitLocOpBuilder &builder) { |
| 129 | Value processLinearIndexInReductionGroup = shard::createProcessLinearIndex( |
| 130 | builder, grid: gridOp.getSymName(), gridAxes: reductionGridAxes); |
| 131 | Value zero = arith::ConstantIndexOp::create(builder, value: 0); |
| 132 | Value isLeadProcess = arith::CmpIOp::create( |
| 133 | builder, result: builder.getI1Type(), predicate: arith::CmpIPredicate::eq, |
| 134 | lhs: processLinearIndexInReductionGroup, rhs: zero); |
| 135 | scf::IfOp ifOp = scf::IfOp::create(builder, resultTypes: partitionedOperand.getType(), |
| 136 | cond: isLeadProcess, addThenBlock: true, addElseBlock: true); |
| 137 | // Then block. |
| 138 | { |
| 139 | OpBuilder::InsertionGuard insertionGuard(builder); |
| 140 | builder.setInsertionPointToEnd(&ifOp.getThenRegion().front()); |
| 141 | scf::YieldOp::create(builder, results: partitionedOperand); |
| 142 | } |
| 143 | |
| 144 | // Else block. |
| 145 | { |
| 146 | OpBuilder::InsertionGuard insertionGuard(builder); |
| 147 | builder.setInsertionPointToEnd(&ifOp.getElseRegion().front()); |
| 148 | SmallVector<OpFoldResult> shape = |
| 149 | tensor::getMixedSizes(builder, loc: builder.getLoc(), value: partitionedOperand); |
| 150 | |
| 151 | SmallVector<Operation *> combinerOps; |
| 152 | matchReduction(iterCarriedArgs: op.getRegionOutputArgs(), redPos: operandNumber, combinerOps); |
| 153 | assert(combinerOps.size() == 1); |
| 154 | std::optional<TypedAttr> neutralEl = |
| 155 | arith::getNeutralElement(op: combinerOps[0]); |
| 156 | |
| 157 | Value init = tensor::EmptyOp::create(builder, location: op.getLoc(), sizes: shape, |
| 158 | elementType: neutralEl.value().getType()); |
| 159 | Value constant = |
| 160 | arith::ConstantOp::create(builder, location: op.getLoc(), value: neutralEl.value()); |
| 161 | Value fill = linalg::FillOp::create(builder, location: op.getLoc(), inputs: constant, outputs: init) |
| 162 | .getResult(i: 0); |
| 163 | |
| 164 | scf::YieldOp::create(builder, results: fill); |
| 165 | } |
| 166 | return ifOp.getResult(i: 0); |
| 167 | } |
| 168 | |
| 169 | // Create the DPS init operands for the partitioned Linalg op. |
| 170 | // Return all the new partitioned operands. |
| 171 | static SmallVector<Value> createDestinationPassingStyleInitOperands( |
| 172 | LinalgOp op, GridOp gridOp, ArrayRef<Value> partitionedOperands, |
| 173 | ArrayRef<GridAxis> reductionGridAxes, IRMapping &partitionMap, |
| 174 | ImplicitLocOpBuilder &builder) { |
| 175 | // TODO: add support for multiple destination passing style initial value |
| 176 | // operands. |
| 177 | assert(op.getNumDpsInits() == 1 && "Multiple initial values not supported." ); |
| 178 | SmallVector<Value> newOperands = llvm::to_vector(Range&: partitionedOperands); |
| 179 | auto operandIdx = op.getDpsInitOperand(i: 0)->getOperandNumber(); |
| 180 | Value partitionedInitOperand = |
| 181 | partitionMap.lookup(from: op->getOperands()[operandIdx]); |
| 182 | newOperands[operandIdx] = createDestinationPassingStyleInitOperand( |
| 183 | op, operandNumber: 0, partitionedOperand: partitionedInitOperand, reductionGridAxes, gridOp, builder); |
| 184 | return newOperands; |
| 185 | } |
| 186 | |
| 187 | static void createAllReduceForResultsWithoutPartialShardings( |
| 188 | LinalgOp unshardedOp, ArrayRef<GridAxis> opReductionGridAxes, |
| 189 | ArrayRef<Sharding> resultShardings, IRMapping &partitionMap, |
| 190 | ImplicitLocOpBuilder &builder) { |
| 191 | ReductionKind reductionKind = getReductionKindOfLinalgOp(op: unshardedOp); |
| 192 | for (auto [unshardedLinalgOpResult, resultSharding] : |
| 193 | llvm::zip_equal(t: unshardedOp->getResults(), u&: resultShardings)) { |
| 194 | Value partitionedLinalgOpResult = |
| 195 | partitionMap.lookup(from: unshardedLinalgOpResult); |
| 196 | Value reducedValue = shard::AllReduceOp::create( |
| 197 | builder, input: partitionedLinalgOpResult, grid: resultSharding.getGrid(), |
| 198 | gridAxes: opReductionGridAxes, reduction: reductionKind); |
| 199 | partitionMap.map(from: unshardedLinalgOpResult, to: reducedValue); |
| 200 | } |
| 201 | } |
| 202 | |
| 203 | static void partitionLinalgOpWithShardedReduction( |
| 204 | LinalgOp op, ArrayRef<Value> partitionedOperands, |
| 205 | ArrayRef<Sharding> operandShardings, ArrayRef<Sharding> resultShardings, |
| 206 | ArrayRef<utils::IteratorType> loopIteratorTypes, |
| 207 | ArrayRef<SmallVector<GridAxis>> gridAxisAssignmentForLoopIterators, |
| 208 | IRMapping &partitionMap, SymbolTableCollection &symbolTable, |
| 209 | ImplicitLocOpBuilder &builder) { |
| 210 | GridOp grid = getGrid(op, operandShardings, resultShardings, symbolTable); |
| 211 | SmallVector<GridAxis> reductionGridAxes = shard::getReductionGridAxes( |
| 212 | loopIteratorTypes, gridAxisAssignmentForLoopIterators); |
| 213 | SmallVector<Value> partitionedLinalgOpOperands = |
| 214 | createDestinationPassingStyleInitOperands(op, gridOp: grid, partitionedOperands, |
| 215 | reductionGridAxes, partitionMap, |
| 216 | builder); |
| 217 | // We must not change the operand mappings of the original partitionMap as |
| 218 | // they are the mappings for the whole partition blob and may be used by |
| 219 | // others. |
| 220 | IRMapping internalPartitionMap; |
| 221 | for (auto [unshardedOperand, partitionedOperand] : |
| 222 | llvm::zip_equal(t: op->getOperands(), u&: partitionedLinalgOpOperands)) { |
| 223 | internalPartitionMap.map(from: unshardedOperand, to: partitionedOperand); |
| 224 | } |
| 225 | partitionTriviallyShardableOperation( |
| 226 | op&: *op, partitionedOperands: partitionedLinalgOpOperands, operandShardings, resultShardings, |
| 227 | partitionMap&: internalPartitionMap, symbolTable, builder); |
| 228 | for (Value result : op->getResults()) { |
| 229 | partitionMap.map(from: result, to: internalPartitionMap.lookup(from: result)); |
| 230 | } |
| 231 | |
| 232 | // Handle partial shardings. |
| 233 | createAllReduceForResultsWithoutPartialShardings( |
| 234 | unshardedOp: op, opReductionGridAxes: reductionGridAxes, resultShardings, partitionMap, builder); |
| 235 | } |
| 236 | |
| 237 | namespace { |
| 238 | // ShardingInterface for ops that implement LinalgStructuredInterface. |
| 239 | // The supported ops are only those where the indexing maps are projected |
| 240 | // permutations. |
| 241 | template <typename Op> |
| 242 | struct StructuredOpShardingInterface |
| 243 | : public shard::ShardingInterface::ExternalModel< |
| 244 | StructuredOpShardingInterface<Op>, Op> { |
| 245 | SmallVector<utils::IteratorType> getLoopIteratorTypes(Operation *op) const { |
| 246 | return llvm::cast<LinalgOp>(Val: op).getIteratorTypesArray(); |
| 247 | } |
| 248 | |
| 249 | SmallVector<AffineMap> getIndexingMaps(Operation *op) const { |
| 250 | LinalgOp linalgOp = llvm::cast<LinalgOp>(Val: op); |
| 251 | SmallVector<AffineMap> res = linalgOp.getIndexingMapsArray(); |
| 252 | |
| 253 | // Results must have the same indexing as destination passing style initial |
| 254 | // operands. |
| 255 | for (int64_t i = 0; i < linalgOp.getNumDpsInits(); ++i) { |
| 256 | res.push_back(Elt: res[linalgOp.getDpsInitOperand(i)->getOperandNumber()]); |
| 257 | } |
| 258 | |
| 259 | return res; |
| 260 | } |
| 261 | |
| 262 | SmallVector<ReductionKind> |
| 263 | getReductionLoopIteratorKinds(Operation *op) const { |
| 264 | LinalgOp linalgOp = llvm::cast<LinalgOp>(Val: op); |
| 265 | SmallVector<utils::IteratorType> iteratorTypes = |
| 266 | linalgOp.getIteratorTypesArray(); |
| 267 | unsigned reductionItersCount = llvm::accumulate( |
| 268 | iteratorTypes, 0u, [](unsigned count, utils::IteratorType iter) { |
| 269 | return count + (iter == utils::IteratorType::reduction); |
| 270 | }); |
| 271 | shard::ReductionKind reductionKind = getReductionKindOfLinalgOp(op: linalgOp); |
| 272 | return SmallVector<ReductionKind>(reductionItersCount, reductionKind); |
| 273 | } |
| 274 | |
| 275 | LogicalResult partition(Operation *op, ArrayRef<Value> partitionedOperands, |
| 276 | ArrayRef<Sharding> operandShardings, |
| 277 | ArrayRef<Sharding> resultShardings, |
| 278 | IRMapping &partitionMap, |
| 279 | SymbolTableCollection &symbolTable, |
| 280 | OpBuilder &builder) const { |
| 281 | LinalgOp linalgOp = llvm::cast<LinalgOp>(Val: op); |
| 282 | |
| 283 | SmallVector<AffineMap> indexingMaps = linalgOp.getIndexingMapsArray(); |
| 284 | bool allIndexingMapsAreProjectedPermutation = |
| 285 | llvm::all_of(indexingMaps, [](AffineMap map) { |
| 286 | return map.isProjectedPermutation(); |
| 287 | }); |
| 288 | if (!allIndexingMapsAreProjectedPermutation) { |
| 289 | // TODO: handle non-projected permutations. |
| 290 | return op->emitOpError() |
| 291 | << "supports indexing maps that are only projected permutation." ; |
| 292 | } |
| 293 | |
| 294 | SmallVector<utils::IteratorType> loopIteratorTypes = |
| 295 | linalgOp.getIteratorTypesArray(); |
| 296 | ShardingArray gridAxisAssignmentForLoopIterators = |
| 297 | getGridAxisAssignmentForLoopIterators(operandShardings, resultShardings, |
| 298 | loopIteratorTypes, indexingMaps); |
| 299 | if (shard::isAtLeastOneReductionIteratorSharded( |
| 300 | loopIteratorTypes, gridAxisAssignmentForLoopIterators)) { |
| 301 | ImplicitLocOpBuilder implicitLocBuilder(op->getLoc(), builder); |
| 302 | partitionLinalgOpWithShardedReduction( |
| 303 | op: linalgOp, partitionedOperands, operandShardings, resultShardings, |
| 304 | loopIteratorTypes, gridAxisAssignmentForLoopIterators, partitionMap, |
| 305 | symbolTable, builder&: implicitLocBuilder); |
| 306 | } else { |
| 307 | partitionTriviallyShardableOperation(op&: *op, partitionedOperands, |
| 308 | operandShardings, resultShardings, |
| 309 | partitionMap, symbolTable, builder); |
| 310 | } |
| 311 | |
| 312 | return success(); |
| 313 | } |
| 314 | }; |
| 315 | } // namespace |
| 316 | |
| 317 | template <typename OpType> |
| 318 | static void registerOne(MLIRContext *ctx) { |
| 319 | OpType::template attachInterface<StructuredOpShardingInterface<OpType>>(*ctx); |
| 320 | } |
| 321 | |
| 322 | /// Variadic helper function. |
| 323 | template <typename... OpTypes> |
| 324 | static void registerAll(MLIRContext *ctx) { |
| 325 | (registerOne<OpTypes>(ctx), ...); |
| 326 | } |
| 327 | |
| 328 | void registerShardingInterfaceExternalModels(DialectRegistry ®istry) { |
| 329 | registry.addExtension(extensionFn: +[](MLIRContext *ctx, LinalgDialect *dialect) { |
| 330 | DialectRegistry registry; |
| 331 | registry.insert<affine::AffineDialect, arith::ArithDialect, scf::SCFDialect, |
| 332 | tensor::TensorDialect>(); |
| 333 | ctx->appendDialectRegistry(registry); |
| 334 | for (StringRef name : registry.getRegisteredDialectNames()) |
| 335 | ctx->getOrLoadDialect(name); |
| 336 | |
| 337 | registerOne<linalg::GenericOp>(ctx); |
| 338 | registerAll< |
| 339 | #define GET_OP_LIST |
| 340 | #include "mlir/Dialect/Linalg/IR/LinalgStructuredOps.cpp.inc" |
| 341 | >(ctx); |
| 342 | }); |
| 343 | } |
| 344 | } // namespace mlir::linalg |
| 345 | |