Cilk

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 21:35, 8 июня 2016.
Cilk
Спроектировано Лаборатория информатики MIT (Massachusetts Institute of Technology)
Печать дисциплины статическая
Портал: http://www.cilk.com
Главная реализация
Cilk, Cilk++, Intel Cilk Plus

Cilk — (произносится [ cɪlk ]) язык программирования, специально разработанный для создания многопоточных приложений и параллельных вычислений.

Язык разрабатывался с 1994 года в Лаборатории Информатики MIT. Cilk основывается на языке ANSI C, с добавлением небольшого количества ключевых слов. Позже язык был расширен на C++ в виде диалекта Cilk++ — коммерческого продукта, разрабатываемого компанией Cilk Arts. В 2009 году компания Cilk Arts стала частью корпорации Intel, которая продолжила развитие языка.

На сегодняшний день наиболее распространённым диалектом Cilk является Intel Cilk Plus.

Уровни параллелизма

  • Распараллеливание на уровне задач. Часто распараллеливание на этом уровне является самым простым и при этом довольно эффективным. Такое распараллеливание возможно в тех случаях, когда решаемая задача естественным образом состоит из независимых подзадач, каждую из которых можно решить отдельно.
  • Распараллеливание на уровне данных. Параллелизм заключается в применении одной и той же операции к множеству элементов данных. Данный вид параллелизма широко используется при решении задач численного моделирования.
  • Уровень распараллеливания алгоритмов. Сюда можно отнести алгоритмы параллельной сортировки, умножение матриц, решение системы линейных уравнений. Задача реализации параллельных алгоритмов достаточно сложна, поэтому существует достаточно большое количество библиотек параллельных алгоритмов для различных языков, позволяющих строить программы, не вдаваясь в устройство реализаций параллельной обработки данных.
  • Параллелизм на уровне инструкций. Наиболее низкий уровень параллелизма, осуществляемый на уровне параллельного выполнения процессором нескольких инструкций. На этом же уровне находится пакетная обработка нескольких элементов данных одной командой процессора (технологии MMX, SSE, SSE2 и т.д.)

Язык Cilk поддерживает параллелизм на уровне задач (task parallelism) и на уровне данных (data parallelism). Это позволяет наиболее эффективно распараллеливать алгоритмы типа "разделяй и властвуй", а также операции над рекурсивными структурами данных, такими как списки и деревья.

Параллелизм в Cilk

Основная концепция языка заключается в том, что программист должен сосредоточиться на структурировании программы таким образом, чтобы "выявлять" параллелизм. Задача же непосредственно планирования выполнения возлагается на систему выполнения Cilk для эффективной работы на данной платформе. Таким образом, система выполнения берёт на себя работу по распределению нагрузки, балансировке и т.п. Благодаря такому разделению, программы на Cilk могут работать на системах с различным количеством процессоров, в том числе и на однопроцессорных. Система выполнения гарантирует эффективность и предсказуемую производительность.

Отличительной особенностью языка является то, что расширения (новые ключевые слова Cilk, которые отсутствуют в чистом Си) слабо меняют программу - так, если их удалить из исходного кода, то получится корректная программа на Си, называемая serial elision (или C elision) от полной Cilk-программы.

Cilk использует три ключевых слова для организация параллелизма:

  • cilk - используется для обозначения Cilk-процедур (фактически, параллельных версий функций C);
  • spawn - создаёт новую задачу (task), вызывая Cilk-процедуру, которая может исполняться параллельно;
  • sync - ожидает завершения ранее созданных задач и продолжает работу.

Важно заметить, что используя ключевое слово spawn, программист именно создаёт задачу, а не пишет код, который будет выполняться в отдельно созданном потоке. Это позволяет менеджеру задач Cilk производить балансировку - если в имеющемся пуле потоков один поток сильно нагружен, а второй простаивает, то менеджер может перераспределить нагрузку и отдать часть задач первого потока второму.

Пример программы на Cilk

Рассмотрим пример программы на Cilk, вычисляющей значение N-го числа Фибоначчи.

cilk int fib(int n)
{
    if (n < 2)
        return n;
    else
    {
        int x, y;
        x = spawn fib(n-1);
        y = spawn fib(n-2);
        sync;
        return (x+y);
    }
}

