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

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) and int j = funcj(x,i)

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

#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轴).

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