Как распараллелить этот цикл Python для при использовании Numba

Я использую дистрибутив Python Anaconda вместе с Numba, и я написал следующую функцию Python, которая умножает разреженную матрицу A (хранится в формате CSR) плотным вектором x:

@jit
def csrMult( x, Adata, Aindices, Aindptr, Ashape ):

    numRowsA = Ashape[0]
    Ax       = numpy.zeros( numRowsA )

    for i in range( numRowsA ):
        Ax_i = 0.0
        for dataIdx in range( Aindptr[i], Aindptr[i+1] ):

            j     = Aindices[dataIdx]
            Ax_i +=    Adata[dataIdx] * x[j]

        Ax[i] = Ax_i

    return Ax

Вот A большой scipy разреженная матрица,

>>> A.shape
( 56469, 39279 )
#                  having ~ 142,258,302 nonzero entries (so about 6.4% )
>>> type( A[0,0] )
dtype( 'float32' )

а также x это numpy массив. Вот фрагмент кода, который вызывает вышеуказанную функцию:

x       = numpy.random.randn( A.shape[1] )
Ax      = A.dot( x )   
AxCheck = csrMult( x, A.data, A.indices, A.indptr, A.shape )

Обратите внимание на @jit -декоратор, который говорит Numba, чтобы сделать своевременную компиляцию для csrMult() функция.

В моих экспериментах моя функция csrMult() примерно в два раза быстрее, чем scipy.dot() метод. Это довольно впечатляющий результат для Numba.

Тем не менее, MATLAB все еще выполняет это умножение матрицы на вектор примерно в 6 раз быстрее, чем csrMult(), Я полагаю, что это потому, что MATLAB использует многопоточность при выполнении разреженного умножения матрицы на вектор.

Вопрос:

Как я могу распараллелить внешнее for петля при использовании Numba?

Раньше у Нумбы prange() функция, которая упростила параллелизацию for -loops. К сожалению, Нумба больше не имеет prange() [на самом деле, это неверно, см. редактирование ниже ]. Так каков правильный способ распараллелить это for сейчас, что Нумба prange() функция ушла?

когда prange() был удален из Numba, какую альтернативу имели в виду разработчики Numba?

Изменить 1:
Я обновил до последней версии Numba, которая составляет 0,35, и prange() вернулся! Это не было включено в версию.33, версию, которую я использовал.
Это хорошая новость, но, к сожалению, я получаю сообщение об ошибке, когда пытаюсь распараллелить цикл for, используя prange(), Вот пример параллельного цикла for из документации Numba (см. Раздел 1.9.2 "Явные параллельные циклы"), а ниже мой новый код:

from numba import njit, prange
@njit( parallel=True )
def csrMult_numba( x, Adata, Aindices, Aindptr, Ashape):

    numRowsA = Ashape[0]    
    Ax       = np.zeros( numRowsA )

    for i in prange( numRowsA ):
        Ax_i = 0.0        
        for dataIdx in range( Aindptr[i],Aindptr[i+1] ):

            j     = Aindices[dataIdx]
            Ax_i +=    Adata[dataIdx] * x[j]

        Ax[i] = Ax_i            

    return Ax

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

AttributeError: Ошибка при nopython (преобразование в parfors) У объекта SetItem нет атрибута get_targets

Дано
вышеуказанная попытка использовать prange вылетает, мой вопрос стоит:

Как правильно (используя prange или альтернативный метод), чтобы распараллелить этот Python for -loop?

Как отмечено ниже, было тривиально распараллелить аналогичный цикл for в C++ и получить 8- кратное ускорение, будучи запущенным на 20 -комп-потоках. Должен быть способ сделать это с помощью Numba, так как цикл for смущающе параллелен (и так как редкое умножение матрицы на вектор является фундаментальной операцией в научных вычислениях).

Изменить 2:
Вот моя C++ версия csrMult(), Распараллеливание for() Цикл в версии C++ делает код примерно в 8 раз быстрее в моих тестах. Это говорит мне о том, что подобное ускорение должно быть возможным для версии Python при использовании Numba.

void csrMult(VectorXd& Ax, VectorXd& x, vector<double>& Adata, vector<int>& Aindices, vector<int>& Aindptr)
{
    // This code assumes that the size of Ax is numRowsA.
    #pragma omp parallel num_threads(20)
    {       
        #pragma omp for schedule(dynamic,590) 
        for (int i = 0; i < Ax.size(); i++)
        {
            double Ax_i = 0.0;
            for (int dataIdx = Aindptr[i]; dataIdx < Aindptr[i + 1]; dataIdx++)
            {
                Ax_i += Adata[dataIdx] * x[Aindices[dataIdx]];
            }

            Ax[i] = Ax_i;
        }
    }
}
Источник

