Как сортировка сетей строится вручную
Есть много 4-элементных, 6-элементных (входных) ... 16-входных сетей сортировки, но мне нужна 32-входная версия, чтобы иметь алгоритм сортировки сдвига 32x32 (который я планирую как вспомогательную функцию Opencl), чтобы иметь сдвиг 1024x1024 алгоритм Opencl. Как я могу получить мою сеть сортировки с 32 входами?
- Может быть, какой-то эволюционный алгоритм, который минимизирует количество перестановок, и я использую его в коде opencl?
- Есть ли фиксированное правило?
или только методом проб и ошибок?
Input array: 1M elements ----> 1024x1024 2D matrix with inverted odd-rows (shear) each row(1024) of matrix --------> 32 x 32 2D matrix (shear) 32 element row ---------> Sorting (network) Each thread computes one row of 1024 elements. So only 1024 threads for 1M element array.
Не расходящееся сравнение, которое я планирую использовать в сети:
if(a>b) // where a and b are between 0 and 16M
swap(a,b)
becomes
a0=a; b0=b; // saving
c = a-b
d = !(sign bit of c) (0 for negative, 1 for positive)
tmp=b*d; //tmp=a if a>b otherwise 0
a=a*d //a=b if a>b otherwise 0
b=tmp*d; //b=tmp if a>b otherwise 0
// a0 is backup of a, b0 is backup of b
e = (sign bit of c) (1 for negative, 0 for positive)
tmp0=a0*e; //tmp0=a0 if a0<=b0 otherwise 0
a0=b0*e //a0=b0 if a0<=b0 otherwise 0
b0=tmp0*e; //b0=tmp0 if a0<=b0 otherwise 0
aOut=a+a0; // only a or a0 can be different than zero
bOut=b+b0; // only b or b0 can be different than zero
Я уверен, что это не самый быстрый, но мне нужно сделать быструю простую сортировку, чтобы примерить мой решатель ограничений частиц, который кричит о сортировке для фиксированной пространственной индексации (сетки), у меня есть 1M частиц, и я пытаюсь использовать сдвиг в сети.
Чтобы проверить сортировку по сдвигу, я реализовал 32-входную сортировку последовательных битовых сортировщиков для каждого потока, чтобы построить матрицу 32x32 для каждого столбца и отсортированной строки. Таким образом, сортировка элементов 32x32 = 1024 заняла 9 мс, а это слишком медленно для 32 ядер при 700 МГц.
Сортировка элемента 1024 занимает 9 мс, и после каждой сортировки 1024 для сортировки массива 1M потребуется не менее 20 итераций. Даже если он достигает 90 мс, это слишком медленно для одних и тех же клавиш. Будет много значений, привязанных к ключам.(Более 100)
Попробовал пузырьковую сортировку вместо битовой и получил 10 мс, так что проблема должна быть в реализации сортировки сдвига, может быть?
2 ответа
В настоящее время сеть сортировки, для которой известно, что для сортировки 32 элементов используются наименьшие единицы сравнения-обмена, работает следующим образом: сортирует первые 16 элементов с помощью наиболее эффективной сети сортировки размером 16, делает то же самое для следующих 16 элементов, а затем использует объединение. шаг от нечетно-четного слияния Дозатора. В основном, это дает следующие пары единиц сравнения-обмена:
Сортировка первой половины массива:
[0,1],[2,3],[4,5],[6,7],[8,9],[10,11],[12,13],[14,15],
[0,2],[4,6],[8,10],[12,14],[1,3],[5,7],[9,11],[13,15],
[0,4],[8,12],[1,5],[9,13],[2,6],[10,14],[3,7],[11,15],
[0,8],[1,9],[2,10],[3,11],[4,12],[5,13],[6,14],[7,15],
[5,10],[6,9],[3,12],[13,14],[7,11],[1,2],[4,8],
[1,4],[7,13],[2,8],[11,14],[5,6],[9,10],
[2,4],[11,13],[3,8],[7,12],
[6,8],[10,12],[3,5],[7,9],
[3,4],[5,6],[7,8],[9,10],[11,12],
[6,7],[8,9]
Сортировать вторую половину массива:
[16,17],[18,19],[20,21],[22,23],[24,25],[26,27],[28,29],[30,31],
[16,18],[20,22],[24,26],[28,30],[17,19],[21,23],[25,27],[29,31],
[16,20],[24,28],[17,21],[25,29],[18,22],[26,30],[19,23],[27,31],
[16,24],[17,25],[18,26],[19,27],[20,28],[21,29],[22,30],[23,31],
[21,26],[22,25],[19,28],[29,30],[23,27],[17,18],[20,24],
[17,20],[23,29],[18,24],[27,30],[21,22],[25,26],
[18,20],[27,29],[19,24],[23,28],
[22,24],[26,28],[19,21],[23,25],
[19,20],[21,22],[23,24],[25,26],[27,28],
[22,23],[24,25]
Нечетное-четное объединение двух половинок массива:
[0, 16],
[8, 24],
[8, 16],
[4, 20],
[12, 28],
[12, 20],
[4, 8],
[12, 16],
[20, 24],
[2, 18],
[10, 26],
[10, 18],
[6, 22],
[14, 30],
[14, 22],
[6, 10],
[14, 18],
[22, 26],
[2, 4],
[6, 8],
[10, 12],
[14, 16],
[18, 20],
[22, 24],
[26, 28],
[1, 17],
[9, 25],
[9, 17],
[5, 21],
[13, 29],
[13, 21],
[5, 9],
[13, 17],
[21, 25],
[3, 19],
[11, 27],
[11, 19],
[7, 23],
[15, 31],
[15, 23],
[7, 11],
[15, 19],
[23, 27],
[3, 5],
[7, 9],
[11, 13],
[15, 17],
[19, 21],
[23, 25],
[27, 29],
[1, 2],
[3, 4],
[5, 6],
[7, 8],
[9, 10],
[11, 12],
[13, 14],
[15, 16],
[17, 18],
[19, 20],
[21, 22],
[23, 24],
[25, 26],
[27, 28],
[29, 30]
Я сгенерировал предыдущие пары индексов с oddeven_merge алгоритм, указанный на странице Википедии. Я не могу гарантировать, что это будет быстрее, чем то, что у вас уже есть, но это, по крайней мере, снизит количество единиц сравнения-обмена с 191 (с нечетно-четным слиянием Бэтчера) до 185. Я читал научные статьи по этому вопросу. и кажется, что в настоящее время мы не знаем сетей сортировки с менее чем 185 компараторами для сортировки 32 элементов.
Я нашел ценную информацию, которая называется Диаграммы Хассе. Чтение, но решение займет некоторое время (возможно, я никогда не смогу), поэтому я искал и нашел ниже уже готовое решение:
Сеть для N=32, используя Merger-Exchange Дозатора. (192 компаратора) http://jgamble.ripco.net/cgi-bin/nw.cgi?inputs=32&algorithm=batcher&output=svg
Используя это для сортировки 32 массивов каждые 32 элемента (нет для цикла, просто написанные от руки компараторы), и применяя сортировку сдвига на 32 ядрах, время ядра сократилось с 9 мс до 2 мс по сравнению с битовой сортировкой (для цикла) + сортировкой сдвига (для циклов). и параллельно).
Это 4-кратное ускорение от перехода к циклическому битоническому сортировщику до неконтурного объединения слияния Дозатора.
Из этого:
void MergeSort32(int * RegisterArray, int dir)"
{"
int n=32;"
for (int s=2; s <= n; s*=2)
{
for (int i=0; i < n;)
{
merge_up((RegisterArray+i),s,dir);
merge_down((RegisterArray+i+s),s,dir);
i += s*2;
}
}
}
в
swapx(arr,0,16,dir);
swapx(arr,1,17,dir);
swapx(arr,2,18,dir);
swapx(arr,3,19,dir);
swapx(arr,4,20,dir);
swapx(arr,5,21,dir);
swapx(arr,6,22,dir);
swapx(arr,7,23,dir);
...
... 191 lines of branchless comparators-swappers
(branching version crashes for some reason, maybe because of
inlined 382 if sentences per core
xor swap idiom shouldnt be a problem.)
Но время компиляции opencl увеличилось с 0,5 до 7,5 секунд. Добавление -cl-opt-disable к опциям делает компиляцию навсегда, пока я не нажму ctrl+alt+del. Таким образом, опции автооптимизации тоже должны оптимизировать компиляцию.
Редактировать: сортировка сдвига (1M), построенная с помощью сортировки сдвига (1k каждый) по Batcher's (32 элемента каждый): 0,341 секунды. HD7870, используя 64 потока на рабочую группу. Сортировка работает как проверено, но намного медленнее, чем сортировка с одноядерным процессором (0,050 секунды).