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

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

1. По результатам работы:

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

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

2. With respect to the algorithm:
   1. Unfortunately, there are only a few things you can do to recover a little bit of performance (there is no real way to speed up the analysis phase). For example, you can split the matrixLU into separate lower and upper triangular parts. Computing with separate triangular parts is in general faster than computing with triangular parts embedded in a general matrix. If you are using incomplete factorization with 0 fill-in as a preconditioner, you can also take advantage of the incomplete-LU/Cholesky with 0 fill-in on the GPU, that has recently become available in the CUSPARSE library. (Edit:) The incomplete-LU factorization with 0 fill-in is available in CUDA Toolkit 5.0 release. Currently the early access version of this release can be obtained by registered developers on the NVIDIA website.
   2. Мы никогда не смотрели, как соотношение между этапами анализа и решения зависит от разных графических процессоров; все наши эксперименты проводились на C2050.
   3. Фаза анализа выполняется медленно, потому что она должна собирать информацию о том, какие строки могут быть объединены в уровни. Фаза решения выполняется быстрее, потому что она обрабатывает только уровни (см. rel="noreferrer">данный документ).

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

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

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

Что касается сравнения ЦП и ГП, то есть определенные задачи (например, умножение плотной матрицы на матрицу или разреженное умножение матрицы на вектор), для которых отлично подходит ГП, а есть и другие (например, обход связанного списка или выполнение полностью последовательного фрагмента кода). код), для которого это не так. Решение разреженных треугольных линейных систем находится где-то посередине между этими алгоритмами (в зависимости от шаблона разреженности матрицы коэффициентов и других свойств линейной системы это может работать или не работать для вас). Кроме того, решение об использовании графического процессора основывается не только на одном алгоритме, таком как разреженное треугольное решение, но и на всем наборе алгоритмов, используемых приложением. В конечном счете, графические процессоры часто очень успешно ускоряют и улучшают производительность всего приложения.

Наконец, что касается сравнения trsm и csrsv, нас не удивляет, что для небольших матриц выполнение операций в плотном хранилище выполняется быстрее, чем в разреженном (даже если эти маленькие матрицы могут быть разреженными). Обычно это верно не только для треугольного решения, но и для других операций линейной алгебры (хотя это может происходить в разных точках пересечения в зависимости от операции и шаблона разреженности матрицы). Кроме того, еще раз, алгоритм разреженного треугольного решения был разработан для работы в итеративной настройке, когда анализ выполняется один раз, а решение выполняется несколько раз. Таким образом, неудивительно, что ее однократный запуск (и подсчет на этапе анализа) приводит к более высокой точке пересечения, чтобы эта операция была более эффективной в разреженном, а не в плотном формате.