将循环转换为并行化

Question

对于这段代码，我还可以做哪些循环转换来增加潜在的并行性？

代码如下：

for (int i=10; i<N; i++)
{
    A[i] = B[i] * 14.3 / A[10];
    C[i] = C[i-1] + C[i-2];
}

到目前为止，我所做的是使用循环剥离：

A[10] = B[10] * 14.3 /A[10]
C[10] = C[10-1] + C[10-2];
for(int i = 11 ; i<N; i++)
{
    A[i] = B[i] * 14.3 / A[10];
    C[i] = C[i-1] + C[i-2];
 }

这就解决了第一行问题，但是有没有办法在循环中转换第二行呢？

Answer 1

for (int i=10; i<N; i++)
    {
    A[i] = B[i] * 14.3 / A[10];
    C[i] = C[i-1] + C[i-2];
    }

因此，正如你已经发现的，A[10]是特例，C不依赖于A,B和使用浮点或定点(所以你可以使用预先计算的常量，而不会造成很大的精度损失)，所以你可以分成：

// serial
A[10] = B[10] * 14.3 / A[10];
c0 = 14.3 / A[10];
// thread 1
for (int i=11; i<N; i++) A[i] = B[i] * c0;
// thread 2
for (int i=10; i<N; i++) C[i] = C[i-1] + C[i-2];

现在B独立于A，因此您可以在任意多个线程上并行执行第一个循环(最多N-11个线程)……

第二个循环依赖于以前的结果，所以除非知道更多关于C的知识和结果的准确性，否则不能拆分它。

结果是：

// serial
A[10] = B[10] * 14.3 / A[10];
c0 = 14.3 / A[10];
for (i0=11,i1=11+(N-11)/M,j=1;j<=M;j++,i0=i1,i1=11+j*(N-11)/M)
 // threads 1...M 
 for (int i=i0; i<i1; i++) A[i] = B[i] * c0;
// thread M+1
for (int i=10; i<N; i++) C[i] = C[i-1] + C[i-2];