Быстрые байты в регистре?
https://stackoverflow.com/questions/1580686
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Учитывая регистр размером 4 байта (или 16 для SIMD), должен быть эффективный способ сортировки байтов в регистре с помощью нескольких инструкций.
Заранее спасибо.
Решение
Найдите эффективный сортировочная сеть для N = количество байтов, которые вас интересуют (4 или 16).Преобразуйте это в последовательность инструкций сравнения и обмена.(Однако для N=16 это будет больше, чем «несколько».)
Другие советы
Нашел!Это есть в статье Фуртака, Амарала и Невядомски «Использование регистров и инструкций SIMD для обеспечения параллелизма на уровне инструкций в алгоритмах сортировки» 2007 года.Раздел 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/ (асм) и здесь 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.
Извините за встроенные строки ссылок;Я не знаю, как добавлять кликабельные ссылки в комментарии stackoverflow.
Все алгоритмы сортировки требуют «перестановки» значений из одного места в другое.Поскольку вы говорите о буквальном регистре ЦП, это означает, что для любого типа потребуется другой регистр, который будет использоваться в качестве временного места для хранения обмениваемых байтов.
Я никогда не видел чипа со встроенным методом сортировки байтов внутри регистра.Я не говорю, что этого не было сделано, но я не могу придумать много вариантов использования такой инструкции.
