Эмулируемый переменный битовый сдвиг, используя только постоянные сдвиги?

Question

Я пытаюсь найти способ выполнить косвенную операцию сдвига влево / вправо, фактически не используя переменную сдвига op или какие-либо ветви.

Конкретный процессор PowerPC, над которым я работаю, обладает особенностью немедленного сдвига, как

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

быстрый, однооперационный и суперскалярный, в то время как смещение на переменную, как

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

- это операция микрокодирования , выполнение которой занимает 7-11 циклов, а весь остальной конвейер останавливается .

То, что я хотел бы сделать, - это выяснить, какой не-микрокодированный PPC выполняет декодирование sraw , а затем выдать их по отдельности. Это не поможет с задержкой самой sraw & mdash; он заменит одну операцию на шесть & mdash; но в промежутке между этими шестью операциями я могу сдать часть работы другим исполнительным блокам и получить чистый выигрыш.

Кажется, я нигде не могу найти, что & mu; sps sraw декодирует в & mdash; Кто-нибудь знает, как я могу заменить переменный бит-сдвиг с последовательностью постоянных сдвигов и основных целочисленных операций? (Цикл for, или переключатель, или что-либо с ветвлением в нем не будет работать, потому что штраф за переходы даже больше, чем штраф за микрокод, даже для правильно предсказанных переходов.)

На это не нужно отвечать в собрании; Я надеюсь изучить алгоритм, а не конкретный код, поэтому ответ на языке C, языке высокого уровня или даже псевдокоде был бы очень полезен.

Редактировать: Пара уточнений, которые я должен добавить:

1. Меня даже не беспокоит переносимость

2. PPC имеет условный ход, поэтому мы можем предположить существование внутренней функции без ответвлений

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

   (если вы напишите троицу, которая делает то же самое, я получу то, что вы имеете в виду)

