DNS分块矩阵的理解

DNS矩阵分块的理解

主要内容是 DNS 矩阵分块算法 的核心概念和实现细节。DNS 是一种高效的并行矩阵乘法算法，能够在 SIMD-CC（单指令多数据并行计算机）架构上快速计算大规模矩阵乘法。

1. 背景与核心思想

背景

• 来源：由 Dekel、Nassimi 和 Sahni 在 1981 年提出。
• 应用场景：在并行计算中优化矩阵乘法运算。
• 核心点：
  • 处理器数量：n^3（即每个矩阵乘法所需的运算由一个独立处理器负责）。
  • 时间复杂度：O(log⁡n)，是并行算法中较快的实现。
• 并行规约的本质

核心思想

• 矩阵分块：
  • 矩阵 AA 和 BB 分解为多个子块，分配到不同处理器执行。
• 广播与并行计算：
  • 使用“一对一”和“一对多”的广播方式，使每个处理器能够获取对应的 A[i,k]和 B[k,j]。
  • 处理器完成本地相乘，并沿 kk 方向累积结果，最后存储在 C[i,j]。

2. 核心计算过程

1. 处理器编号与位置：

   • Pr是处理器编号，其位置由 (k, i, j) 决定。
   • 编号计算公式： r=kn^2+i*n+j, 其中 0≤i,j,k<n。
   • 解释：编号 r 是基于 k,i,j的三维索引，将三维位置映射到一维处理器编号。

2. 数据存储：

   • 每个处理器 Pr的寄存器存储：
     • A[k,i,j]：从矩阵 AA 中分配的数据。
     • B[k,i,j]：从矩阵 BB 中分配的数据。
     • C[k,i,j]：结果矩阵初始为 0，最终存储部分计算结果。

3. 并行计算：

   • 每个处理器通过广播获取需要的 A[i,k]和 B[k,j]，进行点乘： C[i,j]+=A[i,k]×B[k,j]C
   • 重复进行 log n 步操作，最终计算完成。

3. 理解处理器划分

示例：假设 n=4 

• 总处理器数量：n^3 = 64。
• 每个处理器负责一个三维网格点：
  • (k, i, j)：其中 k,i,j∈{0,1,2,3}。
  • 如处理器 P17的位置为 k = 1, i = 0, j = 1，计算公式： r=k*n^2+i*n+j=1*16+0*4+1=17

4. 可能出现的问题

(1) 基础概念题

• DNS 矩阵分块算法的基本思想是什么？
  • 参考：通过分块并行化矩阵乘法，处理器 Pr执行本地相乘并累积，使用广播机制优化数据分发。

(2) 编号计算题

• 给定 n和某处理器编号，计算其对应的三维位置(k, i, j)，反之亦然。
  • 示例：
  • 答案：(2,1,1)。

(3) 时间复杂度分析

• 为什么 DNS 算法的时间复杂度是 O(log⁡ n)？
  • 参考：由于广播和累积的计算步数是按对数级别分布的，总步数为 log⁡ n。

(4) 数据存储与广播

• DNS 算法中，处理器如何获取 A[i,k] 和 B[k,j]的数据？
  • 参考：通过广播机制，每个处理器 PrP_r 与相邻处理器交换所需数据。

总结

DNS 算法是并行计算领域的重要优化方法之一，重点考察以下几个方面：

1. 基本思想：分块、广播、本地计算、累积。
2. 处理器编号与映射：三维位置和编号之间的关系。
3. 时间复杂度：并行优化的关键。
4. 数据流与存储：如何实现高效的广播和累积。