c++ - revista - ¿Hay algún código que resulte en un 50% de error de predicción de ramificación?

revista ethos

Question

El problema:

Estoy tratando de averiguar cómo escribir un código (C preferido, ASM solo si no hay otra solución) que haría que la predicción de ramificación se pierda en el 50% de los casos .

Por lo tanto, tiene que ser un fragmento de código que "es inmune" a las optimizaciones del compilador relacionadas con la bifurcación y también que toda la predicción de la rama HW no debería ser mejor que el 50% (lanzar una moneda). Incluso un desafío mayor es poder ejecutar el código en múltiples arquitecturas de CPU y obtener el mismo 50% de índice de fallas.

Me las arreglé para escribir un código que va al 47% del índice de fallas de sucursal en una plataforma x86. Sospecho que el 3% faltante podría provenir de:

• Gastos generales de lanzamiento del programa que tienen ramificaciones (aunque muy pequeños)
• Gastos generales del generador de perfiles: básicamente, para cada lectura de contador, se genera una interrupción, por lo que esto podría agregar ramas predecibles adicionales.
• Las llamadas del sistema que se ejecutan en segundo plano contienen bucles y bifurcaciones predecibles

Escribí mi propio generador de números aleatorios para evitar llamadas a un rand cuya implementación podría haber ocultado ramas predecibles. Puede usar también rdrand cuando esté disponible. La latencia no me importa.

Las preguntas:

1. ¿Puedo hacerlo mejor que mi versión de código? Mejor significa obtener una mayor cantidad de errores de imprenta y los mismos resultados para todas las arquitecturas de CPU.
2. ¿Puede este código ser predicado ? ¿Qué significaría eso?

El código:

#include <stdio.h>
#include <time.h>

#define RDRAND
#define LCG_A   1103515245
#define LCG_C   22345
#define LCG_M   2147483648
#define ULL64   unsigned long long

ULL64 generated;

ULL64 rand_lcg(ULL64 seed)
{
#ifdef RDRAND
    ULL64 result = 0;
    asm volatile ("rdrand %0;" : "=r" (result));
    return result;
#else
    return (LCG_A * seed + LCG_C) % LCG_M;
#endif
}

ULL64 rand_rec1()
{
    generated = rand_lcg(generated) % 1024;

    if (generated < 512)
        return generated;
    else return rand_rec1();
}

ULL64 rand_rec2()
{
    generated = rand_lcg(generated) % 1024;

    if (!(generated >= 512))
        return generated;
    else return rand_rec2();
}

#define BROP(num, sum)                  /
    num = rand_lcg(generated);          /
    asm volatile("": : :"memory");      /
    if (num % 2)                        /
        sum += rand_rec1();             /
    else                                /
        sum -= rand_rec2();

#define BROP5(num, sum)     BROP(num, sum) BROP(num, sum) BROP(num, sum) BROP(num, sum) BROP(num, sum)
#define BROP25(num, sum)    BROP5(num, sum) BROP5(num, sum) BROP5(num, sum) BROP5(num, sum) BROP5(num, sum)
#define BROP100(num, sum)   BROP25(num, sum) BROP25(num, sum) BROP25(num, sum) BROP25(num, sum)

int main()
{
    int i = 0;
    int iterations = 500000;    
    ULL64 num = 0;
    ULL64 sum = 0;

    generated = rand_lcg(0) % 54321;

    for (i = 0; i < iterations; i++)
    {
        BROP100(num, sum);
        // ... repeat the line above 10 times
    }

    printf("Sum = %llu/n", sum);
}

Actualizar v1:

Siguiendo la sugerencia de usr, generé varios patrones variando el parámetro LCG_C desde la línea de comandos en un script. Pude ir a 49.67% de falta de BP . Eso es suficiente para mi propósito y tengo la metodología para producir esto en varias arquitecturas.

Answer 1

La forma más sencilla de evitar las optimizaciones del compilador es tener las funciones ficticias void f(void) { } y void g(void) { } en otra unidad de traducción, y tener desactivadas las optimizaciones de tiempo de enlace. Esto forzará if (*++p) f(); else g(); if (*++p) f(); else g(); para ser una rama impredecible real, suponiendo que p apunta a una matriz de valores booleanos aleatorios (Esto evita el problema de la predicción de rama dentro de rand() ; simplemente haga eso antes de la medición)

