Методика определения, можно ли генерировать целую последовательность без ветвей?

Question

Если вы оптимизируете архитектуру, на которой ветвление стоит дорого (скажем, процессор ячеек PS3), может быть важно определить, можете ли вы выражать данный алгоритм без использования ветвей или, по крайней мере, с использованием меньшего количества ветвей , Один шаблон, который я вижу много в неоптимизированном коде, - это куча if, используемая для настройки индекса в некоторый массив (если размер массива нечетный, bump индекс на 1, при некоторых других обстоятельствах умножайтесь на 2 и т. Д.). Так что было бы неплохо, если бы был способ, учитывая два списка чисел, чтобы определить, можно ли написать функцию без разбиения, превращая один список в другой.

Например, я недавно хотел узнать, можно ли написать ветвящуюся функцию, которая преобразует: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 в: 0, 2, 4, 6, 8, 9, 7, 5, 3, 1 (по возрастанию, а затем по убыванию). Технически я мог бы написать большую функцию switch/case, но, очевидно, меня интересует функция, которая будет следовать шаблону для произвольных размеров. Написание функции для выполнения этого преобразования является прямым с ветвлением, но если есть способ неважно, это не сразу становится очевидным.

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

Answer 1

Если скорость действительно важна, не могли бы вы выписать инструкции для списков до определенной длины? (Можно было бы, конечно, генерировать этот код).

так:

void algorithm1_Length6(int *srcList, int *destList) 
{ 
     *destList++ = *srcList; 
     *destList++ = srcList[2]; 
     *destList++ = srcList[4]; 
     *destList++ = srcList[5]; 
     *destList++ = srcList[3]; 
     *destList++ = srcList[1]; 
} 

и все другие варианты Шифрование до определенной длины.

Answer 2

Для данного массива можно использовать метод как это:

void tranform(int[] src, int[] dest) { 
     //0, 2, 4, 6, 8, 9, 7, 5, 3, 1 
     dest[0] = src[0]; 
     dest[1] = src[2]; 
     dest[2] = src[4]; 
     dest[3] = src[6]; 
     dest[4] = src[8]; 
     dest[5] = src[9]; 
     dest[6] = src[7]; 
     dest[7] = src[5]; 
     dest[8] = src[3]; 
     dest[9] = src[1]; 
    } 

Но в целом для больших массивов это трудно писать такие методы, поэтому он будет полезен, если вы пишете метод генератора, как это:

static void createFunction(int[] src, int[] dest) { 
     System.out.println("void tranform(int[] src, int[] dest) {"); 
     for (int i = 0; i < dest.length; i++) { 
      for (int j = 0; j < src.length; j++) { 
       if (dest[i] == src[j]) { 
        System.out.println("dest[" + i + "]=src[" + j + "];"); 
        break; 
       } 
      } 
     } 
     System.out.println("}"); 
    } 

вызвать его с массивами: createFunction(new int[]{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, new int[]{0, 2, 4, 6, 8, 9, 7, 5, 3, 1});

и пастообразных выход этого метода к вашей программе.

Answer 3

Если вы оптимизации для PS3 в частности, Power PC Compiler Writers Guide имеет методы на branchfree кода в разделе 3.1.5 и имеет GNU Superoptimizer последовательности для branchfree кода в приложении D.

Вы можете быть заинтересованы в Mike Acton's Cell Performance Блог также.

Answer 4

Если вы создаете желаемые индексы против ваших входных индексов, вы получаете треугольную форму.Оказывается, что для n = 10 случае,

9.5 - abs(2 (x - 4.75)) 

Таким образом, для общего n, было бы

n-0.5 - abs(2*(x - n/2-0.25)) 

Или в целочисленном виде,

(2*n-1 - abs(4*x - 2*n + 1))/2 

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

Очевидно, что если ваши желаемые конечные индексы образуют прямую линию, то преобразование прост. Если у вас есть перегиб в отображении, то вы хотите использовать функцию абсолютного значения, чтобы ввести изгиб, и вы можете настроить масштабирование, чтобы изменить угол поворота. Вы можете наклонить кинк, смещая его (например, abs(x)+x/2). Если вам нужна скачка разрыва в вашей конечной функции индекса, то используйте функцию знака (надеюсь, встроенный или используйте abs (x)/x). Вам нужно проявить творческий подход к использованию графиков общих функций в ваших интересах.

---

Добавление

Если функция индексации кусочно-линейной, есть простой алгоритм. Предположим, искомая функция индекса выражается в виде списка сегментов

{(sx1,sy1)-(ex1,ey1), (sx2,sy2)-(ex2,ey2), ... , (sxN,syN)-(exN,eyN)} 
segment 1   segment 2     segment N 

где EXK> SXK для всех K и SXK> SX (К-1) для всех K (ставят их слева направо).

k = 1 
f(x) = Make affine model of segment k 
g(x) = f(x) 
Do: 
    k = k + 1 
    h(x) = Makeaffine model of segment k 
    If g(x) and h(x) intersect between ex(k-1) and ex(k) 
     f(x) = f(x) + [slope difference of g(x) and h(x)] * ramp(x) 
    Else 
     f(x) = f(x) + (h(ex(k-1)) - f(ex(k-1))) * step(x) 
     f(x) = f(x) + [slope difference of g(x) and h(x)] * ramp(x) 

где ramp(x) = (abs(x)+x)/2 и step(x) = (sign(x)+1)/2. f (x) означает желаемую функцию, g(x) - аффинная модель последнего сегмента, а h(x) - аффинная модель текущего сегмента. Аффинная модель - это всего лишь линия в форме смещения склона: a*x+b, а разница наклона - это разность наклонов. Этот алгоритм просто исходит из левого права, добавляя в него правильные куски функций. Функции, которые он добавляет, всегда равны нулю для x <= 0, поэтому они не влияют на f(x), который был создан до сих пор.

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

Answer 5

Трансформация: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 до: 0, 2, 4, 6, 8, 9, 7, 5, 3, 1 (по возрастанию даже после по убыванию).

Простой: при заданной последовательности значений N от X от 0 до N-1 мы видим, что первая половина последовательности равна 2X. Вторая половина последовательности (2N-1) -2X. Последовательность расщепляется при X = (N + 1)/2 с «целочисленной» математикой. В приведенном выше примере, N == 10.

Так предполагая, 32-разрядные подписанные Интс с арифметическим сдвигом вправо:

int Transform(int x) 
{ 
    const int seq1=x+x; 
    const int mask=(x-((N+1)>>1))>>31; 
    const int seq2=(N+N-1)-seq1; 
    return (mask&seq1)|((~mask)&seq2); 
} 

Обратите внимание, что шаблон маски, используемый здесь, быстро, потому что PowerPC, имеет и с (и дополнение), что делает бесплатной операцию (~mask).

Answer 6

Вы всегда можете написать формулу полинома, используя интерполяцию Лагранжа, например. Не красиво (или особенно быстро), но у него не будет никаких ветвей.

Answer 7

Технически любая серия операций может быть выполнена без «разветвления» с использованием конечного автомата, который использует логические операции. Концепция ветвления связана с тем, что большинство программ представляют собой последовательность команд, выполняемых программным счетчиком, который может идти так или иначе.

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