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

Simple item page
dc.contributor.authorМалашонок, Геннадiй
dc.contributor.authorІваськевич, Андрій
dc.date.accessioned2021-01-08T21:07:25Z
dc.date.available2021-01-08T21:07:25Z
dc.date.issued2020
dc.description.abstractУ цій статті досліджено блочно-рекурсивний паралельний алгоритм розкладання Холецького для суперкомп’ютера з розподіленою пам’яттю. Для зручності масштабування, кількість ядер – це деяка ступінь двійки. Розглянуто стійкість алгоритму до накопичення помилок обчислень і ефективність масштабування статичного блочно-рекурсивного алгоритму. Показано, що для щільних матриць, починаючи з розміру 64, використання подвійної точності (стандартна арифметика з плаваючою точкою і 64-розрядним машинним словом), немає змоги отримувати похибку, меншу ніж 1, навіть у простих випадках. Зі збільшенням розмірів коефіцієнтів похибка тільки зростає, тому використання такої арифметики для матриць ще більшого розміру втрачає сенс. Щоб розв’язати цю проблему, для матриць великого розміру ми використовували арифметику BigDecimal. Вона дає змогу програмно задавати точність, яка вказується як кількість десяткових знаків після коми. Спочатку ми визначаємо необхідну кількість знаків для BigDecimal так, щоб похибка обчислень цієї матриці не перевищувала одиницю, а потім робимо експерименти з різною кількістю ядер для такої матриці. Ми даємо рекомендації для щільних матриць, елементи яких задавались випадково з рівномірним розподілом. Для таких матриць, зважаючи на їхній розмір і кількість десяткових знаків у їхніх елементів, ми рекомендуємо вибір точності для машинної арифметики і кількість ядер для обчислень.uk_UA
dc.description.abstractThis paper investigates the block-recursive parallel algorithm for Cholesky decomposition for a supercomputer with distributed memory. For ease of scaling, the number of cores is a degree of the number two. We investigate the resistance of the algorithm to the accumulation of computational errors and the scaling efficiency of the static block-recursive algorithm. Note that the problem does not have an exact solution in rational numbers (for example, LU-decomposition has an exact solution), so it is necessary to use approximate calculations and there are no other approaches than calculations with some accuracy. We have not been able to find systematic studies on the accumulation of error in the Cholesky algorithm, so we conduct such studies in this paper. elements are integers with a fixed number of binary digits and a uniform distribution. We have shown that for dense matrices, starting with matrix size 64, the use of double precision (standard floating-point arithmetic and 64-bit machine word) does not allow to obtain an error less than 1, even in simple cases. As the size of the coefficients increases, the error only increases, so the use of such arithmetic for matrices of even larger size loses its meaning. To solve this problem, we used BigDecimal arithmetic for large matrices. It allows you to programmatically specify the accuracy, which is specified as the number of decimal places. First, we determine the required number of characters for BigDecimal so that the calculation error of this matrix does not exceed one, and then we experiment with different numbers of cores for such a matrix. We give recommendations for dense matrices, the elements of which were given randomly with a uniform distribution. For such matrices, based on their size and the number of decimal places in their elements, we recommend the choice of accuracy for machine arithmetic and the number of cores for calculations.en_US
dc.identifier.citationМалашонок Г. І. Статичний блочно-рекурсивний алгоритм Холецького для кластера з розподіленою пам'яттю / Малашонок Г. І., Іваськевич A. Я. // Наукові записки НаУКМА. Комп'ютерні науки. - 2020. - Т. 3. - С. 114-120.uk_UA
dc.identifier.issn2617-3808
dc.identifier.urihttps://doi.org/10.18523/2617-3808.2020.3.114-120
dc.identifier.urihttps://ekmair.ukma.edu.ua/handle/123456789/19173
dc.language.isoukuk_UA
dc.relation.sourceНаукові записки НаУКМА. Комп'ютерні науки.uk_UA
dc.statusfirst publisheduk_UA
dc.subjectпаралельне програмуванняuk_UA
dc.subjectалгоритм Холецькогоuk_UA
dc.subjectблочно-рекурсивний алгоритмuk_UA
dc.subjectфакторизація матрицьuk_UA
dc.subjectобчислення на кластері з розподіленою пам’яттюuk_UA
dc.subjectнакопичення похибкиuk_UA
dc.subjectстаттяuk_UA
dc.subjectparallel programmingen_US
dc.subjectCholesky algorithmen_US
dc.subjectblock-recursive algorithmen_US
dc.subjectmatrix factorizationen_US
dc.subjectcomputation on a cluster with distributed memoryen_US
dc.subjecterror accumulationen_US
dc.titleСтатичний блочно-рекурсивний алгоритм Холецького для кластера з розподіленою пам'яттюuk_UA
dc.title.alternativeStatic Block-Recursive Cholesky Algorithm for a Distributed Memory Clusteren_US
dc.typeArticleuk_UA
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Malashonok_Statychnyi_blochno-rekursyvnyi_alhorytm_Kholetskoho.pdf
Size:
461.74 KB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
7.54 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Том 3