Как можно быстрее найти два самых больших из пяти маленьких целых чисел

9

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

    x
  x x x
    x

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

Что приятно, так это то, что все 5 целочисленных входных значений находятся в диапазоне 0-20. Рассчитанное целочисленное значение также находится в диапазоне 0-20!

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

Текущий алгоритм использует 32-битную маску с 1 в позиции, заданной 5 числами, и поддерживаемую HW функцию CLZ.
Я должен сказать, что процессор является проприетарным и недоступен за пределами моей компании. Мой компилятор GCC, но специально для этого процессора.

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

У меня есть комбинаций для ввода, но порядок не важен, то есть такой же, как .215[5,0,0,0,5][5,5,0,0,0]

Бывает, что приведенная ниже хеш-функция создает идеальный хеш без коллизий!

def hash(x):
    h = 0
    for i in x:
        h = 33*h+i
    return h

Но хэш огромен, и для его использования просто недостаточно памяти.

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

Фредрик Пихл
источник
1
Какой алгоритм вы используете в настоящее время? Семи целочисленных сравнений достаточно, это слишком медленно? Ваш hashуже выполняет больше операций. Связаны ли последующие вызовы метода, например, центральный xлинг пересекает матрицу построчно?
Рафаэль
Фильтр свернут через изображение строка за строкой. Т.е. получить 5 значений и выполнить вычисления, затем переместить все на один шаг вправо и повторить. Хеш был только примером. Я протестировал несколько решений с «скользящим окном», чтобы минимизировать чтение данных, но все сводится к нахождению 2 самых высоких значений.
Фредрик Пихл
3
Скорее всего, ваш алгоритм, если он реализован правильно, будет ограничен доступом к памяти, а не вычислениями. Использование хеш-таблицы только увеличит количество обращений к памяти и замедлит работу. Пожалуйста, опубликуйте свой текущий код, чтобы мы могли увидеть, как его можно улучшить - я считаю, что возможна только микрооптимизация. Самое большее, о чем я могу подумать: может быть, мы можем воспользоваться тем фактом, что 2 значения являются общими между соседними окнами?
jkff
@jkff В зависимости от матрицы, размеров кэша и функции отображения (кэша) каждое значение может быть загружено только один раз; тогда большинство операций должно выполняться на регистрах или в кеше L1. Трубопроводы - это еще одна проблема.
Рафаэль
1
Кстати, вы делаете это параллельно? Это кажется особенно подходящим для векторного распараллеливания или SIMD (например, на GPU). Этот маршрут поможет гораздо больше, чем сэкономит несколько процентов на ячейку.
Рафаэль

Ответы:

11

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

U^2(5)знак равно6

Сеть, которую он дает в решениях (переписанная в нулевые массивы)

[0:4][1:4][0:3][1:3][0:2][1:2]

который реализует - после корректировки направления сравнений - в псевдокоде как

def selMax2(a : int[])
  a.swap(0,4) if a[0] < a[4]
  a.swap(1,4) if a[1] < a[4]
  a.swap(0,3) if a[0] < a[3]
  a.swap(1,3) if a[1] < a[3]
  a.swap(0,2) if a[0] < a[2]
  a.swap(1,2) if a[1] < a[2]
  return (a[0], a[1])
end

Теперь наивные реализации все еще имеют условные переходы (через код подкачки). В зависимости от вашей машины вы можете обойти их условными инструкциями. x86, кажется, обычная грязь; ARM выглядит более перспективным, так как, по-видимому, большинство операций являются условными сами по себе. Если я правильно понимаю инструкции , первый своп преобразуется в это, предполагая, что наши значения массива были загружены в регистры R0через R4:

CMP     R0,R4
MOVLT   R5 = R0
MOVLT   R0 = R4
MOVLT   R4 = R6

Да, да, конечно, вы можете использовать обмен XOR с EOR .

Я просто надеюсь, что ваш процессор имеет это, или что-то подобное. Конечно, если вы создадите это для этой цели, может быть, вы сможете подключить туда сеть?

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


  1. Сортировка и поиск Дональд Э. Кнут; Искусство компьютерного программирования Vol. 3 (2-е изд, 1998)
  2. W^2(5)знак равно7
