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

2021-12-11 00:00:00 math for-loop c c++

并行化的一个常用技术是像这样融合嵌套的 for 循环

A common technique in parallelization is to fuse nested for loops like this

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;

我想知道如何才能融合这样的三角形循环

I'm wondering how I can do this to fuse a triangle loop like this

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

这有 n*(n+1)/2 次迭代.我们将融合迭代称为 x.使用二次公式我想出了这个:

This has n*(n+1)/2 iterations. Let's call the fused iteration x. Using the quadratic formula I have come up with this:

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 的转换.

Unlike fusing the square loop this requires using the sqrt function and conversions from int to float and from float to int.

我想知道是否有更简单或更有效的方法来做到这一点?例如，不需要 sqrt 函数或从 int 到 float 或 float 到 int 的转换的解决方案.

I'm wondering if there is a simpler or more efficient way of doing this? For example a solution which does not require the sqrt function or conversions from int to float or float to int.

我不想要依赖于上一次或下一次迭代的解决方案.我只想要像 int i = funci(x) 和 int j = funcj(x,i)

以下是一些代码，表明这是有效的:

Here is some code showing that this works:

#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
", cnt++, i,j);      
        }
    } printf("
");

    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
", x,i,j);
    }       
}

推荐答案

考虑到您试图融合一个三角形以实现并行化，非显而易见的解决方案是选择 x 到 (i,j):

Considering that you're trying to fuse a triangle with the intent of parallelizing, the non-obvious solution is to choose a non-trivial mapping of x to (i,j):

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

毕竟，您不会以任何特殊顺序处理它们，因此无需关心确切的映射.

After all, you're not processing them in any special order, so the exact mapping is a don't care.

所以像计算矩形一样计算 x->i,j，但是如果 i >j then { i=N-i, j = N-j }(镜像Y轴，然后镜像X轴).

So calculate x->i,j as you'd do for a rectangle, but if i > j then { i=N-i, j = N-j } (mirror Y axis, then mirror X axis).

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

相关文章