Patrones de acceso a datos que realmente hacen enojar a la CPU

 (blog.weineng.me)
1 puntos por GN⁺ 3 시간 전 | 1 comentarios | Compartir por WhatsApp
  • Incluso con un bucle que suma los mismos enteros, cambiar solo el orden de acceso puede alterar mucho el tiempo de ejecución, y el experimento muestra que es posible crear una permutación más de 30% más lenta que el acceso aleatorio
  • El acceso lineal es rápido, con 133 millones de ciclos, mientras que el acceso aleatorio se vuelve hasta 1,570 millones de ciclos porque a la CPU le cuesta predecir la siguiente ubicación
  • Si se separan los accesos usando líneas de caché y límites de página, se debilitan el prefetcher y la reutilización de caché, y debido a las características de la caché asociativa por conjuntos, la capacidad útil efectiva de L1d se reduce a alrededor de 768 B
  • Con un stride de página de 8, también se rompe la localidad de las líneas de caché de PTE y se registran 2,060 millones de ciclos, convirtiéndose en un patrón peor que un simple shuffle aleatorio
  • Un patrón aproximado orientado a conflictos de bank/row de DRAM fue un poco más lento, con 2,080 millones de ciclos, pero es difícil controlarlo por completo porque el mapeo de DRAM de las direcciones físicas depende de la plataforma

Condiciones y criterios del experimento

  • El objetivo es crear el tiempo de ejecución más lento cambiando solo la permutación de positions en una función fija accumulator que suma enteros del arreglo data
  • Se excluye el tiempo de generación de positions; solo se mide el tiempo de ejecución de la función de acumulación con el contador de ciclos rdtsc
  • El tamaño de los datos es de 2^26 enteros uint32_t
    • Se usan 65,536 páginas
    • Cada página tiene 4,096 bytes
    • En cada página caben 1,024 enteros
  • Las huge pages están desactivadas
  • La máquina de medición es un sistema x86_64 basado en Intel Core Ultra 7 268V
    • 8 CPU
    • L1d total de 320 KiB, L1i total de 512 KiB
    • L2 total de 14 MiB
    • L3 de 12 MiB
  • El código completo está en el repositorio de GitHub, y el ejemplo se ejecuta con g++ -std=c++2a -O3 slowest.cc && taskset -c 3 sudo ./a.out
  • El bucle principal es una forma simple que suma en orden el data[pos] al que apunta positions[i]

Diferencia entre acceso lineal y acceso aleatorio

  • El patrón más simple, linear, accede el arreglo de principio a fin con positions[i] = i
  • El acceso lineal tardó 132,752,394 ciclos y está entre los más rápidos, porque la CPU está fuertemente optimizada para el acceso secuencial
  • Si positions se convierte en una permutación aleatoria con fisher_yates_shuffle, a la CPU le resulta difícil predecir los datos que se accederán después
  • El acceso aleatorio tardó 1,572,108,618 ciclos, más de 10 veces más que el acceso lineal
  • El experimento va más allá de eso y verifica si se puede crear deliberadamente una permutación peor que la aleatoria

Separar accesos por línea de caché y por página

  • El primer patrón de degradación acomoda positions para que los accesos consecutivos siempre estén separados por una línea de caché
  • Este patrón usa solo un entero de 4 bytes en una línea de caché de 64 bytes y luego pasa a la siguiente línea de caché
    • Para cuando vuelve a la misma línea de caché, es muy probable que los datos reutilizables ya hayan sido expulsados de la caché
  • El acceso con separación de líneas de caché tardó 718,804,156 ciclos, más de 4 veces más que el escaneo lineal
  • Aun así, en este caso el prefetcher de hardware puede detectar un patrón de streaming simple sobre data y traer por adelantado futuras líneas de caché
  • Muchos prefetchers de datos de hardware de Intel no hacen prefetch que cruce límites de página de 4 KiB
  • El siguiente patrón separa los accesos no por línea de caché, sino por páginas completas
    • Cada página tiene 4,096 bytes
    • Primero se accede el mismo offset de cada página, con una forma page_index * elements_per_page + element_index
  • El acceso con separación de páginas se vuelve mucho más lento, con 1,411,153,154 ciclos

