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

Question

Я пытаюсь распараллелить итерационную версию алгоритма Карацубы, используя 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]);
        }
    }
}

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

Answer 1

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

Как расширение 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;