CUDA Assignment #4 Решение краевых задач, системы линейных алгебраических уравнений. - презентация

1 CUDA Assignment #4 Решение краевых задач, системы линейных алгебраических уравнений

2 Задание zОсновное: yРешение 1D/2D задачи диффузии zДополнительное: yРешение СЛАУ с треугольной разряженной матрицей

3 Задача диффузии zУравнение теплопроводности: z - коэффициент теплопроводности yПостоянный: yЛинейный: yНелинейный:

4 Постановка 1D задачи zОбласть определения – отрезок zУравнение теплопроводности на zНачальные условия: zГраничные условия:

5 Методы решения zМетод конечных разностей явные схемынеявные схемы На каждом шаге необходимо решать трехдиагональную СЛАУ

6 Постановка 2D задачи zОбласть определения: zУравнение теплопроводности: zНачальные и граничные условия (W,0) (0,H) (0,0) (W,H)

7 Метод по-координатного расщепления zВременной шаг разбивается на два дробных для каждого фикс. y для каждого фикс. x

8 Пример разностной аппроксимации zРасщепление по X: zНезависимые трехдиагональные СЛАУ для каждого j = 0.. N_y yЛегко параллелится

9 Трехдиагональные СЛАУ zПрямые методы: yМетод прогонки xОптимальный по числу операций, но последовательный yМетод редукции xПараллельный, но больше операций

10 Итерационные методы zЯкоби, Гаусса-Зейделя zGMRES, CG zПреобуславливатель (preconditioner)

11 Дополнительное задание zВерхне-треугольная разряженная матрица NxN zЧисло ненулевых элементов = NNZ X X X X X X X X X X X X X X X X X XX X X XX X

12 Формат хранения zCompressed Sparse Row (CSR) yData[NNZ] – массив ненулевых элементов yIndices[NNZ] – индексы столбцов для каждого ненулевого элемента yPtr[N+1] – смещение в массиве данных для каждой строки xPtr[i+1]-Ptr[i]: число ненулевых эл-тов в i-строке xPtr[N] = NNZ : общее число ненулевых элементов

13 Пример матрицы N=5 NNZ=7 Data Indices Ptr024567

14 Задание zПридумать эффективный алгоритм для реализации на CUDA/GPU zМатрица задается в формате MatrixMarket ( #MMformat) #MMformat

15 Полезные ссылки zУмножение разряженной матрицы на столбец: pub_001.html pub_001.html

16 Вопросы