知识卡片
矩阵乘法为何适合并行
矩阵乘法的每个输出元素 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 中的每个元素。