| 1 | //===- ShardingInterface.cpp -------------------------------------*- C++-*-===// |
| 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/Shard/Interfaces/ShardingInterface.h" |
| 10 | #include "mlir/Dialect/Shard/Interfaces/ShardingInterfaceImpl.h" |
| 11 | |
| 12 | #include "mlir/Dialect/Shard/IR/ShardOps.h" |
| 13 | #include "mlir/IR/AffineMap.h" |
| 14 | #include "mlir/IR/IRMapping.h" |
| 15 | #include "mlir/Support/LLVM.h" |
| 16 | #include "llvm/ADT/ArrayRef.h" |
| 17 | #include "llvm/ADT/STLExtras.h" |
| 18 | #include "llvm/ADT/SmallSet.h" |
| 19 | #include "llvm/Support/Debug.h" |
| 20 | |
| 21 | #include <utility> |
| 22 | |
| 23 | #define DEBUG_TYPE "sharding-interface" |
| 24 | #define DBGS() (llvm::dbgs() << "[" DEBUG_TYPE << "]: ") |
| 25 | |
| 26 | using namespace mlir; |
| 27 | using namespace mlir::shard; |
| 28 | |
| 29 | #include "mlir/Dialect/Shard/Interfaces/ShardingInterface.cpp.inc" |
| 30 | |
| 31 | //===----------------------------------------------------------------------===// |
| 32 | // common util functions |
| 33 | //===----------------------------------------------------------------------===// |
| 34 | |
| 35 | static LogicalResult |
| 36 | checkOperandAffineExprRecursively(AffineExpr expr, |
| 37 | SmallVectorImpl<bool> &seenIds) { |
| 38 | switch (expr.getKind()) { |
| 39 | case AffineExprKind::Add: { |
| 40 | auto binOpExpr = cast<AffineBinaryOpExpr>(Val&: expr); |
| 41 | AffineExpr lhs = binOpExpr.getLHS(); |
| 42 | AffineExpr rhs = binOpExpr.getRHS(); |
| 43 | if (failed(Result: checkOperandAffineExprRecursively(expr: lhs, seenIds))) |
| 44 | return failure(); |
| 45 | if (failed(Result: checkOperandAffineExprRecursively(expr: rhs, seenIds))) |
| 46 | return failure(); |
| 47 | return success(); |
| 48 | } |
| 49 | case AffineExprKind::Mul: { |
| 50 | auto binOpExpr = cast<AffineBinaryOpExpr>(Val&: expr); |
| 51 | AffineExpr lhs = binOpExpr.getLHS(); |
| 52 | AffineExpr rhs = binOpExpr.getRHS(); |
| 53 | AffineExpr dimExpr; |
| 54 | if (lhs.getKind() == AffineExprKind::DimId && |
| 55 | rhs.getKind() == AffineExprKind::Constant) { |
| 56 | dimExpr = lhs; |
| 57 | } else if (rhs.getKind() == AffineExprKind::DimId && |
| 58 | lhs.getKind() == AffineExprKind::Constant) { |
| 59 | dimExpr = rhs; |
| 60 | } else { |
| 61 | return failure(); |
| 62 | } |
| 63 | unsigned position = cast<AffineDimExpr>(Val&: dimExpr).getPosition(); |
| 64 | if ((size_t)position >= seenIds.size() || seenIds[position]) |
| 65 | return failure(); |
| 66 | seenIds[position] = true; |
| 67 | return success(); |
| 68 | } |
| 69 | case AffineExprKind::DimId: { |
| 70 | unsigned position = cast<AffineDimExpr>(Val&: expr).getPosition(); |
| 71 | if ((size_t)position >= seenIds.size() || seenIds[position]) |
| 72 | return failure(); |
| 73 | seenIds[position] = true; |
| 74 | return success(); |
| 75 | } |
| 76 | default: |
| 77 | return failure(); |
| 78 | } |
| 79 | } |
| 80 | |
| 81 | static FailureOr<llvm::SmallSet<unsigned, 2>> |
| 82 | checkOperandAffineExpr(AffineExpr expr, unsigned numDims) { |
| 83 | SmallVector<bool> seenIds(numDims, false); |
| 84 | if (failed(Result: checkOperandAffineExprRecursively(expr, seenIds))) |
| 85 | return failure(); |
| 86 | |
| 87 | llvm::SmallSet<unsigned, 2> positions; |
| 88 | for (auto it : llvm::enumerate(First&: seenIds)) { |
| 89 | if (it.value()) |
| 90 | positions.insert(V: (unsigned)it.index()); |
| 91 | } |
| 92 | return positions; |
| 93 | } |
| 94 | |
| 95 | template <typename T> |
| 96 | SmallVector<GridAxesAttr> |
| 97 | fromArrayOfVector(MLIRContext *ctxt, const SmallVector<SmallVector<T>> &vec) { |
| 98 | SmallVector<GridAxesAttr> res; |
| 99 | for (const auto &v : vec) { |
| 100 | res.emplace_back(GridAxesAttr::get(context: ctxt, content: v)); |
| 101 | } |
| 102 | return res; |
| 103 | } |
| 104 | |
| 105 | //===----------------------------------------------------------------------===// |
| 106 | // shard::getSharding |
| 107 | //===----------------------------------------------------------------------===// |
| 108 | |
| 109 | FailureOr<std::pair<bool, Sharding>> shard::getSharding(OpResult result) { |
| 110 | Value val = cast<Value>(Val&: result); |
| 111 | bool anyShardedForDef = llvm::any_of(Range: val.getUsers(), P: [](Operation *user) { |
| 112 | auto shardOp = llvm::dyn_cast<shard::ShardOp>(Val: user); |
| 113 | if (!shardOp) |
| 114 | return false; |
| 115 | return !shardOp.getAnnotateForUsers(); |
| 116 | }); |
| 117 | |
| 118 | if (anyShardedForDef) { |
| 119 | // expected to have exact one use if it has a use of `shard.shard` without |
| 120 | // unit attr annotate_for_users |
| 121 | if (!val.hasOneUse()) |
| 122 | return failure(); |
| 123 | auto shardOp = llvm::cast<shard::ShardOp>(Val: *val.getUsers().begin()); |
| 124 | return std::make_pair(x: false, y: Sharding(shardOp.getSharding())); |
| 125 | } |
| 126 | |
| 127 | bool anyShardedForUsers = llvm::any_of(Range: val.getUsers(), P: [](Operation *user) { |
| 128 | auto shardOp = llvm::dyn_cast<shard::ShardOp>(Val: user); |
| 129 | if (!shardOp) |
| 130 | return false; |
| 131 | return shardOp.getAnnotateForUsers(); |
| 132 | }); |
| 133 | if (anyShardedForUsers) { |
| 134 | SmallVector<ShardOp> shardOps; |
| 135 | for (Operation *user : val.getUsers()) { |
| 136 | ShardOp shardOp = llvm::dyn_cast<ShardOp>(Val: user); |
| 137 | if (shardOp) |
| 138 | shardOps.push_back(Elt: shardOp); |
| 139 | } |
| 140 | Sharding shardForDef = shardOps[0].getSharding(); |
| 141 | for (size_t i = 1; i < shardOps.size(); ++i) { |
| 142 | // TODO: Deduce a reasonable grid sharding attr for def when they are |
| 143 | // different |
| 144 | assert(shardForDef == shardOps[i].getSharding() && |
| 145 | "only support all shard ops have the same grid sharding attr" ); |
| 146 | } |
| 147 | return std::make_pair(x: true, y&: shardForDef); |
| 148 | } |
| 149 | return failure(); |
| 150 | } |
| 151 | |
| 152 | FailureOr<std::pair<bool, Sharding>> shard::getSharding(OpOperand &opOperand) { |
| 153 | Value val = opOperand.get(); |
| 154 | if (ShardOp shardOp = val.getDefiningOp<ShardOp>()) |
| 155 | return std::make_pair(x: shardOp.getAnnotateForUsers(), |
| 156 | y: Sharding(shardOp.getSharding())); |
| 157 | |
| 158 | return failure(); |
| 159 | } |
| 160 | |
| 161 | //===----------------------------------------------------------------------===// |
| 162 | // ShardingInterface::verifyShardingInterfaceImpl |
| 163 | //===----------------------------------------------------------------------===// |
| 164 | |
| 165 | LogicalResult shard::ShardingInterface::verifyShardingInterfaceImpl() { |
| 166 | Operation *op = getOperation(); |
| 167 | |
| 168 | // check operands and results type |
| 169 | for (Type type : op->getOperandTypes()) |
| 170 | if (!llvm::isa<RankedTensorType>(Val: type) && !type.isIntOrIndexOrFloat()) |
| 171 | return failure(); |
| 172 | for (Type type : op->getResultTypes()) |
| 173 | if (!llvm::isa<RankedTensorType>(Val: type) && !type.isIntOrIndexOrFloat()) |
| 174 | return failure(); |
| 175 | |
| 176 | // check maps |
| 177 | SmallVector<AffineMap> maps = getIndexingMaps(); |
| 178 | if (maps.empty()) |
| 179 | return failure(); |
| 180 | unsigned numOperands = op->getNumOperands(); |
| 181 | unsigned numResults = op->getNumResults(); |
| 182 | if (numOperands + numResults != maps.size()) |
| 183 | return failure(); |
| 184 | |
| 185 | for (OpResult result : op->getResults()) { |
| 186 | auto resultType = dyn_cast<RankedTensorType>(Val: result.getType()); |
| 187 | if (!resultType) |
| 188 | return failure(); |
| 189 | AffineMap map = maps[numOperands + result.getResultNumber()]; |
| 190 | if (!map.isProjectedPermutation()) { |
| 191 | return failure(); |
| 192 | } |
| 193 | } |
| 194 | |
| 195 | return success(); |
| 196 | } |
| 197 | |
| 198 | //===----------------------------------------------------------------------===// |
| 199 | // ShardingInterface::printLoopTypesAndIndexingMaps |
| 200 | //===----------------------------------------------------------------------===// |
| 201 | |
| 202 | void shard::ShardingInterface::printLoopTypesAndIndexingMaps(raw_ostream &os) { |
| 203 | os << "print loop types and indexing maps for: \n" ; |
| 204 | getOperation()->print(os); |
| 205 | os << "\n" ; |
| 206 | os << "loop types: [" ; |
| 207 | for (utils::IteratorType type : getLoopIteratorTypes()) { |
| 208 | os << stringifyEnum(enumValue: type) << " " ; |
| 209 | } |
| 210 | os << "]\n" ; |
| 211 | os << "indexing maps: \n" ; |
| 212 | for (AffineMap map : getIndexingMaps()) |
| 213 | os << map << "\n" ; |
| 214 | os << "\n" ; |
| 215 | } |
| 216 | |
| 217 | //===----------------------------------------------------------------------===// |
| 218 | // detail::defaultGetShardingOption |
| 219 | //===----------------------------------------------------------------------===// |
| 220 | |
| 221 | namespace { |
| 222 | |
| 223 | // Update the given `shardingOption` according to `gridAxes` and `loopIdx` |
| 224 | static LogicalResult fillShardingOption(Operation *op, |
| 225 | ShardingOption &shardingOption, |
| 226 | FlatSymbolRefAttr grid, |
| 227 | ArrayRef<GridAxis> gridAxes, |
| 228 | unsigned loopIdx) { |
| 229 | if ((shardingOption.grid && grid && shardingOption.grid != grid) || |
| 230 | (!shardingOption.shardingArray[loopIdx].empty() && |
| 231 | shardingOption.shardingArray[loopIdx] != gridAxes)) { |
| 232 | LLVM_DEBUG(DBGS() << "sharding option conflicts on loop iterator " |
| 233 | << loopIdx << "\n" ); |
| 234 | return failure(); |
| 235 | } |
| 236 | for (size_t i = 0; i < shardingOption.shardingArray.size(); ++i) { |
| 237 | if (i == loopIdx) |
| 238 | continue; |
| 239 | |
| 240 | for (GridAxis axis : gridAxes) { |
| 241 | if (llvm::is_contained(Range&: shardingOption.shardingArray[i], Element: axis)) { |
| 242 | LLVM_DEBUG(DBGS() << "sharding option conflicts because grid axes " |
| 243 | << axis << " duplicate" ); |
| 244 | return failure(); |
| 245 | } |
| 246 | } |
| 247 | } |
| 248 | if (grid) |
| 249 | shardingOption.grid = grid; |
| 250 | if (shardingOption.shardingArray[loopIdx].empty()) |
| 251 | shardingOption.shardingArray[loopIdx].append(in_start: gridAxes.begin(), |
| 252 | in_end: gridAxes.end()); |
| 253 | return success(); |
| 254 | } |
| 255 | |
| 256 | } // namespace |
| 257 | |
| 258 | FailureOr<ShardingOption> |
| 259 | shard::detail::defaultGetShardingOption(Operation *op, |
| 260 | ArrayRef<Sharding> operandShardings, |
| 261 | ArrayRef<Sharding> resultShardings) { |
| 262 | ShardingInterface shardingOp = llvm::cast<ShardingInterface>(Val: op); |
| 263 | ShardingOption shardingOption; |
| 264 | |
| 265 | if (failed(Result: shardingOp.verifyShardingInterfaceImpl())) |
| 266 | return op->emitOpError() << "invalid sharding interface implementation" ; |
| 267 | SmallVector<utils::IteratorType> loopTypes = |
| 268 | shardingOp.getLoopIteratorTypes(); |
| 269 | SmallVector<AffineMap> maps = shardingOp.getIndexingMaps(); |
| 270 | unsigned numOperands = op->getNumOperands(); |
| 271 | shardingOption.shardingArray.resize(N: loopTypes.size()); |
| 272 | llvm::SmallSet<unsigned, 4> visitedLoopIndices; |
| 273 | bool anyShardingInResultsOrOperands = false; |
| 274 | |
| 275 | // 1. Fill sharding option based on op results |
| 276 | for (auto shardingIt : llvm::enumerate(First&: resultShardings)) { |
| 277 | const Sharding &shardAttr = shardingIt.value(); |
| 278 | if (!shardAttr) |
| 279 | continue; |
| 280 | AffineMap map = maps[numOperands + shardingIt.index()]; |
| 281 | anyShardingInResultsOrOperands = true; |
| 282 | if (shardAttr.getSplitAxes().empty() || map.getResults().empty()) { |
| 283 | shardingOption.grid = shardAttr.getGridAttr(); |
| 284 | } else { |
| 285 | // Handle the split axes: calculate the corresponding loop index for each |
| 286 | // split axes sub-array, and then store the sub-array to |
| 287 | // shardingOption[index] |
| 288 | for (auto it : llvm::zip(t: map.getResults(), u: shardAttr.getSplitAxes())) { |
| 289 | AffineExpr expr = std::get<0>(t&: it); |
| 290 | ArrayRef<GridAxis> axes = std::get<1>(t&: it).asArrayRef(); |
| 291 | auto dim = cast<AffineDimExpr>(Val&: expr); |
| 292 | unsigned index = dim.getPosition(); |
| 293 | visitedLoopIndices.insert(V: index); |
| 294 | if (failed(Result: fillShardingOption(op, shardingOption, |
| 295 | grid: shardAttr.getGridAttr(), gridAxes: axes, loopIdx: index))) |
| 296 | return failure(); |
| 297 | } |
| 298 | } |
| 299 | } |
| 300 | |
| 301 | // 2. Fill sharding option based on operands |
| 302 | for (auto shardingIt : llvm::enumerate(First&: operandShardings)) { |
| 303 | const Sharding &shardAttr = shardingIt.value(); |
| 304 | if (!shardAttr) |
| 305 | continue; |
| 306 | |
| 307 | anyShardingInResultsOrOperands = !shardAttr.getSplitAxes().empty(); |
| 308 | AffineMap map = maps[shardingIt.index()]; |
| 309 | unsigned numDims = map.getNumDims(); |
| 310 | |
| 311 | // Handle the split axes. |
| 312 | // |
| 313 | // TODO: Change to process the operands with single loop index first and |
| 314 | // then the operands with multiple loop indices. |
| 315 | for (auto it : llvm::zip(t: map.getResults(), u: shardAttr.getSplitAxes())) { |
| 316 | AffineExpr expr = std::get<0>(t&: it); |
| 317 | ArrayRef<GridAxis> axes = std::get<1>(t&: it).asArrayRef(); |
| 318 | FailureOr<llvm::SmallSet<unsigned, 2>> loopIndices = |
| 319 | checkOperandAffineExpr(expr, numDims); |
| 320 | if (failed(Result: loopIndices)) |
| 321 | return op->emitOpError() |
| 322 | << "operand's affine expression is restricted to const_i * " |
| 323 | "dim_i + const_j + dim_j + ..." ; |
| 324 | if (loopIndices->empty()) |
| 325 | continue; |
| 326 | if (loopIndices->size() == 1) { |
| 327 | unsigned loopIdx = *loopIndices->begin(); |
| 328 | visitedLoopIndices.insert(V: loopIdx); |
| 329 | if (failed(Result: fillShardingOption(op, shardingOption, |
| 330 | grid: shardAttr.getGridAttr(), gridAxes: axes, loopIdx))) |
| 331 | return failure(); |
| 332 | } |
| 333 | // If multiple loop indices correspond to a dimension of an operand, it is |
| 334 | // difficult to infer which loop indices are responsible for sharding. |
| 335 | // Therefore, the exact loop index must be specified by others. |
| 336 | if (loopIndices->size() > 1) { |
| 337 | bool seenLoopIndices = false; |
| 338 | for (unsigned loopIdx : *loopIndices) { |
| 339 | if (visitedLoopIndices.contains(V: loopIdx)) { |
| 340 | seenLoopIndices = true; |
| 341 | break; |
| 342 | } |
| 343 | } |
| 344 | if (!seenLoopIndices) |
| 345 | return op->emitOpError() |
| 346 | << "the operand " << shardingIt.index() |
| 347 | << " has multiple loop indices in a dimension, but none of " |
| 348 | "them could be found in the exactly specified annotation " |
| 349 | "of op results or operands." ; |
| 350 | } |
| 351 | } |
| 352 | } |
| 353 | |
| 354 | // 3. Finalize sharding option |
| 355 | removeTrailingEmptySubArray(array&: shardingOption.shardingArray); |
| 356 | if (!anyShardingInResultsOrOperands) |
| 357 | shardingOption.empty = true; |
| 358 | return shardingOption; |
| 359 | } |
| 360 | |
| 361 | // Get the sharding attributed for the given result and sharding option. |
| 362 | static Sharding getSharding(OpResult result, |
| 363 | const ShardingOption &shardingOption, AffineMap map, |
| 364 | ArrayRef<utils::IteratorType> loopTypes) { |
| 365 | auto resultType = cast<RankedTensorType>(Val: result.getType()); |
| 366 | SmallVector<SmallVector<GridAxis>> splitAxes(resultType.getRank()); |
| 367 | |
| 368 | // process the split axes |
| 369 | for (auto it : llvm::enumerate(First: map.getResults())) { |
| 370 | AffineExpr expr = it.value(); |
| 371 | // `expr` must be an `AffineDimExpr` because `map` is verified by |
| 372 | // isProjectedPermutation |
| 373 | auto dim = cast<AffineDimExpr>(Val&: expr); |
| 374 | unsigned loopIdx = dim.getPosition(); |
| 375 | if (loopIdx < shardingOption.shardingArray.size()) |
| 376 | splitAxes[it.index()].append(RHS: shardingOption.shardingArray[loopIdx]); |
| 377 | } |
| 378 | |
| 379 | removeTrailingEmptySubArray(array&: splitAxes); |
| 380 | return Sharding::get(grid_: shardingOption.grid, |
| 381 | split_axes_: fromArrayOfVector(ctxt: result.getContext(), vec: splitAxes)); |
| 382 | } |
| 383 | |
| 384 | static FailureOr<Sharding> getSharding(OpOperand &opOperand, |
| 385 | const ShardingOption &shardingOption, |
| 386 | AffineMap map) { |
| 387 | Value operandValue = opOperand.get(); |
| 388 | auto operandType = dyn_cast<RankedTensorType>(Val: operandValue.getType()); |
| 389 | if (!operandType) { |
| 390 | if (operandValue.getType().isIntOrIndexOrFloat()) |
| 391 | return Sharding(); |
| 392 | return failure(); |
| 393 | } |
| 394 | // 0d tensors cannot be sharded and must get replicated |
| 395 | if (operandType.getRank() == 0) { |
| 396 | return Sharding(shardingOption.grid); |
| 397 | } |
| 398 | SmallVector<SmallVector<GridAxis>> splitAxes(operandType.getRank()); |
| 399 | unsigned numDims = map.getNumDims(); |
| 400 | for (auto it : llvm::enumerate(First: map.getResults())) { |
| 401 | int64_t idx = it.index(); |
| 402 | AffineExpr expr = it.value(); |
| 403 | FailureOr<llvm::SmallSet<unsigned, 2>> loopIndices = |
| 404 | checkOperandAffineExpr(expr, numDims); |
| 405 | if (failed(Result: loopIndices)) |
| 406 | return failure(); |
| 407 | SmallVector<unsigned> shardedLoopIndices; |
| 408 | for (unsigned loopIdx : *loopIndices) { |
| 409 | if ((size_t)loopIdx < shardingOption.shardingArray.size() && |
| 410 | !shardingOption.shardingArray[loopIdx].empty()) |
| 411 | shardedLoopIndices.push_back(Elt: loopIdx); |
| 412 | } |
| 413 | // mostly one sharded loop index is accepted |
| 414 | if (shardedLoopIndices.size() > 1) |
| 415 | return failure(); |
| 416 | if (shardedLoopIndices.size() == 1) { |
| 417 | splitAxes[idx].append( |
| 418 | RHS: shardingOption.shardingArray[shardedLoopIndices[0]]); |
| 419 | } |
| 420 | } |
| 421 | |
| 422 | removeTrailingEmptySubArray(array&: splitAxes); |
| 423 | return Sharding::get( |
| 424 | grid_: shardingOption.grid, |
| 425 | split_axes_: fromArrayOfVector(ctxt: opOperand.get().getContext(), vec: splitAxes)); |
| 426 | } |
| 427 | |
| 428 | FailureOr<std::vector<Sharding>> shard::detail::defaultGetShardingAnnotations( |
| 429 | Operation *op, const ShardingOption &shardingOption) { |
| 430 | std::vector<Sharding> res; |
| 431 | |
| 432 | ShardingInterface shardingOp = llvm::cast<ShardingInterface>(Val: op); |
| 433 | SmallVector<utils::IteratorType> loopTypes = |
| 434 | shardingOp.getLoopIteratorTypes(); |
| 435 | SmallVector<AffineMap> maps = shardingOp.getIndexingMaps(); |
| 436 | unsigned numOperands = op->getNumOperands(); |
| 437 | |
| 438 | for (OpOperand &opOperand : op->getOpOperands()) { |
| 439 | FailureOr<Sharding> shardingAttr = ::getSharding( |
| 440 | opOperand, shardingOption, map: maps[opOperand.getOperandNumber()]); |
| 441 | if (failed(Result: shardingAttr)) |
| 442 | return failure(); |
| 443 | res.push_back(x: *shardingAttr); |
| 444 | } |
| 445 | |
| 446 | for (OpResult result : op->getResults()) { |
| 447 | res.push_back(x: ::getSharding(result, shardingOption, |
| 448 | map: maps[numOperands + result.getResultNumber()], |
| 449 | loopTypes)); |
| 450 | } |
| 451 | |
| 452 | return res; |
| 453 | } |
| 454 | |
| 455 | //===----------------------------------------------------------------------===// |
| 456 | // detail::defaultAddShardingAnnotations |
| 457 | //===----------------------------------------------------------------------===// |
| 458 | |
| 459 | // To add a `shard.shard` op for the given result, based on the details provided |
| 460 | // in `shardingOption`, `map`, and `loopTypes`. |
| 461 | static LogicalResult addShardOp(OpBuilder &b, OpResult result, |
| 462 | const ShardingOption &shardingOption, |
| 463 | AffineMap map, |
| 464 | ArrayRef<utils::IteratorType> loopTypes) { |
| 465 | Sharding sharding = getSharding(result, shardingOption, map, loopTypes); |
| 466 | maybeInsertTargetShardingAnnotation(sharding, result, builder&: b); |
| 467 | |
| 468 | return success(); |
| 469 | } |
| 470 | |
| 471 | // To add a `shard.shard` op for the given operand, based on the details |
| 472 | // provided in `shardingOption`, `map`, and `loopTypes`. |
| 473 | static LogicalResult addShardOp(OpBuilder &b, OpOperand &opOperand, |
| 474 | const ShardingOption &shardingOption, |
| 475 | AffineMap map) { |
| 476 | |
| 477 | FailureOr<Sharding> sharding = getSharding(opOperand, shardingOption, map); |
| 478 | if (failed(Result: sharding)) { |
| 479 | return failure(); |
| 480 | } |
| 481 | OpBuilder::InsertionGuard guard(b); |
| 482 | maybeInsertSourceShardingAnnotation(sharding: sharding.value(), operand&: opOperand, builder&: b); |
| 483 | |
| 484 | return success(); |
| 485 | } |
| 486 | |
| 487 | LogicalResult shard::detail::defaultAddShardingAnnotations( |
| 488 | Operation *op, OpBuilder &b, const ShardingOption &shardingOption) { |
| 489 | assert(!shardingOption.empty && shardingOption.grid); |
| 490 | |
| 491 | ShardingInterface shardingOp = llvm::cast<ShardingInterface>(Val: op); |
| 492 | SmallVector<utils::IteratorType> loopTypes = |
| 493 | shardingOp.getLoopIteratorTypes(); |
| 494 | SmallVector<AffineMap> maps = shardingOp.getIndexingMaps(); |
| 495 | unsigned numOperands = op->getNumOperands(); |
| 496 | |
| 497 | // 1. add shard.shard ops for all op results |
| 498 | for (OpResult result : op->getResults()) { |
| 499 | if (failed(Result: addShardOp(b, result, shardingOption, |
| 500 | map: maps[numOperands + result.getResultNumber()], |
| 501 | loopTypes))) |
| 502 | return failure(); |
| 503 | } |
| 504 | |
| 505 | // 2. add shard.shard ops for all operands |
| 506 | for (OpOperand &opOperand : op->getOpOperands()) { |
| 507 | if (failed(Result: addShardOp(b, opOperand, shardingOption, |
| 508 | map: maps[opOperand.getOperandNumber()]))) |
| 509 | return failure(); |
| 510 | } |
| 511 | |
| 512 | return success(); |
| 513 | } |
| 514 | |
| 515 | #ifndef NDEBUG |
| 516 | static bool |
| 517 | isValueCompatibleWithFullReplicationSharding(Value value, |
| 518 | const Sharding &sharding) { |
| 519 | if (isa<RankedTensorType>(value.getType())) { |
| 520 | return isFullReplication(sharding); |
| 521 | } |
| 522 | |
| 523 | return !sharding; |
| 524 | } |
| 525 | |
| 526 | template <typename ValueRange, typename ShardingRage> |
| 527 | static bool |
| 528 | areValuesCompatibleWithFullReplicationShardings(ValueRange &&values, |
| 529 | ShardingRage &&shardings) { |
| 530 | if (std::size(values) != std::size(shardings)) { |
| 531 | return false; |
| 532 | } |
| 533 | return llvm::all_of(llvm::zip_equal(std::forward<ValueRange>(values), |
| 534 | std::forward<ShardingRage>(shardings)), |
| 535 | [](auto valueAndSharding) { |
| 536 | return isValueCompatibleWithFullReplicationSharding( |
| 537 | std::get<0>(valueAndSharding), |
| 538 | std::get<1>(valueAndSharding)); |
| 539 | }); |
| 540 | } |
| 541 | #endif // NDEBUG |
| 542 | |
| 543 | void shard::partitionFullyReplicatedOperation( |
| 544 | Operation &op, ArrayRef<Value> partitionedOperands, |
| 545 | ArrayRef<Sharding> operandShardings, ArrayRef<Sharding> resultShardings, |
| 546 | IRMapping &partitionMap, SymbolTableCollection &symbolTable, |
| 547 | OpBuilder &builder) { |
| 548 | assert(partitionedOperands.size() == operandShardings.size()); |
| 549 | assert(areValuesCompatibleWithFullReplicationShardings(op.getOperands(), |
| 550 | operandShardings)); |
| 551 | assert(areValuesCompatibleWithFullReplicationShardings(op.getResults(), |
| 552 | resultShardings)); |
| 553 | // `clone` will populate the mapping of old to new results. |
| 554 | builder.clone(op, mapper&: partitionMap); |
| 555 | } |
| 556 | |
| 557 | static void updateGridAxisAssignmentForLoopIterators( |
| 558 | ArrayRef<GridAxis> gridAxesAssignmentForTensorAxis, AffineExpr indexingExpr, |
| 559 | SmallVector<std::optional<SmallVector<GridAxis>>> |
| 560 | &gridAxesAssignmentForLoopIterators) { |
| 561 | AffineDimExpr affineDimExpr = cast<AffineDimExpr>(Val&: indexingExpr); |
| 562 | unsigned loopIteratorIdx = affineDimExpr.getPosition(); |
| 563 | if (gridAxesAssignmentForLoopIterators[loopIteratorIdx]) { |
| 564 | assert(llvm::equal(gridAxesAssignmentForTensorAxis, |
| 565 | *gridAxesAssignmentForLoopIterators[loopIteratorIdx])); |
| 566 | } else { |
| 567 | gridAxesAssignmentForLoopIterators[loopIteratorIdx] = |
| 568 | llvm::to_vector(Range&: gridAxesAssignmentForTensorAxis); |
| 569 | } |
| 570 | } |
| 571 | |
| 572 | ShardingArray shard::getGridAxisAssignmentForLoopIterators( |
| 573 | ArrayRef<Sharding> operandShardings, ArrayRef<Sharding> resultShardings, |
| 574 | ArrayRef<utils::IteratorType> loopIteratorTypes, |
| 575 | ArrayRef<AffineMap> indexingMaps) { |
| 576 | SmallVector<std::optional<SmallVector<GridAxis>>> |
| 577 | gridAxisAssignmentForLoopIterators(loopIteratorTypes.size()); |
| 578 | std::vector<Sharding> operatorAndResultShardings; |
| 579 | operatorAndResultShardings.reserve(n: operandShardings.size() + |
| 580 | resultShardings.size()); |
| 581 | llvm::append_range(C&: operatorAndResultShardings, R&: operandShardings); |
| 582 | for (auto [sharding, affineMap] : |
| 583 | llvm::zip_equal(t&: operatorAndResultShardings, u&: indexingMaps)) { |
| 584 | if (!sharding) { |
| 585 | continue; |
| 586 | } |
| 587 | for (auto [gridAxesAssignmentForTensorAxis, indexingExpr] : |
| 588 | llvm::zip(t: sharding.getSplitAxes(), u: affineMap.getResults())) { |
| 589 | updateGridAxisAssignmentForLoopIterators( |
| 590 | gridAxesAssignmentForTensorAxis: gridAxesAssignmentForTensorAxis.asArrayRef(), indexingExpr, |
| 591 | gridAxesAssignmentForLoopIterators&: gridAxisAssignmentForLoopIterators); |
| 592 | } |
| 593 | // Missing trailing split axes means replication on those tensor dimensions. |
| 594 | for (unsigned i = sharding.getSplitAxes().size(); |
| 595 | i < affineMap.getNumResults(); ++i) { |
| 596 | updateGridAxisAssignmentForLoopIterators( |
| 597 | gridAxesAssignmentForTensorAxis: {}, indexingExpr: affineMap.getResults()[i], gridAxesAssignmentForLoopIterators&: gridAxisAssignmentForLoopIterators); |
| 598 | } |
| 599 | } |
| 600 | |
| 601 | ShardingArray res; |
| 602 | llvm::transform(Range&: gridAxisAssignmentForLoopIterators, d_first: std::back_inserter(x&: res), |
| 603 | F: [](std::optional<SmallVector<GridAxis>> &axes) { |
| 604 | if (!axes) { |
| 605 | return SmallVector<GridAxis>(); |
| 606 | }; |
| 607 | return std::move(*axes); |
| 608 | }); |
| 609 | return res; |
| 610 | } |
| 611 | |
| 612 | bool shard::isAtLeastOneReductionIteratorSharded( |
| 613 | ArrayRef<utils::IteratorType> loopIteratorTypes, |
| 614 | ArrayRef<SmallVector<GridAxis>> gridAxisAssignmentForLoopIterators) { |
| 615 | for (auto [loopIteratorType, gridAxisAssignment] : |
| 616 | llvm::zip_equal(t&: loopIteratorTypes, u&: gridAxisAssignmentForLoopIterators)) { |
| 617 | if (loopIteratorType == utils::IteratorType::reduction && |
| 618 | !gridAxisAssignment.empty()) { |
| 619 | return true; |
| 620 | } |
| 621 | } |
| 622 | return false; |
| 623 | } |
| 624 | |
| 625 | SmallVector<GridAxis> shard::getReductionGridAxes( |
| 626 | ArrayRef<utils::IteratorType> loopIteratorTypes, |
| 627 | ArrayRef<SmallVector<GridAxis>> gridAxisAssignmentForLoopIterators) { |
| 628 | SmallVector<GridAxis> gridAxes; |
| 629 | for (auto [loopIteratorType, gridAxisAssignment] : |
| 630 | llvm::zip_equal(t&: loopIteratorTypes, u&: gridAxisAssignmentForLoopIterators)) { |
| 631 | if (loopIteratorType == utils::IteratorType::reduction) { |
| 632 | llvm::append_range(C&: gridAxes, R: gridAxisAssignment); |
| 633 | } |
| 634 | } |
| 635 | return gridAxes; |
| 636 | } |
| 637 | |
| 638 | void shard::partitionTriviallyShardableOperation( |
| 639 | Operation &op, ArrayRef<Value> partitionedOperands, |
| 640 | ArrayRef<Sharding> operandShardings, ArrayRef<Sharding> resultShardings, |
| 641 | IRMapping &partitionMap, SymbolTableCollection &symbolTable, |
| 642 | OpBuilder &builder) { |
| 643 | // `clone` will populate the mapping of old to new results. |
| 644 | Operation *newOp = builder.clone(op, mapper&: partitionMap); |
| 645 | // Set the result types to the sharded counterparts. |
| 646 | for (auto [oldResult, newResult, sharding] : |
| 647 | llvm::zip_equal(t: op.getResults(), u: newOp->getResults(), args&: resultShardings)) { |
| 648 | newResult.setType(shardType( |
| 649 | type: newResult.getType(), |
| 650 | grid: getGridOrNull(op: &op, gridSymbol: sharding.getGridAttr(), symbolTableCollection&: symbolTable), sharding)); |
| 651 | } |
| 652 | } |
| 653 | |