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

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

Если вы строите желаемые индексы относительно ваших входных индексов, вы получаете функцию треугольной формы. Получается, что для вашего 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 4

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

Тебя может заинтересовать Блог Майка Актона Блог.

Answer 5

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

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

Answer 6

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

 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 7

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

так:

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

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