Первая страница
Наша команда
Контакты
О нас

    Головна сторінка



Дослідження швидкості виконання паралельних алгоритмів сортування реалізованих засобами Intel tbb

Дослідження швидкості виконання паралельних алгоритмів сортування реалізованих засобами Intel tbb




Дата конвертації10.03.2017
Розмір68.1 Kb.

УДК 681.3, 004.051

Волих Р.В.

Національний університет «Львівська політехніка»,

кафедра електронних обчислювальних машин


Дослідження швидкості виконання паралельних алгоритмів сортування реалізованих засобами Intel TBB
© Волих Р.В.
Електро́нна обчи́слювальна маши́на (скорочено ЕОМ) - загальна назва для обчислювальних машин, що є електронними (починаючи з перших лампових машин, включаючи напівпровідникові тощо) на відміну від електромеханічних (на електричних реле тощо) та механічних обчислювальних машин.
, 2015

В даній статті розглянуто дослідження швидкостей виконання паралельних алгоритмів сортування реалізованих за допомогою засобів Intel TBB. Приведено часові витрати на виконання сортування у вигляді таблиці, а також схему алгоритму сортування.
Ключові слова: потоковий граф алгоритму, intel tbb, паралелізм, сортування.
Studies speed of parallel sorting algorithms implemented by means Intel TBB

© Volyh R.V., 2015
Sort operation is most common operation in every application. All real-time programs require fast execution, that why sort operation programmers trying to make parallel, to use most CPU power efficiently. In this work was explored sort operation execution time implemented with Intel TBB.
Keywords: flow graph algorithm, intel tbb, parallelism, sort.
Вступ. Метою технологій паралелізму – є забезпечування умови, що дозволяє комп’ютерним програмам виконувати великий об’єм роботи за той самий інтервал часу[1]. Тому проектування програм повинно орієнтуватись не на виконання одної задачі в деяких проміжках часу, а на одночасне виконання декількох задач, на які попередньо повинна бути розбита програма. Часто буває, що складну послідовність команд можна спростити, організувавши її у вигляді невеликих операцій, що виконуються паралельно.

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

Математи́чне програмува́ння - це прикладна математична дисципліна, яка досліджує екстремум функції (задачі пошуку максимуму або мінімуму) і розробляє методи їх розв'язання. Такі задачі ще називають оптимізаційними.
Штучний інтелект Шту́чний інтеле́кт (англ. Artificial intelligence, AI) - розділ комп'ютерної лінгвістики та інформатики, що займається формалізацією проблем та завдань, які нагадують завдання, виконувані людиною.
Екосисте́ма - це сукупність живих організмів, які пристосувалися до спільного проживання в певному середовищі існування, утворюючи з ним єдине ціле.
Ко́смос (від грец. κόσμος - «порядок») - одне з ключових понять давньогрецької історії та культури. Вживалося на позначення встановленого Богом (богами, Божеством) Всесвітнього Ладу, Порядку - на противагу Хаосу - Всесвітньому Безладу.

Не зважаючи на сфери програмування, майже будь-яка система використовує операцію сортування. Тому дану операцію намагаються реалізувати паралельно на різних технологія паралельного програмування [4]. Одною з таких технологій є Intel Threading Building Block (Intel TBB) [5]. Засоби Intel TBB дозволяють окрім використання шаблону паралельного сортування tbb::parallel_sort, реалізувати власні паралельні алгоритми сортування.

Алгоритм сортування Алгоритм сортування - це алгоритм, що розв'язує задачу сортування, тобто здійснює впорядкування лінійного списку (масиву) елементів.
Інтерфейс flow graph, технології Intel TBB, дозволяє реалізувати будь-які алгоритми в концепції теорії графів, що буде зручно для побудови паралельного сортування [6].
Теорія графів Теорія графів - розділ математики, що вивчає властивості графів. Наочно граф можна уявити як геометричну конфігурацію, яка складається з точок (вершини) сполучених лініями (ребрами). У строгому визначенні графом називається така пара множин G = (V, E), де V є підмножина будь-якої зліченної множини, а E - підмножина V × V.

