c++ - Predicción de rama: Escribir código para entenderlo; Obteniendo resultados extraños

branch-prediction

Question

Estoy tratando de entender bien la predicción de las ramas midiendo el tiempo para ejecutar bucles con ramas predecibles y bucles con ramas aleatorias.

Así que escribí un programa que toma arrays grandes de 0 y 1 dispuestos en diferentes órdenes (es decir, todos los 0, repitiendo 0-1, todo rand), e itera a través de la bifurcación de la matriz según si el índice actual es 0 o 1, haciendo tiempo. -un desperdicio de trabajo.

Esperaba que las matrices más difíciles de adivinar tardaran más en ejecutarse, ya que el predictor de ramificación acertaría más a menudo, y que el tiempo-delta entre ejecuciones en dos conjuntos de matrices seguiría siendo el mismo, independientemente de la cantidad de tiempo. desperdiciando trabajo

Sin embargo, a medida que aumentaba la cantidad de trabajo que desperdiciaba tiempo, aumentaba la diferencia en el tiempo de ejecución entre matrices, MUCHO.

(El eje X es una cantidad de trabajo que desperdicia tiempo, el eje Y es tiempo de ejecución)

¿Alguien entiende este comportamiento? Puedes ver el código que estoy ejecutando en el siguiente código:

#include <stdlib.h>
#include <time.h>
#include <chrono>
#include <stdio.h>
#include <iostream>
#include <vector>
using namespace std;
static const int s_iArrayLen = 999999;
static const int s_iMaxPipelineLen = 60;
static const int s_iNumTrials = 10;

int doWorkAndReturnMicrosecondsElapsed(int* vals, int pipelineLen){
        int* zeroNums = new int[pipelineLen];
        int* oneNums = new int[pipelineLen];
        for(int i = 0; i < pipelineLen; ++i)
                zeroNums[i] = oneNums[i] = 0;

        chrono::time_point<chrono::system_clock> start, end;
        start = chrono::system_clock::now();
        for(int i = 0; i < s_iArrayLen; ++i){
                if(vals[i] == 0){
                        for(int i = 0; i < pipelineLen; ++i)
                                ++zeroNums[i];
                }
                else{
                        for(int i = 0; i < pipelineLen; ++i)
                                ++oneNums[i];
                }
        }
        end = chrono::system_clock::now();
        int elapsedMicroseconds = (int)chrono::duration_cast<chrono::microseconds>(end-start).count();

        //This should never fire, it just exists to guarantee the compiler doesn''t compile out our zeroNums/oneNums
        for(int i = 0; i < pipelineLen - 1; ++i)
                if(zeroNums[i] != zeroNums[i+1] || oneNums[i] != oneNums[i+1])
                        return -1;
        delete[] zeroNums;
        delete[] oneNums;
        return elapsedMicroseconds;
}

struct TestMethod{
        string name;
        void (*func)(int, int&);
        int* results;

        TestMethod(string _name, void (*_func)(int, int&)) { name = _name; func = _func; results = new int[s_iMaxPipelineLen]; }
};

int main(){
        srand( (unsigned int)time(nullptr) );

        vector<TestMethod> testMethods;
        testMethods.push_back(TestMethod("all-zero", [](int index, int& out) { out = 0; } ));
        testMethods.push_back(TestMethod("repeat-0-1", [](int index, int& out) { out = index % 2; } ));
        testMethods.push_back(TestMethod("repeat-0-0-0-1", [](int index, int& out) { out = (index % 4 == 0) ? 0 : 1; } ));
        testMethods.push_back(TestMethod("rand", [](int index, int& out) { out = rand() % 2; } ));

        int* vals = new int[s_iArrayLen];

        for(int currentPipelineLen = 0; currentPipelineLen < s_iMaxPipelineLen; ++currentPipelineLen){
                for(int currentMethod = 0; currentMethod < (int)testMethods.size(); ++currentMethod){
                        int resultsSum = 0;
                        for(int trialNum = 0; trialNum < s_iNumTrials; ++trialNum){
                                //Generate a new array...
                                for(int i = 0; i < s_iArrayLen; ++i)  
                                        testMethods[currentMethod].func(i, vals[i]);

                                //And record how long it takes
                                resultsSum += doWorkAndReturnMicrosecondsElapsed(vals, currentPipelineLen);
                        }

                        testMethods[currentMethod].results[currentPipelineLen] = (resultsSum / s_iNumTrials);
                }
        }

        cout << "/t";
        for(int i = 0; i < s_iMaxPipelineLen; ++i){
                cout << i << "/t";
        }
        cout << "/n";
        for (int i = 0; i < (int)testMethods.size(); ++i){
                cout << testMethods[i].name.c_str() << "/t";
                for(int j = 0; j < s_iMaxPipelineLen; ++j){
                        cout << testMethods[i].results[j] << "/t";
                }
                cout << "/n";
        }
        int end;
        cin >> end;
        delete[] vals;
}

