Сучасні інформаційні технології/Обчислювальна техніка і програмування

Гопанюк О. В.

Мясіщев О. А.

Хмельницький національний університет, Україна

Дослідження ефективного використання багатоядерних процесорів для вирішення деяких задач лінійної алгебри

В наш час одно процесорні системи послідовних програм не мають перспективи для виконання високо програмованих обчислень, що пов’язано з неможливістю відводу тепла для високих частот, обмеженням передачі даних швидкості світла. В зв’язку з цим перспективи напрямку мають паралельні системи. Розглянемо паралельні системи на базі багатоядерних процесорів. На сьогоднішній день існує багато задач, де доцільно застосовувати розпаралелювання по ядрах: завдання перенесення тепла, розрахунку на міцність, задач теорії пластичності, пружності, де широко використовується метод кінцевих елементів. Також в різних галузях застосовуються матричні обчислення, при математичному моделюванні різних процесів і явищ. З врахуванням ефективного виконання матричних розрахунків багато стандартних бібліотек програм містять процедури для матричних операцій та оптимізації їх роботи [1].

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

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

Оцінку продуктивності комп'ютера будемо робити в Мегафлопсах (1 MFLOPS - мільйон операцій з плаваючою точкою за одну секунду). Розділимо число операцій на час, помножений на 1000000, формула 1.

     (1)

За обчислювальну систему приймемо комп’ютер на базі 6-ти ядерного процесора AMD Phenom™ II; Soket AM3; Частота процессора 3.2 ГГц; L3 кеш: 6 Мб; L2 кеш: 512 Кб. Операційну систему оберемо 10.04.2-desktop-amd64, компілятор – Fortran 77. Компіляція програми здійснюється за допомогою скрипта mpif77, виконання – скрипта mpirun:

mpif77 –O3 radw6.f –o radw6

mpirun –np 6 –machininefile machines radw6

Тут radw6.f – початковий текст програми, radw6 – виконуваний модуль, опція –O3 повідомляє компілятор про необхідність оптимізації коду, параметр –np – задає кількість ядер, на яких обчислюватиметься програма.

В досліджуваннях використовуватиметься компіляція програм без оптимізації коду та з ключем  –O3 для оптимізації [2].

1.                 Розглянемо результати перемноження матриць за допомогою технології MPI. Результати розрахунків наведені в таблицях 1.1, 1.2.

Таблиця 1.1 - Результати розрахунків з ключем –О3, одинарна точність

Розмір матриці

Одне ядро

Чотири ядра

Прискорення

Шість ядер

Прискорення

500

0,2/1247

0.1/2345

2

0.089/2793

2.25

1000

1,19/1675

0.5/4003

2.38

0.4/4905

2.98

2000

10,61/1506

3.54/4513

2.997

2.97/5380

3.57

3000

35,78/1508

11.98/45.06

3.986

9.61/5612

3.72

Таблиця 1.2 - Результати розрахунків  без ключа –О3 одинарна точність

Розмір матриці

Одне ядро

Чотири ядра

Прискорення

Шість ядер

Прискорення

500

0.8/311

0.23/1075

3.48

0.16/1494

5

1000

5.14/388

1.48/1341

3.47

1.01/1959

5.09

2000

42.32/377

11.66/1371

3.63

7.88/2029

5.37

3000

139.71/386

39.06/1381

3.58

26.25/2056

5.32

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

Розглянемо результати перемноження тих же матриць, але чисел подвійної точності. Результати розрахунків наведені в таблицях 1.3, 1.4.

Таблиця 1.3 - Результати розрахунків  з ключом –О3 подвійна точність

Розмір матриці

Одне ядро

Два ядра

Приск.

Чотири ядра

Приск.

Шість ядер

Приск.

500

0,18/1387

0.09/2703

2

0,08/3078

2,25

0,11/2260

1,64

1000

1,79/1113

1.1/1806

1.63

0,79/2512

2,27

0,71/2807

2,52

2000

13,42/1191

8.62/1853