Стан проблеми. Зростання частоти було основною причиною підвищення продуктивності комп'ютерів з 1980-тих до 2004. Час роботи програми дорівнює числу інструкцій, помноженому на середній час потрібний на виконання інструкції. Тому збільшення частоти зменшує час виконання всіх програм, у яких основним ресурсом виступає процесорний час. Після 2004 основні виробники процесорів, такі, як Intel і AMD – визнали, що більш пріоритетним шляхом підвищення продуктивності комп’ютерів полягає у збільшенні числа ядер процесорів. Це також пов’язано з тим, що більшість сучасних ОС є мультизадачними, а збільшення кількості ядер в комп’ютерах дає змогу користувачам запускати кілька процесів без втрати продуктивності. В той же час послідовні програми можуть виконуватись без втрати продуктивності [7].

Також популярності набули високопродуктивні обчислення, що вирішують задачі моделювання в медичній, біологічній та інших сферах і здійснюються як правило на суперкомп’ютерах. Окрім цього з’явилось поняття GPGPU, що під собою скриває обчислення на графічних прискорювачах . Все це призводить до глобального прискорення програмних додатків з використанням паралелізму. Отже виходячи з цього основною задачею лишається розпаралелення програм, що часто є досить складною проблемою [8,9].

У більшості програм присутня операція сортування, що інколи виконується над великим масивом даних, тим самим витрачаючи багато часу. З настанням «ери паралельного програмування» розроблено різноманітні алгоритми сортування з використанням технологій паралельного програмування.
Постановка задачі. Дослідити швидкості виконання паралельних алгоритмів сортування реалізованих засобами Intel TBB, привести та описати схеми алгоритмів виконання та отриманих результатів.
Розв’язання задачі. Технологія Intel TBB містить кілька готових паралельних алгоритмів, одним з яких є алгоритм паралельного сортування tbb::parallel_sort, окрім цього в ній присутній інтерфейс flow graph [10], на якому реалізовано сортування, алгоритм якого зображено на рис.1.

Рис. 1. Алгоритм сортування, що реалізований на flow graph

Алгоритм на flow graph реалізований за допомогою розробленої програми, що дозволяє реалізувати алгоритми представлені ПГА. Вузли і зв’язки між ними (ребра) прописані наступним чином:

make_edge(output_port<1>(node1), input_port<0>(join1));

make_edge(output_port<0>(node2), input_port<1>(join1));

make_edge(join1, node4);

Функція make_edge використовується для створення зв’язків між вихідним і вхідними портами вузлів. Для того, щоб вузол очікував наявності кількох значень для обробки, використовується проміжні вузли, що в flow graph називаються join_node. По наведеному прикладу коду вузли node1, node2 та node3 є функціональними вузлами (functional_node), що виконують операцію порівняння і перестановки.

ПГА у програмі генерації вихідного коду на flow graph зберігається в колекції наступного типу:

class CM{

pair left; //Вузол і його вихідний порт, що є лівим входом поточного вузла

pair right; //Вузол і його вихідний порт, що є правим входом поточного вузла

int stage; //Номер яруса на якому знаходиться поточний вузол

int fo; //Номер операція, яку повинен виконувати вузол

};

Номер поточного вузла СМ відповідає його індексу в колекції 1.



Шаблонна функція tbb::parallel_sort використовує unstable алгоритм сортування, тобто однакові значення можуть бути поміняні місцями. Сортування є детерміністичним (здійснюється перевірка посеред виконання алгоритму, чи дані є відсортовані, якщо так то завершується виконання алгоритму). Виконання сортування над однією і тією ж послідовністю даних буде здійснюватися за один і той самий час.

В табл. 1 приведено часові затрати на виконання операції сортування за допомогою засобів Intel TBB, а саме tbb::parallel_sort та flow graph.

Таблиця 1

Час виконання сортування за допомогою Intel TBB






Кількість вхідних даних, час [мкс]




16

32

64

128

256

512

1024

parallel_sort

21

34

47

60

77

205

318

flow graph

43

101

156

604

1037

9865

38505

Замірювання часу проводилось на чотирьох ядерному процесорі в віртуальній машині з 1 ГБайтом оперативної пам’яті, що працювала під ОС Linux Mint.
Віртуальна машина - модель обчислювальної машини, створеної шляхом віртуалізації обчислювальних ресурсів: процесора, оперативної пам'яті, пристроїв зберігання та вводу і виводу інформації.