2 ответа

Решение

Спасибо за ваши количественные обновления, Дэниел.
Следующие строки может быть трудно проглотить, но, пожалуйста, поверьте мне, есть еще вещи, которые необходимо учитывать. Я работал над проблемами HPC / параллельных вычислений, имеющих матрицы в масштабах ~ N [TB]; N > 10 и их редкое сопровождение, поэтому некоторые кусочки опыта могут быть полезны для ваших дальнейших просмотров.

ВНИМАНИЕ: не ожидайте, что какой-либо ужин будет подан бесплатно

Желание распараллелить кусок кода звучит как все более современная современная переформулированная мана. Проблема не в коде, а в стоимости такого перемещения.

Экономика является проблемой номер один. Закон Амдала, как он был первоначально сформулирован Джином Амдалем, не учитывал сами издержки [PAR] -процессы-настройки + [PAR] -processes-финализации и завершения, которые действительно должны быть оплачены в каждой реальной реализации.

Строгий закон Амдала отображает масштаб этих неизбежных неблагоприятных последствий и помогает понять несколько новых аспектов, которые необходимо оценить, прежде чем кто-либо решит ввести параллелизацию (при приемлемой стоимости, поскольку это очень, действительно ОЧЕНЬ ЛЕГКО платить больше, чем можно выиграть - где наивное разочарование из-за ухудшенной производительности обработки - самая легкая часть истории).

Не стесняйтесь читать больше постов о пересмотре формулировки закона Амдала в строгом смысле слова, если хотите лучше понять эту тему и предварительно рассчитать фактический " минимальный "-подробный-" размер ", для которого сумма [PAR] - накладные расходы будут, по крайней мере, оправданы инструментами реального мира для введения параллельного разбиения подзадачи на N_trully_[PAR]_processes (не любое "просто"- [CONCURRENT], но правда- [PARALLEL] - это путь не равный).

Питон может получить дозу стероидов для повышения производительности:

Python - отличная прототипная экосистема, тогда как numba, numpy и другие скомпилированные расширения помогают значительно повысить производительность дальше, чем нативный, GIL-пошаговый python (co-)- обычно обеспечивает обработка.

Здесь вы пытаетесь провести в жизнь numba.jit() организовать работу практически бесплатно, просто с помощью jit() - лексический анализатор времени (для которого вы добавляете свой код), который должен "понять" вашу глобальную цель (что делать), а также предложить некоторые приемы векторизации (как лучше собрать кучу инструкций процессора для максимальной эффективности такое выполнение кода).

Это звучит легко, но это не так.

Команда Трэвиса Олифанта добилась огромного прогресса в numba инструменты, но давайте будем реалистичными и справедливыми, чтобы не ожидать, что любая форма автоматизированного волшебства будет реализована внутри .jit() -lexer + code-analysis, при попытке преобразовать код и собрать более эффективный поток машинных инструкций для реализации цели задачи высокого уровня.

@guvectorize? Вот? Шутки в сторону?

Из-за [PSPACE] Размер, вы можете сразу забыть спросить numba как-то эффективно "заполнить" GPU-движок данными, объем памяти которых сильно отстает от размеров GPU-GDDR (не говоря уж о слишком "мелких" размерах ядра GPU для такой математически "крошечной" обработки) просто умножить, потенциально в [PAR], но позже суммировать в [SEQ]).

(Re -) - Загрузка GPU с данными занимает кучу времени. Если вы заплатите за это, задержки памяти в In-GPU не очень благоприятны для экономики "крошечных" GPU-ядер - ваше выполнение кода GPU-SMX должно будет заплатить ~ 350-700 [ns] просто для извлечения числа (скорее всего, не выровнено автоматически для лучшего повторного использования объединенного SM-кэша в следующих шагах, и вы можете заметить, что вы никогда, позвольте мне повторить, НИКОГДА не использовать повторно одну матричную ячейку вообще, поэтому само по себе кэширование ничего не даст 350~700 [ns] на ячейку матрицы), а умный чистый numpy -векторизованный код может обработать матрично-векторный продукт менее чем за 1 [ns] на клетку даже на самом большом [PSPACE] Следы

Это критерий для сравнения.

(Профилирование лучше показать здесь неопровержимые факты, но этот принцип хорошо известен заранее, без проверки того, как можно TB данных на GPU-ткань, просто чтобы реализовать это самостоятельно.)

Худшие из плохих новостей:

Учитывая масштабы памяти матрицы A худший ожидаемый эффект состоит в том, что разреженная организация хранения матричного представления, скорее всего, опустошит большинство, если не все, возможное повышение производительности, достижимое за счет numba-векторные трюки для представлений с плотной матрицей, поскольку вероятность эффективного повторного использования строки кэша, извлеченной из памяти, будет почти нулевой, а разреженность также нарушит любой простой способ добиться компактного отображения векторизованных операций, и вряд ли они смогут получить легко переводится на передовые аппаратные ресурсы векторной обработки CPU.

Инвентаризация решаемых задач:

  • всегда лучше предварительно выделить вектор Ax = np.zeros_like( A[:,0] ) и передать его в качестве другого параметра в numba.jit() скомпилированные части кода, чтобы избежать повторной оплаты дополнительных [PTIME,PSPACE] - затраты на создание (опять же) новых выделений памяти (тем более, если вектор подозревается в использовании внутри процесса итеративной оптимизации, организованной извне)
  • всегда лучше указывать (чтобы сузить универсальность, ради результирующей производительности кода)
    По крайней мере numba.jit( "f8[:]( f4[:], f4[:,:], ... )" ) директивы интерфейса вызова
  • всегда просматривайте все numba.jit() -опции доступны и их соответствующие значения по умолчанию (может изменить версию на версию) для вашей конкретной ситуации (отключение GIL и лучшее согласование целей с numba + аппаратные возможности всегда помогут в численно интенсивных частях кода) 
@jit(   signature = [    numba.float32( numba.float32, numba.int32 ),                                   #          # [_v41] @decorator with a list of calling-signatures
                         numba.float64( numba.float64, numba.int64 )                                    #
                         ],    #__________________ a list of signatures for prepared alternative code-paths, to avoid a deferred lazy-compilation if undefined
        nopython = False,      #__________________ forces the function to be compiled in nopython mode. If not possible, compilation will raise an error.
        nogil    = False,      #__________________ tries to release the global interpreter lock inside the compiled function. The GIL will only be released if Numba can compile the function in nopython mode, otherwise a compilation warning will be printed.
        cache    = False,      #__________________ enables a file-based cache to shorten compilation times when the function was already compiled in a previous invocation. The cache is maintained in the __pycache__ subdirectory of the directory containing the source file.
        forceobj = False,      #__________________ forces the function to be compiled in object mode. Since object mode is slower than nopython mode, this is mostly useful for testing purposes.
        locals   = {}          #__________________ a mapping of local variable names to Numba Types.
        ) #____________________# [_v41] ZERO <____ TEST *ALL* CALLED sub-func()-s to @.jit() too >>>>>>>>>>>>>>>>>>>>> [DONE]
 def r...(...):
      ...
Источник

Нумба была обновлена ​​и prange()работает сейчас! (Я отвечаю на свой вопрос.)

Улучшения в возможностях параллельных вычислений Numba обсуждаются в этом посте от 12 декабря 2017 года. Вот соответствующий фрагмент из блога:

Давным-давно (более 20 выпусков!) В Numba была поддержка идиомы для написания параллельных циклов, называемых prange(), После серьезного рефакторинга базы кода в 2014 году эту функцию пришлось удалить, но с тех пор она стала одной из наиболее часто запрашиваемых функций Numba. После того, как разработчики Intel распараллелили выражения массива, они поняли, что возвращение prange было бы довольно легко

Используя Numba версии 0.36.1, я могу распараллелить мою смущающую параллель for-loop, используя следующий простой код:

@numba.jit(nopython=True, parallel=True)
def csrMult_parallel(x,Adata,Aindices,Aindptr,Ashape): 

    numRowsA = Ashape[0]    
    Ax = np.zeros(numRowsA)

    for i in numba.prange(numRowsA):
        Ax_i = 0.0        
        for dataIdx in range(Aindptr[i],Aindptr[i+1]):

            j = Aindices[dataIdx]
            Ax_i += Adata[dataIdx]*x[j]

        Ax[i] = Ax_i            

    return Ax

В моих экспериментах распараллеливание for-loop заставил функцию выполняться примерно в восемь раз быстрее, чем версия, которую я разместил в начале моего вопроса, которая уже использовала Numba, но не была распараллелена. Более того, в моих экспериментах распараллеленная версия примерно в 5 раз быстрее, чем команда Ax = A.dot(x) который использует функцию умножения разреженных матриц-векторов Сципи. Numba разбил scipy, и у меня наконец есть подпрограмма умножения редких матриц-векторов на Python, такая же быстрая, как MATLAB.

Источник
Другие вопросы по тегам