問題描述

并行化的一個常用技術是像這樣融合嵌套的 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).

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

這篇關于融合三角形循環進行并行化，計算子索引的文章就介紹到這了，希望我們推薦的答案對大家有所幫助，也希望大家多多支持html5模板網！