知识卡片

结构图卡 · 9783.f · 生成模型:DeepSeek-V4.1-Flash

矩阵乘法为何适合并行

理解等级:高级

矩阵乘法的每个输出元素 C[i][j] 是 A 第 i 行与 B 第 j 列的内积。关键观察是:A[i][j] 只参与 C 的第 i 行,B[i][j] 只参与 C 的第 j 列,所以每个非零元素都能独立地广播到它影响的全部输出位置。mapper 把 A 的元素 (i,j,v) 发到键 (i, y)(y 取遍 B 的列),把 B 的元素 (i,j,v) 发到键 (x, j)(x 取遍 A 的行),值里带上自己的内标号;reducer 以输出坐标 (i,j) 为键,收到两侧同内标的两组值,配对相乘再求和。每个输出元素互不依赖,因此可完全并行,代价是中间数据被放大若干倍。

结构图:

flowchart LR
  A[A 的非零元素] --> M[mapper 广播]
  B[B 的非零元素] --> M
  M -->|键为输出坐标| P[按 (i,j) 分区到 reducer]
  P --> R[reducer 配对被乘数相乘求和]
  R --> C[得到 C[i][j]]
这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第25章 MapReduce · 查看原书依据

      为了使用这种算法,请注意,每个元素 A[i][j] 仅用于计算 C 的第 i 行元素,每个元素 B[i] [j] 仅用于计算 C 的第 j 列中的元素。我们的目标是使 reducer 的每个输出都是 C 的单个元素,这意味着我们将需要用 mapper 发送键值,明确 C 中的每个元素。

    参考来源

    - 位置:《数据科学入门(第2版)》第25章 MapReduce(源文件:extracted/数据科学入门(第2版)/_epub-src/OEBPS/Text/0029.xhtml) - 结论依据:原文这一段直接给出本卡的核心判断:「为了使用这种算法,请注意,每个元素 A[i][j] 仅用于计算 C 的第 i 行……」 - 原始内容:为了使用这种算法,请注意,每个元素 A[i][j] 仅用于计算 C 的第 i 行元素,每个元素 B[i] [j] 仅用于计算 C 的第 j 列中的元素。我们的目标是使 reducer 的每个输出都是 C 的单个元素,这意味着我们将需要用 mapper 发送键值,明确 C 中的每个元素。