Как улучшить производительность алгоритма иглмен -wunsch в CUDA

Question

Мне нужен совет по оптимизации моей реализации алгоритма Needleman-Wunsch в CUDA.

Я хочу оптимизировать свой код для заполнения матрицы DP в CUDA. Из-за зависимости данных между матричными элементами (каждый следующий элемент зависит от других, оставшихся до него, вплоть до него и слева от него), я заполняю антидиагональные матричные элементы параллельно следующим образом:

__global__ void alignment_kernel(int *T, char *A, char *B, int t_M, int t_N, int d) { 
    int row = BLOCK_SIZE_Y * blockIdx.y + threadIdx.y; 
    int col = BLOCK_SIZE_X * blockIdx.x + threadIdx.x; 

    // Check if we are inside the table boundaries. 
    if (!(row < t_M && col < t_N)) { 
    return; 
    } 

    // Check if current thread is on the current diagonal 
    if (row + col != d) { 
    return; 
    } 

    int v1; 
    int v2; 
    int v3; 
    int v4; 
    v1 = v2 = v3 = v4 = INT_MIN; 

    if (row > 0 && col > 0) { 
    v1 = T[t_N * (row - 1) + (col - 1)] + score_matrix_read(A[row - 1], B[col - 1]); 
    } 
    if (row > 0 && col >= 0) { 
    v2 = T[t_N * (row - 1) + col] + gap; 
    } 
    if (row >= 0 && col > 0) { 
    v3 = T[t_N * row + (col - 1)] + gap; 
    } 
    if (row == 0 && col == 0) { 
    v4 = 0; 
    } 

    // Synchronize (ensure all the data is available) 
    __syncthreads(); 

    T[t_N * row + col] = mmax(v1, v2, v3, v4); 
} 

Тем не менее, одна очевидная проблема с моим кодом заключается в том, что я выполняю несколько вызовов ядра (код ниже). До сих пор я не знаю, как использовать потоки для обработки антидиагональной синхронно, не делая этого. Я думаю, что это серьезная проблема для достижения лучшей производительности.

// Invoke kernel. 
    for (int d = 0; d < t_M + t_N - 1; d++) { 
    alignment_kernel<<< gridDim, blockDim >>>(d_T, d_A, d_B, t_M, t_N, d); 
    //CHECK_FOR_CUDA_ERROR(); 
    } 

Как я могу обработать анти-диагонали параллельно и, возможно, с использованием разделяемой памяти, чтобы увеличить ускорение?

Помимо этой проблемы, есть ли способ сделать задний шаг следа алгоритма иглы-вунша параллельно?

Answer 1

В настоящее время я работаю над параллельной реализацией алгоритма Needleman Wunsch (для использования в анализаторе генома). В зависимости от того, сколько выравниваний вы будете делать, может быть более эффективным сделать одно выравнивание для потока.

Однако здесь есть publication, который выполняет одно выравнивание параллельно (на графическом процессоре). Новизна их подхода заключается в том, что он не генерирует матрицу последовательно, а по диагонали. Они не говорят о том, как они отступают в своей публикации. Они отправляют матрицу обратно на хост после ее создания, затем выполняют обратный путь с использованием процессора. Я думаю, что откат на графическом процессоре будет ужасно неэффективным из-за ветвления.