Преобразуйте цикл для распараллеливания

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];