Очень медленная производительность анализа cusparse csrsv

Я написал решатель сопряженного градиента (для линейной системы уравнений) с предварительным условием LU, я использовал статьи доктора Максима Наумова на исследовательском сообществе nvidia в качестве руководства, шаг обновления остатков, который требует решения нижней треугольной матричной системы, а затем решение верхней треугольной матричной системы делится на две фазы:

]}


    Фаза анализа (которая использует модель разреженности и определяет уровень распараллеливания).
  1. фаза решения сам.


Согласно всем постам, связанным с этой темой, и самой статье Наумова, фаза анализа значительно медленнее, чем фаза решения, но она выполняется один раз, поэтому это не должно быть проблемой при рассмотрении всего времени выполнения, однако в моей программе фаза анализа требует ~35-45% всего времени решения (время, необходимое для выполнения всех итераций!), что довольно раздражает, другое дело, что я совершенно уверен, что разреженность матрицы паттерн не допускает большого распараллеливания, так как почти все элементы требуют, чтобы предыдущие элементы были известны (потому что в CFD каждый узел будет нуждаться по крайней мере в соседних 6 узлах (шестигранных объемах) вокруг него, и это повторяется в каждой строке), так что фаза анализа не будет очень полезной в любом случае !



matrixLU в этом коде содержатся как верхние, так и нижние треугольные матрицы, в верхней треугольной матрице используются исходные диагонали матрицы, а в нижней треугольная матрица имеет диагонали единства (факторизация LU).



// z = inv(matrixLU)*r

cusparseMatDescr_t descrL = 0 ;

cusparseMatDescr_t descrU = 0 ;

cusparseStatus = cusparseCreateMatDescr(&descrL) ;

cusparseStatus = cusparseCreateMatDescr(&descrU) ;



cusparseSetMatType(descrL,CUSPARSE_MATRIX_TYPE_GENERAL) ;

cusparseSetMatIndexBase(descrL,CUSPARSE_INDEX_BASE_ONE) ;

cusparseSetMatDiagType(descrL,CUSPARSE_DIAG_TYPE_UNIT) ;

cusparseSetMatFillMode(descrL,CUSPARSE_FILL_MODE_LOWER) ;



cusparseSetMatType(descrU,CUSPARSE_MATRIX_TYPE_GENERAL) ;

cusparseSetMatIndexBase(descrU,CUSPARSE_INDEX_BASE_ONE) ;

cusparseSetMatDiagType(descrU,CUSPARSE_DIAG_TYPE_NON_UNIT) ;

cusparseSetMatFillMode(descrU,CUSPARSE_FILL_MODE_UPPER) ;



cusparseSolveAnalysisInfo_t inforL = 0 ;

cusparseSolveAnalysisInfo_t inforU = 0 ;

cusparseStatus = cusparseCreateSolveAnalysisInfo(&inforL) ;

cusparseStatus = cusparseCreateSolveAnalysisInfo(&inforU) ;



double startFA = omp_get_wtime() ;

cusparseStatus = cusparseDcsrsv_analysis(cusparseHandle, CUSPARSE_OPERATION_NON_TRANSPOSE, N, NZ, descrL, matrixLU, iRow, jCol, inforL) ;

if(cusparseStatus != CUSPARSE_STATUS_SUCCESS) printf("%s nn","cusparseDcsrsv_analysis1 Error !") ;

cusparseStatus = cusparseDcsrsv_analysis(cusparseHandle, CUSPARSE_OPERATION_NON_TRANSPOSE, N, NZ, descrU, matrixLU, iRow, jCol, inforU) ;

if(cusparseStatus != CUSPARSE_STATUS_SUCCESS) printf("%s nn","cusparseDcsrsv_analysis2 Error !") ;

double finishFA = omp_get_wtime() ;


Итак, кто-нибудь знает, почему фаза анализа идет так медленно ? и как его можно ускорить ? это (фазовый анализ времени выполнения)/(решить этапа исполнения) отношение ГПУ зависимые ?

Редактировать:
Я пробовал этот решатель для многих случаев, и результаты были близки, но в конкретном случае, о котором я беспокоюсь, он имеет следующие условия:




  • Размер (N ) : ~860,000 * 860,000

  • число ненулевых чисел(NZ): ~6,000,000

  • число итераций, необходимых для сходимости: 10


  • анализ Время выполнения фазы: 210 МС


  • решить Время выполнения фазы (суммирование всех итераций): 350 ms

  • все операции с плавающей запятой выполняются в форматеdouble precision

  • GPU: GeForce GTX 550 Ti

  • OS: Windows 7 ultimate, 64 bit

580   1  

1 ответ:

