1. Послідовна реалізація алгоритму множення матриць Спробуємо розробити власну реалізацію алгоритму...
2. Вплив порядку циклів на швидкість обчислень

Послідовна реалізація алгоритму множення матриць

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

Базова реалізація алгоритму множення матриць

Реалізуємо алгоритм множення згідно з визначенням.

//single.cpp #include "mult.h" void mult (ELEMENT_TYPE * A, ELEMENT_TYPE * B, ELEMENT_TYPE * C, int n) {ELEMENT_TYPE s; int i, j, k; for (j = 0; j <n; j ++) for (i = 0; i <n; i ++) C [j * n + i] = 0; for (i = 0 i <n; i ++) for (j = 0; j <n; j ++) for (k = 0; k <n; k ++) C [j * n + i] + = A [j * n + k] * B [k * n + i]; }

Вкажемо в рядку компіляції файл з реалізацією алгоритму:

icpc -mmic -mkl = parallel -openmp ./single.cpp ./main.cpp ./routine.cpp -osingle

Скомпілюємо і запустимо додаток.

на Мал. 10.2 представлений результат роботи програми.

Отже, ми бачимо ( таблиця 10.4 ), Що при N = 1024 час роботи становить близько 57с. При цьому час роботи аналогічної (більш складної) функції в бібліотеці MKL становить близько 0,1 с. Для визначеності зробимо запуск для N = 1025. Зауважимо, що час роботи нашої програми істотно скоротилося, в той час як час роботи функції з MKL залишилося колишнім. Містика чи об'єктивна реальність?

Таблиця 10.4. Порівняння часу множення матриць (Intel MKL) з наївною реалізацією (час в секундах). N Наївна реалізація MKL sequential MKL parallel 1024 57,34 0,207 0,004 1025 33,09 0,200 0,004

Спробуємо відповісти на поставлене запитання. Той факт, що час роботи першої наївною реалізації сильно відрізняється від "еталона", не є сюрпризом. Розробники високопродуктивних бібліотек добре знають свою справу. А ось істотне скорочення часу при збільшенні розміру на одиницю - більш ніж дивний факт. Причина може бути знайдена за допомогою Профілювальники, який виявить, що при розмірі матриці N = 1024 ми звертаємося в пам'ять з таким кроком, що потрібні нам дані повинні бути завантажені в одну і ту ж кеш-лінію. В результаті кеш-пам'ять використовується вкрай неефективно: при наступній операції з даними ми змушені витіснити кеш-лінійку, яку недавно завантажували і планували використовувати далі, тоді як значна частина інших кеш-лінійок не використовується. При розмірі матриці N = тисяча двадцять п'ять цього не відбувається. Слухачам пропонується скласти фрагмент карти звернень в пам'ять з урахуванням того, що кеш є 8-асоціативним, розмір кеш-лінії становить 64 байта, розмір кеш-пам'яті становить 32KB. Дана карта допоможе зрозуміти розглянутий вище ефект, а також стане в нагоді для подальшого вивчення питання ефективного використання кеш-пам'яті.

Вплив порядку циклів на швидкість обчислень

Подивившись уважно на карту звернень в пам'ять, складену раніше, можна помітити, що ми звертаємося в пам'ять не в тому порядку, в якому зберігаємо дані ( Мал. 10.3 ). Спробуємо змінити порядок циклів і досліджуємо питання про те, як це впливає на час роботи програми.

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

В таблиці 10.5 представлені часи обчислень:

Таблиця 10.5. Порівняння часу обчислень при різному порядку циклів на Intel Xeon Phi (N = 1024, час у секундах). Ijk Ikj Kij Kij jki jik MKL seq. 57,34 117,5 116,81 2,149 12,084 56,904 0,207
Мал. 10.3. Час виконання алгоритму в залежності від порядку циклів (час в секундах)

Чому часи так сильно відрізняються?

Одна з головних причин низької продуктивності при "неправильному порядку" циклів - погано організована робота з пам'яттю. Сучасні процесори чутливі до того, в якому порядку відбувається читання і запис в пам'ять. Чутливість пов'язана зі складною архітектурою організації пам'яті, як процесорів, так і сопроцессоров [6]. Якщо читання і запис відбувається послідовно, то процесор може це передбачити і заздалегідь завантажити дані в кеш-пам'ять. Доступ до кеш-пам'яті набагато швидше доступу до оперативної пам'яті. Крім того, дані в кеш-пам'ять завантажуються не поелементно, а відразу групами (розмір кеш-лінійки рівний 64 КБ.). Якщо з кеш-лінії використовувати тільки один елемент, то багато даних буде завантажено в процесор і не використано в обчисленнях. Звернемо увагу на те, що звернення до елементів матриць A і B таке, що багато елементів читаються і використовуються в кеш-пам'яті (при великих розмірах матриць) один раз.

У реалізації алгоритму множення матриць з розділу 4.1 (порядок циклів ijk відповідає визначенню), обхід матриці відбувається, як показано на Мал. 10.4 .

Мал.10.4.

Обхід матриць в реалізації множення за визначенням

З огляду на, що матриці зберігаються безперервним вектором, обхід матриць B і С не оптимальний (хоч і має регулярний характер). Значну роль в зниження продуктивності грає обхід матриці B. Елементи матриці B використовуються раз, а матриці С - раз.

При оптимальному порядку циклів jki обхід матриць показаний на Мал. 10.5 . Доступ до елементів став послідовним. Як наслідок, підвищилася продуктивність.

Мал.10.5.

Обхід матриць з порядком циклів jki.

на Мал. 10.6 представлений результат обчислень при найкращому циклів.

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