Статичний блочно-рекурсивний алгоритм Холецького для кластера з розподіленою пам’яттю

Автор(и)

  • Gennadi Malaschonok доктор фізико-математичних наук, професор, завідувач кафедри мережних технологій факультету інформатики Національного університету «Києво-Могилянська академія»
  • Andrii Ivaskevych студент 4 курсу факультету інформатики Національного університету «Києво-Могилянська академія»

DOI:

https://doi.org/10.18523/2617-3808.2020.3.114-120

Ключові слова:

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

Анотація

У цій статті досліджено блочно-рекурсивний паралельний алгоритм розкладання Холецького для суперкомп’ютера з розподіленою пам’яттю. Для зручності масштабування, кількість ядер – це деяка ступінь двійки. Розглянуто стійкість алгоритму до накопичення помилок обчислень і ефективність масштабування статичного блочно-рекурсивного алгоритму. Показано, що для щільних матриць, починаючи з розміру 64, використання подвійної точності (стандартна арифметика з плаваючою точкою і 64-розрядним машинним словом), немає змоги отримувати похибку, меншу ніж 1, навіть у простих випадках. Зі збільшенням розмірів коефіцієнтів похибка тільки зростає, тому використання такої арифметики для матриць ще більшого розміру втрачає сенс. Щоб розв’язати цю проблему, для матриць великого розміру ми використовували арифметику BigDecimal. Вона дає змогу програмно задавати точність, яка вказується як кількість десяткових знаків після коми. Спочатку ми визначаємо необхідну кількість знаків для BigDecimal так, щоб похибка обчислень цієї матриці не перевищувала одиницю, а потім робимо експерименти з різною кількістю ядер для такої матриці. Ми даємо рекомендації для щільних матриць, елементи яких задавались випадково з рівномірним розподілом. Для таких матриць, зважаючи на їхній розмір і кількість десяткових знаків у їхніх елементів, ми рекомендуємо вибір точності для машинної арифметики і кількість ядер для обчислень.

Матеріал надійшов 09.06.2020

Біографії авторів

Gennadi Malaschonok, доктор фізико-математичних наук, професор, завідувач кафедри мережних технологій факультету інформатики Національного університету «Києво-Могилянська академія»

malaschonok@ukma.edu.ua

Andrii Ivaskevych, студент 4 курсу факультету інформатики Національного університету «Києво-Могилянська академія»

a.ivaskevich@ukma.edu.ua

Посилання

Ilchenko, E. A. (2015). Ob effektivnom metode rasparallelivania blochnykh rekurivnykh algoritmov. Vestnik Tambovskogo universiteta. Ser. Estestvennye i tehnichekie nauki, 20 (5), 1173–1186 [in Russian].

Malashonok, G. I. (2009). Upravlenie parallelnym vychislitelnym processom. Vestnik Tambovskogo universiteta. Ser. Estestvennye i tehnichekie nauki, 14 (1), 269–274 [in Russian].

Malashonok, G. I., & Valeev, Ju. D. (2008). Organizacia parallelnykh vychislenii v rekursivnykh simvolno-chislennykh algoritmakh. In Trudy konferencii PaVT’2008 (Sankt-Peterburg) (pp. 153–165). Cheliabinsk: JuUrGU [in Russian].

##submission.downloads##