Итерационный алгоритм Карацубы, распараллеленный и векторизованный с использованием OpenACC на C ++

Я пытаюсь распараллелить итеративную версию алгоритма Карацубы с помощью OpenACC на C ++. Я хотел бы спросить, как я могу векторизовать внутренний for loop. Мой компилятор показывает это сообщение об этом цикле:

526, Complex loop carried dependence of result-> prevents parallelization
     Loop carried dependence of result-> prevents parallelization
     Loop carried backward dependence of result-> prevents vectorization

а вот код двух вложенных циклов:

#pragma acc kernels num_gangs(1024) num_workers(32) copy (result[0:2*size-1]) copyin(A[0:size],$
{
    #pragma acc loop gang 
    for (TYPE position = 1; position < 2 * (size - 1); position++) {
        // for even coefficient add Di/2
        if (position % 2 == 0)
            result[position] += D[position / 2];

        TYPE start = (position >= size) ? (position % size ) + 1  : 0;
        TYPE end = (position + 1) / 2;

        // inner loop: sum (Dst) - sum (Ds + Dt) where s+t=i
        #pragma acc loop worker 
        for(TYPE inner = start; inner < end; inner++){
            result[position] += (A[inner] + A[position - inner]) * (B[inner] + B[position - inn$
            result[position] -= (D[inner] + D[position - inner]);
        }
    }
}

Собственно, я не уверен, можно ли его векторизовать. Но если это так, я не могу понять, что делаю не так. Спасибо


c++ parallel-processing vectorization openacc karatsuba
person Community    schedule 13.04.2018    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Проблема «Сложный цикл несет зависимость результата» возникает из-за наложения указателей. Компилятор не может определить, перекрывается ли объект, на который указывает "результат", с одним из других объектов указателя.

В качестве расширения C ++ вы можете добавить ключевое слово C99 restrict к объявлению ваших массивов. Это подтвердит компилятору, что указатели не имеют псевдонимов.

В качестве альтернативы вы можете добавить «независимое» предложение OpenACC в свои директивы цикла, чтобы сообщить компилятору, что циклы не имеют никаких зависимостей.

Обратите внимание, что OpenACC не поддерживает сокращение массива, поэтому вы не сможете распараллелить «внутренний» цикл, если не измените код для использования скаляра. Что-то типа:

rtmp = result[position];
#pragma acc loop vector reduction(+:rtmp) 
    for(TYPE inner = start; inner < end; inner++){
        rtmp += (A[inner] + A[position - inner]) * (B[inner] + B[position - inn$
        rtmp -= (D[inner] + D[position - inner]);
    }
result[position] = rtmp;
person Mat Colgrove    schedule 16.04.2018