1.56

6,14/2603

2,19

5,36/2982

2,50

3000

46,37/1164

29.03/1860

1.6

20,44/2640

2,27

17,81/3029

2,60

Таблиця 1.4 - Результати розрахунків  без ключа –О3 подвійна точність

Розмір матриці

Одне ядро

Два ядра

Приск.

Чотири ядра

Прис.

Шість ядер

Приск.

500

0.73/337

0.38/654

1.92

0.24/1016

3.042

0,18/1364

4.06

1000

6.02/331

3.05/653

1.97

1.6/1249

3.76

1,11/1788

5.42

2000

48.15/332

24.12/663

1.99

12.49/1280

3.855

8,5/1880

5.66

3000

161.16/335

81.04/666

1.98

41.76/1292

3.859

28,5/1890

5.65

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

При написані коду для програми перемноження матриць за технологія MPI необхідно вручну розпаралелювати частини матриці по ядрах. Існують і більш «кваліфіковані» технології, такі як бібліотеки Scalapack, Blas, Atlas. Дані бібліотеки містять базові програми лінійної алгебри (Blas) та програмне забезпечення, яке автоматично настроюється для вирішення задач лінійної алгебри (Atlas) [3]. Дані бібліотеки автоматично розкидують частини програми по ядрах, при цьому матриця розбивається на блоки (підматриці), розмірність яких вказує користувач. Саме ці під матриці і розходяться на ядра.

2.                 Отже, розглянемо результати роботи даних бібліотек. Для проведення дослідів оберемо бібліотеку Scalapack-1.8.0 та BLAS. Розмірність підматриць обираємо 25×25, як показали досліди це найбільш оптимальний варіант при якому досягається найбільша продуктивність. Будемо розглядати числа лише подвійної точності.

Результати розрахунків наведені в таблицях 2.1, 2.2.

Таблиця 2.1 - Результати розрахунків  з ключом –О3

Розмір матриці

Одне ядро

Чотири ядра

Приск.

Шість ядер

Прискорення

1000×25

1,6/1248

0,28/7058

5,71

0,25/7939

6,4

2000×25

12,45/1284

1,95/8174

6,38

1,68/9497

7,41

3000×25

42,32/1275

6,26/8614

6,76

5,25/10283

8,06

4000×25

101,24/1264

14,59/8771

6,94

18,69/6845

5,41

Таблиця 2.2 - Результати розрахунків  без ключа –О3

Розмір матриці

Одне ядро

Чотири ядра

Прискорення

Шість ядер

Прискорення

1000×25

1,87/1064

0,29/6826

6,44

0,25/7898

7,48

2000×25

13,98/1144

2,48/6448

5,64

1,7/9383

8,22

3000×25

45,36/1190

6,52/8277

6,95

5,07/10648

8,95

4000×25

111,23/1150

16,34/7830

6,8

19,59/6532

5,68

При даних умовах дослідження з таблиць видно, що без оптимізації процесу максимальне прискорення обчислень дорівнює 8.95, що значно вище очікуваного, але при застосування ключа –О3 загальний час обчислень менший, хоча і прискорення дає менші результати. Таке прискорення свідчить про досить ефективне використання кеш-пам’яті, хоча продуктивність значно падає при досягненні матриці розмірності 4000×4000.

3.                 Наступною розглянемо бібліотеку ATLAS. Для дослідження скористаємося версією ATLAS, яка підтримує інструкції для 64-розрядної ОС – atlas 3.8.3. результати приведені в таблиці 3.1:

Таблиця 3.1 - Результати з ключем –О3

Розмір матриці

Одне ядро

Чотири ядра

Приск.

Шість ядер

Приск.

1000×25

0,23/8632

0,15/12943

1,53

0,17/8638

1,35

2000×25

1,57/10169

0,88/18101

1,78

0,86/18935

1,78

3000×25

5,12/10554

2,76/19519

1,86

2,78/19354

1,84

4000×25

11,69/10947

5,77/22159

2,02

