Методи та засоби ефективної обробки паралельних задач в комп’ютерних кластерних системах (стр. 4 )

–  у Національному технічному університеті України "Київський політехнічний інститут" в Українсько-корейському центрі інформаційних технологій при НТУУ "КПІ" (використовуються при проведенні тренінгів з підвищення кваліфікації інженерів) та кафедрах обчислювальної техніки, автоматизованих систем обробки інформації і управління, програмного забезпечення комп’ютерних систем (використовуються при проведенні лекційних і лабораторних занять, при курсовому і дипломному проектуванні).

Зазначені впровадження підтверджені відповідними актами.

Особистий внесок здобувача

Всі основні результати дисертації отримані здобувачем самостійно. У роботах, що опубліковані у співавторстві, здобувачеві належать: [3, 10, 11, 22, 27, 28, 31, 33-35, 37-40] – методи підвищення ефективності обміну даними між процесорами в системах з локальною пам’яттю; [5, 13, 16, 19] – методи балансування навантаження в динамічному режимі за рахунок використання дерева підзадач, що було отримано на попередніх етапах обчислень; [7, 12, 14, 18, 20, 23, 30, 32, 36] – ідея та методика попередньої оцінки інформаційної структури задачі; [21, 25, 26] – загальна концепція організації додаткового рівня абстракції для підвищення ступеню завантаження системи та скорочення загального часу виконання паралельних програм; [15, 24, 29] – загальна концепція підвищення ефективності обчислювальних систем за рахунок використання інтерактивної системної статистики, щодо паралельних процесів.

Апробація результатів дисертації

Матеріали дисертації доповідались та обговорювались на наступних симпозіумах, конференціях та семінарах.

1. The 17th EUGridPMA - Building Trust for Authentication in e-Science, September 14-16, 2009, Berlin, Germany.

2. XI Міжнародна науково-технічна конференція "Системний аналіз та інформаційні технології" (26-30 травня 2009, Київ, Україна).

3. Workshop: Establishment ICT Centers, August 17-20, 2009, Seoul, Republic of Korea.

4. Ювілейна міжнародна науково-практична конференція "Розподілені комп’ютерні системи", що присвячена 50-річчю створення першої на Україні кафедри обчислювальної техніки. (6-8 квітня 2010, Київ, Україна).

5. Друга наукова конференція присвячена 20-річчю факультету прикладної математики "Прикладна математика та комп’ютинг ПМК 2010" (14-16 квітня 2010 р., Київ, Україна).

6. XII Міжнародна науково-технічна конференція "Системний аналіз та інформаційні технології" (26-29 травня 2010 р., Київ, Україна).

7. Workshop: Establishment ICT Centers, August 2-5, 2010, Seoul, Republic of Korea.

8. 12-ї Міжнародна науково-технічна конференція "Автоматизация: проблемы, идеи, решения" (6-10 сентября 2010 р., Севастополь, Україна).

9. The 21st EUGridPMA - Building Trust for Authentication in e-Science. January 24-26, 2011, Utrecht, Netherlands.

10. XXIV Международная научная конференция "Математические методы в технике и технологиях ММТТ-24" (21-24 апреля 2011, Саратов, Россия);

11. XI международная научная конференция им. ИАИ-2011 (17-20 мая 2011, Киев, Україна).

12. V Міжнародна науково-технічна конференції "Сучасні проблеми радіоелектроніки, телекомунікації та приладобудування" (19-21 травня 2011 р., Вінниця, Україна).

13. Міжнародна науково-технічна конференція SAIT 2011 (23-28 травня 2011 р., Київ, Україна).

14. The 23nd EUGridPMA - Building Trust for Authentication in e-Science. September 12-14, 2011, Marrakesh, Morocco.

15. The 6th IEEE International Conference on Intelligent Data Acquisition and Advanced Computing Systems: Technology and Applications (September 15-17 2011, Prague, Czech Republic).

16. The 1st International conference on High Performance Computing, (October 12-14, 2011, Kyiv, Ukraine).

17. The 25th EUGridPMA - Building Trust for Authentication in e-Science. May 7-9, 2012, Karlsruhe, Germany.

18. The 9th OWL: Experiences and Directions Workshop (OWLED 2012), May 27-28, 2012, Heraklion, Crete.

29. The 26th EUGridPMA - Building Trust for Authentication in e-Science. September 10-12, 2012, Lyon, France.

20. The 2nd International conference on High Performance Computing (October 8-10, 2012, Kyiv, Ukraine).

21. 28th EUGridPMA - Building Trust for Authentication in e-Science. May 13-15, 2013, Kyiv, Ukraine;

22. PICTURE and INARMERA-ICT Joint Workshop on Components, Computing Systems and Networks (CSIT 2013), 25-th September, 2013, Yerevan, Armenia;

23. The 3d International conference on High Performance Computing (October 7-11, 2013, Kyiv, Ukraine).

24. The 21th International Workshop on Multimedia Signal Processing & Transmission (February 5, 2014, Jeonju, South Korea).

25. 6th International Workshop on Science Gateways, IWSG-2014 (3-5 June, 2014, Dublin, Ireland).

26. Eastern Europe-Luxembourg Workshop on Cloud Computing Communications, Security and Services (CLOUDCOMS) (October 8-10, 2014, Luxembourg).

Публікації

За темою дисертації опубліковано 40 наукових робіт, у тому числі 1 монографія, 22 статті у науково-технічних фахових виданнях, з них 1 – в іноземному виданні та 18 – у виданнях України, що входять до наукометричних баз даних, та 17 тез доповідей в збірниках матеріалів конференцій. Результати, що опубліковано охоплюють усі положення, які виносяться на захист.

