Just In Time Compilation (JIT)

Hoy voy a hacer un pequeno comentario sobre una tecnica de programacion muy interesante para entornos de alto rendimiento embebidos y es lo que se llama JIT, o como podria decirse en espanol "Compilacion en tiempo real".

EXPLICACION:
El rendimiento de un procesador puede ser calculado por el flujo maximo de datos que genera por ciclo de reloj, sin embargo, cuando se pasa a la implementacion de un determinado algoritmo nos podemos encontrar que generamos un flujo bastante inferior al teorico. Esto puede ocurrir por:

1) Uso sub-optimo de la vectorizacion (Ejemplo): Un procesador de 64 bits puede hacer 8 sumas de 8 bits en paralelo, si queremos aplicar un filtro sobre una componente de un pixel definido como:



La inicializacion es un poco mas compleja, pero basicamente hace lo mismo pero con 3 operaciones cada 8 pixels contra 16 por 8 pixels.

2) Por stalls en la pipeline (Ejemplo): Debidos a cache miss (Instrucciones o Datos), o la concatenacion de instrucciones que utilizan las mismas unidades aritmeticas.

3) Por ruptura de la pipeline debido a un salto (Ejemplo): Un if (...) no bien predicho.

En concreto, la programacion de tipo JIT, tiene como objetivo eliminar (o reducir considerablemente) los stalls en la pipeline debidos a instruction miss, y las rupturas de pipeline debidas a salto.

COMO:
La programacion consiste a crear un pequeno buffer de instrucciones en tiempo real, para ello tenemos que crearnos un minicompilador interno y segun los datos de entrada generamos unas instrucciones en codigo maquina (bytecode) adaptadas a nuestro algoritmo.
Imaginemos la interpolacion lineal:
El algoritmo de base es:



Para general el codigo git equivalente supongamos:

a) el tamano de la linea de la data cache es de 32 bytes.
b) y las siguientes funciones

void generate_ldrb_r_r_off(uint32_t * jitcmdbuf, int rd, int ra, int off);
genera el codigo fuente de una instruccion que guarda en el registro rd el byte contenido en la direccion guardada
en [ra] + offset y lo anade a jitcmdbuf

void generate_pld_r_off(uint32_t * jitcmdbuf, int ra, int off);
este genera un preload en cache de los 32 bytes a partir de la direccion calculada en [ra] + off

void generate_strb_r_r_off(uint32_t * jitcmdbuf, int rd, int ra);
idem a ldrb pero guardando

void generate_save(uint32_t *);void generate_rest(uint32_t *);
salvan y recuperan el estado de los registros y el program counter.

void generate_addb_r_r_r_asr(uint32_t * jitcmdbuf, int rd, int rm, int rs, int asr);
suma los datos de rm y rs en rd, y le aplica un shift de asr a la derecha al resultado.

Pues en jit primero preparariamos el codebufer.



Ahora "func" es un puntero a funcion de tipo void interpolate(uint8_t * in, uint8_t *out) que tiene las siguiente ventajas:
1) No hay rupturas de pipeline (los ifs son precalculados)
2) No hay calculos internos de los offsets
3) No hay data miss (los preloads son predichos)
Aun se podria mejorar, pero como proof of concept esta bien.

LIMITACIONES:

• Generar las funciones toma tiempo, mejor utilizarlas en cosas repetitivas.

• Las funciones generan un numero grande de instrucciones, hay que tener cuidado que cada uno de nuestros monstruitos no supere el tamano de la cache de instrucciones.

• En arquitecturas conbit NX (No execute) hay que tener cuidado para que nuestra funcion sea ejecutable.

• Hay que comentar y documentar bien, si no es ilegible

Pues esto es una pequena introduccion, algun dia metere esquemitas.

Para otros dias me dejo otras perlitas como:
A) Vectorizacion (introducida hoy)
B) Gestion buffer de salida de datos y de entrada.
C) Reordenacion de instrucciones.


CURIOSIDAD:

La compilacion JIT es muy similar a la técnica de injección de codigo de los buffer-overflow.