Поговорим про Intel® Clik™ Plus

Мой недавний пост про OpenMP 4.0 натолкнул меня на мысль, что было бы неплохо написать и про Intel® Cilk™ Plus, потому что модель программирования весьма интересная и уж точно заслуживает отдельного внимания. Ну и раз её часть стала фактически новым стандартом OpenMP, то, вероятно, были на то веские причины.

Начну с истории возникновения самого названия.
Итак, как же всё начиналось. С 1994 года в MIT разрабатывали язык Cilk, позволявший легко реализовывать параллелизм по задачам. Причем он являлся расширением для языка C, потому что, удалив из исходников все ключевые слова Cilk, он превращался в совершенно корректный и легко собираемый «сишным» компилятором код. Естественно, со временем появилась и коммерческая версия Cilk’а, которую назвали Cilk++. Она в свою очередь поддерживала уже и С++, а так же была совместима с компиляторами gcc и Microsoft, причем разработкой занималась уже коммерческая организация Cilk Arts, Inc. Вот тут то и подкрался Intel, выкупив Cilk Arts, технологию Cilk++ торговую марку Cilk. Примечательно, что сам я начал работать в Intel с 2008 года, и помню все этапы развития Cilk’а в нашем компиляторе. Так вот, вскоре, а именно в 2010 году, вышла первая коммерческая версия под названием Intel® Clik™ Plus, являющаяся частью С++ компилятора Intel. Почему Plus, спросите вы? Да потому что фактически только половина в Intel® Clik™ Plus от той технологии Cilk++, позволявшей вводить параллелизм по задачам. Вторая же половина – это та часть, которая даёт возможность реализовывать параллелизм по данным и помогает векторизовать код. Схематично выглядит это примерно так:

Теперь вам известны «тайны» такого длинного названия, и потайной смысл Plus’a – это та часть, которая отвечает за векторизацию. Понятно, постарались маркетологи и объединили две разные технологии под «одну крышу». Кстати, именно векторная часть перекочевала в новый OpenMP, и именно про неё я уже частично рассказывал в предыдущем своём посте.
Здесь же расскажу больше именно про сам Cilk. Кстати, вопрос весьма риторический, какая часть важнее и значимее для разработчика. Если мы хотим получить максимальную производительность, то нам необходимо использовать все типы параллелизма, так что всё крайне полезно. Из личного опыта, часть по векторизации использую чаще и с большей выгодой. Конечно это не связано с тем, что tasking Cilk’а плох, просто я чаще встречаюсь с использованием OpenMP для распараллеливания по задачам. Хотя «Силковская» реализация хороша.

Идея проста – минимальное количество новых ключевых слов, в количестве 3 штуки, с максимальной отдачей: cilk_spawn, cilk_sync и cilk_for. Внутри – современный, лёгкий и эффективный планировщик задач, осуществляющий захват работы для балансировки нагрузки. Но, обо всё по порядку.

Если посмотреть на скелет какой-либо функции, в которой вызывается другая функция g() и выполняется работа work (абстрактно говоря), то выглядит она в последовательной версии примерно так:

void f() {   g();   work    work         }  void g() {   work   work } 

Теперь, мы «легким движением руки» превратим код в параллельный:

void f() {   cilk_spawn g();   work   work   cilk_sync;   work } 

Что же здесь происходит? Мы создаём задачу (task’у) для возможного параллельного выполнения функции g(), и той работы, которая осталась в функции f() до строчки cilk_sync (в терминах Cilk’a – continuation). Немного терминологии:

Важно, что мы не создаём поток (thread) и не говорим какой код выполнять в каком потоке. Вся работа основана на задачах, что позволяет эффективно распределять нагрузку и гарантировать параллелизм. Как? Очень просто.
У нас имеется пул потоков, допустим для простого примера, что потока всего 2. И у каждого есть очередь задач, которые должны быть выполнены. В случае если имеется дисбаланс, то есть один поток занят работой, а у другого её нет, то происходит захват задач из очереди другого потока.
Причем в нашем примере будет происходить захват continuation области. Примерно вот так:

Таким образом, мы гарантируем, что все ядра будут загружены работой. Кстати, такой же планировщик реализован и в Intel® Threading Building Blocks (TBB). cilk_sync же является точкой синхронизации.

Конструкция cilk_for предназначена, как говорит «Капитан Очевидность», для введения параллелизма в циклах for. Зачем нужна отдельная конструкция? Я не буду давать прямого ответа, но дам наводящий пример. Чем отличаются два данных цикла?

for (int x = 0; x < n; ++x) { cilk_spawn f(x); } cilk_for (int x = 0; x < n; ++x) { f(x); } 

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

Очевидно, что spawn нужно делать не на каждой итерации, а скажем, только один раз, а все остальные итерации пусть воспринимаются как continuation. Думаю, ответ на вопрос о необходимости cilk_for теперь отпадает.

Собственно, почти всё. Осталось решить вопрос с общим доступом к памяти. Нам придётся заботиться об этом самим, с помощью reducer’ов. Общие данные создаются с использованием шаблонов из Cilk’a, гарантируя тем самым безопасную работу с ними.

Продолжим наш простой пример:

int sum=3; void f() {   cilk_spawn g();   work    sum += 2;   work }  void g() {   work   sum++;   work }  

Понятно, что возникает «нехорошая» ситуация с общей переменной sum. Для её решения, нам необходимо объявить её так:

cilk::reducer_opadd<int> sum(3); 

Причём можно писать и свои reducer’ы, наследуясь от классов cilk::monoid_base и cilk::reducer. Это, кстати, стало возможным и в последней версии OpenMP.
Надеюсь что я рассказал достаточно для понимания того, что есть в Intel® Cilk™ Plus. Собственно, там есть почти всё — и параллелизм по задачам через ключевые слова Cilk’a, и параллелизм по данным с использованием директив и нового синтаксиса (про это я пока умышленно не рассказывал). Как видите, технология мощная и даёт большой потенциал для того, чтобы использовать все типы параллелизма в вашем приложении. Дерзайте, и “May the Force be with you”!