Рішення розріджених СЛАР великих розмірностей засобами ManagedCuda в .NET

Найчастіше в прикладних математичних і комп'ютерних моделях виникає необхідність розв'язувати системи лінійних алгебраїчних рівнянь (СЛАУ). Як правило, на практиці матриця в таких СЛАР виявляється розрідженою. Наприклад, розріджені матриці зустрічаються в моделях з кінцево-різницевими або звичайно-елементними методами розв'язання диференціальних рівнянь. Виникають сильно розріджені матриці великої розмірності при моделюванні матеріальних та інформаційних потоків у великих технологічних мережах (системи газопостачання і газорозподілу, каналізаційні та теплопостачальні системи, електромережі і комп'ютерні мережі та ін). Загальним для технологічних мереж є подання їх моделей у вигляді графа, у якого матриця інциденцій виявляється практично завжди сильно розрідженою.

У статті буде розказано про те, як ваш покірний слуга значно підвищив ефективність комп'ютерної моделі розрахунку нестаціонарних течій газу в великих системах газопостачання довільної конфігурації, завдяки застосування бібліотеки ManagedCuda і nVidia CUDA 7.0. Проте виклад буде вестися без прив'язки до конкретної предметної області.

Постановка завдання

Розглядається класична задача рішення СЛАУ:
Ax=b
Тут матриця A розміром nxn, x — вектор невідомих розміром n, b — вектор відомих вільних членів розміром n.

Автор статті займається розробкою спеціалізованого програмно-обчислювального комплексу (ПВК) для моделювання і оптимізації нестаціонарних течій газу в системах газопостачання. В вирішуваних мною завдання A є позитивно певним якобианом з діагональним переважанням деякої системи нелінійних рівнянь. A виходить в результаті матричних перетворень матриці інциденцій графа системи газопостачання та інших матриць. В моїх практичних розрахунках A зазвичай заповнена на 6-10%, решта нулі. Розмір її залежить від розміру конкретної системи газопостачання і варіюється n від 10 до 1000.

Наш ПВК розробляється під .NET 4.0 на C#. Розрахунковий модуль і вся математика також розробляється на C#. Спочатку для вирішення СЛАУ я написав власну, доморощену, бібліотеку, не використовує технологію розріджених матриць. Для вирішення СЛАУ застосовував метод LU декомпозиції. І до пори мене все влаштовувало, поки я не почав займатися завданням оптимізацією нестаціонарних режимів течії газу, де доводиться методом динамічного програмування здійснювати велику кількість перебору значень керуючих параметрів і, відповідно, багато разів розв'язувати СЛАР. Стандартний профілювальник Visual Studio показав, що в процесі виконання програми близько 40% витрат припадає на рішення СЛАУ.

Саме в цей момент я зрозумів, що пора щось міняти.

Математична бібліотека Math.Net Numerics

Провівши аналіз наявних математичних бібліотек під .Net я вирішив зупинитися на бібліотеці Math.Net Numerics. Детально ознайомитися з нею ви можете тут.

Мене зацікавили її ключові можливості:
  • Реалізована технологія розріджені матриць і векторів;
  • Є вбудовані всі необхідні вектор-матричні операції;
  • Присутні вбудовані розв'язувачі;
  • Інтуїтивно зрозумілий API.
Наведу лістинг з прикладом вирішення СЛАУ засобами Math.Net Numerics:

SparseMatrix matrix = new SparseMatrix(n);
double[] rightSide = new double[n];
//Заповнення матриці і вектора правій частині
//...
var x = matrix.Solve(DenseVector.Build.DenseOfArray(rightSide)).ToArray();

Як видно, всі дуже елегантно виглядає, але практично відразу мене спіткало розчарування — вбудований вирішувач Math.Net Numerics працював значно повільніше мого. Мене це абсолютно не влаштувало, однак претензії до реалізованих в бібліотеці вектор-матричних операцій не настільки істотні. Тому повністю відмовлятися від Math.Net Numerics я не став, залишивши код, де проводиться робота з векторами та матрицями.

