tiempo - precio del bitcoin hoy en dolares

¿Emula el cambio de bit variable usando solo cambios constantes?

Question

Estoy tratando de encontrar una forma de realizar una operación indirecta de desplazamiento a la izquierda / derecha sin usar realmente la variable shift op ni ninguna rama.

El procesador PowerPC en particular en el que estoy trabajando tiene la peculiaridad de que un cambio-por-constante-inmediato, como

int ShiftByConstant( int x ) { return x << 3 ; } 

es rápido, de una sola operación y superescalar, mientras que un cambio por variable, como

int ShiftByVar( int x, int y ) { return x << y ; }

es una operación microcodificada que tarda de 7 a 11 ciclos en ejecutarse mientras todo el resto de la tubería se detiene .

Lo que me gustaría hacer es descubrir qué operaciones PPC enteras no microcodificadas descodifica la sraw y luego emitirlas individualmente. Esto no ayudará con la latencia del sraw en sí - reemplazará una operación por seis - pero entre esas seis operaciones puedo despachar un poco de trabajo a las otras unidades de ejecución y obtener una ganancia neta.

Parece que no puedo encontrar en ninguna parte en qué descodifica el μops sraw, ¿alguien sabe cómo puedo reemplazar un cambio de bit variable con una secuencia de cambios constantes y operaciones enteras básicas? (Un bucle for o un interruptor o cualquier cosa con una bifurcación en él no funcionará porque la penalización de rama es incluso mayor que la penalización de microcódigo).

Esto no necesita ser respondido en el ensamblaje; Espero aprender el algoritmo en lugar del código en particular, por lo que una respuesta en C o un lenguaje de alto nivel o incluso un pseudocódigo sería perfectamente útil.

editar: Un par de aclaraciones que debo agregar:

1. Ni siquiera estoy un poco preocupado por la portabilidad

2. PPC tiene un movimiento condicional, por lo que podemos asumir la existencia de una función intrínseca sin sucursales

   int isel (a, b, c) {return a> = 0? antes de Cristo; }

   (Si escribes un ternario que haga lo mismo, obtendré lo que quieres decir)

