Cilk

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Cilk
Парадигма імперативне програмування, Паралельні обчислення, процедурне програмування і структурне програмування
Дата появи 1994
Розробник Чарлз Ерік Лейзерсон
Система типізації статична, слабка типізація[d] і manifest typingd
Під впливом від C
Вебсайт cilkplus.org

Cilk, Cilk++ і Cilk Plus є  мовами програмування загального призначення розроблені для багатопотокових паралельних обчислень. Вони засновані на мовах C і C++, які вони розширюють конструкціями для створення паралельних потоків та fork–join методологією.

Спочатку мова була розроблена в 1990-і роки в Массачусетському технологічному інституті (MIT) в групі Чарльза Лейзерсона. Пізніше Cilk була розширена в Cilk ++ компанією Cilk Arts. Ця компанія згодом була придбана компанією Intel, що дозволило збільшити сумісність з існуючим C і C ++ кодом.

Історія[ред. | ред. код]

MIT Cilk[ред. | ред. код]

Мова програмування Cilk утворилася внаслідок об'єднання трьох окремих проектів МІТ: [1]

  • Теоретична робота з планування багатопотокових програм.
  • StarTech - паралельна шахова програма побудована для запуску на Thinking Machines Corporation's Connection Machine моделі CM-5
  • PCM/Threaded-C – оснований на С пакет для планування continuation-passing потоків на СМ-5

У квітні 1994 року ці три проекти були об'єднані в "Cilk". Перший компілятор Cilk-1  був випущений у вересні 1994 року.

Оригінальний Cilk мову був заснований на ANSI C, з додаванням до Cilk спеціальних ключових слів, для можливості здійснювати паралельність програм.

Cilk був реалізований як транслятор на C, орієнтований на GNU C Compiler (GCC). Остання версія, Cilk 5.4.6, доступна в MIT в лабораторії комп'ютерних наук та штучного інтелекту (CSAIL), але більше не підтримується.[2]

Cilk Arts та Cilk++[ред. | ред. код]

До 2006, ринок Cilk був обмежений для високопродуктивних обчислень. Поява багатоядерних процесорів в звичайних обчислювальних системах та продажі сотні мільйонів нових паралельних комп'ютерів, які поставляються з кожним роком все більше і більше, наштовхнула Cilk Arts створити і вивести на ринок сучасну версію Cilk, яка підтримуватиме комерційні потреби програмістів нового покоління. В жовтні 2007 року компанія закрила фінансування компіляторів серії А, і випустила новий продукт — Cilk ++ 1.0, який почав поставлятися в грудні 2008 року.

Cilk ++ відрізняється від Cilk декількома рішеннями: підтримка C ++, підтримка циклів, і hyperobjects — нової конструкції, призначеної для вирішення проблеми в паралельному доступі  до глобальних змінних. Cilk ++ був пропрієтарним програмним забезпеченням. Як і його попередник, він був реалізований як компілятор Cilk-to-C ++. Вона підтримує компілятори Microsoft і GNU.

Intel Cilk Plus[ред. | ред. код]

31 липня 2009, Cilk Arts оголосила на своєму вебсайті, що її продукти і технічна команда в даний час входять до складу Intel Corp. Intel і Cilk Arts об'єднали свої передові технології, що в подальшому призвело до виходу Intel Cilk Plus у вересні 2010 року. Cilk Plus отримує значні спрощення в конструкціях, запропонованих Cilk Arts в Cilk ++, щоб усунути необхідність в декількох вихідних ключових словах Cilk, додаючи можливість spawn функції  мати справу зі змінними, які беруть участь в операціях по скороченню. Cilk Plus відрізняється від Cilk і Cilk ++ додаванням масиву розширень, які включаються в комерційний компілятор (від Intel), а також сумісністю з існуючими відладчиками.[3]

Відмінності між версіями[ред. | ред. код]

У початковій реалізації MIT Cilk, ключовим словом, яке визначало функцію написану на Cilk було слово cilk. В цій версії Cilk-процедури можуть безпосередньо викликати C-процедури, але C-процедури не можуть викликати або створювати процедури Cilk. Тому дане ключове слово було необхідне, щоб відрізнити Cilk код від коду C. Cilk Plus знімає ці обмеження, так що функції С і С ++ можуть викликатися в Cilk Plus коді і навпаки.

Функції мови[ред. | ред. код]

Принципом конструкції мови Cilk є те, що програміст повинен сам визначити паралельні блоки програми, які можуть безпечно виконуватися паралельно; при цьому вони повинні бути позначені в середовищі виконання, зокрема,в планувальнику, який вирішує, під час виконання, як розділити роботу між процесорами. Саме тому, що обов'язки розділені між процесорами, програма на Cilk може працювати без перезапису на будь-якій кількість процесорів, в тому числі і на одному

Завдання паралелізму: spawn and sync[ред. | ред. код]

Головним доповненням до Cilk C є два ключових слова, які в сукупності дозволяють писати паралельні програми

  • spawn дозволяє безпечно викликати і запускати функції в паралельному потоці.
  • Ключове слово sync вказує на те, що поточна функція не може виконуватись поки не завершаться всі функції, які були викликані раніше.

