Быстрая регистрация типа байтов?
Учитывая регистр 4 байта (или 16 для SIMD), должен быть эффективный способ сортировки байтов в регистре с помощью нескольких инструкций.
Заранее спасибо.
4 ответа
Найдите эффективную сеть сортировки для N = количество байтов, о которых вы заботитесь (4 или 16). Преобразуйте это в последовательность инструкций сравнения и обмена. (Для N=16 это будет больше, чем "несколько".)
Нашел это! Это в статье 2007 года "Использование регистров SIMD и инструкций для включения параллелизма на уровне инструкций в алгоритмах сортировки" Фуртака, Амарала и Невиадомского. Раздел 4
Он использует 4 регистра SSE, имеет 12 шагов и выполняет 19 инструкций, включая загрузку и сохранение.
В этой же статье проделана отличная работа по динамическому созданию сетей сортировки с использованием SIMD.
Чтобы ускорить сортировку строк, я в итоге упаковал 7 байт на удвоение и отсортировал (ранжировал) массив из 16 двойников в SSE2, используя битовую сортировку для создания двух серий по 8 и двоичное слияние для объединения двух серий. Вы можете увидеть первую часть здесь http://mischasan.wordpress.com/2011/07/29/okay-one-more-poke-at-sse2-sorting-doubles/ (asm) и здесь http://mischasan.wordpress.com/2011/09/02/update-on-bitonic-sse2-sort-of-16-doubles/ (C) и шаг битонического слияния (если вы хотите пройти SSE до конца) здесь: http://mischasan.wordpress.com/2012/11/04/sse2-odd-even-merge-the-last-step-in-sorting/. Я заменил сортировку вставки в нижней части qsort на эту сортировку, и она примерно в 5 раз быстрее прямой qsort. НТН
Я не видел газету UofA; Битонная логика взята из старой школы (CTM) GPGPU.
Извините за встроенные строки ссылок; Я не знаю, как добавить кликабельные ссылки в комментариях stackru.
Все алгоритмы сортировки требуют "перестановки" значений из одного места в другое. Поскольку вы говорите о буквальном регистре ЦП, это означает, что для любого вида потребуется другой регистр, который будет использоваться как временное место для хранения заменяемых байтов.
Я никогда не видел чип со встроенным методом для сортировки байтов в регистре. Не сказать, что это не было сделано, но я не могу придумать много вариантов использования такой инструкции.