3. la multiplicación de números enteros también está microcodificada e incluso más lenta que sraw. :-(

Answer 1

Aquí hay algunas cosas buenas con respecto a la magia negra de la manipulación de bits: manipulación avanzada de bits fu (blog de Christer Ericson)

No sé si alguno de ellos es directamente aplicable, pero si hay una forma, es probable que haya algunos indicios de que hay algo allí.

Answer 2

Este me rompe la cabeza. Ahora he descartado media docena de ideas. Todos ellos explotan la noción de que agregar una cosa a sí mismo se desplaza a la izquierda 1, haciendo lo mismo con los cambios de resultado a la izquierda 4, y así sucesivamente. Si mantiene todos los resultados parciales para el desplazamiento a la izquierda 0, 1, 2, 4, 8 y 16, entonces probando los bits 0 a 4 de la variable de cambio puede obtener su turno inicial. Ahora hazlo de nuevo, una vez por cada 1 bit en la variable shift. Francamente, también podrías enviar tu procesador a tomar un café.

El único lugar en el que buscaría ayuda real es Hank Warren''s Hacker''s Delight (que es la única parte útil de esta respuesta).

Answer 3

Qué tal esto:

int[] multiplicands = { 1, 2, 4, 8, 16, 32, ... etc ...};

int ShiftByVar( int x, int y )
{
    //return x << y;
    return x * multiplicands[y];
}

Answer 4

Supongamos que su cambio máximo es 31. Entonces la cantidad de cambio es un número de 5 bits. Debido a que el cambio es acumulativo, podemos dividirlo en cinco cambios constantes. La versión obvia usa ramificación, pero la descartó.

Deje N ser un número entre 1 y 5. Desea desplazar x por 2 N si el bit cuyo valor es 2 N se establece en y; de lo contrario, mantenga x intacto. Aquí una forma de hacerlo:

#define SHIFT(N) x = isel(((y >> N) & 1) - 1, x << (1 << N), x);

La macro asigna x bien x << 2 ** N o x, dependiendo de si el bit Nth se establece en y o no.

Y luego el conductor:

SHIFT(1); SHIFT(2); SHIFT(3); SHIFT(4); SHIFT(5)

Tenga en cuenta que N es una variable macro y se convierte en constante.

No obstante, no sé si esto va a ser realmente más rápido que el cambio de variable. Si fuera así, uno se pregunta por qué el microcódigo no ejecutaría esto en su lugar ...

Answer 5

Aquí hay algo que es trivialmente desenrollable:

int result= value;

int shift_accumulator= value;

for (int i= 0; i<5; ++i)
{
    result += shift_accumulator & (-(k & 1)); // replace with isel if appropriate
    shift_accumulator += shift_accumulator;
    k >>= 1;
}

Answer 6

Qué tal esto:

if (y & 16) x <<= 16;
if (y & 8) x <<= 8;
if (y & 4) x <<= 4;
if (y & 2) x <<= 2;
if (y & 1) x <<= 1;

probablemente demorará más en ejecutarse pero será más fácil intercalar si tiene otro código para ir entre ellos.

Answer 7

Aqui tienes...

Decidí probar esto también ya que Mike Acton afirmó que sería más rápido que usar el cambio microcodificado CELL / PS3 en su sitio CellPerformance, donde sugiere evitar el cambio indirecto . Sin embargo, en todas mis pruebas, el uso de la versión microcodificada no solo fue más rápido que un reemplazo genérico sin ramificación completo para el cambio indirecto, sino que requiere menos memoria para el código (1 instrucción).

La única razón por la que hice esto como plantillas fue para obtener el resultado correcto para los cambios firmados (generalmente aritméticos) y sin signo (lógicos).

template <typename T> FORCEINLINE T VariableShiftLeft(T nVal, int nShift)
{   // 31-bit shift capability (Rolls over at 32-bits)
    const int bMask1=-(1&nShift);
    const int bMask2=-(1&(nShift>>1));
    const int bMask3=-(1&(nShift>>2));
    const int bMask4=-(1&(nShift>>3));
    const int bMask5=-(1&(nShift>>4));
    nVal=(nVal&bMask1) + nVal;   //nVal=((nVal<<1)&bMask1) | (nVal&(~bMask1));
    nVal=((nVal<<(1<<1))&bMask2) | (nVal&(~bMask2));
    nVal=((nVal<<(1<<2))&bMask3) | (nVal&(~bMask3));
    nVal=((nVal<<(1<<3))&bMask4) | (nVal&(~bMask4));
    nVal=((nVal<<(1<<4))&bMask5) | (nVal&(~bMask5));
    return(nVal);
}
template <typename T> FORCEINLINE T VariableShiftRight(T nVal, int nShift)
{   // 31-bit shift capability (Rolls over at 32-bits)
    const int bMask1=-(1&nShift);
    const int bMask2=-(1&(nShift>>1));
    const int bMask3=-(1&(nShift>>2));
    const int bMask4=-(1&(nShift>>3));
    const int bMask5=-(1&(nShift>>4));
    nVal=((nVal>>1)&bMask1) | (nVal&(~bMask1));
    nVal=((nVal>>(1<<1))&bMask2) | (nVal&(~bMask2));
    nVal=((nVal>>(1<<2))&bMask3) | (nVal&(~bMask3));
    nVal=((nVal>>(1<<3))&bMask4) | (nVal&(~bMask4));
    nVal=((nVal>>(1<<4))&bMask5) | (nVal&(~bMask5));
    return(nVal);
}

EDITAR: Nota sobre isel () Vi su código isel () en su sitio web .

// if a >= 0, return x, else y
int isel( int a, int x, int y )
{
    int mask = a >> 31; // arithmetic shift right, splat out the sign bit
    // mask is 0xFFFFFFFF if (a < 0) and 0x00 otherwise.
    return x + ((y - x) & mask);
};

FWIW, si reescribe su isel () para hacer un complemento de máscara y máscara, será más rápido en su objetivo de PowerPC ya que el compilador es lo suficientemente inteligente como para generar un código de operación ''andc''. Es la misma cantidad de códigos de operación, pero hay una menor dependencia de registro de resultado a entrada en los códigos de operación. Las dos operaciones de máscara también se pueden emitir en paralelo en un procesador superescalar. Puede ser 2-3 ciclos más rápido si todo está alineado correctamente. Solo necesita cambiar el retorno a esto para las versiones de PowerPC:

return (x & (~mask)) + (y & mask);