Первое знакомство с технологией Intel® Cilk™ Plus

В конкурсной задаче Acceler8 2011 требовалось найти подматрицу с наибольшей суммой в матрице, заполненной псевдослучайными значениями. Линейность используемого генератора псевдослучайных чисел позволяла заполнять матрицу параллельно.

В одном из вариантов известного кубического алгоритма в качестве предварительного шага требуется преобразовать матрицу в матрицу столбцов префиксных сумм. Поставим задачу написать эффективный код, который заполнит матрицу и вычислит префиксные суммы столбцов. При этом программа должна использовать как параллелизм на уровне задач (multicore), так и на уровне данных (SIMD векторизация), и сохранять наглядность последовательного алгоритма.

Технология Intel Cilk Plus подкупает именно тем, что обещает решить эти задачи. Например, расширение C/C++ Extensions for Array Notation (CEAN), входящее в состав Cilk Plus, позволяет лаконично сформулировать параллельный алгоритм заполнения массива.
Следующий код выводит таблицу умножения 16x16:


#include <stdio.h>

#include <cstdlib>

#include <cilk/cilk.h>

#include <iostream>


int main(int argc, char* argv[])

{

#define N 16

#define M 16

    int a[M][N];

    cilk_for(int j = 0; j < N; j++) {

        a[0][j] = j + 1;

    }

    cilk_for(int i = 1; i < M; i++) {

        a[i][:] = a[0][:] * (i + 1);

    }

    for(int i = 0; i < M; i++) {

        for(int j = 0; j < N; j++) {

            printf("%4d ", a[i][j]);

        }

        std::cout << std::endl;

    }

}


exmpl1.cpp

Использование Cilk Plus здесь позволило сделать параллелизацию и векторизацию так, что код стал даже короче, чем он был бы на обычном C/C++.

Нужно отметить, что гибкость CEAN-синтаксиса поразительна – легко записываются срезы массивов с произвольным чередованием рядов и/или столбцов. При этом для всех многомерных операций выполняется контроль размерностей операндов, и все операции компилятор обещает по возможности векторизовывать. Если все заявленные возможности действительно работают, то это почти язык APL, встроенный в компилятор.

Если нужно, чтобы массив был динамическим, то просто приводим указатель к типу 'int (*)[N]':

    int (* a)[N]  = (int (*)[N]) _mm_malloc(N * M * sizeof(int), 64);


К сожалению, неожиданная проблема возникает, если размер N не константен. Так, стоит определить N и M как переменные, и компиляция оборвется ошибкой:

exmpl2.cpp(12): error: a variable captured by a lambda cannot have a type involving a variable-length array
a[0][j] = j + 1;
^



Дело в том, что Cilk Plus создает для тела цикла lambda-функцию C++0x, выполнение которой затем рекурсивно разветвляется вызовами cilk_spawn. По-видимому, текущая реализация lambda-функций не позволяет включать в замыкание многомерный массив с переменными размерами измерений.

Чтобы обойти эту проблему, приходится заводить псевдонимы для строк исходного массива и использовать CEAN-синтаксис с явным диапазоном операций:


#include <stdio.h>

#include <cstdlib>

#include <cilk/cilk.h>

#include <iostream>


int main(int argc, char* argv[])

{

    int N = 16;

    int M = 16;

    int * arr  = (int *) _mm_malloc(N * M * sizeof(int), 64);

    cilk_for(int j = 0; j < N; j++) {

        arr[j] = j + 1;

    }

    cilk_for(int i = 1; i < M; i++) {

        int * a = &(arr[i * N]);

        a[0:N] = arr[0:N] * (i + 1);

    }

    int (* a)[N] = (int (*)[N]) arr;

    for(int i = 0; i < M; i++) {

        for(int j = 0; j < N; j++) {

            printf("%4d ", a[i][j]);

        }

        std::cout << std::endl;

    }

    _mm_free(a);

}


exmpl2.cpp

Предположим, что мы хотим заполнить таблицу умножения другим способом, размножив сначала первую строку на всю таблицу, а затем заполнив столбцы значениями префиксных сумм. Тогда код будет таким:


#include <stdio.h>

