Especulación para simulación. Innovación en verificación

Reeditado por Platón

seguidores: 0

Esta es una idea interesante, usar paralelismo especulativo soportado por hardware para acelerar la simulación, con un giro que requiere hardware personalizado. Paul Cunningham (VP senior/GM, Verificación en Cadence), Raúl Camposano (Silicon Catalyst, emprendedor, ex CTO de Synopsys y ahora CTO de Silvaco) y yo continuamos nuestra serie sobre ideas de investigación. Como siempre, los comentarios son bienvenidos.

Especulación para simulación

La innovación

La elección de este mes es Chronos: paralelismo especulativo eficiente para aceleradores. Los autores presentaron el documento en la Conferencia de 2020 sobre soporte arquitectónico para lenguajes de programación y sistemas operativos y son del MIT.

Explotar el paralelismo usando procesadores multinúcleo es una opción para aplicaciones donde el paralelismo es evidente. Es posible que otros algoritmos no se dividan tan fácilmente, pero podrían beneficiarse de la ejecución especulativa que explota el paralelismo intrínseco. Por lo general, la ejecución especulativa depende de la coherencia de la caché, una sobrecarga alta, especialmente para la simulación. Este método evita la necesidad de coherencia, localiza físicamente la ejecución de tareas para calcular mosaicos por objeto de lectura y escritura de destino, lo que garantiza que la detección de conflictos se pueda detectar localmente, sin necesidad de una gestión de coherencia global. Las tareas pueden ejecutarse especulativamente en paralelo; cualquier conflicto detectado se puede desenrollar de una tarea a través de sus tareas secundarias y luego volver a ejecutarse sin necesidad de detener otros subprocesos.

Otro punto a tener en cuenta aquí. Este método admite la simulación basada en demoras, a diferencia de la mayoría de las técnicas de aceleración de hardware.

Punto de vista de pablo

¡Guau, qué maravilloso artículo de alto octanaje del MIT! Cuando me preguntan sobre computación paralela, inmediatamente pienso en subprocesos, mutexes y coherencia de memoria. Por supuesto, así es como se diseñan las CPU multinúcleo modernas. Pero no es la única forma de soportar la paralelización en hardware.

Este artículo propone una arquitectura alternativa para la paralelización llamada Chronos que se basa en una cola ordenada de tareas. En tiempo de ejecución, las tareas se ejecutan en orden de marca de tiempo y cada tarea puede crear nuevas subtareas que se agregan dinámicamente a la cola. La ejecución comienza poniendo algunas tareas iniciales en la cola y finaliza cuando no hay más tareas en la cola.

Las tareas en la cola se asignan a múltiples elementos de procesamiento (PE) en paralelo, lo que significa que Chronos está ejecutando especulativamente tareas futuras antes de que se complete la tarea actual. Si la tarea actual invalida cualquier tarea futura ejecutada especulativamente, las acciones de esas tareas futuras se "deshacerán" y se volverán a poner en cola. Implementar este concepto correctamente en el hardware no es fácil, pero para el usuario externo es hermoso: simplemente codifica su algoritmo como si la cola de tareas se ejecutara en serie en un solo PE. No es necesario codificar ningún mutex ni preocuparse por el interbloqueo.

Los autores implementan Chronos en SystemVerilog y lo compilan en un FPGA. Gran parte del documento está dedicado a explicar cómo han implementado la cola de tareas y cualquier despliegue necesario en el hardware para lograr la máxima eficiencia. Chronos se compara con cuatro algoritmos que se adaptan bien a una arquitectura basada en colas de tareas. Cada algoritmo se implementa de dos maneras: en primer lugar, utilizando un PE específico del algoritmo dedicado y, en segundo lugar, utilizando una CPU RISC-V integrada de código abierto de 32 bits lista para usar como el PE. Luego, el rendimiento de Chronos se compara con las implementaciones de software de subprocesos múltiples de los algoritmos que se ejecutan en un servidor Intel Xeon con un precio similar al de la FPGA que se usa para Chronos. Los resultados son impresionantes: Chronos se escala entre 3 y 15 veces mejor que con el servidor Xeon. Sin embargo, comparar la Tabla 3 con la Figura 14 hace que me preocupe un poco que la mayoría de estas ganancias provengan de los PE específicos del algoritmo en lugar de la arquitectura de Chronos en sí.