Si un bucle for(;;) te da problemas, simplemente lanza un goto .

Tenga en cuenta que el "truco de desenrollado de bucle" en el comentario es un tanto engañoso. Esencialmente estás creando miles de ramas. Cada rama se predeciría individualmente, excepto que es probable que ninguna de ellas se prediga ya que la CPU simplemente no puede contener miles de predicciones distintas. Esto puede o no ser un beneficio para su objetivo real.

Answer 2

Rellene una matriz con bytes y escriba un bucle que verifique cada byte y las ramas según el valor del byte.

Ahora examine la arquitectura de su procesador y su predicción de rama con mucho cuidado. Rellene los bytes iniciales de la matriz para que, después de examinarlos, el procesador se encuentre en un estado conocido predecible. A partir de ese estado conocido, puede averiguar si la próxima rama se predice tomada o no. Establezca el siguiente byte para que la predicción sea incorrecta. Nuevamente, averigüe si la próxima rama se predice tomada o no, y establezca el siguiente byte para que la predicción sea incorrecta y así sucesivamente.

Si deshabilita las interrupciones también (lo que podría cambiar la predicción de la rama), puede acercarse al 100% de las ramas mal pronosticadas.

Como un caso simple, en un viejo procesador PowerPC con predicción fuerte / débil, después de tres ramas tomadas, siempre estará en el estado "fuerte tomado" y una rama no tomada lo cambia a "débil tomado". Si ahora tiene una secuencia de ramas alternas no tomadas / tomadas, la predicción siempre es incorrecta y cambia entre débil no tomado y débil tomado.

Por supuesto, esto solo funcionará con ese procesador en particular. La mayoría de los procesadores modernos verían esa secuencia como casi 100% predecible. Por ejemplo, podrían usar dos predictores separados; una para el caso "se tomó la última rama" y otra para el caso "no se tomó la última rama". Pero para tal procesador, una secuencia diferente de bytes dará la misma tasa de error de predicción del 100%.

Answer 3

Si sabe cómo funciona el predictor de rama, puede llegar a un 100% de predicción errónea. Simplemente tome la predicción esperada del predictor cada vez y haga lo contrario. El problema es que no sabemos cómo se implementa.

He leído que los predictores típicos son capaces de predecir patrones como 0,1,0,1 y así sucesivamente. Pero estoy seguro de que hay un límite a la duración del patrón. Mi sugerencia sería probar cada uno de los patrones de una longitud determinada (como 4) y ver cuál se acerca más a su porcentaje objetivo. Debes poder apuntar tanto al 50% como al 100% y acercarte mucho. Este perfil debe realizarse para cada plataforma una vez o en tiempo de ejecución.

Dudo que el 3% del número total de sucursales estén en el código del sistema, como usted dijo. El kernel no tiene una sobrecarga del 3% en el código de usuario puramente vinculado a la CPU. Aumente la prioridad de programación al máximo.

Puedes eliminar el RNG del juego generando datos aleatorios una vez e iterando sobre los mismos datos muchas veces. Es poco probable que el predictor de rama detecte esto (aunque claramente podría).

Yo implementaría esto llenando un bool[1 << 20] con un patrón de cero-uno como lo describí. A continuación, puede ejecutar el siguiente bucle sobre él muchas veces:

int sum0 = 0, sum1 = 0;
for (...) {
 //unroll this a lot
 if (array[i]) sum0++;
 else sum1++;
}
//print both sums here to make sure the computation is not being optimized out

Tendrá que examinar el desmontaje para asegurarse de que el compilador no hizo nada inteligente.

No veo por qué es necesaria la configuración complicada que tienes ahora. El RNG puede eliminarse de la pregunta y no veo por qué se necesita más que este simple bucle. Si el compilador está jugando trucos, es posible que tenga que marcar las variables como volatile que hace que el compilador (mejor: la mayoría de los compiladores) las trate como si fueran llamadas a funciones externas.

Ya que el RNG ya no importa, ya que casi nunca se llama, incluso puede invocar el RNG criptográfico de su sistema operativo para obtener números que no se distinguen (a cualquier humano) de los verdaderos números aleatorios.