#include <cstdlib>

#include <cilk/cilk.h>

#include <iostream>


int main(int argc, char* argv[])

{

#define N 16

#define M 16

    int (* a)[N]  = (int (*)[N]) _mm_malloc(N * M * sizeof(int), 64);

    cilk_for(int j = 0; j < N; j++) {

        a[0][j] = j + 1;

    }

    cilk_for(int i = 1; i < M; i++) {

        a[i][:] = a[0][:];

    }

    for(int i = 1; i < M; i++) {

        a[i][:] += a[i - 1][:];

    }

    for(int i = 0; i < M; i++) {

        for(int j = 0; j < N; j++) {

            printf("%4d ", a[i][j]);

        }

        std::cout < std::endl;

    }

    _mm_free(a);

}


exmpl3.cpp

Здесь для простоты снова предполагается, что размер N константен. Если for-цикл в строке 17 заменить на cilk_for, то программа станет некорректной, а компилятор об этом не сообшит. Результат работы программы в общем случае будет непредсказуем, но при M=16 ошибка проявляться не будет – ветвление не вызывается для коротких циклов.

Значит, данный код накопления префиксных сумм векторизован, но не параллелизован. Исправить это можно, разделив матрицу на вертикальные полосы определенного размера. Но тогда, к сожалению, проявляется странная ошибка компилятора CEAN-синтаксиса, которая приводит к неверному результату, поэтому здесь пришлось вернуться к обычному внутреннему циклу:

    int chunks = 2;

    int chunk = N/chunks;   // make sure  N % chunks == 0

    cilk_for(int k = 0; k < chunks; k++) {

        int start = k * chunk;

        int end = (k + 1) * chunk;

        for(int i = 1; i < M; i++) {

            // this brings wrong results:

            // a[i][start:end] += a[i - 1][start:end];


            // although, this works properly:

            for(int j = start; j < end; j++) {

                a[i][j] += a[i - 1][j];

            }

        }

    }


exmpl4.cpp

(Использованная версия компилятора: icpc (ICC) 12.1.0 20110811.) Данная ошибка компилятора не связана с cilk_for конструкцией, а при большом (динамическом) массиве данных программа начинает вести себя непредсказуемо.

Возвращаясь к исходной задаче, отмечаем, что в ней есть три этапа:

    1. вычисление среднего значения псевдослучайных чисел,

    1. заполнение матрицы,

    1. вычисление префиксных сумм.




Для вычисления среднего нужно воспользоваться преобразователем (reducer), который позволяет корректно складывать промежуточные суммы, избегая конфликтов доступа к общей переменной (race condition), см. исходный код программы, fill.cpp.

Алгоритм для остальных двух этапов не отличается от уже разобранных выше. В тексте программы также применяется специальный преобразователь для вычисления псевдослучайного числа в произвольной позиции. Этот преобразователь использует ассоциативность преобразования линейного конгруэнтного генератора и позволяет понизить сложность адресации n-го псевдослучайного числа до O(log(log(n)) (если заранее приготовлена логарифмическая шкала степеней преобразования). Код этого преобразователя был получен минимальной адаптацией примера linear-recurrence.cpp, входящего в состав компилятора Intel.

Подводя итоги, можно отметить замеченные преимущества и недостатки технологии Cilk Plus.

Pros:

    • простота перехода от последовательного кода к параллельному

    • гибкий и эффективный механизм адресации массивов (CEAN)

    • гибкий механизм divide-and-conquer, дополненный механизмом преобразователей (reducers)

    • эффективность планирования задач и балансировка нагрузки (work-stealing)





Cons:


    • трудности в работе с массивами переменного размера

    • инструмент еще очень молодой и, возможно, недостаточно стабильный для ответственных приложений

    • отсутствие статической проверки корректности параллелизации




Очевидно, что замеченные ошибки скоро будут исправлены.
Кроме того, поскольку Cilk Plus поддерживается на уровне компиляции, есть надежда, что можно ожидать значительный прогресс как в верификации корректности программы, так и в улучшении качества кодогенерации.

Tags:
Nähere Informationen zur Compiler-Optimierung finden Sie in unserem Optimierungshinweis.