La ejecución de programas dinámicos o generados en tiempo de ejecución en GPUs presenta un desafío fundamental debido a la arquitectura SIMT (Single Instruction, Multiple Threads) y el problema de la divergencia de warps. Cuando diferentes hilos dentro de un warp toman caminos de ejecución distintos (por ejemplo, en un intérprete basado en tabla de opcodes), el hardware debe serializar estas rutas, lo que degrada severamente el rendimiento. Este problema se agrava con programas que dependen de datos para su control de flujo, donde incluso la búsqueda de instrucciones puede divergir.
La tesis central de este trabajo es que es posible construir una máquina virtual de GPU que elimine la divergencia de warps por diseño, utilizando una única instrucción. Al reemplazar las bifurcaciones tradicionales con operaciones condicionales que seleccionan valores en lugar de rutas de ejecución, se asegura que todos los lanes de un warp ejecuten la misma instrucción en cada ciclo, independientemente de los datos. Esto permite procesar eficientemente millones de entradas con programas potencialmente diferentes por lane, sin incurrir en las penalizaciones de rendimiento asociadas a la divergencia.
Arquitectura del Sistema
El corazón de la arquitectura es la instrucción FMAG: fmag(a, b, c, d, e) = e > 0 ? fma(a, b, c) : d. Esta instrucción combina una operación FMA (a*b+c) con una selección condicional basada en el signo de e. Si e es positivo, el resultado es el FMA; de lo contrario, es d. Esta única instrucción es suficiente para emular cualquier operación aritmética y lógica, incluyendo add, mul, sub, neg, select, relu, max, min y abs, al fijar el guard e a un valor constante o a un resultado computado.
La toolchain incluye un frontend de lenguaje de sombreado (SL), un constructor de IR (Intermediate Representation) basado en SSA CFG (Static Single Assignment Control Flow Graph), y un conjunto de pases de optimización y lowering. Estos pases transforman el IR en un "stream" plano de instrucciones FMAG. Las optimizaciones clave incluyen inlining, reconocimiento de ternarios, if-conversion (predicación del control de flujo), constant folding, guard stripping, multiply-add fusion, common subexpression elimination y dead code elimination. La asignación de registros se realiza durante el lowering, minimizando el uso de registros para reducir la presión en la GPU. Las instrucciones FMAG se empaquetan en cuatro palabras de 32 bits, donde los operandos b, c y guard pueden ser literales o índices de registro (NaN-boxed), mientras que a y d (destino y fallback) son siempre índices de registro. El intérprete GLSL en la GPU decodifica estas instrucciones y ejecuta el stream de forma branchless, utilizando mix para la selección condicional.
Flujo de Compilación y Ejecución de Programa Dinámico
- 1 Lenguaje de Sombreado/IR Programa fuente (SL) o IR (SSA CFG) generado en tiempo de ejecución.
- 2 IR Builder Construye la representación intermedia del programa.
- 3 Pases de Optimización Inlining, if-conversion, constant folding, CSE, DCE, etc.
- 4 Lowering y Reg-Alloc Transforma IR a stream FMAG plano, asigna registros.
- 5 Stream FMAG Programa final como secuencia de instrucciones FMAG empaquetadas.
- 6 GPU (Shader) Intérprete GLSL carga y ejecuta el stream FMAG.
- 7 Ejecución Branchless Cada FMAG se ejecuta en lockstep, usando mix/cndmask para condicionales.
| Capa | Tecnología | Justificación |
|---|---|---|
| compute | GPU (RDNA3) | Plataforma de ejecución paralela masiva para la VM FMAG. |
| data-processing | C (fmag.h) | Implementación de la VM, toolchain de compilación y optimización. vs Python (prototipado), Odin (prototipado) Amalgamación en un solo header 'stb-style'. |
| orchestration | GLSL | Lenguaje para el intérprete de la VM que se ejecuta en la GPU. |
Trade-offs
Ganancias
- ▲▲ Eliminación de divergencia de warps
- ▲ Ejecución eficiente de programas dinámicos en GPU
- ▲ Simplicidad del intérprete en GPU
Costes
- △ Mayor número de instrucciones por operación lógica
- ▲ Complejidad de la toolchain de optimización
- △ Restricción de no usar NaN/Infinity como literales
float r[16];
vec3 loadops(uvec3 o) {
vec3 f = uintBitsToFloat(o);
uvec3 i = o & 15u;
return mix(f, vec3(r[i.x], r[i.y], r[i.z]), isnan(f));
}
void exec(uvec4 op) {
vec3 v = loadops(op.xyz);
uint d = op.w & 15u;
uint a = (op.w >> 16) & 15u;
r[d] = mix(r[d], fma(r[a], v.x, v.y), v.z > 0.0);
}
void main() {
for (uint i = 0u; i < u_length; ++i) exec(b_code[i]);
}Fundamentos Teóricos
El concepto de una máquina con una única instrucción, conocido como OISC (One Instruction Set Computer), ha sido históricamente una curiosidad académica más que una base para sistemas prácticos. Sin embargo, este trabajo demuestra una aplicación legítima y eficiente de los principios OISC en un contexto muy específico: la computación paralela masiva en GPUs. La clave reside en la reinterpretación del control de flujo. Mientras que las arquitecturas von Neumann tradicionales se basan en saltos condicionales para el control de flujo, este diseño adopta un enfoque más cercano a la computación basada en predicados o la ejecución condicional, donde todas las operaciones se ejecutan, pero sus resultados se seleccionan o se descartan en función de una condición. Esto se alinea con los principios de las arquitecturas SIMD/SIMT que buscan maximizar la utilización de unidades de ejecución evitando la divergencia, un problema bien documentado en la literatura de arquitectura de computadoras paralelas.