Caché asociativa por conjuntos y distancia de reutilización

  • La caché L1d por núcleo de la máquina del experimento es de 48 KB, 12-way, con 64 sets
  • Como L1d tiene 64 sets, las direcciones A y A + 4096 bytes se mapean al mismo set de L1d
    • 4,096 bytes equivalen a 64 sets * 64-byte cache line
  • El stride a nivel de página hace que cada bucle interno no se distribuya uniformemente por los 64 sets completos, sino que golpee continuamente el mismo set
  • Como un set solo tiene 12 ways, si compiten más de 12 líneas de caché activas, la CPU tiene que expulsar y recargar líneas repetidamente
  • Aunque la capacidad total de L1d es de 48 KB, la capacidad de L1d útil en este patrón de acceso es de alrededor de 768 B, es decir, 12 ways * 64B
  • El patrón separated_by_a_page accede 65,536 líneas de caché antes de volver a la misma línea de caché, por lo que la distancia de reutilización de línea de caché es 65,536
  • El patrón separated_by_a_page_and_cacheline, que además separa las líneas de caché dentro de la página, aumenta la distancia de reutilización hasta 65536 pages * 4096 page size / 64 cacheline size
  • Sin embargo, el resultado fue 1,408,519,172 ciclos, casi igual que el acceso a nivel de página
  • El experimento se ejecutó en el core 3, que tiene L2 de 2.5 MB y L1 de 48 KB
    • Al recorrer 65,536 páginas una vez, se accede a 4 MB de datos
    • Esto supera la capacidad de L1/L2 privada de ese núcleo
    • Es poco probable que la siguiente línea de caché necesaria siga en la caché privada
  • La reutilización de la caché privada solo se puede esperar cuando la distancia de reutilización de línea de caché es menor que aproximadamente ((2560+48)*1024/64), es decir, cerca de 40 mil

Molestar también al stride de página, PTE y DRAM

  • La siguiente variante es el patrón separated_by_stride_pages_and_cacheline, que accede no a páginas consecutivas sino con una separación de N páginas
  • Tras medir varios strides, el peor resultado apareció cuando el stride de página era 8, y fue más lento que el acceso aleatorio
  • Ejecutado por separado con -DSTRIDE=8, tardó 2,058,425,640 ciclos
  • Una posible razón del pico con stride 8 es la traducción de direcciones
    • El acceso a direcciones virtuales es traducido por la MMU a direcciones físicas
    • Para la traducción se usa una page table entry (PTE)
    • Una PTE tiene 8 bytes, y en una línea de caché caben 8 PTE
    • Con un stride de 8 páginas, se considera que en cada acceso se trae no solo la línea de caché de datos, sino también una línea de caché separada para el mapeo de página
  • El último paso es un intento de interferir también con el comportamiento del controlador de DRAM
  • DRAM se compone de channel, rank, chip, bank, row y column
    • Dentro de un bank hay varias rows
    • Para acceder a una row específica, se activa esa row y se copia al row buffer
    • Para acceder a otra row en el mismo bank, hay que cerrar la row existente con precharge y activar la nueva row
  • Si se accede alternadamente a distintas rows dentro del mismo bank, ocurre un row-buffer conflict y la respuesta del controlador de DRAM se vuelve más lenta
  • En cambio, acceder a una row ya abierta produce un row-buffer hit, y al usar varios banks al mismo tiempo el memory controller puede solapar trabajo
  • La estrategia para crear un patrón lento es la siguiente
    • Convertir el virtual page number a physical frame number (PFN) mediante la page table
    • Conservar el page offset para construir la dirección física
    • Interpretar la dirección física como DRAM channel, rank, bank group, bank, row y column
    • Acceder repetidamente a distintas rows dentro del mismo bank para forzar precharge y activation en casi cada solicitud
  • Sin embargo, el mapeo desde la dirección física hacia DRAM channel, rank, bank y row no está documentado y depende de la plataforma
    • Puede variar según CPU, tipo de memoria, configuración de BIOS/firmware, configuración de channel/rank y address hashing
    • Se pueden usar herramientas como DRAMA o Sudoku, pero no fue posible hacerlas funcionar en esta máquina de pruebas
  • Basándose en el paper de DRAMA y en experimentos locales, se hizo una aproximación usando 4 bank groups, 4 banks por group y DRAM_ROW_SHIFT = 18
  • El patrón que también considera conflictos de DRAM bank/row fue consistentemente un poco más lento que stride 8, con 2,082,308,014 ciclos, pero la diferencia no es grande
  • Hay varias limitaciones que impidieron crear un row conflict completo
    • Las estimaciones de bank group hash, bank hash y row shift pueden no ser precisas
    • Un stride de 8 páginas implica accesos con una separación de unos 32 KB, por lo que es difícil que estén en la misma DRAM row
    • Debido al bank hashing de Intel, en la práctica se terminan usando varios banks al mismo tiempo
  • Un ejemplo de ejecución completa muestra estos resultados
    • linear: 132,752,394
    • fisher_yates_shuffle: 1,572,108,618
    • separated_by_a_cacheline: 718,804,156
    • separated_by_a_page: 1,411,153,154
    • separated_by_a_page_and_cacheline: 1,408,519,172
    • stride=8 separated_by_stride_pages_and_cacheline: 2,058,425,640
    • separated_by_stride_bank_conflicts_and_cacheline: 2,082,308,014
  • Al degradar sucesivamente caché, prefetcher, reutilización de líneas de caché, acceso a PTE y características de DRAM bank/row, se puede crear un patrón de suma 33% más lento que el acceso aleatorio
  • También hay formas de volver más lenta la acumulación, como cambiar a un modo de ahorro de energía, pero eso es independiente del experimento de cambiar solo el patrón de acceso

