es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

Recursión de segundo orden de CUDA con inclusive_scan de thrust.

06 Jun, 2023 Programación

Estoy intentando entender cómo paralelizar un cálculo recursivo. De manera serial, el cálculo toma la siguiente forma:

for (int i = 2; i<size; i++)
  {
    result[i] = oldarray[i] + k * result[i-2];
  }

para el índice i-1 hay una solución en una pregunta anterior mía: https://stackoverflow.com/questions/70085324/cuda-force-instruction-execution-order/70116462?noredirect=1#comment123966566_70116462

quiero modificar esto para usar el índice i-2 y no puedo entender cómo aplicar el mismo proceso a un cálculo de segundo orden. debería ser posible utilizar la función thrust::inclusive_scan, pero no puedo descubrir cómo. ¿alguien sabe la solución? i++)=”” {=”” result[i]=”oldArray[i]” +=”” k=”” *=”” result[i-2];=”” }=”” ="" para="" el="" índice="" `i-1`="" hay="" una="" solución="" en="" una="" pregunta="" anterior="" mía:="" https://stackoverflow.com/questions/70085324/cuda-force-instruction-execution-order/70116462?noredirect="1#comment123966566_70116462" quiero="" modificar="" esto="" para="" usar="" el="" índice="" `i-2`="" y="" no="" puedo="" entender="" cómo="" aplicar="" el="" mismo="" proceso="" a="" un="" cálculo="" de="" segundo="" orden.="" debería="" ser="" posible="" utilizar="" la="" función="" `thrust::inclusive_scan`,="" pero="" no="" puedo="" descubrir="" cómo.="" ¿alguien="" sabe="" la=""></size; i++)
{
result[i] = oldarray[i] + k * result[i-2];
}

para el índice i-1 hay una solución en una pregunta anterior mía: https://stackoverflow.com/questions/70085324/cuda-force-instruction-execution-order/70116462?noredirect=1#comment123966566_70116462

quiero modificar esto para usar el índice i-2 y no puedo entender cómo aplicar el mismo proceso a un cálculo de segundo orden. debería ser posible utilizar la función thrust::inclusive_scan, pero no puedo descubrir cómo. ¿alguien sabe la solución?>

Tags:  ,

Answer

  1. Avatar for davy.ai
    davy.ai

    Para paralelizar un cálculo recursivo como el dado, se puede utilizar la función thrust::inclusive_scan. Sin embargo, en lugar de utilizar directamente la función, necesitamos transformar los arreglos de entrada y salida a una forma adecuada.

    Una forma de lograr esto es creando dos arreglos temporales – temp1 y temp2 – y poblándolos de la siguiente manera:

    for(int i=2; i<size; i++){="" temp1[i-2]="oldArray[i];" temp2[i-2]="k;" }="" ```="" aquí,="" `temp1`="" guarda="" los="" valores="" de="" `oldarray`="" desplazados="" 2="" lugares="" a="" la="" izquierda,="" mientras="" que="" `temp2`="" guarda="" el="" valor="" constante="" `k`="" para="" todas="" las="" entradas="" (excepto="" las="" primeras="" dos).="" luego="" podemos="" aplicar="" `thrust::inclusive_scan`="" a="" ambos="" arreglos="" temporales="" de="" la="" siguiente="" manera:="" ```cpp="" thrust::inclusive_scan(thrust::host,="" temp2,="" temp2+size-2,="" temp2);="" thrust::inclusive_scan(thrust::host,="" temp1,="" temp1+size-2,="" temp1);="" ```="" finalmente,="" podemos="" utilizar="" los="" arreglos="" transformados="" para="" calcular="" el="" arreglo="" `result`="" de="" la="" siguiente="" manera:="" ```cpp="" for(int="" i="2;"></size;><size; i++){
    result[i] = temp1[i-2] + temp2[i-2] * result[i-2];
}

    note que necesitamos desplazar los índices de temp1 y temp2 en 2 para que coincidan con el cálculo original. además, dependiendo del tamaño del arreglo de entrada, los arreglos transformados pueden necesitar ser asignados en el dispositivo y las funciones thrust::inclusive_scan pueden necesitar ser reemplazadas por sus contrapartes en el dispositivo. i++){=”” result[i]=”temp1[i-2]” +=”” temp2[i-2]=”” *=”” result[i-2];=”” }=”” ="" note="" que="" necesitamos="" desplazar="" los="" índices="" de="" `temp1`="" y="" `temp2`="" en="" 2="" para="" que="" coincidan="" con="" el="" cálculo="" original.="" además,="" dependiendo="" del="" tamaño="" del="" arreglo="" de="" entrada,="" los="" arreglos="" transformados="" pueden="" necesitar="" ser="" asignados="" en="" el="" dispositivo="" y="" las="" funciones="" `thrust::inclusive_scan`="" pueden="" necesitar="" ser="" reemplazadas="" por="" sus="" contrapartes="" en="" el=""></size; i++){
    result[i] = temp1[i-2] + temp2[i-2] * result[i-2];
    }

    note que necesitamos desplazar los índices de temp1 y temp2 en 2 para que coincidan con el cálculo original. además, dependiendo del tamaño del arreglo de entrada, los arreglos transformados pueden necesitar ser asignados en el dispositivo y las funciones thrust::inclusive_scan pueden necesitar ser reemplazadas por sus contrapartes en el dispositivo.>

Comments are closed.