Estoy tratando de aprovechar las nuevas instrucciones AVX2 GATHER para acelerar una matriz dispersa: multiplicación de vectores. La matriz está en formato CSR (o Yale) con un puntero de fila que apunta a una matriz de índice de columna que a su vez contiene las columnas. El código C para tal mat-vec mul se ve así:
for (int row = 0; row < n_rows - 1; row++) { double rowsum = 0; for (int col = row_ptr[row]; col < row_ptr[row + 1]; col++) { rowsum += values[col] * x[col_indices[col]]; } result[row] = rowsum; }Ahora mi objetivo es acelerar esto con los intrínsecos de AVX2. El siguiente código funciona con la última versión de Intel o GCC, según https://blog.fox-toolkit.org/?p=174 . Eliminé el resto aquí porque todas mis filas se alinean en 4 dobles (columnas% 4==0) de todos modos (suerte mía). También tengo el código que trata con el resto si alguien está interesado, pero el punto es que el código es en realidad un poco más lento. Verifiqué el desmontaje y para la versión anterior solo se generan instrucciones FP y para mi código AVX2 todas las operaciones AVX2 aparecen como se esperaba. Incluso con matrices pequeñas que caben en el caché, la versión AVX2 no es buena. Estoy desconcertado aquí...
double* value_base = &values[0]; double* x_base = &x[0]; int* index_base = &col_indices[0]; for (int row = 0; row < n_rows - 1; row++) { int col_length = row_ptr[row + 1] - row_ptr[row]; __m256d rowsum = _mm256_set1_pd(0.); for (int col4 = 0; col4 < col_length; col4 += 4) { // Load indices for x vector(const __m128i*) __m128i idxreg = _mm_load_si128((const __m128i*)index_base); // Load 4 doubles from x indexed by idxreg (AVX2) __m256d x_ = _mm256_i32gather_pd(x_base, idxreg, 8); // Load 4 doubles linear from memory (value array) __m256d v_ = _mm256_load_pd(value_base); // FMA: rowsum += x_ * v_ rowsum = _mm256_fmadd_pd(x_, v_, rowsum); index_base += 4; value_base += 4; } __m256d s = _mm256_hadd_pd(rowsum, rowsum); result[row] = ((double*)&s)[0] + ((double*)&s)[2]; // Alternative (not faster): // Now we split the upper and lower AVX register, and do a number of horizontal adds //__m256d hsum = _mm256_add_pd(rowsum, _mm256_permute2f128_pd(rowsum, rowsum, 0x1)); //_mm_store_sd(&result[row], _mm_hadd_pd( _mm256_castpd256_pd128(hsum), _mm256_castpd256_pd128(hsum) ) ); }Cualquier sugerencia es bienvenida.
muchas gracias, cris
Reunirse en Haswell es lento. Implementé una búsqueda de LUT de índice de 8 bits de valores de 16 bits (para GF16 multiplicado por par2) de diferentes maneras, para averiguar qué es lo más rápido. En Haswell, la versión VPGATHERDD tardó 1,7 veces más que la versión movd / pinsrw . (Solo se necesitaron un par de instrucciones VPUNPCK / shift más allá de las reuniones). Codifique aquí, si alguien quiere ejecutar el punto de referencia .
Como es común cuando se introduce una instrucción por primera vez, no dedican una gran cantidad de silicio para que sea súper rápida. Está ahí solo para obtener soporte HW, por lo que se puede escribir código para usarlo. Para un rendimiento ideal en todas las CPU, debe hacer lo que hizo x264 para pshufb : tener un indicador SLOW_SHUFFLE para CPU como Core2, y tenerlo en cuenta en su mejor configuración de puntero de función de búsqueda de rutina, en lugar de solo lo que insns una CPU apoya
Para proyectos menos fanáticos de tener versiones de asm ajustadas para cada CPU en la que puedan ejecutarse, la introducción de una versión sin aceleración de una instrucción hará que la gente la use antes, de modo que cuando llegue el próximo diseño y sea rápido, más código se acelerará. Lanzar un diseño como Haswell donde reunir es en realidad una desaceleración es un poco arriesgado. ¿Quizás querían ver cómo la gente lo usaría? Aumenta la densidad del código, lo que ayuda cuando la recopilación no está en un ciclo cerrado.
Se supone que Broadwell tiene una implementación de recopilación más rápida, pero no tengo acceso a una. El manual de Intel que enumera la latencia/rendimiento para obtener instrucciones dice que la recopilación de Broadwell es aproximadamente 1,6 veces más rápida, por lo que aún sería un poco más lento que un bucle hecho a mano que cambia/desempaqueta los índices en los registros GP y los usa para PINSRW en vectores.
Si la gather pudiera aprovechar los casos en los que varios elementos tenían el mismo índice, o incluso un índice que apuntaba al mismo bloque de búsqueda 32B, podría haber grandes aceleraciones dependiendo de los datos de entrada.
Esperemos que Skylake mejore aún más. Pensé que había leído algo que decía que lo haría, pero al verificar, no encontré nada.
RE: Matrices dispersas: ¿no hay un formato que duplique los datos, para que pueda hacer lecturas contiguas para filas o columnas? No es algo para lo que haya tenido que escribir código, pero creo que lo he visto mencionado en algunas respuestas.