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

Question

并行化中的一种常见技术是像这样融合嵌套的 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) 和 int j = funcj(x,一)

这里有一些代码表明这是可行的:

#include <stdio.h>
#include <math.h>
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=N-i, j = N-j }(镜像Y轴，然后镜像X轴)。

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