Статичний блочно-рекурсивний алгоритм Холецького для кластера з розподіленою пам'яттю
Loading...
Date
2020
Authors
Малашонок, Геннадiй
Іваськевич, Андрій
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
У цій статті досліджено блочно-рекурсивний паралельний алгоритм розкладання Холецького
для суперкомп’ютера з розподіленою пам’яттю. Для зручності масштабування, кількість ядер –
це деяка ступінь двійки. Розглянуто стійкість алгоритму до накопичення помилок обчислень
і ефективність масштабування статичного блочно-рекурсивного алгоритму. Показано, що для
щільних матриць, починаючи з розміру 64, використання подвійної точності (стандартна арифметика з плаваючою точкою і 64-розрядним машинним словом), немає змоги отримувати похибку,
меншу ніж 1, навіть у простих випадках. Зі збільшенням розмірів коефіцієнтів похибка тільки
зростає, тому використання такої арифметики для матриць ще більшого розміру втрачає сенс.
Щоб розв’язати цю проблему, для матриць великого розміру ми використовували арифметику
BigDecimal. Вона дає змогу програмно задавати точність, яка вказується як кількість десяткових знаків після коми. Спочатку ми визначаємо необхідну кількість знаків для BigDecimal так, щоб
похибка обчислень цієї матриці не перевищувала одиницю, а потім робимо експерименти з різною
кількістю ядер для такої матриці. Ми даємо рекомендації для щільних матриць, елементи яких
задавались випадково з рівномірним розподілом. Для таких матриць, зважаючи на їхній розмір
і кількість десяткових знаків у їхніх елементів, ми рекомендуємо вибір точності для машинної
арифметики і кількість ядер для обчислень.
This 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.
This 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.
Description
Keywords
паралельне програмування, алгоритм Холецького, блочно-рекурсивний алгоритм, факторизація матриць, обчислення на кластері з розподіленою пам’яттю, накопичення похибки, стаття, parallel programming, Cholesky algorithm, block-recursive algorithm, matrix factorization, computation on a cluster with distributed memory, error accumulation
Citation
Малашонок Г. І. Статичний блочно-рекурсивний алгоритм Холецького для кластера з розподіленою пам'яттю / Малашонок Г. І., Іваськевич A. Я. // Наукові записки НаУКМА. Комп'ютерні науки. - 2020. - Т. 3. - С. 114-120.