Алгоритм Флойда-Уоршалла на графическом процессоре с использованием numba

Я пишу оптимизированный алгоритм Флойда-Уоршалла на графическом процессоре с использованием numba. Мне нужно, чтобы он работал за несколько секунд в случае 10к матриц. Сейчас обработка сделана примерно за 60-е годы. Вот мой код:

def calcualte_distance_to_all_gpu(matrix):
    threadsperblock = (32, 32)
    blockspergrid_x = math.ceil(matrix.shape[0]/ threadsperblock[0])
    blockspergrid_y = math.ceil(matrix.shape[1] / threadsperblock[1])
    blockspergrid = (blockspergrid_x, blockspergrid_y)
    calculate_distance_to_all_cuda[blockspergrid, threadsperblock](matrix)


@cuda.jit
def calculate_distance_to_all_cuda(matrix):
    i, j = cuda.grid(2)

    N = len(matrix)
    for k in prange(N):
        if i < matrix.shape[0] and j < matrix.shape[1]:
            if matrix[i, k] + matrix[k, j] < matrix[i, j]:
                matrix[i, j] = matrix[i, k] + matrix[k, j]

Честно говоря, я новичок в написании скриптов на GPU, так что у вас есть идеи, как сделать этот код еще быстрее? Я также заметил на своем графическом процессоре, что во время обработки есть только небольшой пик до 100%, а затем он перестает быть занятым, поэтому, возможно, проблема в отправке данных с процессора на графический процессор? Если да, можно ли как-нибудь оптимизировать этот процесс? Или, может быть, мне стоит использовать другой алгоритм для этой задачи?


python optimization gpu numba floyd-warshall
person Aleksander    schedule 05.12.2020    source источник

Ответы (1)


arrow_upward
0
arrow_downward

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

https://moorejs.github.io/APSP-in-parallel/#References < / а>

Через несколько дней я перепишу этот подход в python numba и опубликую в комментарии;).

person Aleksander    schedule 10.12.2020