Lecturas relacionadas

1 comentarios

 
GN⁺ 3 시간 전
Comentarios en Lobste.rs

  • Me pareció divertido leerlo, como si así se viera una investigación interna de desarrollo de Windows 11 /s

  • Aprendí esto mientras creaba https://github.com/ob/cache

    • Me da curiosidad cómo interpretar dos frases del README
      Una dice que vio por primera vez la técnica para generar cifras de latencia en el ejercicio 5.2 de la página 476 de Computer Architecture: A Quantitative Approach, y la otra dice que la idea vino de la tesis doctoral de Rafael Héctor Saavedra‑Barrera
      Quisiera confirmar si hablan de cosas distintas, si se contradicen, o si son lo mismo y Saavedra-Barrera aparece citado en CA:AQA
      Tampoco queda claro si el programa Claude quedó excluido de la redacción del README, y como también figura como contribuidor del repositorio, primero quisiera verificar si la referencia es real

  • Si quieres experimentar con accesos a jerarquías de caché personalizadas, también recomiendo el simulador que hice
    https://github.com/TheCloudlet/Stratum

  • Me pregunto cómo separaron el overhead de calcular los índices del costo real de acceso

    • Si la pregunta es cómo medir solo los ciclos del accumulator sin incluir también el tiempo de crear positions, usé una macro que primero ejecuta reset y arrange_positions, y luego pone solo accumulator(data, positions) entre rdtsc_start() y rdtsc_end()
      Después imprime el resultado, verifica sum == linear_scan_sum y evita que se elimine por optimización con do_not_optimize(sum)

  • Si lo hacemos también con los patrones de acceso a datos que enseñan los profesores, primero hay que crear una clase SafeNumber.java y se necesita un miembro add(SafeNumber b)
    El próximo semestre parece que aprenderemos una arquitectura que pone esto detrás de Redis para lograr rendimiento a escala web
    Gracias a Claude pasé el benchmark a Java, y Java SafeNumber[] fue aproximadamente 3.6 veces más lento que uint32_t[] de C++ en acceso lineal, y en Fisher-Yates shuffle fue 52.2 veces más lento que el acceso lineal en C++
    En tiempos absolutos, para 67 millones de elementos, fueron: C++ lineal 10,258,584 ns, Java lineal 36,740,667 ns, C++ shuffle 264,856,042 ns y Java shuffle 535,724,208 ns; me impresionó que fuera “apenas 4 veces” en vez de más

    • El multiplicador de Java no es muy bueno, pero cuando salga Project Valhalla quizás pueda acercarse más