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

Question

Estoy tratando de encontrar una manera de realizar una operación indirecta de desplazamiento a la izquierda/derecha sin utilizar realmente la variable shift op o cualquier rama.

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

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

es rápido, sencillo-op, y superescalar, mientras que un cambio por caso variables, como

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

es un microcoded operation that takes 7-11 cycles to execute while the entire rest of the pipeline stops dead.

Lo que me gustaría hacer es averiguar qué números PPC enteros no microcodificados se decodifican en sraw y luego emitirlos individualmente. Esto no ayudará con la latencia del sraw en sí — reemplazará una operación con seis — pero entre esas seis operaciones puedo despachar dos tareas a las otras unidades de ejecución y obtener una ganancia neta.

Parece que no puedo encontrar μ ops sraw decodifica en — ¿Alguien sabe cómo puedo reemplazar un cambio de bit variable con una secuencia de cambios constantes y operaciones enteras básicas? (Un bucle o un interruptor o cualquier cosa con una bifurcación no funcionará porque la penalización de bifurcación es incluso mayor que la penalización de microcódigo.)

No es necesario responder esta pregunta en el conjunto; 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.

edición: Un par de aclaraciones que debo añadir:

1. ni siquiera estoy un poco preocupado acerca de la portabilidad

2. PPC tiene un condicional-movimiento, por lo que puede suponer la existencia de una función intrínseca sin sucursal

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

   (si se escribe un ternaria que hace lo mismo voy a conseguir lo que quiere decir )

3. número entero se multiplican también microcodificado e incluso más lento que sraw. :-(

Answer 1

Aquí tienes ...

yo decidimos probar estos fuera así desde que Mike Acton afirmó que sería más rápido que utilizando la celda/PS3 cambio microcodificado en su sitio CellPerformance donde he suggests to avoid the indirect shift. 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 tanto para los cambios firmados (normalmente aritméticos) como para los sin firmar (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); 
} 

EDIT: Nota sobre ISEL() Vi su isel() code on your website.

// 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 se vuelve a escribir su ISEL() para hacer una máscara y una máscara de complemento, que será más rápido en su objetivo PowerPC ya que el compilador es suficientemente inteligente como para generar un código de operación 'y c'. 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.Sólo tiene que cambiar la vuelta a esto para las versiones PowerPC:

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

Answer 2

¿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 necesitará más tiempo para ejecutar aún más fácil, pero para intercalar si tiene otro código para ir entre

Answer 3

Ésta rompe la cabeza. Ahora he descartado media docena de ideas. Todas 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 que quedan a la izquierda 4. Y así sucesivamente. Si mantiene todos los resultados parciales del turno izquierdo 0, 1, 2, 4, 8 y 16, luego probando los bits 0 a 4 de la variable de cambio puede obtener su turno inicial. Ahora hágalo nuevamente, onc e por cada 1 bit en la variable de cambio. Francamente, también podrías enviar tu procesador a tomar un café.

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

Answer 4

¿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 5

Vamos a suponer que su desplazamiento máximo es 31. Por lo tanto la cantidad de desplazamiento 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. Usted quiere cambiar x por 2 N si el bit cuyo valor es 2 N está configurado en y, de lo contrario, mantenga x intacto. Aquí una manera de hacerlo:

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

Los cesionarios de macro para x, ya sea x < < 2 ** N o x, dependiendo de si el bit N-ésimo se establece en Y o no.

Y entonces el conductor:

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

Nótese que N es una variable macro y se vuelve constante.

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

Answer 6

Hay algunas cosas buenas aquí con respecto a la manipulación de bits magia negro: Advanced bit manipulation fu (Christer Ericson's blog)

No sabe si cualquiera de sus directamente aplicable, pero si hay una manera, es probable que haya algunos indicios de esa manera en alguna parte.

Answer 7

Aquí hay algo que es trivialmente desenrollables:

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; 
}