По отриманих значеннях добре видно, що спеціалізований алгоритм сортування, виконується куди швидше ніж отриманий універсальним засобом відображення ПГА за допомогою flow graph. Однією з причин цього являється великий розмір програми, що використовує відображення ПГА на Intel TBB. Це заставляє весь час міняти сторінки пам’яті програми, тим самим затрачаючи додаткові витрати часу.



Висновки. Результат виконання алгоритмів сортування за допомогою технології Intel TBB продемонстрував перевагу в швидкодії спеціалізованого засобу на відміну від універсального реалізованого з flow graph. Причинами програшу являється обсяг пам’яті згенерованого flow graph додатку, а також відсутність детермінованості алгоритму сортування, оскільки генерація коду з ПГА відбувається з відсутністю знань, що саме виконує програма. Дане дослідження дозволило побачити слабкі місця програми відображення ПГА за допомогою Intel TBB flow graph, та відокремити напрямки подальшої роботи над нею.
Література


  1. Arndt Bode. Advanced Parallel Processing Technologies: “Guangzhou, China”, 2007. - 765 p.

  2. Edie Rasmussen. Parallel Processing: “The Gale Group Inc”, 2002. - 5 p.

  3. Norm Matlof. Programming on Parallel Machines: “University of California”, 2012. – 410 p.

  4. Michael McCool. Structured Parallel Programming: Patterns for Efficient Computation: “Morgan Kaufmann”, 2012. - 432 p.

  5. Сысоев А.В., Мееров И.Б., Сиднев А.А. Средства разработки параллельных программ для систем с общей памятью. Библиотека Intel Threading Building Blocks: “ННГУ”, 2007. – 86 c.
    Intel Threading Building Blocks (також відома як TBB) - кросплатформна бібліотека шаблонів С++, розроблена компанією Intel для паралельного програмування. Бібліотека містить алгоритми і структури даних, що дозволяють програмісту уникнути багатьох складнощів, що виникають при використанні традиційних реалізацій нитей, таких як POSIX Threads, Windows threads або Boost Threads, в яких створюються окремі ниті виконання, що синхронізуються і зупиняються вручну. Бібліотека TBB абстрагує доступ до окремих нитей. Всі операції трактуються як «задачі», які динамічно розподіляються між ядрами процесора. Крім того, досягається ефективне використання кешу. Програма, написана з використанням TBB, створює, синхронізує і руйнує графи залежностей завдань відповідно до алгоритму. Потім завдання виконуються відповідно до залежностей. Цей підхід дозволяє програмувати паралельні алгоритми на високому рівні, абстрагуючись від деталей архітектури конкретної машини.


  6. James Reinders. Intel Threading Building Blocks. Outfitting C for Multi-core Processor Parallelism: “O'Reilly Media”, 2007. – 336 p.

  7. В.П. Гергель, Р.Г. Стронгин. Основы параллельных вычислений для многопроцессорных вычислительных систем: “ННГУ”, 2003. – 184 с.

  8. David H. Eberly. GPGPU Programming for Games and Science: “A K Peters/CRC Press”, 2014. – 469 p.

  9. Ade Miller. Book: C AMP. Accelerated Massive Parallelism with Microsoft Visual Studio C : “Microsoft Press”, 2012. – 358 p.

  10. James Jeffers,James Reinders. Intel Xeon Phi Coprocessor High-Performance Programming: “Morgan Kaufmann”, 2013. – 432 p.

Каталог: sntk -> doc -> spr
spr -> Львівська політехніка
spr -> Львівська політехніка
doc -> Обробка цифрових підписів з використанням хмарних обчислень гнатків Н. О., 2015
doc -> Львівська політехніка
doc -> Львівська політехніка
doc -> Львівська політехніка
spr -> Програмно-апаратне забезпечення тестової само-балансуючої одноосьової робототехнічної колісної платформи
spr -> Програмний сервіс розпізнавання емоцій обличчя людини на основі методу головних компонент
spr -> Програмна система прогнозування потреби в ресурсах для малого підприємства
spr -> Система криптографічного захисту bluetooth зв’язку між пристроєм інтернету речей та мобільним обчислювальним пристроєм



  • Ключові слова: потоковий граф алгоритму, intel tbb, паралелізм, сортування. Studies speed of parallel sorting algorithms implemented by means Intel TBB
  • Keywords: flow graph algorithm, intel tbb, parallelism, sort. Вступ .
  • Intel Threading Building Blocks