TL;博士：
大学花更多的时间在阿姆达尔定律的实际例子上来展示营销女孩和男孩是多么容易对多核和多核玩具产生错误的期望，这很好。
也就是说，让我们定义测试用例：
Floyd-Warshall 处理中的问题可以构造为：
- 进程启动开销
- 数据结构内存分配+设置
- 数据值初始化
- Floyd-Warshall 特定条件（归零对角线等）
- 部分计时工具
- 具有 Floyd-Warshall O(N^3)过程的部分，具有潜在的改进-待测 [IUT]
鉴于第 [6] 节包含要评估的 [IUT]，阿姆达尔定律宣布了任何流程整体“改进”的最终限制，而整体“改进”永远不会比~ 1 / ( ( 1 - IUT ) + ( IUT / N ) ).
留给善良的读者测试和记录( 1 - IUT )部分实验的时间安排。
如何计算[IUT]代码第 [6] 节中潜在并行化的效果？
首先，让我们关注在纯SEQ（串行）代码执行流程中最初发布的代码中发生的情况：
即使没有基于 OpenMP 的尝试将任务分配到更大的资源库，初始代码段也有一些性能改进空间：
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，如在两种情况下的原始问题中发布的那样，Amdahl 定律将显示零甚至“负面”改进。
为什么？为什么不加速4？为什么甚至一点改善都没有？
因为代码被指示在所有资源上“机械地”重复运行，运行完全相同，相同范围的任务整整 4 次，肩并肩，每个人都在其他人之外，所以 4 倍的资源确实没有带来任何预期的积极影响，因为他们一起花费了相同的时间来共同运行任务的所有部分 4 次，每个部分都独立于其他人的潜在“帮助”（如果不是更糟，由于某些情况，当在整个任务运行期间观察到资源争用）。
所以，让我们宁愿使用 OpenMP 的优势来拆分任务，让每个资源只处理算法范围的足够部分（感谢 Floyd-Warshall 算法，因为这在这个方向上非常宽容，并且允许，因为它的处理方案，即使在允许负权重的情况下，也是不干预的，所以不需要敌对的屏障、同步、临界区来在线程之间传播任何东西）
那么，我们可以在这里获得任何 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;
}
所提出的方法通过一些有趣的实验为进一步探索开辟了一些潜力：
- 将线程数设置为 1（用作实验基线）
- 将线程数设置为 ( nCPUcores / 2 )
- 将线程数设置为 ( nCPUcores - 1 )
- 将线程数设置为 (nCPUcores) + 运行磁盘碎片整理/压缩
- 将线程数设置为 ( nCPUcores * 2 )
- 将线程数设置为 ( nCPUcores * 2 ) + 仅在 2 个 CPU 核心上强制执行 CPU 亲和性
- 将线程数设置为 ( nCPUcores * 20 )
- 设置行数/列数 N ~ { 1.000 | 10.000 | 100.000 | 1.000.000 } 并检查效果