Я связался с нашей командой библиотек линейной алгебры в NVIDIA, и они предоставили следующую обратную связь.

  1. Относительно результатов выполнения:

    1. Итерационный метод CG выполняет только 10 итераций, пока не будет найдено решение линейной системы. По-видимому, в данном случае итераций недостаточно для уменьшения времени, затрачиваемого на фазу анализа. (Edit:) число шагов, требуемых для сходимости к решению, варьируется в зависимости от типа решения. разные приложения. В некоторых случаях нетрадиционные итерационные методы не сходятся (или требуют тысяч итераций), а предварительно обусловленные итерационные методы требуют десятков (или сотен) итераций для сходимости к решению. Тот факт, что в данном конкретном приложении итерационный метод сходится за 10 итераций, не обязательно является репрезентативным для всех приложений.

    2. Соотношение фаз анализа и решения равно 6 = 210/35, что согласуется с нашими экспериментами на других матрицы, где она обычно находится в интервале [4,10]. Неясно, как время для анализа и фазы решения сравнивается со временем, затраченным на разреженное треугольное решение на процессоре. (Это было бы интересно узнать.)

  2. относительно алгоритма:
      К сожалению, есть только несколько вещей, которые вы можете сделать, чтобы восстановить немного производительности (нет реального способа ускорить фазу анализа). Например, можно разбить матрицу на части. на отдельные нижнюю и верхнюю треугольные части. Вычисления с отдельными треугольными частями в общем случае быстрее, чем вычисления с треугольными частями, вложенными в общую матрицу. Если вы используете незавершенную факторизацию с 0 заполнением в качестве предобусловливателя, вы также можете воспользоваться неполной-LU/Cholesky с 0 заполнением на GPU, которая недавно стала доступна в библиотеке CUSPARSE. (Edit: ) неполная факторизация LU с 0 заполнением доступна в CUDA Toolkit 5.0 освобождать. В настоящее время раннюю версию этого релиза могут получить зарегистрированные разработчики на веб-сайте NVIDIA.
    3. Мы никогда не рассматривали, как меняется соотношение фаз анализа и решения в разных графических процессорах; все наши эксперименты проводились на C2050.
  3. этап анализа медленный, потому что он должен собирать информацию о том, какие строки могут быть обработаны вместе в уровни. Фаза решения быстрее, потому что она обрабатывает только уровни (см. это бумага ).

Наконец, вы также упомянули, что считаете, что в этой задаче недостаточно параллелизма. Но количество параллелизма может быть трудно угадать, просто глядя на матрицу. Если действительно существует мало параллелизма (каждая строка зависит от предыдущей строки), то решение CUSPARSE sparse triangular может не быть правильным алгоритмом для этой задачи. Кроме того, вы можете попробовать запустить итерационный метод CG без предварительной подготовки или с другими типами предобуславливатели, которые могут быть более подходящими для вашей проблемы.

Как упоминалось ранее, было бы интересно узнать, как производительность этого кода сравнивается на GPU и CPU.

Редактировать: Относительно некоторых комментариев... Как упоминалось ранее, конечное число итераций для предварительно обусловленного итерационного метода варьируется в разных приложениях. В некоторых случаях он может быть очень маленьким (например, 10, как в вашем приложении), но в других случаях он может быть относительно большим (измеряется в 100s). В статье речь идет не о "триумфе", а о компромиссах алгоритма. Он пытается дать пользователю более глубокое понимание процедуры для того, чтобы она была использована эффективно. Опять же, если модель разреженности под рукой не имеет никакого параллелизма, это не правильный алгоритм для вас.

Что касается сравнения CPU и GPU, существуют определенные проблемы (такие как плотная Матрица-Матрица или разреженная матрица-векторное умножение), для которых GPU является большим, есть и другие (например, обход связанного списка или выполнение полностью последовательного фрагмента кода), для которых это не так. Решение разреженных треугольных линейных систем лежит где-то между этими алгоритмами (в зависимости от разреженности матрицы коэффициентов и других свойств линейной системы это может хорошо или плохо работать для вас). Кроме того, решение об использовании GPU основано не только на одном алгоритме, таком как sparse triangular solve, но и на всем наборе алгоритмы, используемые приложением. В конечном счете, графические процессоры часто очень успешно ускоряют и улучшают производительность всего приложения.

Наконец, в отношении trsm и csrsv нас не удивляет, что для малых матриц выполнение операций в плотном хранилище происходит быстрее, чем в разреженном хранилище (хотя эти малые матрицы могут быть разреженными). Обычно это справедливо не только для треугольных решений, но и для других операций линейной алгебры (это может быть однако это происходит в разных точках пересечения в зависимости от операции и разреженности матрицы). Кроме того, еще раз, алгоритм разреженного треугольного решения был разработан для работы в итерационной среде, где анализ выполняется один раз, а решение выполняется несколько раз. Поэтому неудивительно, что выполнение его один раз (и подсчет на этапе анализа) приводит к более высокой точке пересечения для того, чтобы эта операция была более эффективной в разреженном, а не в плотном формате.
5  
2012-07-23 05:07:48

Comments

    Ничего не найдено.
Click here to cancel reply.