cilk int main(int argc, char *argv[])
{
    int n, result;
    n = atoi( argv[1] );
    result = spawn fib(n);
    sync;
    printf("Result: %d\n", result);
    return 0;
}

Большая часть Cilk-процедур выполняется последовательно, как и в Си. Параллелизм достигается за счёт использования ключевого слова spawn при вызове Cilk-процедур. spawn можно считать параллельным аналогом стандартного вызова функций в Си. Однако если в Си выполнение родительской функции останавливается и управление передаётся вызванной функции, то в Cilk в случае создания новой задачи родительская процедура может продолжать выполняться параллельно с дочерней.

Cilk-процедура не должна использовать значения, возвращаемые дочерними процедурами, пока не будет выполнен оператор sync. Если на момент вызова этого оператора хотя бы одна дочерняя процедура продолжает выполняться, родительская процедура приостанавливает своё выполнение и не продолжает его до тех пор, пока все задачи не завершатся. После этого, процедура продолжает своё выполнение.

sync служит своего рода барьером, но локальным, а не глобальным, как в параллельных системах, основанных на сообщениях. В Cilk sync ждёт завершения лишь тех задач, которые были созданы в текущей процедуре, а не всех выполняющихся в данный момент. В примере с вычислением чисел Фибоначчи, выполнение sync необходимо перед return x+y, поскольку в противном случае значения x и y могут быть посчитаны не до конца.

Таким образом, при работе с Cilk программист использует ключевые слова spawn и sync для выделения параллелизма в программе, а система выполнения Cilk берёт на себя задачу эффективного выполнения. Программа на Cilk минимально отличается от программы на чистом Си. Если убрать ключевые слова, то из параллельного варианта программы получится последовательный.

При компиляции программ, Cilk неявно добавляет ключевое sync перед каждым return. Таким образом, процедура никогда не завершится, пока выполняется хотя бы одна из созданных ею задач. Главная процедура должна называться main (так же как и в Си) и должна быть определена с использованием ключевого слова cilk. В отличие от Си, Cilk требует, чтобы main возвращала значение типа int.

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

cilk float foo(void);
cilk void bar(void)
{
    int x;
    x = spawn foo();
    sync;
}

Вместо этого необходимо присвоить значение переменной типа float, а затем уже его преобразовать в int.

Взаимодействие Cilk и C

Несмотря на то, что при компиляции программы Cilk транслируются в код на Си, существует несколько ограничений касательно того, как эти два языка могут взаимодействовать друг с другом. Так, Cilk-процедура может вызывать функции, написанные на Си, но те не могут в свою очередь обращаться к Cilk-процедурам или создавать (spawn) основанные на них задачи. При этом из функций Си можно обращаться к специальным автоматически генерируемым функциям-заглушкам, которые в свою очередь могут создавать задачи.

К примеру, пусть из написанной на Си функции f требуется обратиться к Cilk-процедуре p, которая принимает и возвращает тип double. Для этого f предварительно необходимо создать объект контекста CilkContext, обратившись к функции Cilk_init из стандартной библиотеки Cilk. Далее функция должна будет обратиться уже не к p а к EXPORT(p). После завершения выполнения заглушки объект контекста может быть освобождён с помощью функции Cilk_terminate. Для работы с этими функциями необходимо подключить заголовочный файл cilk.h. При создании объекта контекста Cilk операционная система выделяет программе необходимые ресурсы (потоки), поэтому эффективнее будет повторно использовать уже созданный контекст, чем освобождать его и создавать новый.

Функция Cilk_init принимает два аргумента: int *argc, char *argv[] (в отличие от заголовка функции main, количество аргументов передаётся по указателю). Таким образом, функция f может контролировать поведение системы выполнения Cilk точно так же, как и с помощью аргументов командной строки.

Далее приводится исходный код описанной программы.

#include <cilk.h>
cilk double p(double x)
{
    return x * 0.1
}
void f()
{
    double y;
    CilkContext* context;    context = Cilk_init(&amp;argc, argv);
    y = EXPORT(p)(context, 3.14);
    Cilk_terminate(context);
}
cilk int main (int argc, char *argv[])
{
    f();
    return 0;
}

Использование разделяемой памяти и блокировок

