company_banner

Поговорим про Intel® Cilk™ 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 Cilk Plus, являющаяся частью С++ компилятора Intel. Почему Plus, спросите вы? Да потому что фактически только половина в Intel Cilk 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”!
    Intel
    Компания

    Комментарии 22

      +4
      Вот объясните на кой чёрт вот это уродское ® и (tm) писать?
        +5
        Это требование юристов, никуда от этого не деться.
          –2
          А зачем юристы этого требуют?
            +8
            Ну это риторический вопрос. Они же получают за что-то зарплату. А если серьёзно, то есть набор правил (внутренних), которых нужно придерживаться при публикации с использованием брэнда Intel, и различных торговых марок. Cilk одна их них.
              0
              AFAIK по российскому законодательству написание ©, ® и (tm) не обязательно, твои права защищены в любом случае. Я неправ?
                +4
                Вероятно, всё правильно. Но ещё раз — есть набор внутренних правил и норм, которым мы должны следовать, являясь сотрудниками Intel.
                  +3
                  Т.е. вы не можете пойти к юристам и сказать «вы знаете, аудитория Хабра чрезвычайно раздражается от всего этого визуального мусора, давайте не будем в статье на Хабр гадить всеми этими ©, ® и (tm), раз уж с юридической точки зрения это ни на что не влияет»?
                    +4
                    Всё несколько сложнее. В международной компании учитываются нормы не только Российского права. И если у нас в стране указывать данные знаки возможно не обязательно, то в других очень даже. И потом, я не думаю, что это уж так сильно раздражает. А если на кого-то и имеет такое влияние, так это тоже неплохо, по крайней мере, пост запомнится, ведь любая эмоция — это хорошо. Плохо когда её нет.
          +4
          Я могу попробовать ответить. Любая торговая марка после её регистрации принадлежит компании только при условии, что эта компания отстаивает своё право на эксклюзивное использование вот именно этой комбинации слов. Если же слово/фраза становится нарицательным, или им начинают обозначать нечто большее, чем было изначально задумано, и не ассоциируют с правообладателем, то в суде исключительное право на использование как торговой марки после этого уже не отстоять.
          Такое случалось в истории. Такие слова, как «капрон», «героин» и т.д. Я был очень удивлён, узнав совсем недавно, что «термос» — это тоже торговая марка! Обратный пример: компания Google отказала Оксфордскому словарю во включении глагола «to google» в словарь по тем же самым причинам.
          По этой причине сотрудников любой компании обязуют в публичных коммуникациях обозначать торговые марки во этими дурацкими символами. Потому что если уж даже члены компании не защищают торговую марку, и есть документальные подтверждения в виде постов на форумах, то в суде при случае отстоять ничего не получится.
            –1
            А к российской практике это всё какое отношение имеет?
              0
              Да. Закон «О товарных знаках, знаках обслуживания и наименованиях мест происхождения товаров» статья 6, пункт 1:
              1. Не допускается регистрация в качестве товарных знаков обозначений, не обладающих различительной способностью или состоящих только из элементов:

              вошедших во всеобщее употребление для обозначения товаров определенного вида;

              являющихся общепринятыми символами и терминами;


              Ссылка
                0
                Ну и статья на Википедии, которая цитирует этот закон России.
                  –1
                  Здесь речь идёт только о регистрации знака — ничего не сказано, что зарегистрированный знак, ставший общепринятым термином, перестаёт быть товарным знаком.
                  +1
                  Вы же понимаете, что Хабр не только в России читают?
                    –4
                    Да блин. Хабр, что с тобой не так? Какого черта все ринулись защищать это мерзейшее замусоривание языка бессмыленными маркетинговыми значками?
              0
              Plus будет?:)
                0
                В смысле будет ли + от его использования или будет ли описание про ту Plus'овую часть?
                +5
                Мне кажется, что надо упомянуть ещё одну нечасто вспоминаемую, но, как мне кажется, критически важную особенность параллельных программ, написанных на Cilk и на Cilk Plus. Это — возможность детерминистичного (повторяемого от запуска к запуску) исполнения. Для последовательных программ это свойство почти естественно, тогда как немногие парадигмы параллельного программирования гарантируют это. Я думаю, не нужно объяснять ценность повторяемости исполнения при отладке.
                Более того, для программ на Cilk определена «сериальная элизия» (serial elision) — результат работы параллельной программы эквивалентен одному из исполнений её последовательного «близнеца», в котором такие директивы, как spawn, cilk_for заменены на вызов функции и обыкновенный for.

                Вы скажете: «А как же программы, которые используют генератор (псевдо)случайных чисел?». Для этого случая для Cilk реализован быстрый параллельный детерминированный генератор псевдослучайных чисел (прочтите внимательно все определения, чтобы впечатлиться). Статья, описывающая, как это работает, за авторством Чарльза Лейзерсона (один из авторов «Introduction to Algorithms»): Deterministic Parallel Random-Number
                Generation for Dynamic-Multithreading Platforms
                  +1
                  Григорий, отличный комментарий. Действительно, этого свойства почти нет у современных моделей параллельного программирования, у Силка же оно имеется исторически, с первых реализаций.
                  0
                  Все, все делают свой task-based concurrency. Я вот всё жду, когда такие вещи начнут появляться в примитивах операционных систем, столько же велосипедов уже написано.

                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                Самое читаемое