3. целочисленное умножение также микрокодируется и даже медленнее, чем sraw. : - (
4. На Xenon PPC задержка прогнозируемой ветви составляет 8 циклов, поэтому даже один делает это столь же дорогостоящим, как и микрокодированная инструкция. Переход к указателю (любая косвенная ветвь или указатель на функцию) является гарантированным ошибочным прогнозом, остановкой на 24 цикла.

Answer 1

Вот, пожалуйста ...

Я решил попробовать их также, поскольку Майк Актон заявил, что это будет быстрее, чем использование микрокодированного сдвига CELL / PS3 на его сайте CellPerformance, где он предлагает избежать косвенного сдвига . Однако во всех моих тестах использование микрокодированной версии было не только быстрее, чем полная универсальная замена без ветвления для косвенного сдвига, но и потребовало гораздо меньше памяти для кода (1 инструкция).

Единственная причина, по которой я сделал это в качестве шаблонов, заключается в том, чтобы получить правильный вывод как для знаковых (обычно арифметических), так и для беззнаковых (логических) смен.

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

РЕДАКТИРОВАТЬ: Примечание на isel () Я видел ваш isel () код на вашем сайте .

// 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, если вы переписываете свой isel () для создания маски и дополнения к маске, это будет быстрее для вашей цели PowerPC, поскольку компилятор достаточно умен, чтобы сгенерировать код операции 'andc'. Это такое же количество кодов операций, но в кодах операций имеется одна зависимость результата от регистра ввода-вывода. Две операции маски могут также выполняться параллельно на суперскалярном процессоре. Это может быть на 2-3 цикла быстрее, если все выстроено правильно. Вам просто нужно изменить возврат на это для версий PowerPC:

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

Answer 2

Как насчет этого:

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;

вероятно, потребуется больше времени для выполнения, но легче чередовать, если у вас есть другой код для перехода.

Answer 3

Предположим, что ваш максимальный сдвиг равен 31. Таким образом, величина сдвига является 5-битным числом. Поскольку сдвиг является кумулятивным, мы можем разбить его на пять постоянных сдвигов. Очевидная версия использует ветвление, но вы исключили это.

Пусть N будет числом от 1 до 5. Вы хотите сдвинуть x на 2 ^N , если бит, значение которого равно 2 ^N устанавливается в y , в противном случае сохраните x без изменений. Вот один из способов сделать это:

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

Макрос присваивает x либо x << 2ᴺ, либо x, в зависимости от того, установлен бит N ^th в y или нет.

А потом драйвер:

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

Обратите внимание, что N является макропеременной и становится постоянной.

Не знаю, будет ли это на самом деле быстрее, чем переменная shift. Если это так, то возникает вопрос, почему микрокод не запустил бы это вместо этого ...

Answer 4

Этот ломает мне голову. Теперь я отбросил полдюжины идей. Все они используют понятие, что добавление вещи к себе сдвигает влево 1, делает то же самое с сдвигами результата влево 4 и так далее. Если вы сохраните все частичные результаты для сдвига влево 0, 1, 2, 4, 8 и 16, то, протестировав биты от 0 до 4 переменной сдвига, вы можете получить ваш начальный сдвиг. Теперь сделайте это снова, один раз для каждого 1 бита в переменной сдвига. Честно говоря, вы могли бы также отправить свой процессор для кофе.

Единственное место, куда я бы обратился за реальной помощью, - это Восторг Хакера от Хэнка Уоррена (единственная полезная часть этого ответа).

Answer 5

Если количество смен можно рассчитать заранее, у меня есть две идеи, которые могут сработать

• Использование самоизменяющегося кода

  Просто измените величину смены непосредственно в инструкции. Альтернативно генерировать код динамически для функций с переменной shift

• Сгруппируйте значения с одним и тем же числом сдвигов, если это возможно, и выполните операцию одновременно, используя указатель устройства или функции Даффа, чтобы минимизировать ошибочное прогнозирование ветвления

  // shift by constant functions
  typedef int (*shiftFunc)(int);    // the shift function
  #define SHL(n) int shl##n(int x) { return x << (n); }
  SHL(1)
  SHL(2)
  SHL(3)
  ...
  shiftFunc shiftLeft[] = { shl1, shl2, shl3... };
  
  int arr[MAX];       // all the values that need to be shifted with the same amount
  shiftFunc shl = shiftLeft[3]; // when you want to shift by 3
  for (int i = 0; i < MAX; i++)
      arr[i] = shl(arr[i]);
  

  Этот метод также можно использовать в сочетании с самоизменяющимся кодом или генерацией кода во время выполнения, чтобы устранить необходимость в указателе функции.

  Редактировать: Как уже отмечалось, к сожалению, предсказание ветвления при переходе на регистрацию вообще отсутствует, поэтому единственный способ, которым это может сработать, - это генерировать код, как я уже говорил выше, или использовать SIMD

---

Если диапазон значений невелик, справочная таблица является другим возможным решением

#define S(x, n) ((x) + 0) << (n), ((x) + 1) << (n), ((x) + 2) << (n), ((x) + 3) << (n), \
                ((x) + 4) << (n), ((x) + 5) << (n), ((x) + 6) << (n), ((x) + 7 << (n)
#define S2(x, n)    S((x + 0)*8, n), S((x + 1)*8, n), S((x + 2)*8, n), S((x + 3)*8, n), \
                    S((x + 4)*8, n), S((x + 5)*8, n), S((x + 6)*8, n), S((x + 7)*8, n)
uint8_t shl[256][8] = {
    { S2(0U, 0), S2(8U, 0), S2(16U, 0), S2(24U, 0) },
    { S2(0U, 1), S2(8U, 1), S2(16U, 1), S2(24U, 1) },
    ...
    { S2(0U, 7), S2(8U, 7), S2(16U, 7), S2(24U, 7) },
}

Теперь x << n - это просто shl[x][n] с x, равным uint8_t. Таблица стоит 2 КБ (8 × 256 B) памяти. Однако для 16-битных значений вам понадобится таблица размером 1 МБ (16 × 64 КБ), которая все еще может быть жизнеспособной, и вы можете сделать 32-битный сдвиг, комбинируя два 16-битных сдвига вместе

Answer 6

Вот что-то, что тривиально неуправляемо:

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 7

Здесь есть кое-что хорошее, касающееся битовой манипуляции с черной магией: Продвинутая фу манипуляция битами (блог Кристера Эриксона)

Не знаю, применимо ли какое-либо из них напрямую, но если есть какой-то путь, вероятно, есть где-то намеки на этот путь.

Answer 8

Как насчет этого:

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

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