Статичний блочно-рекурсивний алгоритм Холецького для кластера з розподіленою пам’яттю
DOI:
https://doi.org/10.18523/2617-3808.2020.3.114-120Ключові слова:
паралельне програмування, алгоритм Холецького, блочно-рекурсивний алгоритм, факторизація матриць, обчислення на кластері з розподіленою пам’яттю, накопичення похибкиАнотація
У цій статті досліджено блочно-рекурсивний паралельний алгоритм розкладання Холецького для суперкомп’ютера з розподіленою пам’яттю. Для зручності масштабування, кількість ядер – це деяка ступінь двійки. Розглянуто стійкість алгоритму до накопичення помилок обчислень і ефективність масштабування статичного блочно-рекурсивного алгоритму. Показано, що для щільних матриць, починаючи з розміру 64, використання подвійної точності (стандартна арифметика з плаваючою точкою і 64-розрядним машинним словом), немає змоги отримувати похибку, меншу ніж 1, навіть у простих випадках. Зі збільшенням розмірів коефіцієнтів похибка тільки зростає, тому використання такої арифметики для матриць ще більшого розміру втрачає сенс. Щоб розв’язати цю проблему, для матриць великого розміру ми використовували арифметику BigDecimal. Вона дає змогу програмно задавати точність, яка вказується як кількість десяткових знаків після коми. Спочатку ми визначаємо необхідну кількість знаків для BigDecimal так, щоб похибка обчислень цієї матриці не перевищувала одиницю, а потім робимо експерименти з різною кількістю ядер для такої матриці. Ми даємо рекомендації для щільних матриць, елементи яких задавались випадково з рівномірним розподілом. Для таких матриць, зважаючи на їхній розмір і кількість десяткових знаків у їхніх елементів, ми рекомендуємо вибір точності для машинної арифметики і кількість ядер для обчислень.
Матеріал надійшов 09.06.2020
Посилання
- 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##
Як цитувати
Номер
Розділ
Ліцензія
Авторське право (c) 2020 Gennadi Malaschonok, Andrii Ivaskevych
Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.
Автори, які публікуються у цьому журналі, погоджуються з такими умовами:
а) Автори зберігають за собою авторські права на твір на умовах ліцензії CC BY 4.0 Creative Commons Attribution International License, котра дозволяє іншим особам вільно поширювати (копіювати і розповсюджувати матеріал у будь-якому вигляді чи форматі) та змінювати (міксувати, трансформувати, і брати матеріал за основу для будь-яких цілей, навіть комерційних) опублікований твір на умовах зазначення авторства.
б) Журнал дозволяє автору (авторам) зберігати авторські права без обмежень.
в) Автори мають право укладати самостійні додаткові угоди щодо поширення твору (наприклад, розміщувати роботу в електронному репозитарії), за умови збереження посилання на його першу публікацію. (Див. Політика Самоархівування)
г) Політика журналу дозволяє розміщення авторами в мережі Інтернет (наприклад, у репозитаріях) тексту статті, як до подання його до редакції, так і під час його редакційного опрацювання, оскільки це сприяє виникненню продуктивної наукової дискусії та позитивно позначається на оперативності та динаміці цитування опублікованої роботи (див. The Effect of Open Access).