Структура й обсяг дисертації

Дисертаційна робота складається зі вступу, шести глав, виводів і 2 додатків. Загальний обсяг роботи становить 320 сторінок друкованого тексту, 85 рисунків, 9 таблиць, і список використаної літератури з 147 найменувань.

РОЗДІЛ 1

АНАЛІЗ ІСНУЮЧИХ РІШЕНЬ

1.1.  Загальний огляд підходів до організації обчислень в сучасних паралельних комп’ютерних системах

Однією з особливостей сучасних технологій побудови паралельних ЕОМ є використання багатьох рівнів паралелізму. [1] Найвищий рівень (може бути відсутній) – об’єднання декількох окремих ЕОМ в кластер. Кожна ЕОМ працює під управлінням своєї ОС, а кластерне проміжне програмне забезпечення дозволяє користувачу використовувати ресурси багатьох ЕОМ для розв’язання однієї задачі. Наступний рівень – поєднання кількох різних обчислювальних пристроїв в ЕОМ. На сьогоднішній день це звичайно один чи більше процесорних чипів, відеоадаптер, що здатний виконувати обчислення загального призначення (англ. GPGPU), та прискорювач обчислень типу Intel Xeon Phi. На наступному рівні кожен із згаданих пристроїв можна розділити на окремі обчислювальні пристрої, що працюють паралельно. Так, в одному процесорному чині може бути кілька ядер, в відеоадаптері – багато так званих «мультипроцесорів», в прискорювачах обчислень – багато ядер. В кожному з ядер звичайно присутній не тільки скалярний, а й векторний арифметико-логічний пристрій, але крім того, саме ядро здатне виконувати декілька незалежних команд на 1 такт (суперскалярність).

Майже всі сучасні процесори включають векторні арифметико-логічні пристрої. [2] Векторні АЛП сучасних процесорів відповідають класу SIMD в таксономії Фліна. [3] Використання векторних команд дозволяє значно зменшити час виконання однопоточних програм (до 4 разів при обробці чисел з плаваючою комою одинарної точності на сучасних процесорах Intel). [4] Але, нажаль, написання оптимізованого векторного коду на асемблері або з використанням вбудованих підпрограм компілятора є схильним до помилок та надмірно багатослівним – навіть найпростіші алгоритми виражаються складним для розуміння, довгим програмним кодом.

Безпосереднє використання векторних команд в програмному коді призводить до необхідності врахування таких особливостей як:

– вирівнювання вхідних даних. Деякі векторні команди можуть виконувати зчитування та запис в пам’ять тільки за вирівняними адресами.

Для даних деякого типу T природно вирівняною називається адреса, числове значення якої ділиться па розмір значення типу T в байтах без остачі.

Вихідні дані – дані цілих типів, типів з плаваючою комою одинарної та подвійної точності – вирівняні відносно своїх типів. Але векторні команди інтерпретують ці дані як вектори, що містять кілька елементів вихідних даних (наприклад, векторний тип, що являє собою вісім 32-бітних цілих чисел). Якщо інтерпретувати вихідні дані як векторні, то в залежності від конкретного розміщення даних в пам’яті, дані можуть бути, а можуть і не бути вирівняні як векторні. Якщо дані не вирівняні як векторні, то і напряму застосовувати векторні команди неможливо. Необхідно спочатку пропустити невирівняний блок, обробивши його скалярними командами.

– псевдоніми вхідних даних у вихідних даних (англ. data aliasing). Якщо алгоритм обробляє декілька масивів даних (наприклад, в операції SAXPY операції першого рівня BLAS [5], Y = αX + Y, вхідними є скаляр а, вектор X; вектор Y є вхідним та вихідним), то для використання векторних команд необхідно, щоб серед вихідних даних були відсутні псевдоніми вхідних. Під псевдонімами розуміється перетин областей пам’яті, в яких зберігаються дані.

Звичайно, складність написання векторного коду була виявлена і раніше, і основним підходом усунення цієї складності стала розробка компіляторів, що векторизують код в автоматичному режимі. Однак, як показують сучасні дослідження та експерименти [4] компілятори векторизують лише 50% - 70% циклів, що можуть бути векторизовані вручну. Причому це число показує просто частину циклів, до яких компілятор зміг застосувати векторизацію. Частка циклів, для яких така трансформація зменшила час виконання, є меншою, ніж 50%, а середні коефіцієнти прискорення склали близько 1,7, що далеко від максимально можливого значення 4.

Продуктивність обчислень паралельних ЕОМ може бути збільшена двома способами:

– покращення мікроархітектури окремих обчислювальних ядер;

– збільшення кількості обчислювальних ядер.

Спочатку розглянемо перший спосіб та покажемо його обмеженість.

Останнім часом однією з проблем стало досягнення фундаментальних фізичних обмежень напівпровідникової технології. Зокрема, фізичні обмеження створюють проблеми тепловиділення та синхронізації даних. [6, 7] Ці проблеми в першу чергу пов’язані з максимальною швидкістю передачі сигналів через неідеальні лінії з ненульовою ємністю. Перезарядження цієї паразитної ємності і є основна причина тепловиділення в напівпровідникових інтегральних схемах, а час перезаряду – причина затримок передачі даних, більших, ніж в ідеальному випадку (коли єдиним обмеженням є швидкість світла). Мінімально можливий час передачі даних звичайно зумовлює максимально можливу тактову частоту мікропроцесора. Таким чином, можна зробити висновок, що необмежене зростання продуктивності за рахунок збільшення тактової частоти та інженерних рішень, продуктивність яких залежить від частоти, неможливе.