如何并行化这个矩阵运算
How to parallelize this matrix operation
阻力距离矩阵的计算在最后一步遇到了瓶颈，如下：
matrix1[i, j] = matrix2[i, i] - 2*matrix2[i, j] + matrix[j, j]
我发现的每个算法都会并行化除此步骤之外的每个步骤，所以现在我只有一个双 for 循环。矩阵是 16000x16000，所以这非常耗时。有没有办法加快这样的操作？
怎么样：
matrix1 = matrix2.diagonal()[:,None] - 2*matrix2 + matrix.diagonal()[None,:]
≣≣≣≣≣≣≣≣≣≣≣≣≣≣≣≣≣≣≣≣≣≣≣≣≣≣≣≣≣≣≣≣ ( How to parallelize this matrix operation ) ≣≣≣≣≣≣≣
Q :
"Is there a way to speed up such an operation?"
A :
嗯，这里我们有两个非常不同的请求：
(a)
并行化一些东西，没有看到任何更广泛的背景，除了知道Python代码执行生态系统和粗略的规模，但w/odtype和
(b)
加速这种与上下文无关的SLOC计算
实际硬件生态系统 - x86-CISC | ARM-RISC | ... - 实际的 NUMA 属性 ?
细节很重要。
大矩阵运算智能优化，最终处理时间从N天缩短到11~12分钟（长话短说），细节决定成败。
关键性能限制摘要事实：
鉴于尺寸，大约有 16E3 * 16E3 / 1E9 * 8 * ( 1 + 1 + 1 )
~ 6.144 [GB] 的 RAM 占用空间，如果 8B 单元格是 dtype，则操作必须覆盖，如果 complex128（甚至 object ... )，如果有任何一种不太丰富的 { 4B | ... | 1B } 数据表示形式（遗憾的是没有在 O/P 上下文中提到它），那么让我们使用 8B 一个。使用较小的 dtype 可能意味着最终过程的速度会加快。有许多先前的大规模 numpy-案例，其中 8B-dtype-s 数据单元在数值过程中实际上得到更快的处理，因为 CPU-word 适应是不需要，即使以拥有两倍大的内存占用和 memory-I/O 流量为代价。较小的数据足迹速度较慢
我们的主要敌人在哪里？
这个 6.1 GB RAM 占用空间，给定一个微不足道的数学“沉重”的计算（只做三个的总和，但有点“疯狂”-每个目标矩阵单元格位置的索引单元格元素，将是我们在 fight-for-speed 中的主要“敌人” - (b)
下的请求
“狂野”（但仍不像在其他情况下那样狂野）索引将是我们进行性能调整的第二个“敌人”
“并行化”的愿望 python 生态系统内部的某些东西引入了问题，因为 python 解释器仍在 2022 年第一季度依赖于pure-[SERIAL]，任何&所有并发防止 GIL-lock step-dancing。当然，numpy、numba 和其他非本地 Python 解释工具有助于绕过 GIL 交错、一个块接一个块、大约 10 [ms] 长，切碎的代码块解释。
这就是说，请求 (a) 没有简单的方法可以满足。 Numpy 可以从 GIL 中“逃脱”，但这不是 [PARALLEL] 代码执行。 Numpy 足够聪明，可以“向量化”（并且机器 CPU 架构可能会更好地利用（或不使用）CPU-CISC/RISC ILP 和智能AVX-512、FMA3、FMA4 和类似的 CPU-uOps 级可用操作，如果 numpy 之前已设置并编译为确实能够使用任何这些基于硅的、特定于平台的
powers ),
尽管如此
none我们的主要敌人会被任何numpy-硬编码的聪明解决，如果我们不帮助他尽可能聪明地工作.
临时或临时的 RAM 分配（这里说的是 N x 2.048 GB RAM 足迹）非常昂贵
- 因此尽可能预分配和重新使用
2020: Still some improvements, prediction for 2025
-------------------------------------------------------------------------
0.1 ns - NOP
0.3 ns - XOR, ADD, SUB
0.5 ns - CPU L1 dCACHE reference (1st introduced in late 80-ies )
0.9 ns - JMP SHORT
1 ns - speed-of-light (a photon) travel a 1 ft (30.5cm) distance -- will stay, throughout any foreseeable future :o)
?~~~~~~~~~~~ 1 ns - MUL ( i**2 = MUL i, i )~~~~~~~~~ doing this 1,000 x is 1 [us]; 1,000,000 x is 1 [ms]; 1,000,000,000 x is 1 [s] ~~~~~~~~~~~~~~~~~~~~~~~~~
3~4 ns - CPU L2 CACHE reference (2020/Q1)
5 ns - CPU L1 iCACHE Branch mispredict
7 ns - CPU L2 CACHE reference
10 ns - DIV
19 ns - CPU L3 CACHE reference (2020/Q1 considered slow on 28c Skylake)
71 ns - CPU cross-QPI/NUMA best case on XEON E5-46*
100 ns - MUTEX lock/unlock
100 ns - own DDR MEMORY reference
135 ns - CPU cross-QPI/NUMA best case on XEON E7-*
202 ns - CPU cross-QPI/NUMA worst case on XEON E7-*
325 ns - CPU cross-QPI/NUMA worst case on XEON E5-46*
| | | |...
| | | |...ns
| | |...us
| |...ms
|...s
RAM-memory-I/O（说 N x 2.048 GB RAM-footprint）是超出任何 L3 / L2 / L1 缓存大小的数量级，因此，缓存内重用降为零并且访问时间跳了 4+ 个数量级，是的，大了数万 - 从 [ns] 的十分之一到 [ns] 的数百（详情请看 here）
- 所以最好避免任何类型的循环，并最好保留 numpy-矢量化技巧，以尽可能高效地矢量化和平铺他们的代码设计者能够发明和实施（numpy.flags FORTRAN-v/s-CLANG 排序可能帮助，但没有 SLOC 的外部上下文，没有机会猜测这是否有助于外部范围操作）
最快和并行解决方案的潜力
我的（本地主机非基准）候选人将是：
- 使用预分配和重新使用（即可破坏）
matrix1, matrix2 + matrix, matrix2 对角线 可能的单独和维护向量
那时并且只有那时（并且只有当 SLOC 的更广泛的上下文允许时）
- 可能会将
MUL 和 ADD 的 [SERIAL] 操作拆分为一对可能的 [PARALLEL] 代码执行流
-- 一个
做一个矢量化预存储（使用矢量广播）一个并就地添加（matrix1 += ）另一个，单独维护，对角线矢量vecDmatrix，vecDmatrix2（相应地广播和转置）进入 matrix1
-- other
通过 -2 替换 MUL matrix2 ~ 与其他添加分开执行 matrix2 *= -2 步骤
-- finally
在完全完成两个相互独立的（因此实际上是可并行化的）操作流程后，执行就地 ADD，如 matrix1 += matrix2 ( where
inplace matrix2 *= -2已经单独预计算，在前面的true-[PARALLEL]-section )
在某些情况下且仅在这种情况下，执行此真实 [并行] 部分编排的设置和其他开销附加成本不会超过单独执行任何一部分工作的净效果，您可能会喜欢实现请求 -(a) 不损害请求的目标 -(b)，否则永远不会。
阻力距离矩阵的计算在最后一步遇到了瓶颈，如下：
matrix1[i, j] = matrix2[i, i] - 2*matrix2[i, j] + matrix[j, j]
我发现的每个算法都会并行化除此步骤之外的每个步骤，所以现在我只有一个双 for 循环。矩阵是 16000x16000，所以这非常耗时。有没有办法加快这样的操作？
怎么样：
matrix1 = matrix2.diagonal()[:,None] - 2*matrix2 + matrix.diagonal()[None,:]
≣≣≣≣≣≣≣≣≣≣≣≣≣≣≣≣≣≣≣≣≣≣≣≣≣≣≣≣≣≣≣≣ ( How to parallelize this matrix operation ) ≣≣≣≣≣≣≣
Q :
"Is there a way to speed up such an operation?"
A :
嗯，这里我们有两个非常不同的请求：
(a)
并行化一些东西，没有看到任何更广泛的背景，除了知道Python代码执行生态系统和粗略的规模，但w/odtype和
(b)
加速这种与上下文无关的SLOC计算
实际硬件生态系统 - x86-CISC | ARM-RISC | ... - 实际的 NUMA 属性 ?
细节很重要。
大矩阵运算智能优化，最终处理时间从N天缩短到11~12分钟（长话短说），细节决定成败。
关键性能限制摘要事实：
鉴于尺寸，大约有 16E3 * 16E3 / 1E9 * 8 * ( 1 + 1 + 1 )
~ 6.144 [GB] 的 RAM 占用空间，如果 8B 单元格是 dtype，则操作必须覆盖，如果 complex128（甚至 object ... )，如果有任何一种不太丰富的 { 4B | ... | 1B } 数据表示形式（遗憾的是没有在 O/P 上下文中提到它），那么让我们使用 8B 一个。使用较小的 dtype 可能意味着最终过程的速度会加快。有许多先前的大规模 numpy-案例，其中 8B-dtype-s 数据单元在数值过程中实际上得到更快的处理，因为 CPU-word 适应是不需要，即使以拥有两倍大的内存占用和 memory-I/O 流量为代价。较小的数据足迹速度较慢
我们的主要敌人在哪里？
这个 6.1 GB RAM 占用空间，给定一个微不足道的数学“沉重”的计算（只做三个的总和，但有点“疯狂”-每个目标矩阵单元格位置的索引单元格元素，将是我们在 fight-for-speed 中的主要“敌人” - (b)
“狂野”（但仍不像在其他情况下那样狂野）索引将是我们进行性能调整的第二个“敌人”
“并行化”的愿望 python 生态系统内部的某些东西引入了问题，因为 python 解释器仍在 2022 年第一季度依赖于pure-[SERIAL]，任何&所有并发防止 GIL-lock step-dancing。当然，numpy、numba 和其他非本地 Python 解释工具有助于绕过 GIL 交错、一个块接一个块、大约 10 [ms] 长，切碎的代码块解释。
这就是说，请求 (a) 没有简单的方法可以满足。 Numpy 可以从 GIL 中“逃脱”，但这不是 [PARALLEL] 代码执行。 Numpy 足够聪明，可以“向量化”（并且机器 CPU 架构可能会更好地利用（或不使用）CPU-CISC/RISC ILP 和智能AVX-512、FMA3、FMA4 和类似的 CPU-uOps 级可用操作，如果 numpy 之前已设置并编译为确实能够使用任何这些基于硅的、特定于平台的
powers ),
尽管如此
none我们的主要敌人会被任何numpy-硬编码的聪明解决，如果我们不帮助他尽可能聪明地工作.
临时或临时的 RAM 分配（这里说的是 N x 2.048 GB RAM 足迹）非常昂贵
- 因此尽可能预分配和重新使用
2020: Still some improvements, prediction for 2025
-------------------------------------------------------------------------
0.1 ns - NOP
0.3 ns - XOR, ADD, SUB
0.5 ns - CPU L1 dCACHE reference (1st introduced in late 80-ies )
0.9 ns - JMP SHORT
1 ns - speed-of-light (a photon) travel a 1 ft (30.5cm) distance -- will stay, throughout any foreseeable future :o)
?~~~~~~~~~~~ 1 ns - MUL ( i**2 = MUL i, i )~~~~~~~~~ doing this 1,000 x is 1 [us]; 1,000,000 x is 1 [ms]; 1,000,000,000 x is 1 [s] ~~~~~~~~~~~~~~~~~~~~~~~~~
3~4 ns - CPU L2 CACHE reference (2020/Q1)
5 ns - CPU L1 iCACHE Branch mispredict
7 ns - CPU L2 CACHE reference
10 ns - DIV
19 ns - CPU L3 CACHE reference (2020/Q1 considered slow on 28c Skylake)
71 ns - CPU cross-QPI/NUMA best case on XEON E5-46*
100 ns - MUTEX lock/unlock
100 ns - own DDR MEMORY reference
135 ns - CPU cross-QPI/NUMA best case on XEON E7-*
202 ns - CPU cross-QPI/NUMA worst case on XEON E7-*
325 ns - CPU cross-QPI/NUMA worst case on XEON E5-46*
| | | |...
| | | |...ns
| | |...us
| |...ms
|...s
RAM-memory-I/O（说 N x 2.048 GB RAM-footprint）是超出任何 L3 / L2 / L1 缓存大小的数量级，因此，缓存内重用降为零并且访问时间跳了 4+ 个数量级，是的，大了数万 - 从 [ns] 的十分之一到 [ns] 的数百（详情请看 here）
- 所以最好避免任何类型的循环，并最好保留 numpy-矢量化技巧，以尽可能高效地矢量化和平铺他们的代码设计者能够发明和实施（numpy.flags FORTRAN-v/s-CLANG 排序可能帮助，但没有 SLOC 的外部上下文，没有机会猜测这是否有助于外部范围操作）
最快和并行解决方案的潜力
我的（本地主机非基准）候选人将是：
- 使用预分配和重新使用（即可破坏）
matrix1, matrix2+matrix, matrix2对角线 可能的单独和维护向量
那时并且只有那时（并且只有当 SLOC 的更广泛的上下文允许时）
- 可能会将
MUL和ADD的[SERIAL]操作拆分为一对可能的[PARALLEL]代码执行流
-- 一个
做一个矢量化预存储（使用矢量广播）一个并就地添加（matrix1 +=）另一个，单独维护，对角线矢量vecDmatrix，vecDmatrix2（相应地广播和转置）进入matrix1
-- other
通过-2替换MULmatrix2~ 与其他添加分开执行matrix2 *= -2步骤
-- finally
在完全完成两个相互独立的（因此实际上是可并行化的）操作流程后，执行就地ADD，如matrix1 += matrix2( where
inplacematrix2 *= -2已经单独预计算，在前面的true-[PARALLEL]-section )
在某些情况下且仅在这种情况下，执行此真实 [并行] 部分编排的设置和其他开销附加成本不会超过单独执行任何一部分工作的净效果，您可能会喜欢实现请求 -(a) 不损害请求的目标 -(b)，否则永远不会。