有很多 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 毫秒，这对于 700 MHz 的 32 核来说太慢了。
1024个元素排序耗时9ms，每次1024次排序后至少需要迭代20次才能对1M数组进行排序。即使达到 90 毫秒，这对于按键来说也太慢了。键绑定(bind)的值会很多(超过100个)
尝试用冒泡排序代替双音排序并得到 10 毫秒，所以问题一定出在剪切排序实现中？
请您参考如下方法:
目前，已知使用最少比较交换单元对 32 个元素进行排序的排序网络的工作方式如下:使用 most efficient sorting network of size 16 对前 16 个元素进行排序。 ，对以下 16 个元素执行相同操作，然后使用来自 Batcher's odd-even mergesort 的合并步骤.基本上，它给出了以下成对的比较交换单元:
对数组的前半部分进行排序:
[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(使用 Batcher 的奇偶合并排序)减少到 185。我已经阅读了有关此事的研究论文并且我们目前似乎不知 Prop 有少于 185 个比较器的排序网络可以对 32 个元素进行排序。