Dado que este es un blog de verificación, naturalmente me acerqué al punto de referencia de simulación a nivel de puerta. La industria de EDA ha invertido mucho para probar y paralelizar la simulación lógica y ha resultado difícil ver grandes ganancias más allá de unos pocos casos de uso específicos. Esto se debe principalmente a que el rendimiento de la mayoría de las simulaciones del mundo real está dominado por las instrucciones de carga/almacenamiento que faltan en la memoria caché L3 y se van a la DRAM. En este documento solo se compara un caso de prueba y se trata de un pequeño sumador de almacenamiento y almacenamiento de 32 bits. Si está leyendo este blog y le interesaría hacer una evaluación comparativa más exhaustiva, hágamelo saber: si Chronos realmente puede escalar bien en simulaciones del mundo real, ¡tendría un gran valor comercial!

La mirada de Raúl

La principal contribución de este trabajo es la Modelo de ejecución de tareas ordenadas ubicadas espacialmente (SLOT) que es eficiente para aceleradores de hardware que explotan el paralelismo y la especulación, y para aplicaciones que generan tareas dinámicamente en tiempo de ejecución. El soporte de paralelismo dinámico es inevitable para la simulación y la sincronización especulativa es una opción atractiva, pero la sobrecarga de coherencia es demasiado alta.

SLOT evita la necesidad de coherencia al restringir cada tarea para operar (escribir) en un solo objeto y admite tareas ordenadas para habilitar la atomicidad de múltiples objetos. Las aplicaciones SLOT son tareas ordenadas y creadas dinámicamente caracterizadas por una marca de tiempo y una identificación de objeto. Las marcas de tiempo especifican restricciones de orden; los identificadores de objetos especifican las dependencias de los datos, es decir, las tareas dependen de los datos si y solo si tienen el mismo identificador de objeto. (si hay una dependencia de lectura, la tarea se puede ejecutar especulativamente). La detección de conflictos se vuelve local (sin estructuras de seguimiento complejas) mediante la asignación de identificadores de objetos a núcleos o mosaicos y al envío de cada tarea a donde se asigna su identificador de objeto.

La Cronos El sistema se implementó en el marco AWS FPGA como un sistema con 16 mosaicos, cada uno con 4 elementos de procesamiento (PE) específicos de la aplicación, que se ejecutan a 125 MHz. Este sistema se compara con una línea de base que consta de Intel Xeon E20-40v2.4 de 5 núcleos/2676 hilos de 3 GHz, elegido específicamente porque su precio es comparable con el de FPGA (aproximadamente $2/hora). Al ejecutar una sola tarea en un PE, Chronos es 2.45 veces más rápido que la línea de base. A medida que aumenta la cantidad de tareas simultáneas, la implementación de Chronos escala a una aceleración relativa de 44.9x en 8 mosaicos, lo que corresponde a una aceleración de 15.3x sobre la implementación de la CPU. También compararon una implementación basada en RISC-V de propósito general en lugar de PE específicos de la aplicación; Los PE fueron 5 veces más rápidos que RISC-V.

El documento me impresionó porque cubre todo, desde un concepto hasta la definición del modelo de ejecución SLOT, la implementación del hardware y la comparación detallada con una CPU Xeon tradicional para 4 aplicaciones. El esfuerzo es sustancial, Chronos supera las 20,000 líneas de SystemVerilog. El resultado es una aceleración media de 5.4 veces (de las 4 aplicaciones) con respecto a las versiones paralelas de software, debido a un mayor paralelismo y un mayor uso de la ejecución especulativa. También vale la pena leer el documento para su aplicación a tareas que no sean de simulación; el documento incluye tres ejemplos.

Comparte esta publicación a través de: