融合三角形循环进行并行化，计算子索引

并行化的一种常见技术是将嵌套的for循环融合在一起

for(int i=0; i<n; i++) { for(int j=0; j<n; j++) { 

至

 for(int x=0; x<n*n; x++) { int i = x/n; int j = x%n; 

我想知道我怎么能这样做融合像这样的三角形循环

 for(int i=0; i<n; i++) { for(int j=0; j<i+1; j++) { 

这具有n*(n+1)/2次迭代。 让我们调用融合迭代x 。 使用二次方程式我得出了这个：

 for(int x=0; x<(n*(n+1)/2); x++) { int i = (-1 + sqrt(1.0+8.0*x))/2; int j = x - i*(i+1)/2; 

与融合方形循环不同，这需要使用sqrt函数和从int到float以及从float到int的转换。

我想知道是否有更简单或更有效的方法吗？ 例如，一个不需要sqrt函数或从int转换为float或float转换为int的解决方案。

编辑：我不想要一个依赖于前一次或下一次迭代的解决方案。 我只想要像int i = funci(x) and int j = funcj(x,i)

这是一些代码显示这是有效的：

 #include  #include  int main() { int n = 5; int cnt = 0; for(int i=0; i<n; i++) { for(int j=0; j<i+1; j++) { printf("%d: %d %d\n", cnt++, i,j); } } printf("\n"); int nmax = n*(n+1)/2; for(int x=0; x<nmax; x++) { int i = (-1 + sqrt(1.0+8.0*x))/2; int j = x - i*(i+1)/2; printf("%d: %d %d\n", x,i,j); } } 

Answer 1

考虑到你试图将三角形融合为并行化的意图，非显而易见的解决方案是选择x到（i，j）的非平凡映射：

 j |\ i -> | \ ____ | | \ => |\\ | V |___\ |_\\__| 

毕竟，您没有按任何特殊顺序处理它们，因此确切的映射是无关紧要的。

所以计算x->i,j就像你对矩形一样，但是如果i > j则{ i=Ni, j = Nj } （镜像Y轴，然后是镜像X轴）。

  ____ |\\ | |\ |\ |_\\__| ==> |_\ __ => | \ / | | \ /__| |___\ 

Answer 2

最理智的forms当然是第一种forms。

也就是说，融合forms最好用条件：

 int i = 0; int j = 0; for(int x=0; x<(n*(n+1)/2); x++) { // ... ++j; if (j>i) { j = 0; ++i; } } 

Answer 3

我想知道是否有更简单或更有效的方法吗？

是的，你必须开始的代码。 请记住以下几点：

• 浮点运算不存在比普通整数更快的情况。
• 然而，存在大量浮点比普通整数慢得多的情况。 FPU或没有FPU。
• 浮点变量通常比大多数系统上的普通整数大，因此仅因此原因较慢。
• 代码的第一个版本可能对缓存内存最友好。 对于任何手动优化的情况，这完全取决于您使用的CPU。
• 无论是对普通整数还是浮点数，大多数系统的除法通常都很慢。
• 任何forms的复杂算术都比简单计算慢。

因此，对于世界上任何给定的CPU，您的第二个示例几乎可以保证比第一个示例慢得多。 此外，它也完全不可读。