Рафаэль
источник
Я принимаю это. Я получил много новых идей, которые мне нужно сравнить, прежде чем двигаться дальше. Ссылка на Кнут всегда работает для меня :-) Спасибо за ваши усилия и время!
Фредрик Пихл
@FredrikPihl Круто, пожалуйста, дайте нам знать, как это получается в конце концов!
Рафаэль
Я буду! Чтение главы 5.3.3 прямо сейчас. Люблю начало этого со ссылками на Льюиса Кэрролла и теннисный турнир :-)
Фредрик Пихл
2
В зависимости от набора инструкций может быть полезным использование 2 * max (a, b) = a + b + abs (ab) вместе с сетью выбора; это может быть дешевле, чем непредсказуемые условные переходы (даже без внутреннего или условного перемещения для abs: gcc, по крайней мере для x86, генерирует последовательность без переходов, которая, кажется, не зависит от x86). Наличие последовательности без прыжков также полезно в сочетании с SIMD или GPU.
AProgrammer
1
Обратите внимание, что сети выбора (например, сети сортировки) поддаются параллельным операциям; в частности, в указанной сети выбора сравнения 1: 4 и 0: 3 могут выполняться параллельно (если процессор, компилятор и т. д. поддерживают это эффективно), а сравнения 1: 3 и 0: 2 также могут выполняться параллельно.
Брюс Лилли
4

Просто для того, чтобы это было на столе, вот прямой алгоритм:

// Sort x1, x2
if x1 < x2
  M1 = x2
  m1 = x1
else
  M1 = x1
  m1 = x2
end

// Sort x3, x4
if x3 < x4
  M2 = x4
  m2 = x3
else
  M2 = x3
  m2 = x4
end

// Pick largest two
if M1 > M2
  M3 = M1
  if m1 > M2
    m3 = m1
  else
    m3 = M2
  end
else
  M3 = M2
  if m2 > M1
    m3 = m2
  else
    m3 = M1
  end
end

// Insert x4
if x4 > M3
  m3 = M3
  M3 = x4
else if x4 > m3
  m3 = x4
end

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

Это некрасиво, но занимает только

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

W2(5)

Однако нельзя ожидать, что это будет быстрым на машинах с конвейерной обработкой; учитывая высокий процент условных скачков, большая часть времени, вероятно, будет проведена в стойле.

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


  1. Сортировка и поиск Дональд Э. Кнут; Искусство компьютерного программирования Vol. 3 (2-е изд, 1998)
Рафаэль
источник
Интересно, что оптимизатор может сделать с ними.
Рафаэль
Я реализую это и сравню с текущим решением на базе CLZ. Спасибо за ваше время!
Фредрик Пихл
1
@FredrikPihl Каков был результат ваших тестов?
Рафаэль
1
SWAP-подход превосходит CLZ! На мобильном сейчас. Вы можете опубликовать больше данных в другой раз, на мобильном сейчас
Фредрик Пихл
@FredrikPihl Круто! Я счастлив, что старый добрый теоретический подход может (все еще) иметь практическое применение. :)
Рафаэль
4

Это может быть отличным приложением и тестовым примером для проекта Souper . Souper - это супероптимизатор - инструмент, который принимает короткую последовательность кода в качестве входных данных и пытается максимально оптимизировать ее (пытается найти эквивалентную последовательность кода, которая будет быстрее).

Souper с открытым исходным кодом. Вы можете попробовать запустить Souper в своем фрагменте кода, чтобы посмотреть, сможет ли он работать лучше.

Смотрите также конкурс Джона Регера на написание быстрого кода для сортировки 16 4-битных значений ; Возможно, что некоторые из техник там могут быть полезны.

DW
источник
Мне было бы интересно узнать, что это может делать с программами, которые пытается использовать ОП.
Рафаэль
3

213

T[T[T[441*a+21*b+c]*21+d]*21+e]

214 таблицу , вы можете сократить ее до двух поисков в таблице, хотя не ясно, что это будет быстрее.

212

212

Юваль Фильмус
источник