(В Cilk Plus, ключові слова описуються як _Cilk_spawn і _Cilk_sync або cilk_spawn і cilk_sync, якщо включені заголовки Cilk Plus)

Нижче наведено код рекурсивної реалізації функції Фібоначчі в Cilk, з паралельним викликом рекурсивних функцій, що демонструє використання ключових слів, spawn та sync. 

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 Arts та Cilk++[ред. | ред. код]

До 2006, ринок Cilk був обмежений для високопродуктивних обчислень. Поява багатоядерних процесорів в звичайних обчислювальних системах та продажі сотні мільйонів нових паралельних комп'ютерів, які поставляються з кожним роком все більше і більше, наштовхнула Cilk Arts створити і вивести на ринок сучасну версію Cilk, яка підтримуватиме комерційні потреби програмістів нового покоління. В жовтні 2007 року компанія закрила фінансування компіляторів серії А, і випустила новий продукт — Cilk ++ 1.0, який почав поставлятися в грудні 2008 року.

У початковій реалізації MIT Cilk, ключовим словом, яке визначало функцію написану на Cilk було слово cilk. В цій версії Cilk-процедури можуть безпосередньо викликати C-процедури, але C-процедури не можуть викликати або створювати процедури Cilk. Тому дане ключове слово було необхідне, щоб відрізнити Cilk код від коду C. Cilk Plus знімає ці обмеження, так що функції С і С ++ можуть викликатися в Cilk Plus коді і навпаки.

Паралельні цикли[ред. | ред. код]

В Cilk ++ були додані додаткові конструкції, однією із них є паралельний цикл, який позначається cilk_for в Cilk Plus.

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;
    }
}

Цей алгоритму реалізує паралельний цикл, який має таке трактування: тіло циклу, в даному випадку, викликає деяку функцію F, яка отримує як параметр деяке значення з масиву а, виконується для кожного значення і від нуля до n в невизначеному порядку. Специфікація Cilk не визначає точну поведінку конструкції, типова реалізація виконується за принципом "розділяй і володарюй". 

Редуктори та гіпероб'єкти[ред. | ред. код]

(В Cilk Plus, ключові слова описуються як _Cilk_spawn і _Cilk_sync або cilk_spawn і cilk_sync, якщо включені заголовки Cilk Plus)

Найбільш поширеним типом hyperobject є редуктор, що відповідає пункту відновлення в OpenMP або алгебраїчному поняттю моноїд. Кожен редуктор має одиничний елемент і асоціативну операцію, яка поєднує в собі два значення. Архетипний редуктор є підсумовувачем чисел: одиничний елемент визначається, як рівний нулю, а асоціативна функція обчислює суму. Цей редуктор вбудований в Cilk ++ і Cilk Plus:

// Compute ∑ foo(i) for i from 0 to N, in parallel.
cilk::reducer_opadd<float> result(0);
cilk_for (int i = 0; i < N; i++)
    result += foo(i);

Масиви значень[ред. | ред. код]

Intel Cilk Plus додає позначення для вираження високорівневих операцій над цілими масивами або секціями масивів

 // y ← α x + y
 void axpy(int n, float alpha, const float *x, float *y)
 {
     for (int i = 0; i < n; i++) {
         y[i] += alpha * x[i];
     }
 }

В Cilk Plus може бути виражено, як: 

y[0:n] += alpha * x[0:n];

Це позначення допомагає компіляторові ефективно векторизувати додатки. Intel Cilk Plus дозволяє використовувати С/C++ операції до кількох елементів масиву паралельно, а також надає набір вбудованих функцій, які можуть бути використані для виконання векторизованих зрушень, обернень і скорочень. Подібна функціональність існує в Fortran 90; Cilk Plus відрізняється тим, що він ніколи не виділяє тимчасові масиви, тому використання пам'яті легше передбачити.

Елементарні функції[ред. | ред. код]

В Cilk Plus елементарними функціями є регулярні функції, які можна викликати або зі скалярними аргументами або із елементами масиву паралельно. Вони аналогічні функціям в OpenCL.

#pragma simd[ред. | ред. код]

Прагма дає дозвіл компіляторові векторизувати цикл навіть у тих випадках, коли автоматична векторизація може призвести до збою. Це найпростіший спосіб вручну застосувати векторизацію.

Дивитись також[ред. | ред. код]

Література[ред. | ред. код]

  1. ↑ "A Brief History of Cilk. Архів оригіналу за 26 червня 2015. Процитовано 11 листопада 2016.
  2. ↑ "The Cilk Project" [Архівовано 22 листопада 2016 у Wayback Machine.].
  3. ↑ "Intel Cilk Plus: A quick, easy and reliable way to improve threaded performance" [Архівовано 22 липня 2012 у Wayback Machine.], Intel.

Посилання[ред. | ред. код]

Отримано з https://uk.wikipedia.org/w/index.php?title=Cilk&oldid=38966756