Enlace de Pastebin: http://pastebin.com/F0JAu3uw

Answer 1

Además de lo que JasonD señaló, también me gustaría señalar que hay condiciones dentro for bucle for , que pueden afectar la predicción de la rama:

if(vals[i] == 0)
{
    for(int i = 0; i < pipelineLen; ++i)
        ++zeroNums[i];
}

i <pipelineLen; es una condición como tu if s. Por supuesto, el compilador puede desenrollar este bucle, sin embargo, pipelineLen es un argumento que se pasa a una función, por lo que probablemente no lo haga.

No estoy seguro de si esto puede explicar el patrón ondulado de sus resultados, pero:

Como el BTB solo tiene 16 entradas en el procesador Pentium 4, la predicción eventualmente fallará para bucles que tengan más de 16 iteraciones. Esta limitación se puede evitar desenrollando un bucle hasta que tenga solo 16 iteraciones. Cuando se hace esto, un condicional de bucle siempre se ajustará a la BTB, y no se producirá una predicción errónea de bifurcación en la salida del bucle. El siguiente es un ejemplo de desenrollado de bucle:

Lea el artículo completo: http://software.intel.com/en-us/articles/branch-and-loop-reorganization-to-prevent-mispredicts

De modo que sus bucles no solo miden el rendimiento de la memoria, sino que también afectan a la BTB.

Si ha pasado el patrón 0-1 en su lista pero luego ejecutó un bucle for con pipelineLen = 2 su BTB se llenará con algo como 0-1-1-0 - 1-1-1-0 - 0-1-1-0 - 1-1-1-0 y luego comenzará a superponerse, por lo que esto puede explicar el patrón ondulado de sus resultados (algunos solapamientos serán más dañinos que otros).

Tome esto como un ejemplo de lo que puede suceder en lugar de una explicación literal. Su CPU puede tener una arquitectura de predicción de rama mucho más sofisticada.

Answer 2

Creo que puede estar midiendo el rendimiento de la memoria caché / memoria, más que la predicción de rama. Tu bucle interno de "trabajo" está accediendo a una porción cada vez mayor de memoria. Lo que puede explicar el crecimiento lineal, el comportamiento periódico, etc.

Podría estar equivocado, ya que no he intentado replicar sus resultados, pero si fuera usted, factorizaría los accesos a la memoria antes de cronometrar otras cosas. Quizás sumar una variable volátil en otra, en lugar de trabajar en una matriz.

También tenga en cuenta que, dependiendo de la CPU, la predicción de la rama puede ser mucho más inteligente que solo registrar la última vez que se tomó una rama; por ejemplo, los patrones de repetición no son tan malos como los datos aleatorios.

De acuerdo, una prueba rápida y sucia me detuve en mi pausa para el té que intentaba reflejar su propio método de prueba, pero sin golpear el caché, se ve así:

¿Es eso más lo que esperabas?

Si puedo dedicar algo de tiempo más tarde, hay algo más que quiero probar, ya que realmente no he visto lo que está haciendo el compilador ...

Editar:

Y, aquí está mi prueba final: la recodifiqué en el ensamblador para eliminar la bifurcación del bucle, garantizar un número exacto de instrucciones en cada ruta, etc.

También agregué un caso extra, de un patrón de repetición de 5 bits. Parece bastante difícil alterar el predictor de rama en mi Xeon envejecido.