Але тут мені згадався дуже вдалий досвід колег по аспірантурі, які для вирішення завдань підземної гідродинаміки використовували графічні процесори. В розпорядженні у мене є ноутбук з відеокартою nVidia GeeForce GT 540M з 2 ГБ пам'яті і підтримкою технології CUDA. Було прийнято рішення спробувати цю технологію на ділі, про що не жалкую.

Бібліотека ManagedCuda

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

Мене зацікавила бібліотека cuSPARSE. При першому знайомстві з нею я натрапив на проблеми:
  • Безпосередня робота з бібліотекою можлива тільки через C/C++. Звичайно, проблема вирішиться, якщо використовувати якісний врапперов, який дуже не хотілося писати. За результатами пошуку був знайдений CUDA-врапперов .Net під назвою Cudafy.
  • cuSPARCE дозволяє розв'язувати СЛАР з трикутними матрицями, а в моєму випадку матриці такими не є. Однак cuSPARSE містить методи факторизації матриць, приводять їх до трикутної форми (метод LU факторизації, розкладання Холецького). Проте в API Cudafy були відсутні відповідні методи, тому від Cudafy довелося відмовитися.
Після продовження пошуку я відкрив для себе бібліотеку ManagedCuda, яка є високорівневої обгорткою над CUDA API. Всі її можливості я перераховувати не буду — їх можна знайти на офіційному сайті, але зупинюся на тому, як можна, використовуючи Math.Net Numerics і ManagedCuda, елегантно і ефективно розв'язувати СЛАР.

Ідея полягає у використанні SparseMatrix з Math.Net Numerics для формування і зберігання розрідженої матриці в форматі CSR, який приймають на вхід cuSPARSE і ManagedCuda. Далі наводиться лістинг відповідної програми:

SparseMatrix matrix = new SparseMatrix(n);
double[] rightSide = new double[n];
//Заповнення матриці і вектора правій частині
//...

var storage = matrix.Storage as SparseCompressedRowMatrixStorage<double>; //Містить необхідну 
//інформацію про розрідженої матриці в CSR форматі

var nonZeroValues = storage.EnumerateNonZero().ToArray(); //Отримуємо ненульові елементи матриці
double[] x = new double[matrix.RowCount]; //Виділяється пам'ять під результат розрахунку

CudaSolveSparse sp = new CudaSolveSparse(); //Створюємо вирішувач з бібліотеки ManagedCuda
CudaSparseMatrixDescriptor matrixDescriptor = new CudaSparseMatrixDescriptor(); // Створюється дескриптор матриці
double tolerance = 0.00001; //Точність розрахунку. Значення взято для ілюстрації

sp.CsrlsvluHost(matrix.RowCount, nonZeroValues.Length, matrixDescriptor, nonZeroValues, 
storage.RowPointers, storage.ColumnIndices, rightSide,
tolerance, 0, x); //Рішення СЛАУ методом LU факторизації

Обчислювальний експеримент: аналіз часових витрат на вирішення СЛАУ різними технологіями

Щоб не втомлювати читача сухим текстом і листингами програм, розглянемо результати розрахунків СЛАР розмірностей від 50 до 500 з допомогою різних технологій:
  • Доморощений вирішувач, написаний автором статті. Назвемо його Mani.Net.
  • Стандартний вирішувач бібліотеки Math.Net Numerics.
  • Метод LU декомпозиції бібліотеки ManagedCuda.
Матриця A заповнюється на 10% випадковим чином.

image

Малюнок наочно демонструє, чому мені довелося відмовитися від Math.Net Numerics для розв'язання СЛАР.
Зазначимо, при розмірності матриці дорівнює 500 моїм власним решателю (Mani.Net) знадобилося 1170 мс, Math.Net Numerics — 12968 мс, ManagedCuda — 70 мс.

Висновок

Слід очікувати в коментарях зауваження, мовляв де не на всіх машинах є GPU nVidia з підтримкою CUDA. Дійсно, це так. Тому наше додаток налаштоване на дві конфігурації компіляції: з власною бібліотекою рішення СЛАУ і з ManagedCuda.

Щодо Mani.Net зазначу, що це не реклама моєї власної бібліотеки. Знайти її ніде неможливо і нікому я її передавати не буду. Ні, я не жадібний. Мені соромно за код.

Спасибі за прочитання статті! Буду радий дізнатися про вашу думку та зауваження в коментарях.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.