Сортировка массивов фиксированной длины с применением SIMD
Простая сортировка массива очень простая задача, в то время как эффективная сортировка очень сложная, во многом из-за простоты задачи.
Смысл этого логического парадокса заключается в том, что решение сложной задачи возможно множеством способов, среди которых всегда можно попробовать найти еще более эффективный. В то время как решение простой задачи, обычно возможно всего несколько способами, усовершенствовать которые не так просто, по причине того, что за десятки лет работы множества людей оптимизация достигла поистине впечатляющего уровня.
Наиболее очевидным путем оптимизации сортировки массива является параллельная сортировка его частей, но этот способ сталкивается с проблемой высоких накладных расходов на запуск параллельных процессов и несоизмеримой сложностью решения проблемы и получаемого результата. Как следствие представляется очень интересным способ задействовать для сортировки возможности SIMD инструкций, которые даже для «стандартного» SSE2 теоретически могут позволить сортировать 4-е потока 32-х битных чисел и добиться четырёхкратного прироста скорости.
Ниже представлен вариант сортировки массива из 16-и, 32-х битных безнаковых чисел, реализованный посредством SIMD инструкций SSE4.1 сета. Представленный код по своей сути является демонстратором алгоритма и не подразумевает практического применения.
Возражения что массивы редко бывают четко фиксированной длины, я хотел бы парировать замечанием, что большие массивы можно разделить на субмассивы требуемой длины, алгоритм может быть легко расширен до 32-х и 64-х членов, а массивы не кратной длины могут быть легко дополнены «избыточными» элементами имеющими максимально/минимальное значение, которые как следствие в ходе сортировки сосредоточатся на каком либо из концов массива где их можно будет легко проигнорировать.
Возражение что это частный случай исключительно для безнаковых 32-х битных чисел, я хотел бы парировать замечанием, что SIMD инструкции позволяют написать абсолютно аналогичные алгоритмы для знаковых целых чисел и чисел с плавающей запятой одинарной точности. Эффективность работы с числами двойной точностью уже не столь значительна, но продолжает сохраняться.
Будем считать, что метод принимает один единственный параметр, это начала массива, которое в соответствии с соглашением о вызовах VECTORCALL будет расположен в регистре ECX.
Загружаем все 16-ть значений подлежащих сортировки в SIMD регистры. Это первое и последние обращение к памяти для чтения, следующие обращение будет использовано уже для записи отсортированного массива. Таким образом, один раз получив данные, алгоритм вернет уже полностью отсортированный массив максимально сократив количества обращений к памяти.
movdqa xmm1, [rcx + xmmword * 0]
movdqa xmm2, [rcx + xmmword * 1]
movdqa xmm4, [rcx + xmmword * 2]
movdqa xmm5, [rcx + xmmword * 3]Буквально 6-ю командами сортируем массив, объединяя числовой ряд в восемь упорядоченных пар.
movdqa xmm0, xmm2
pmaxud xmm2, xmm1
pminud xmm1, xmm0
movdqa xmm3, xmm5
pmaxud xmm5, xmm4
pminud xmm4, xmm3Следующий шаг это сортировка полученных пар в тетрады и если найти наименьшие/наибольшие не представляется сложным, нужно просто сравнить самое наименьшие/наибольшие число из каждой пары с аналогичным ему числом из другой пары, то нахождение «промежуточных» чисел не так очевидно, но тоже довольно просто. Необходимо найти наименьшие из наибольших и наибольшие из наименьших, после чего уже сравнить и упорядочить их. Для этого потребуеться всего 9 инструкций.
movdqa xmm0, xmm1
pminud xmm0, xmm4
movdqa xmm3, xmm2
pmaxud xmm3, xmm5
pminud xmm2, xmm5
pmaxud xmm1, xmm4
movdqa xmm4, xmm1
pminud xmm1, xmm2
pmaxud xmm2, xmm4Транспонируем полученную матрицу для дальнейшей сортировки. Не берусь утверждать, что представленный код транспонирования наиболее эффективный, возможно его можно сократить на пару тактов, но для демонстрации алгоритма это не критично.
movdqa xmm4, xmm0
punpckhdq xmm4, xmm1
movdqa xmm5, xmm2
punpckldq xmm5, xmm3
punpckldq xmm0, xmm1
movdqa xmm1, xmm0
punpcklqdq xmm0, xmm5
punpckhqdq xmm1, xmm5
punpckhdq xmm2, xmm3
movdqa xmm3, xmm4
punpckhqdq xmm3, xmm2
punpcklqdq xmm4, xmm2Теперь, после транспонирования, в каждом регистре расположены четыре числа упорядоченных по возрастанию. Произведем 4-е сравнения и обмена, в ходе которых произведем объединение 4-х тетрад в 2-е октавы. Стоит заметить, что если в первом сравнения происходит обмен 4-х пар чисел, то на последующих сравнениях количество обменов с каждым разом уменьшается на единицу и в последнем сравнении происходит всего один обмен.
mov eax, 4
@@:
movdqa xmm2, xmm1
pmaxud xmm1, xmm0
pminud xmm0, xmm2
pshufd xmm1, xmm1, 10010011b
movdqa xmm5, xmm4
pmaxud xmm4, xmm3
pminud xmm3, xmm5
pshufd xmm4, xmm4, 10010011b
dec eax
jnz @bВыполняем последнюю серию сравнений, в ходе которой окончательно упорядочиваем числовую последовательность, сравнивая две октавы.
mov eax, 8
@@:
movdqa xmm2, xmm3
movdqa xmm5, xmm4
pmaxud xmm3, xmm0
pmaxud xmm4, xmm1
pminud xmm0, xmm2
pminud xmm1, xmm5
pshufd xmm3, xmm3, 10010011b
pshufd xmm4, xmm4, 10010011b
movss xmm5, xmm3
movss xmm3, xmm4
movss xmm4, xmm5
dec eax
jnz @bФормально, для того чтобы алгоритм можно было считать полным необходимо выполнить запись полученных данных в память.
movdqa [rcx + xmmword * 0], xmm0
movdqa [rcx + xmmword * 1], xmm1
movdqa [rcx + xmmword * 2], xmm3
movdqa [rcx + xmmword * 3], xmm4Надеюсь вам было интересно, рад буду услышать интересную, конструктивную критику.
P.S. Эффективность алгоритма значительно возрастает при наличии на целевой машине AVX.
