El predictor de ramas 2-ahead de Zen 5: una idea de hace 30 años que abre nuevas posibilidades
(chipsandcheese.com)- AMD Zen 5 introdujo el 2-Ahead Branch Predictor dentro de un rediseño completo de la arquitectura Zen, trayendo de vuelta a la expansión del frontend x86 moderno la investigación de los años 90 sobre predicción anticipada de ramas en múltiples bloques
- La predicción de ramas es un mecanismo que permite que el frontend del CPU siga trayendo instrucciones incluso antes de que se conozca el resultado de una rama condicional; un fallo de predicción deriva en un vaciado del pipeline y en el costo de reiniciar
- Zen 5 cuenta con dos fetch pipes de 32 bytes/ciclo desde la caché de instrucciones L1 de 32 KB, cada uno conectado a un cluster de decodificación 4-wide; el Op Cache también tiene una estructura 6-wide dual-ported y puede suministrar hasta 12 operandos al Op Queue
- La nueva estructura procesa en un ciclo dos ramas tomadas a través de bloques de instrucciones no contiguos, y usa un campo de longitud de 5 bits para encontrar el punto de inicio de la tercera ventana de predicción, reduciendo el uso excesivo de recursos de decodificación y de Op Cache
- Como en x86 es difícil paralelizar la detección de límites de instrucciones debido a sus instrucciones de longitud variable, el 2-Ahead Branch Predictor y la estructura doble de fetch y decodificación se convierten en cambios clave para escalar el frontend de la familia Zen
Dónde cambia el frontend de Zen 5
- AMD presentó Zen 5 como un rediseño completo de la arquitectura Zen, y el 2-Ahead Branch Predictor es una de las partes más destacadas de ese cambio
- Esta estructura reaparece, basada en ideas tratadas en artículos de hace 30 años, dentro de una tendencia que busca elevar aún más el rendimiento de un solo núcleo
- Predecir varias ramas tomadas a la vez permite que el frontend mire por adelantado hasta flujos de instrucciones más lejanos
Por qué la predicción de ramas es necesaria en el pipeline de un CPU
- Los CPU modernos usan una estructura de pipeline que divide la obtención de instrucciones (fetch), la decodificación y la ejecución en varias etapas
- Cuando hay una rama condicional, el frontend debe decidir qué ubicación de instrucciones traer a continuación antes de que termine la evaluación de la condición
- Las opciones posibles son, en términos generales, dos:
- Detenerse hasta que salga el resultado de la rama
- Predecir la siguiente ruta y, si se equivoca, descartar el trabajo incorrecto y volver a empezar desde un punto seguro
- Si la predicción falla, se necesita un flush que elimine del pipeline el trabajo que dependía de esa especulación
- El costo de detenerse ante una condición de rama es proporcional al número de etapas del pipeline entre el instruction fetch y la finalización de la evaluación de la branch condition
- En definitiva, el CPU debe predecir con la mayor precisión posible el flujo de instrucciones del programa
El contexto en el que apareció la idea 2-ahead
- Entre los métodos de predicción simples existía la estrategia de tratar los backward jumps cortos como siempre tomados, lo que históricamente aportó una gran ventaja frente a traer siempre la siguiente dirección
- Mantener un pequeño estado, como el historial reciente de ramas o registros de direcciones, permite obtener mejores resultados en programas reales
- Incluso con estructuras de apenas decenas de KB era posible lograr tasas de predicción de ramas en el rango alto del 90%
- El 2-Ahead Branch Predictor es una propuesta discutida desde principios de los años 90, y en ese momento también se abordaba el problema de ampliar el ancho de la arquitectura a 8-wide o más
- Más tarde, cuando los CPU comerciales pasaron a multinúcleo, el área de cada núcleo individual se volvió más importante, y la academia se concentró en mejorar los predictors TAGE con mayor eficiencia de área
- A medida que la miniaturización de procesos permitió colocar más transistores en un área similar, volvió a crecer el interés por el rendimiento de un solo núcleo, junto con la tendencia de escalar hasta cientos de CPU out-of-order
Por qué el frontend x86 es más complejo
- En una ISA con instrucciones de longitud fija, como Arm de 64 bits, es fácil decodificar en paralelo partes arbitrarias de una línea de caché de instrucciones
- Basta con dividir los datos de entrada en límites de bytes de instrucción garantizados y replicar la lógica del decodificador
- En x86, las instrucciones tienen longitud variable, por lo que hay que parsear linealmente los bytes de instrucción para conocer el siguiente límite de cada instrucción
- Se puede paralelizar en cierta medida con técnicas de pipeline, como una decodificación parcial previa de los prefijos, pero en x86 ese costo no es bajo
- Ese es también el trasfondo de que la decodificación 4-wide haya sido común durante mucho tiempo en núcleos x86 orientados al rendimiento
- Diseños como la decodificación 6-wide de Intel Golden Cove se pudieron comercializar gracias al aumento de densidad lógica en procesos modernos, pero el costo de área y energía de la decodificación x86 paralela monolítica crece de forma superlineal con el aumento del ancho
- El código entero de aplicaciones comunes tiene una branch density de aproximadamente 1 rama cada 5 a 6 instrucciones, lo que reduce el incentivo para ampliar mucho más el ancho del decodificador
- El frontend x86 necesita una forma segura de llegar al siguiente límite de instrucción, saltándose una etapa difícil de paralelizar: la detección de límites de instrucciones
Implementación de doble fetch y decodificación en Zen 5
- “Multiple-block ahead branch predictors” de Seznec et al. es un artículo clave que trata el motivo y la forma de implementación del 2-Ahead Branch Predictor
- Un predictor que procese varias ramas tomadas no basta por sí solo; Seznec et al. consideraron que, para aprovecharlo sin disparar los requisitos de área, era necesario el dual-porting del instruction fetch
- Zen 5 cambió el instruction fetch y el Op Cache a una estructura dual-port
- Usa dos fetch pipes de 32 bytes/ciclo desde la caché de instrucciones L1 de 32 KB
- Cada fetch pipe está conectado a su propio cluster de decodificación 4-wide
- El Op Cache tiene un diseño 6-wide dual-ported y puede suministrar hasta 12 operandos al Op Queue
- El Branch Target Buffer también entra entre los elementos con dual-porting
- La gran escala del L1 BTB de Zen 5, con 16K entries accesibles, puede explicar la posibilidad de un L1 BTB dual-ported
- El L2 BTB tiene 8K entries, por lo que es más pequeño que el L1 BTB
- AMD usa el L2 BTB de forma similar a una victim cache, y las entries expulsadas del L1 BTB se mueven al L2 BTB
Cómo procesa dos ramas tomadas en un ciclo
- Zen 5 puede procesar dos ramas tomadas en un ciclo a través de bloques de instrucciones no contiguos
- Este cambio reduce la pérdida de ancho de banda de fetch al encontrar una rama tomada y permite predecir más allá de dos ramas tomadas
- Al poder mirar más lejos en el instruction stream posterior a la segunda rama tomada, puede tener tres prediction windows
- Las tres prediction windows pueden utilizarse para producir instrucciones para decodificación
- La segunda prediction window incluye un length field de 5 bits
- Evita situaciones en las que se reservan en exceso recursos de decodificación o de Op Cache
- Es más pequeño que un pointer, pero proporciona el punto de inicio de la tercera prediction window
- Cuando la tercera prediction window cruza un límite de cache line, no hace falta guardar estado adicional en el prediction lookup index para el siguiente ciclo
- Si la tercera prediction window está dentro de la misma cache line que la primera o la segunda prediction window, esa tercera ventana parcial no es tan efectiva como una tercera prediction window completa
Restricciones que quedan en SMT
- En Zen 5, cuando dos threads están activos, el fetch pipe asociado a cada decode cluster se particiona estáticamente
- En ese estado, para comportarse como un núcleo de dual fetch, debe hacer fetch tanto desde la caché de instrucciones L1 como desde el Op Cache
- La razón por la que AMD hizo dual-port el Op Cache podría ser mantener mejor el dual fetch pipeline
Artículos relacionados mencionados
- “Multiple-block ahead branch predictors” de Seznec et al. – ASPLOS 1996: trata el motivo y la dirección de implementación del 2-Ahead Branch Predictor
- “Optimization of Instruction Fetch Mechanisms for High Issue Rates” de Conte et al. – ISCA 1995: trata la optimización de mecanismos de instruction fetch para altas issue rates
- “Increasing the instruction fetch rate via multiple branch prediction and a branch address cache” de Yeh et al. – ICS 1993: trata el aumento del fetch rate mediante multiple branch prediction y branch address cache
- “Out-of-Order Instruction Fetch using Multiple Sequencers” de Oberoi y Sohi – ICPP’02: trata el out-of-order instruction fetch usando multiple sequencers
- “Parallelism in the Front-End” de Oberoi y Sohi – ISCA 2003: trata el paralelismo en el frontend del CPU
1 comentarios
Opiniones de Hacker News
Para una buena explicación de la predicción de saltos desde las primeras implementaciones, está muy bien https://danluu.com/branch-prediction/
[0]: https://www.youtube.com/watch?v=nhXevKMm3JI&list=PLzH6n4zXuc...
[1]: https://www.youtube.com/watch?v=nczJ58WvtYo&list=PLzH6n4zXuc...
Me da curiosidad cómo será el rendimiento con SMT, y espero que este enfoque aporte beneficios y se refine más en la próxima generación
Zen5c llega hasta 192 núcleos o 384 vCPU, y parece posible que el Zen 6c del año que viene llegue a 256 núcleos. En un servidor 1U de doble socket, eso sería potencialmente 512 núcleos y 1024 vCPU
Los problemas de escalado de apps web que enfrentábamos en 2014 ahora cabrían en un solo servidor, siempre que se pueda enfriar. Incluso tomando apenas 1 RPS por vCPU, serían 1000 RPS sin contar aciertos de caché, y ni siquiera la portada de HN le pega a un servidor con 1000 páginas vistas por segundo
Me pregunto cómo será el rendimiento en HPC. La refrigeración en sí quizá no sea un gran problema, pero a partir de cierto punto podría convertirse en un asunto “húmedo” que requiera refrigeración líquida directa (DLC)
Si se considera un rack denso de servidores con GPU como una sola máquina, ya estamos en cientos de kilonúcleos
Una vez discutí con alguien que no entendía la idea de que un servicio a escala de Wikipedia pudiera servirse desde un solo servidor, y fue bastante divertido. Ya hace tiempo que eso es algo fácil; simplemente no se hace por razones prácticas como disponibilidad o eficiencia de costos
Intuitivamente, si hay más trabajos que procesan el mismo problema a la mitad de velocidad, parecería que debería haber un costo en uso de memoria; me pregunto si son comunes las apps que al activar SMT solo usan más memoria sin ganar velocidad
En muchos benchmarks públicos, parece que la mayoría de las apps no obtiene una mejora notable en velocidad de ejecución
Siempre es interesante ver cómo un paper de hace décadas se publicó en su momento sin llamar mucho la atención y, cuando el hardware se vuelve lo suficientemente potente, de repente pasa a ser de vanguardia
Por ejemplo está el Z-buffer. Se usa en videojuegos 3D, pero cuando apareció por primera vez en un paper se trató casi como un tema secundario, no por el tema en sí, sino porque requería demasiada memoria
Unas décadas después, los megabytes se volvieron bastante baratos y al final todos los renderizadores 3D en tiempo real lo usaron
Creo que hubo un vacío de unos 38 años en la literatura hasta que David MacKay los redescubrió
Su primer uso masivo fue en 2003, y ahora se usan en WiFi, Ethernet y 5G
[1] https://en.wikipedia.org/wiki/Low-density_parity-check_code
[2] https://scholar.google.com/scholar?q=%22low+density+parity+c...
Ir a una biblioteca y leer lo que investigadores de ciencias de la computación publicaban en papers impresos podría revelar ideas que en su momento eran poco realistas, pero que hoy podrían implementarse
Durante los últimos 20 años, el rendimiento de un solo núcleo estuvo contenido al priorizar el escalado horizontal, es decir, más núcleos, y por eso la complejidad y el área de die de cada núcleo se volvieron un problema. Si esa tendencia no hubiera existido y los diseñadores de CPU hubieran buscado principalmente rendimiento de un solo núcleo, creo que habríamos visto implementaciones mucho antes
El Z-buffer es un concepto simple, así que es comprensible que en el paper pareciera secundario. Un mejor ejemplo quizá sea el ray tracing. Incluso sin experiencia en gráficos 3D, el concepto en sí es bastante claro, pero hasta hace poco era inviable en rendimiento para renderizado en tiempo real
Lo interesante es que no hayamos encontrado un enfoque más simple para aproximar un renderizado parecido a la realidad y tengamos que volver a una solución antigua, algo ingenua y costosa
Muchos académicos pensaban que los sistemas de tipos subestructurales básicamente habían muerto a manos de la recolección de basura, pero Rust los revivió combinándolos con ideas nuevas de C++ de la época
Esa necesidad extra de ancho de banda de memoria hizo que fuera difícil y caro implementarlo bien. Las implementaciones de gama alta usaban canales de RAM dedicados, pero en hardware barato consumía mucho del ancho de banda de la interfaz de memoria compartida
Por ejemplo, algunos juegos de N64 desactivaban el Z-buffer y optimizaban el dibujado de fondo/primer plano gestionado por software para evitar el costo de leer y actualizar la información de profundidad
Los predictores especulativos han sido objetivo de varios ataques para extraer datos privados
Si una buena parte de las ISA comunes son vulnerables, me pregunto si se están tomando medidas para reducir el impacto de estos ataques
No hay forma de impedirlo, salvo un enfoque del nivel de hervir el océano[0]. La ejecución especulativa es demasiado valiosa para el rendimiento; una computadora sin ella sería prácticamente inutilizable. Si de verdad quieres un procesador sin ejecución especulativa, compra un Pentium de primera generación viejo
Hay varias mitigaciones prácticas, pero como mínimo deben garantizar la separación de procesos entre un proceso víctima con secretos y un posible atacante que pueda influir en la ejecución de la víctima
Intel fue atrapada ejecutando especulativamente a través de anillos, por eso desde el espacio de usuario se podía leer memoria del kernel o del hipervisor. En una CPU que no esté mal diseñada, lo que principalmente debería preocuparte son los iframe de HTML
Los distintos orígenes no pueden enviar solicitudes HTTP libremente[1], pero sí pueden incluirse entre sí sin permiso[2]. Tradicionalmente, esa información se cargaba en el proceso del atacante y podía filtrarse mediante ataques de temporización
La primera solución de la web no fue separar los iframe por proceso, sino eliminar por completo el multithreading con memoria compartida. Si le quitas al atacante una referencia de tiempo, importa menos qué ejecute especulativamente la víctima. Pero para eso hay que eliminar el multithreading. Si no, un hilo puede crear un reloj escribiendo datos conocidos en un bucle repetidamente
[0] https://hackaday.com/2013/08/02/the-mill-cpu-architecture/
[1] Al menos no, salvo que el origen de destino lo permita con CORS
[2] Por ejemplo: hotlinking de imágenes o incrustación de iframe
No es una vulnerabilidad inherente a la predicción en sí
Como principiante en este campo, incluso después de leer el artículo no me queda claro qué es exactamente un predictor de ramas 2-ahead
En los 90 se tendía más a una u otra de esas cosas, pero los procesadores modernos parecen tener ambas en su mayoría
El resumen de “Multiple-block ahead branch predictors” explica que no usa la información del bloque de instrucciones actual para predecir la dirección del siguiente bloque de instrucciones, sino para predecir el bloque que viene después. Esto reduce el cuello de botella de búsqueda de instrucciones en procesadores “brainiac” de despacho amplio y permite predecir eficientemente dos direcciones de bloques de instrucciones en un ciclo
También dice que, en procesadores “speed demon”, permite segmentar en pipeline el proceso de predicción de ramas para lograr relojes más altos o mejorar la precisión mediante estructuras de predicción más grandes. A diferencia de los métodos existentes con múltiples predictores, los predictores de ramas varios bloques por delante pueden usar cualquier método de predicción de ramas
[0] https://dl.acm.org/doi/10.1145/237090.237169
De paso, parece que eyegor ya puso el enlace, pero lo digo para que al menos vean el resumen
Será mucho más difícil que predecir la siguiente rama, pero permite traer mucho antes el código que alimentará a pipelines más profundos
Así que no solo puede evaluar por adelantado n+1 como en la predicción de ramas normal, sino también el resultado n+2. No tengo claro cómo funciona esto sin arruinar la caché L1
Si es una forma de mirar más allá de n+1, parecería que habría muchas más expulsiones de caché, así que siento que me estoy perdiendo algo
Se dice que Zen 5 puede ver más lejos, hasta el flujo de instrucciones más allá de la segunda rama tomada, y como resultado puede tener 3 ventanas de predicción útiles para generar instrucciones que decodificar
El paper original es de acceso público, pero todavía no lo he leído mucho: https://dl.acm.org/doi/10.1145/237090.237169
Cada dirección de la rama lleva al comienzo de un nuevo bloque de instrucciones, y la última instrucción de esos bloques suele ser otra rama
Es decir, un predictor de ramas es un dispositivo que acierta la dirección del siguiente bloque. Un predictor de ramas 2-ahead hace lo mismo, pero para los dos bloques siguientes
En palabras del paper, “la información del bloque de instrucciones actual se usa para predecir la dirección del bloque que viene después del siguiente bloque de instrucciones”
A diferencia de un predictor de ramas normal, puede hacerlo sin esperar a que se decodifiquen las instrucciones del siguiente bloque. Por eso puede alimentar varios decodificadores de instrucciones al mismo tiempo
Esto es especialmente útil en las CPU modernas, donde el decodificador de instrucciones se ha vuelto un cuello de botella. Con un solo decodificador que decodifica apenas 1 instrucción por ciclo, cuesta seguirle el ritmo a un front-end amplio capaz de ejecutar muchas instrucciones, como 4 a 6 por ciclo
Quizá hagan falta más pistas de ramas: https://github.com/ziglang/zig/issues/5177
Me pregunto si se podría tener cold, warm, warmer y omitir hot porque sería el valor por defecto. A veces también podría marcarse como cold todas las ramas salvo una
Quizá sea una mala idea, pero quiero entender por qué.
Me pregunto por qué, cuando hay una rama condicional, no se pueden traer y preparar las instrucciones de ambos lados posibles de la rama y luego descartar el lado incorrecto.
Quiero saber si eso es mucho más difícil, o si hay alguna otra razón que hace que no valga la pena.
Los predictores de ramas TAGE modernos aciertan por bastante más del 99%. Por eso, las instrucciones adicionales de la rama opuesta casi siempre se descartan.
Lo peor es que el front-end trae instrucciones decenas de ramas por delante del punto en el que el back-end puede confirmar la dirección real. ¿Qué harías en la siguiente rama? ¿Decodificar 4 ramas posibles, luego 8, 16, 32? La mayoría se terminaría descartando.
Si tienes hardware para traer varios flujos de instrucciones en paralelo, como Intel Gracemont/Goldmont/Skymont y AMD Zen 5, una mejor estrategia es asumir que el predictor de ramas acierta el 100% de las veces. Sigues una rama, y luego sigues la siguiente.
Intel Skymont tiene 3 decodificadores y cada uno es 3-wide, así que decodifica en paralelo los siguientes 3 objetivos de rama. Intel incluso inserta ramas falsas para dividir bloques grandes de código, de modo que los tres decodificadores siempre estén decodificando partes distintas del flujo de instrucciones que viene. Luego fusiona los 3 flujos de microoperaciones para que Skymont mantenga un ancho de banda efectivo de decodificación de 9 instrucciones por ciclo.
Ejecutar ambos lados de una rama solo reduce un poco la latencia en los casos raros en que la predicción falla. En cambio, si sigues las siguientes dos o tres predicciones en una sola dirección, Intel y AMD pueden hacer que varios decodificadores trabajen en paralelo. Intel puede lograr 9-wide con tres decodificadores 3-wide más simples, y AMD puede lograr 8-wide con dos decodificadores 4-wide más simples.
El compilador, el runtime, la CPU, etc., muchas veces pueden acertar qué resultado es más probable, y por lo general es una mejor estrategia no hacer trabajo extra desde el principio. Es mejor que gastar silicio y calor en la respuesta equivocada por si acaso.
Creo que mucha gente no tiene intuición de cuán precisa puede ser la predicción de ramas. Basta con mirar tu propio código para darte cuenta rápidamente de que “la mayor parte del flujo de control va por aquí, y esta rama existe para manejar un caso excepcional”.
Los compiladores actuales también infieren esto bastante bien, y la CPU/JIT/runtime pueden crear heurísticas impresionantes. Aun así, cuando fallan, puedes poner pistas explícitas en el código para indicar al compilador y demás cuál es la dirección esperada.
El búfer de reordenamiento de instrucciones de una CPU moderna tiene una profundidad de cientos de instrucciones, y si entre ellas hay apenas 8 saltos condicionales, el programa puede tomar 256 rutas.
Si la probabilidad de que el predictor de ramas acierte las 8 supera el 50%, y de hecho es así, no vale la pena hacer 256 veces más trabajo para cubrirse.
Necesitas silicio para mantener más estado microarquitectónico, y más unidades de ejecución para aprovechar por completo la técnica. Pero las CPU superescalares ya necesitan esas cosas para explotar el paralelismo a nivel de instrucciones en código con pocas ramas, así que ya las tienen.
El resto es el trabajo complicado de lidiar con cosas como aliasing e interrupciones, pero los ingenieros de hardware son como magos y logran hacerlo.
Sin embargo, la ejecución especulativa abre la posibilidad de explotar canales laterales de temporización de caché para extraer información de datos tocados por código que solo se ejecutó especulativamente y cuyos efectos secundarios arquitectónicos no se confirmaron. Es decir, puede filtrarse información incluso desde código que no se ejecutó “realmente”.
Esto incluye código que no se habría ejecutado explícitamente debido a una comprobación condicional, por ejemplo una verificación de permisos.
Un ejemplo conocido de ataque es Spectre: https://en.m.wikipedia.org/wiki/Spectre_(security_vulnerabil...
Así que, básicamente, no salen las cuentas para nada. Es mucho mejor usar esos recursos del chip en otros hilos o núcleos.
Para juzgar si es una buena idea, primero me gustaría ver datos de rendimiento. Tampoco hay información sobre la penalización de predicción de ramas de este enfoque.
En cualquier caso, la intuición detrás de este enfoque parece estar en traer y decodificar agresivamente instrucciones que quizá todavía no estén en la caché de instrucciones L1 o en la caché de microoperaciones.
Esto es importante en x86, y probablemente también en RISC-V. Ambas tienen instrucciones de longitud variable, así que con solo mirar un bloque de caché de instrucciones el núcleo no puede saber cómo decodificar las instrucciones dentro de ese bloque. En ambas ISA, para empezar a decodificar un bloque de caché de instrucciones hay que conocer al menos el PC de una instrucción.
Por eso, si sabes hacia dónde puede saltar la aplicación dentro de dos bloques, eso ayuda a traer y decodificar más adelante que con el enfoque actual.
Este enfoque se parece al prefetching de instrucciones, pero el prefetching de instrucciones no le da al núcleo información sobre el punto de inicio.
Es probable que los núcleos ARM de alto rendimiento no sufran el problema de “encontrar el punto de inicio”, porque todas sus instrucciones miden 32 bits. Por lo tanto, aunque no conozcan el punto de inicio, pueden realizar el procedimiento de decodificación en paralelo.
Este método parece beneficiar a aplicaciones con mucho peso en el front-end, por ejemplo cargas de trabajo en la nube cuyos bloques de código calientes están dispersos por todo el binario. Me da curiosidad si en otros tipos de aplicaciones habría ganancias o pérdidas de rendimiento.
Todavía no tengo la menor idea de qué es un predictor de ramas 2-ahead.
En general, los papers de investigación antiguos asumen que el lector sabe mucho menos sobre estos temas, porque en aquella época ese conocimiento era mucho más de nicho.
Ahora lo que hace falta es ancho de banda de memoria. Los dos canales de memoria del socket AM5 para consumidores se quedan cortos frente a este nivel de rendimiento de cómputo, incluso comparados con el Apple Silicon básico.
Pasé de una configuración Zen pesada a un M2 Max, y me volvió a sorprender cuánto acelera el mayor ancho de banda de memoria las cargas de trabajo intensivas en datos. Incluso con multitarea bastante pesada, el estrecho canal de memoria de la configuración Zen se saturaba con frecuencia.
La razón por la que la gente mira especialmente Apple Silicon por los LLM es que, aunque los LLM son más adecuados para GPU, también necesitan mucha VRAM, y NVIDIA cobra precios absurdos por las GPU con mucha VRAM.
Si AMD de verdad quiere frenar el impulso de NVIDIA, debería vender GPU de consumo con 64~128 GB de VRAM.