Анотація: Мета даної лабораторної роботи - розгляд питань оптимізації роботи з пам'яттю при розробці програм для Intel Xeon Phi.
Вступ
Презентацію до лабораторної роботи Ви можете завантажити тут .
З одного боку, програмування для Intel Xeon Phi за своєю суттю мало чим відрізняється від програмування для традиційних центральних процесорів. Як і раніше, ми повинні ефективно використовувати векторні набори команд (парадигма SIMD, паралелізм за даними), забезпечувати по можливості рівномірне завантаження потоків (паралелізм на рівні ядер), ефективно працювати з пам'яттю (облік багаторівневої схеми організації пам'яті).
Методи досягнення мети також є певною мірою стандартними. Так, для векторизації обчислень ми можемо використовувати високопродуктивні бібліотеки, можливості оптимізують компіляторів, допомагаючи їм спеціальними опціями і директивами, застосовувати технологію Intel Cilk Plus, при необхідності реалізовувати деякі частини програми з використанням інтрінсіков або асемблерних вставок. При цьому більш широкі регістри, наявність FMA, розширені операції для роботи з пам'яттю і деякі інші особливості векторних розширень в системі команд Xeon Phi здатні значно прискорити розрахунки. Для досягнення паралелізму на рівні ядер ми можемо використовувати добре знайомі технології (MPI, OpenMP, Intel Cilk Plus і ін.). При цьому вибір відповідного поєднання числа процесів і потоків може чинити істотний вплив на підсумкову продуктивність програми. Базові методи оптимізації роботи з пам'яттю також є досить стандартними. Так, ми повинні дбати про ефективне використання кеш-пам'яті, намагатися уникати перевантаження шини даних, а також мінімізувати обміни з оперативною пам'яттю хоста. В цілому, оптимізація на традиційних процесорах Intel часто призводить до скорочення часу роботи на Xeon Phi і навпаки. Тим не менш, це не одне і те ж. У лекціях і лабораторних роботах даного курсу на прикладах демонструється, як змінюється час роботи на хості і на співпроцесор в результаті застосування різних технік оптимізації.
Основна ідея цієї роботи полягає у вивченні базових принципів застосування перерахованих вище способів підвищення продуктивності на прикладі відомої, широко поширеною в додатках і добре дослідженою в літературі завдання - множенні щільних матриць. На відміну від попередніх лабораторних робіт, детально вивчають різні техніки оптимізації розрахунків, основна увага приділяється питанням оптимізації роботи з пам'яттю.
Методичні вказівки
Цілі і завдання роботи
Мета даної лабораторної роботи - розгляд питань оптимізації роботи з пам'яттю при розробці програм для Intel Xeon Phi. Основна увага приділяється базовим методам підвищення ефективності використання кеш-пам'яті. Як приклад використовується завдання множення квадратних щільних матриць. Вважається, що всі дані, які беруть участь в розрахунках, цілком містяться в оперативну пам'ять.
Дана мета передбачає вирішення таких основних завдань:
- Використання бібліотеки Intel MKL для вирішення завдання множення матриць на хості і на співпроцесор.
- Послідовна реалізація алгоритму множення матриць за визначенням.
- Вивчення питання про продуктивність базової версії, розгляд способів скорочення часу обчислень з використанням векторизації, вибір відповідного порядку звернення до даних.
- Реалізація послідовної і паралельної версій блочного алгоритму для множення матриць.
структура роботи
Розглядається задача множення щільних матриць. Для порівняння результатів обчислень і часу роботи реалізується множення щільних матриць з використанням високопродуктивної бібліотеки Intel MKL. Наводиться наївна реалізація алгоритму множення матриць. Розглядаються питання впливу порядку циклів на час обчислень на співпроцесор Intel Xeon Phi. Вивчається вплив вирівнювання і підказок компілятору на векторизацію обчислень. Реалізується кілька редакцій блочного алгоритму множення матриць. Формулюються завдання для самостійного опрацювання.
Тестова інфраструктура
Для проведення експериментів використовувалися обчислювальні ресурси МСЦ РАН (МВС-10П) [ 12.3 ]. Тестова інфраструктура представлена в таблиці 10.1 .
Таблиця 10.1. Тестова інфраструктура Процесор 2 процесора на вузол Xeon E5-2690 (2.9 GHz, 8 ядер) Пам'ять 64 GB Сопроцессор Intel Xeon Phi 7110X Операційна система Linux CentOS 6.2 Компілятор, профілювальник, відладчик Intel C / C ++ Compiler 14
Завдання множення щільних матриць
Нехай дано дві матриці A і B розмірності 
. За визначенням результатом множення двох матриць є матриця C розмірності , Де кожен елемент матриці обчислюється за формулою:
Цей алгоритм передбачає виконання 
операцій множення і 
операцій додавання елементів вихідних матриць 
операцій.
Відомі послідовні алгоритми множення матриць, що володіють меншою обчислювальною складністю. Зокрема, до таких алгоритмів відноситься алгоритм Штрассена. В даному алгоритмі Кожна восьма множення замінюється складаннями, що призводить до оцінки складності 
. Ще меншою оцінкою складності володіє алгоритм Копперсміта-Винограду 
. Даний алгоритм був поліпшений в 2010 році Вірджинією Вільямс. Складність алгоритму склала 
. Ряд дослідників вважають, що дану оцінку можна істотно поліпшити. Бажаючі ознайомитися з теоретичними аспектами даної проблеми можуть, наприклад, вивчити огляд алгоритмів в дисертації Вірджинії Вільямс ( http://theory.stanford.edu/~virgi/thesis.pdf ) І ряд публікацій, вільно доступних з її персональної сторінки ( http://theory.stanford.edu/~virgi ).
Незважаючи на існування досконаліших алгоритмів з точки зору асимптотики, на практиці їх застосовують рідко. Як правило, в оцінці складності присутня велика константа. Як наслідок, алгоритми мають кращу продуктивністю тільки при дуже великих розмірах матриць, що не поміщаються в оперативну пам'ять сучасних комп'ютерів.
В рамках лабораторної роботи для демонстрації підходів до реалізації і подальшої оптимізації алгоритму множення матриць на співпроцесор Intel Xeon Phi будемо використовувати алгоритм, що отримується з визначення. Будемо вважати, що матриці зберігають дані з плаваючою комою в одинарної точності.
