为什么关于串行和并行分数的 Amdahl 定律在四核 CPU 上没有提供 4 的理论加速？
Why Amdahl Law on serial and parallel fractions does not provide a theoretical speedup of 4 on quad-core CPU?
我有一个代码
（Floyd-Warshall algorithm表示NxN矩阵中的最短路径），
有三个for-循环，一个在另一个循环中，循环次数相同。
在最后一个 for 中，我通过三元运算进行了赋值 = <bool> ? <val1> : <val2> - 基于比较，如果它是 True 与否。
我使用 OpenMP 将第二个 for 与 #pragma omp parallel for 并行化.
我无法计算代码的并行百分比和串行百分比以成功应用 Amdahl Law 来恢复理论加速。
for (k = 0; k < N; k++)
#pragma omp parallel for private(i,j) shared(x) num_threads(4)
for (i = 0; i < N; i++){
for (j = 0; j < N; j++) {
x[i][j] = x[i][j] < (x[i][k] + x[k][j]) ? x[i][j] : (x[i][k] + x[k][j]) ;
}
}
我使用的是四核，因此我预计理论上的加速比为 4。
X[i][j]是矩阵，其中每个元素作为连接节点i和j的边的权重；如果它们未连接，则为宏 INF（无限）。
两个内部循环和最内部循环的主体在每个 core.That 上串行执行，因为您将外部循环标记为并行执行。
但是：
- 我希望比 4 的加速少得多。总是存在通信开销
最内层循环中的主体对所有核心使用相同的矩阵，并且还修改了矩阵。因此矩阵中的变化必须传播到所有其他核心。这可能会导致以下问题：
- CPU-缓存可能无用，因为缓存的数组元素可能会被另一个可能具有不同缓存的核心更改。
- 在最坏的情况下，矩阵中的所有修改都取决于之前的更改（我没有针对您的情况进行检查）。在这种情况下，并行执行是不可能的 => 一个以上的核心根本没有加速。
您应该检查是否可以以可以处理不相交的部分矩阵的方式更改您的算法。如果内核处理单独而不相交的数据，您将获得最佳加速。
由于这样做几乎没有任何努力，因此您应该明确分析代码及其变体。
TL;DR:
大学在 Amdahl's Law 实际示例中花费更多时间来展示市场营销的女孩和男孩是多么容易对 multi-core 和 many-core 玩具产生错误的期望，这很好。
也就是说，让我们定义 test-case:
Floyd-Warshall处理中的问题可以构造为：
- 处理启动开销
- data-structures 内存分配 + 设置
- data-values 初始化
- Floyd-Warshall具体情况（零化对角线等）[=82=]
- 节计时工具
- 具有 Floyd-Warshall O(N^3) 过程的部分 Improvement-Under-Test [IUT]
Amdahl's Law 声明任何进程的最终限制 总体 "improvement"，假设第 [6] 节包含要评估的 [IUT]，而总体 "improvement" 永远不会变得比 ~ 1 / ( ( 1 - IUT ) + ( IUT / N ) ) 更好。
实验( 1 - IUT )部分的时间留待好心读者自行测试和记录。
如何计算代码第 [6] 节中潜在并行化 [IUT] 的效果？
首先，让我们关注一下最初发布的代码中发生的事情，在纯 SEQ（串行）code-execution 流程中：
即使没有基于 OpenMP 的尝试将任务分发到更大的 resources-base:
，初始代码片段已经有一些 space 用于性能改进
for ( k = 0; k < N; k++ )
for ( i = 0; i < N; i++ ){
for ( j = 0; j < N; j++ ){
x[i][j] = x[i][j] > ( x[i][k] + x[k][j] ) // .TEST <bool>
? ( x[i][k] + x[k][j] ) // .ASSIGN <val1>
: x[i][j]; // .ASSIGN <val2>
}
}
如果这是 运行 纯粹的 SEQ 独奏或试图利用 #pragma omp，如原始问题 in both cases the Amdahl's Law will show ZERO or even "negative" improvement.[=23 中所张贴的那样=]
为什么？为什么不是 4 的 speed-up？为什么一点改善都没有？
因为代码被指示运行 "mechanically" 在所有资源上重复，运行ning 完全相同，相同范围的任务整整 4 次，shoulder-on-shoulder, 每个人都在其他人之外，所以 4 倍多的资源并没有带来任何预期的积极效果，因为他们一起花费了相同的时间 co-run 任务的所有部分 4 次独立地在其他人的潜力 "help"（如果不是更糟，由于某些情况，当在整个任务 运行ning 期间观察到资源争用时）。
所以，我们宁愿使用 OpenMP 的优势来拆分任务，让每个资源只处理算法范围的适当部分（感谢 Floyd-Warshall 算法，因为 这在这个方向上非常宽容并允许，因为它的处理方案，即使允许负权重，也是non-intervening，所以没有敌对障碍，同步，critical-section需要在线程之间传播任何东西）
那么，我们可以在这里获得任何 OpenMP 好处吗？哦，是的，很多：
#include "omp.h" // .MUST SET a gcc directive // "-fopenmp"
// --------------------------------------------------------[1] ref. above
void main(){
int i, j, k;
const int N = 100;
int x[100][100];
// --------------------------------------------------------[2] ref. above
// --------------------------------------------------------[3] ref. above
// --------------------------------------------------------[4] ref. above
for ( k = 0; k < N; k++ )
{
// --------------------------------------------------------[5] ref. above
//------------------------------------------------------[6]----- OMP
// ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
// PARALLEL is not precise, "just"-CONCURRENT is EXACT IN THE SECTION LEVEL BELOW
#pragma omp parallel for private(i,j) shared(x) num_threads(4)
for ( i = 0; i < N; i++ ){ // .MUST incl.actual k-th ROW, in case NEG weights are permitted
int nTHREADs = omp_get_num_threads(); // .GET "total" number of spawned threads
int tID = omp_get_thread_num(); // .GET "own" tID# {0,1,..omp_get_num_threads()-1} .AVOID dumb repeating the same .JOB by all spawned threads
for ( j = tID; j < N; j += nTHREADs ){ // .FOR WITH tID#-offset start + strided .INC STEP // .MUST incl.actual k-th COL, in case NEG weights are permitted
// - - - - - - - - - - - - - - - - - - - - - - - -
// SINCE HERE: // .JOB WAS SPLIT 2 tID#-ed, NON-OVERLAPPING tasks
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ // .N.B: dumb "just"-CONCURRENT processing is O.K. here
// ................................................ // 1-thread .INC STEP +1 a sure ZERO Amdahl-Law effect ( will bear an adverse penalty from use-less omp_get_*() calls )
// °.°.°.°.°.°.°.°.°.°.°.°.°.°.°.°.°.°.°.°.°.°.°.°. // 2-threads .INC STEP +2 may have Amdahl-Law effect ~ 1 / ( ( 1 - OMP ) + ( OMP / 2 ) ) if enough free CPU-resources
// '-.'-.'-.'-.'-.'-.'-.'-.'-.'-.'-.'-.'-.'-.'-.'-. // 3-threads .INC STEP +3 may have Amdahl-Law effect ~ 1 / ( ( 1 - OMP ) + ( OMP / 3 ) ) if enough free CPU-resources
// ^'-.^'-.^'-.^'-.^'-.^'-.^'-.^'-.^'-.^'-.^'-.^'-. // 4-threads .INC STEP +4 may have Amdahl-Law effect ~ 1 / ( ( 1 - OMP ) + ( OMP / 4 ) ) if enough free CPU-resources
// o1234567o1234567o1234567o1234567o1234567o1234567 // 8-threads .INC STEP +8 may have Amdahl-Law effect ~ 1 / ( ( 1 - OMP ) + ( OMP / 8 ) ) if enough free CPU-resources
// o123456789ABCDEFo123456789ABCDEFo123456789ABCDEF // 16-threads .INC STEP +16 may have Amdahl-Law effect ~ 1 / ( ( 1 - OMP ) + ( OMP / 16 ) ) if enough free CPU-resources
// o123456789ABCDEFGHIJKLMNOPQRSTUVo123456789ABCDEF // 32-threads .INC STEP +32 may have Amdahl-Law effect ~ 1 / ( ( 1 - OMP ) + ( OMP / 32 ) ) if enough free CPU-resources
// o123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijkl // 64-threads .INC STEP +64 may have Amdahl-Law effect ~ 1 / ( ( 1 - OMP ) + ( OMP / 64 ) ) if enough free CPU-resources
// o123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijkl // 128-threads .INC STEP +128 may have Amdahl-Law effect ~ 1 / ( ( 1 - OMP ) + ( OMP / 128 ) ) if enough free CPU-resources
int aPair = x[i][k] + x[k][j]; // .MUST .CALC ADD( x_ik, x_kj ) to TEST // .MAY smart re-use in case .GT. and ASSIGN will have to take a due place
if ( x[i][j] > aPair ) x[i][j] = aPair; // .IFF .UPD // .AVOID dumb re-ASSIGN(s) of self.value(s) to self
// - - - - - - - - - - - - - - - - - - - - - - - -
}
}
// ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
}// --------------------------------------------------------------- OMP
return;
}
了解 OpenMP beyond an Amdahl's Law predicted 限制：
所提出的方法通过一些有趣的实验开启了进一步探索的潜力：
- 将线程数设置为 1（用作实验基线）
- 设置线程数为 ( nCPUcores / 2 )
- 设置线程数为 ( nCPUcores - 1 )
- 设置线程数为 ( nCPUcores ) + 运行 disk defragmentation/compression
- 设置线程数为 ( nCPUcores * 2 )
- 将线程数设置为 ( nCPUcores * 2 ) + 强制 CPU-affinity on just 2 CPU-cores
- 设置线程数为 ( nCPUcores * 20 )
- 设置rows/cols N ~ { 1.000 | 的数量10.000 | 100.000 | 1.000.000 } 并检查效果
我有一个代码
（Floyd-Warshall algorithm表示NxN矩阵中的最短路径），
有三个for-循环，一个在另一个循环中，循环次数相同。
在最后一个 for 中，我通过三元运算进行了赋值 = <bool> ? <val1> : <val2> - 基于比较，如果它是 True 与否。
我使用 OpenMP 将第二个 for 与 #pragma omp parallel for 并行化.
我无法计算代码的并行百分比和串行百分比以成功应用 Amdahl Law 来恢复理论加速。
for (k = 0; k < N; k++)
#pragma omp parallel for private(i,j) shared(x) num_threads(4)
for (i = 0; i < N; i++){
for (j = 0; j < N; j++) {
x[i][j] = x[i][j] < (x[i][k] + x[k][j]) ? x[i][j] : (x[i][k] + x[k][j]) ;
}
}
我使用的是四核，因此我预计理论上的加速比为 4。
X[i][j]是矩阵，其中每个元素作为连接节点i和j的边的权重；如果它们未连接，则为宏 INF（无限）。
两个内部循环和最内部循环的主体在每个 core.That 上串行执行，因为您将外部循环标记为并行执行。
但是：
- 我希望比 4 的加速少得多。总是存在通信开销
最内层循环中的主体对所有核心使用相同的矩阵，并且还修改了矩阵。因此矩阵中的变化必须传播到所有其他核心。这可能会导致以下问题：
- CPU-缓存可能无用，因为缓存的数组元素可能会被另一个可能具有不同缓存的核心更改。
- 在最坏的情况下，矩阵中的所有修改都取决于之前的更改（我没有针对您的情况进行检查）。在这种情况下，并行执行是不可能的 => 一个以上的核心根本没有加速。
您应该检查是否可以以可以处理不相交的部分矩阵的方式更改您的算法。如果内核处理单独而不相交的数据，您将获得最佳加速。
由于这样做几乎没有任何努力，因此您应该明确分析代码及其变体。
TL;DR:
大学在 Amdahl's Law 实际示例中花费更多时间来展示市场营销的女孩和男孩是多么容易对 multi-core 和 many-core 玩具产生错误的期望，这很好。
也就是说，让我们定义 test-case:
Floyd-Warshall处理中的问题可以构造为：
- 处理启动开销
- data-structures 内存分配 + 设置
- data-values 初始化
- Floyd-Warshall具体情况（零化对角线等）[=82=]
- 节计时工具
- 具有 Floyd-Warshall O(N^3) 过程的部分 Improvement-Under-Test [IUT]
Amdahl's Law 声明任何进程的最终限制 总体 "improvement"，假设第 [6] 节包含要评估的 [IUT]，而总体 "improvement" 永远不会变得比 ~ 1 / ( ( 1 - IUT ) + ( IUT / N ) ) 更好。
实验( 1 - IUT )部分的时间留待好心读者自行测试和记录。
如何计算代码第 [6] 节中潜在并行化 [IUT] 的效果？
首先，让我们关注一下最初发布的代码中发生的事情，在纯 SEQ（串行）code-execution 流程中：
即使没有基于 OpenMP 的尝试将任务分发到更大的 resources-base:
，初始代码片段已经有一些 space 用于性能改进 for ( k = 0; k < N; k++ )
for ( i = 0; i < N; i++ ){
for ( j = 0; j < N; j++ ){
x[i][j] = x[i][j] > ( x[i][k] + x[k][j] ) // .TEST <bool>
? ( x[i][k] + x[k][j] ) // .ASSIGN <val1>
: x[i][j]; // .ASSIGN <val2>
}
}
如果这是 运行 纯粹的 SEQ 独奏或试图利用 #pragma omp，如原始问题 in both cases the Amdahl's Law will show ZERO or even "negative" improvement.[=23 中所张贴的那样=]
为什么？为什么不是 4 的 speed-up？为什么一点改善都没有？
因为代码被指示运行 "mechanically" 在所有资源上重复，运行ning 完全相同，相同范围的任务整整 4 次，shoulder-on-shoulder, 每个人都在其他人之外，所以 4 倍多的资源并没有带来任何预期的积极效果，因为他们一起花费了相同的时间 co-run 任务的所有部分 4 次独立地在其他人的潜力 "help"（如果不是更糟，由于某些情况，当在整个任务 运行ning 期间观察到资源争用时）。
所以，我们宁愿使用 OpenMP 的优势来拆分任务，让每个资源只处理算法范围的适当部分（感谢 Floyd-Warshall 算法，因为 这在这个方向上非常宽容并允许，因为它的处理方案，即使允许负权重，也是non-intervening，所以没有敌对障碍，同步，critical-section需要在线程之间传播任何东西）
那么，我们可以在这里获得任何 OpenMP 好处吗？哦，是的，很多：
#include "omp.h" // .MUST SET a gcc directive // "-fopenmp"
// --------------------------------------------------------[1] ref. above
void main(){
int i, j, k;
const int N = 100;
int x[100][100];
// --------------------------------------------------------[2] ref. above
// --------------------------------------------------------[3] ref. above
// --------------------------------------------------------[4] ref. above
for ( k = 0; k < N; k++ )
{
// --------------------------------------------------------[5] ref. above
//------------------------------------------------------[6]----- OMP
// ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
// PARALLEL is not precise, "just"-CONCURRENT is EXACT IN THE SECTION LEVEL BELOW
#pragma omp parallel for private(i,j) shared(x) num_threads(4)
for ( i = 0; i < N; i++ ){ // .MUST incl.actual k-th ROW, in case NEG weights are permitted
int nTHREADs = omp_get_num_threads(); // .GET "total" number of spawned threads
int tID = omp_get_thread_num(); // .GET "own" tID# {0,1,..omp_get_num_threads()-1} .AVOID dumb repeating the same .JOB by all spawned threads
for ( j = tID; j < N; j += nTHREADs ){ // .FOR WITH tID#-offset start + strided .INC STEP // .MUST incl.actual k-th COL, in case NEG weights are permitted
// - - - - - - - - - - - - - - - - - - - - - - - -
// SINCE HERE: // .JOB WAS SPLIT 2 tID#-ed, NON-OVERLAPPING tasks
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ // .N.B: dumb "just"-CONCURRENT processing is O.K. here
// ................................................ // 1-thread .INC STEP +1 a sure ZERO Amdahl-Law effect ( will bear an adverse penalty from use-less omp_get_*() calls )
// °.°.°.°.°.°.°.°.°.°.°.°.°.°.°.°.°.°.°.°.°.°.°.°. // 2-threads .INC STEP +2 may have Amdahl-Law effect ~ 1 / ( ( 1 - OMP ) + ( OMP / 2 ) ) if enough free CPU-resources
// '-.'-.'-.'-.'-.'-.'-.'-.'-.'-.'-.'-.'-.'-.'-.'-. // 3-threads .INC STEP +3 may have Amdahl-Law effect ~ 1 / ( ( 1 - OMP ) + ( OMP / 3 ) ) if enough free CPU-resources
// ^'-.^'-.^'-.^'-.^'-.^'-.^'-.^'-.^'-.^'-.^'-.^'-. // 4-threads .INC STEP +4 may have Amdahl-Law effect ~ 1 / ( ( 1 - OMP ) + ( OMP / 4 ) ) if enough free CPU-resources
// o1234567o1234567o1234567o1234567o1234567o1234567 // 8-threads .INC STEP +8 may have Amdahl-Law effect ~ 1 / ( ( 1 - OMP ) + ( OMP / 8 ) ) if enough free CPU-resources
// o123456789ABCDEFo123456789ABCDEFo123456789ABCDEF // 16-threads .INC STEP +16 may have Amdahl-Law effect ~ 1 / ( ( 1 - OMP ) + ( OMP / 16 ) ) if enough free CPU-resources
// o123456789ABCDEFGHIJKLMNOPQRSTUVo123456789ABCDEF // 32-threads .INC STEP +32 may have Amdahl-Law effect ~ 1 / ( ( 1 - OMP ) + ( OMP / 32 ) ) if enough free CPU-resources
// o123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijkl // 64-threads .INC STEP +64 may have Amdahl-Law effect ~ 1 / ( ( 1 - OMP ) + ( OMP / 64 ) ) if enough free CPU-resources
// o123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijkl // 128-threads .INC STEP +128 may have Amdahl-Law effect ~ 1 / ( ( 1 - OMP ) + ( OMP / 128 ) ) if enough free CPU-resources
int aPair = x[i][k] + x[k][j]; // .MUST .CALC ADD( x_ik, x_kj ) to TEST // .MAY smart re-use in case .GT. and ASSIGN will have to take a due place
if ( x[i][j] > aPair ) x[i][j] = aPair; // .IFF .UPD // .AVOID dumb re-ASSIGN(s) of self.value(s) to self
// - - - - - - - - - - - - - - - - - - - - - - - -
}
}
// ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
}// --------------------------------------------------------------- OMP
return;
}
了解 OpenMP beyond an Amdahl's Law predicted 限制：
所提出的方法通过一些有趣的实验开启了进一步探索的潜力：
- 将线程数设置为 1（用作实验基线）
- 设置线程数为 ( nCPUcores / 2 )
- 设置线程数为 ( nCPUcores - 1 )
- 设置线程数为 ( nCPUcores ) + 运行 disk defragmentation/compression
- 设置线程数为 ( nCPUcores * 2 )
- 将线程数设置为 ( nCPUcores * 2 ) + 强制 CPU-affinity on just 2 CPU-cores
- 设置线程数为 ( nCPUcores * 20 )
- 设置rows/cols N ~ { 1.000 | 的数量10.000 | 100.000 | 1.000.000 } 并检查效果