Tiempo de ejecución variable de un programa en C

La implementación de mi (simd) toma una cantidad de tiempo variada, aunque se ejecuta para una entrada fija. El tiempo de ejecución varía entre, por ejemplo, 100 millones de ciclos de reloj a 120 millones de ciclos de reloj. El programa llama a una función alrededor de 600 veces, y la parte más costosa de la función es en la que se accede a la memoria ~ 2000 veces. Por lo tanto, la participación general de la memoria en bastante alto en mi programa.Tiempo de ejecución variable de un programa en C

¿La variación en el tiempo de ejecución se debe a los patrones de acceso a la memoria/contenido de la memoria inicial?

Utilicé valgrind para analizar el perfil de mi programa. Muestra que cada acceso a la memoria requiere aproximadamente 8 instrucciones. ¿Esto es normal?

La siguiente es la pieza de código (función) que se llama 600 veces. Mulprev [32] [20] es la matriz a la que se accede la mayor cantidad de veces.

j = 15; 
u3v = _mm_set_epi64x (0xF, 0xF); 
while (j + 1) 
{ 

    l = j << 2; 
    for (i = 0; i < 20; i++) 
    { 
     val1v = _mm_load_si128 ((__m128i *) &elm1v[i]);  
     uv = _mm_and_si128 (_mm_srli_epi64 (val1v, l), u3v); 
     u1 = _mm_extract_epi16 (uv, 0); 
     u2 = _mm_extract_epi16 (uv, 4) + 16; 

     for (ival = i, ival1 = i + 1, k = 0; k < 20; k += 2, ival += 2, ival1 += 2) 
     { 
      temp11v = _mm_load_si128 ((__m128i *) &mulprev[u1][k]); 
      temp12v = _mm_load_si128 ((__m128i *) &mulprev[u2][k]); 

      val1v = _mm_load_si128 ((__m128i *) &res[ival]); 
      val2v = _mm_load_si128 ((__m128i *) &res[ival1]); 

      bv = _mm_xor_si128 (val1v, _mm_unpacklo_epi64 (temp11v, temp12v)); 
      av = _mm_xor_si128 (val2v, _mm_unpackhi_epi64 (temp11v, temp12v)); 

      _mm_store_si128 ((__m128i *) &res[ival], bv);         
      _mm_store_si128 ((__m128i *) &res[ival1], av); 
     } 
    } 

    if (j == 0) 
     break; 
    val0v = _mm_setzero_si128(); 

    for (i = 0; i < 40; i++) 
    { 
     testv = _mm_load_si128 ((__m128i *) &res[i]); 
     val1v = _mm_srli_epi64 (testv, 60); 
     val2v = _mm_xor_si128 (val0v, _mm_slli_epi64 (testv, 4)); 
     _mm_store_si128 (&res[i], val2v); 
     val0v = val1v; 
    } 
    j--; 
}

Quiero reducir el tiempo de cálculo de mi programa. ¿Alguna sugerencia?

Fuente

2011-01-30 anup

Necesita publicar el código real si quiere ayuda para optimizarlo –

Consulte la pregunta editada ... – anup

Está realizando casi ningún cálculo entre cargas y almacenes, por lo tanto, su tiempo de ejecución probablemente estará dominado por el costo de E/S hacia/desde el caché/memoria. Lo que es peor, su conjunto de datos parece ser relativamente pequeño. Probablemente, la única manera de optimizar esto es mejorar el patrón de acceso a la memoria (hacer accesos secuenciales siempre que sea posible y garantizar que las líneas de caché no se desperdicien, etc.) y/o combinar estas operaciones con otro código que funcione en el mismo conjunto de datos antes/después de esta rutina (por lo que el costo de las cargas/tiendas en algo amortizado).

EDITAR: tenga en cuenta que le di una respuesta muy similar cuando hizo la misma pregunta para una versión aparentemente anterior de esta rutina: How to make the following code faster - parece haber olvidado que su principal problema de rendimiento aquí es el acceso a la memoria, no cálculo.

Fuente

2011-01-30 23:37:12

Esto. Mucho esto. –

Las computadoras son complicadas. Podría ser fácilmente que los procesos en segundo plano interfieran de alguna manera. Es difícil sugerir mejoras sin información adicional. En general, las mejores optimizaciones son las de alto nivel. Elija mejores algoritmos, minimice operaciones costosas. Si no cree que haya mucho margen de mejora allí, no espere ganancias demasiado altas. Usted dice que sus accesos de memoria toman muchos ciclos. Podría sugerir que use punteros restringidos siempre que sea posible, pero es difícil dar consejos generales sobre problemas de optimización. Tienes que probar las cosas tú mismo.

Fuente

2011-01-30 14:03:07 Oystein

Iba a sugerir lo mismo (no hay garantía de qué procesos se ejecutarán en un sistema operativo multitarea, si tienen el misma prioridad), pero luego leí esto: http://valgrind.org/docs/manual/cl-manual.html#cl-manual.cycles Aparentemente, los ciclos en valgrind no son lo mismo que los ciclos del procesador (?) – esaj

@esaj: Quise decir ciclos de reloj ... – anup

@esaj ese enlace describe ciclos de gráficos http://en.wikipedia.org/wiki/Cycle_(graph_theory) en el gráfico de llamadas del programa. –

8 ciclos para acceder a la memoria es bastante tiempo. Otro proceso puede estar teniendo un impacto negativo en los cachés de la CPU, lo que ocasiona que el programa pierda muchas caché, o si su memoria está asignada dinámicamente, es posible que vea penalizaciones de acceso a la memoria no alineadas.

Podría ser cualquier cosa.

Fuente

2011-01-30 14:50:20 James

¿Puede darme un tiempo de lectura de caché L1 típico con un golpe asumido? Si los datos están en caché, se garantiza que el tiempo de recuperación sea similar independientemente de su ubicación en el caché. ¿Alguna referencia? – anup

8 ciclos es * NO * un tiempo prolongado para acceder a la memoria.En el caso de un error de caché que llega hasta la DRAM, puede tomar 100 ciclos y más en una CPU moderna. –

@anup, @Axel: la latencia para un golpe L1 en las CPU modernas suele ser ~ 4 ciclos (consulte las Guías de optimización de Intel o la documentación específica del procesador para obtener más detalles). Vale la pena señalar que en realidad dijo "[Valgrind] muestra que cada acceso a la memoria requiere unas 8 instrucciones". Las instrucciones no son ciclos; una CPU Intel moderna puede potencialmente retirar 4 instrucciones por ciclo, por lo que "8 instrucciones" en realidad podrían significar solo un par de ciclos, en línea con un golpe L1. Sin embargo, no estoy familiarizado con Valgrind, así que no sé cómo se mide realmente. –

Tiempo de ejecución variable de un programa en C

Respuesta

Cuestiones relacionadas