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

Question

Если вы оптимизируете архитектуру, в которой ветвление стоит дорого (скажем, процессор ячеек PS3), может быть важно определить, можете ли вы выразить данный алгоритм без использования ветвей или, по крайней мере, с использованием меньшего количества ветвей. Один из примеров, который я часто вижу в неоптимизированном коде, - это набор if, используемый для подстройки индекса в некоторый массив (если размер массива нечетный, увеличьте индекс на 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

Преобразование: 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 имеет ANDC (и с дополнением), который делает (~mask) бесплатная операция.

Answer 2

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

Answer 3

Если вы оптимизируете, в частности, для PS3, в Руководстве по написанию компиляторов Power PC в разделе 3.1.5 приведены методы для кода без ветвлений, а в приложении D. приведены последовательности супероптимизатора GNU для кода без ветвей.

Вы также можете быть заинтересованы в блоге Майка Актона "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). Если вам нужна прерывность перехода в вашей конечной индексной функции, используйте функцию sign (будем надеяться, встроенную или используйте 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(K-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

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

так:

 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 6

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

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

Answer 7

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

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

И вставьте вывод этого метода в вашу программу.