Cilk предоставляет возможности работы с разделяемой памятью путём простого обращения процедур к глобальным переменным, или путём передачи в процедуры указателей:

cilk void bar(int *px)
{
    *px = *px+1
    printf("%d", *px);
    return;
}
cilk int foo(void)
{
    int x = 0;
    printf("%d", x)
    spawn bar(&amp;x);
    sync;
    printf("%d", x)
    return (y);
}

Тем не менее, в случаях, когда несколько процедур работают с одной областью памяти (читают и записывают данные), могут возникать состояния гонки. Cilk предоставляет три способа решения этой проблемы.

Первый способ - использование функции Cilk_fence(), которая гарантирует, что все операции записи или чтения памяти будут завершены, до того как будет выполнена следующая инструкция. Тем не менее, данный способ далеко не всегда оказывается полезным.

Второй способ - использование блокировок, которые позволяют создавать атомарные блоки кода. Для этого используются функции Cilk_lock (захватывает блок; если тот уже захвачен - ожидает освобождения) и Cilk_unlock (освобождает блок), работающие с переменными типа Cilk_lockvar. Эти переменные предварительно должны быть инициализированы с помощью Cilk_lock_init:

#include <cilk-lib.h>
...
Cilk_lockvar mylock;
Cilk_lock_init(mylock);
...
{
    Cilk_lock(mylock); /* begin critical section */
    /* do something */
    Cilk_unlock(mylock); /* end critical section */
}

Третий способ - использование ключевого слова inlet. Оно позволяет задать в пределах Cilk-процедуры функцию, способную атомарно изменять значение локальных переменных этой процедуры. В теле inlet-функции допускается использовать ключевое слово abort, которое сигнализирует о возможности прервать задачи, запущенные ранее из родительской процедуры. Далее приводится пример функции, рекурсивно вычисляющей произведение элементов массива, и завершающей выполнение, если в какой-то момент произведение становится равным нулю.

cilk int product(int *array, int size)
{
    int prod = 1;
    inlet void mult(int x)
    {
        prod *= x;
        if (prod == 0)
            abort;
    }    if (size == 1)
        return array[0];    int s2 = size/2;
    mult( spawn product(array, s2) );
    if ( prod == 0 )
        return 0;
    mult( spawn product(a+s2, size-s2) );
    sync;
    return prod;
}

Intel Cilk Plus

Intel Cilk Plus - современный диалект языка Cilk, разрабатываемый корпорацией Intel и основывающийся на диалекте Cilk++, который, в свою очередь, является расширением Cilk на C++. Основные отличия Cilk Plus от Cilk заключаются в следующем:

  • убраны ключевые слова cilk, inlet, abort; ключевые слова spawn и sync заменены на cilk_spawn и cilk_sync;
  • помимо обычных функций, cilk_spawn может работать с методами объектов, функторами (объектами с перегруженным operator ()) и лямбда-выражениями (С++11)
  • добавлена возможность параллельного выполнения итераций циклов с использованием ключевого слова cilk_for (в условии завершения цикла можно использовать только операторы < > <= >= != == , в блоке инкрементации допустимы только ++ -- += -=);
  • можно указывать, какое максимальное количество итераций цикла может выполнять одна нить (strand) выполнения Cilk с помощью #pragma cilk grainsize = количество
  • добавлена нотация для использования инструкций векторной обработки массивов (SIMD processing) и обработки фрагментов массива с помощью массив[начало:длина:шаг];
  • добавлена возможность использования потокобезопасных переменных на базе шаблонов: reducers. Стандартный набор типов таких переменных поддерживает арифметические операции, поиск максимума и минимума, работу со списками и т.д. допускается создание пользовательских типов на основе cilk::monoid_base и cilk::reducer.
#include <cilk/cilk.h>
#include <cilk/reducer_opadd.h>

unsigned int compute(unsigned int i)
{
    return i;
}

int main(int argc, char* argv[])
{
    unsigned long long int n = 1000000;
    cilk::reducer_opadd<unsigned long long int> total(0);    cilk_for (unsigned int i = 1; i <= n; ++i)
        total += compute(i);    std::cout << "Total " << total.get_value() << std::endl;
    return 0;
}

Ссылки