18,95/2435

0,62

5000×25

22,46/11130

39,44/6337

0,57

102,62/2435

0,21

Таблиця 3.2 - Результати без ключа –О3

Розмір матриці

Одне ядро

Чотири ядра

Приск.

Шість ядер

Приск.

1000×25

0,24/8025

0,16/12415

1,5

0,16/12025

1,5

2000×25

1,62/9816

0,9/17652

1,8

0,92/17237

1,76

3000×25

5,22/10342

2,79/19355

1,87

2,8/19198

1,86

4000×25

11,8/10845

5,81/22035

2,03

15,02/8516

0,78

5000×25

22,87/10929

32,96/7583

0,69

53,02/4691

0,43

 В даному випадку, по результат таблиць ми бачимо, що істотного прискорення ми не досягли ні на 4-х ні на 6-ти ядрах, тобто при застосуванні даної бібліотеки кеш-пам'ять не використовується достатньо ефективно. А при  розмірності матриць вище 4000×4000, прискорення і взагалі відсутнє. Ці явища також пояснюються тим, що ядра процесори не отримують дані в потрібному обсязі через занадто вузької смуги пропускання шини пам’яті.

4.                 Проведемо порівняльний аналіз множення матриць за допомогою технології MPI та бібліотек SCALAPACK BLAS та ATLAS. Результати порівняння наведені в таблиці 4.1.

 

Таблиця 4.1 - Результати порівняння

Розмірність  матриць

Технологія MPI

Бібліотека BLAS

Бібліотека ATLAS

1 ядро

6 ядер

Приск.

1 ядро

6 ядер

Приск.

1 ядро

6 ядер

Приск.

1000

1,79/

1113

0,71/

2807

2,52

1,6/

1248

0,25/

7939

6,4

0,23/

8632

0,17/

8638

1,35

2000

13,42/1191

5,36/

2982

2,50

12,45/

1284

1,68/

9497

7,41

1,57/

10169

0,86/

18935

1,78

3000

46,37/1164

17,81/3029

2,60

42,32/

1275

5,25/

10283

8,06

5,12/

10554

2,78/

19354

1,84

4000

-

-

-

101,24/

1264

18,69/

6845

5,41

11,69/

10947

18,95/

2435

0,62

 

Отже в даному випадку по результатам з таблиць видно, що використання спеціальних бібліотек, технологій та оптимізації значно покращує роботу обчислень системи зі збільшенням числа ядер. Навіть при використанні бібліотеки ATLAS, яка не дає істотного прискорення, в порівнянні з використанням технології MPI видно, що прискорення досягає в 16,68 разів.

Висновки

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

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

3.                 Результати обчислювального експерименту показали, що перехід до блокового поданням матриць, до 64-х розрядному програмного забезпечення, до компілятора fortran77 дозволило підвищити швидкість розрахунків для чисел одинарної і подвійної точності приблизно в 10,5-16,7 разів.

4.                 Недоліком багатоядерних систем є недостатній розмір кеш-пам’яті та вузька смуга пропускання шини пам’яті. Це призводить до того, що при оптимізації розміру даних, які надходять до кешу, в даному випадку це блоки матриці, їх кількість збільшується, що призводить до затримок і відповідно неефективного використання всіх ядер.

 Література

1.                 Заболотная Н. И. Организация параллельного перемножения знакопеременных матриц в цифровом оптоэлектронном процессоре многоуровневых изображений / Наталья Заболотна, Владислав Шолота // Электронное моделирование . – 1997. - №3. –С. 41 – 49.

2.                 Мясищев А.А. Оптимизация матричного умножения за счет использования библиотек ScaLAPACK для систем с многоядерными процессорами. http://www.rusnauka.com/26_NII_2009/Informatica/52121.doc.htm - 2009.

3.                 Гергель В.П. Теория и практика параллельных вычислений. -http://www.intuit.ru/department/calculate/paralltp/ - 2007

4.                 The ScaLAPACK Project. - http://www.netlib.org