标题： 基于列表偏移归并排序器的硬件中有序输入列表的快速高效合并 显示英文标题

标题： Fast and Efficient Merge of Sorted Input Lists in Hardware Using List Offset Merge Sorters

摘要： 这里介绍了一组新的硬件归并排序设备，这些设备能够以快速高效的方式将多个已排序的输入列表合并成一个已排序的输出列表。 在每个归并排序器中，来自已排序输入列表的值被安排在一个输入二维设置数组中，但每个已排序输入列表的顺序相对于其他已排序输入列表的顺序有所偏移。 在这些新设备中，称为列表偏移归并排序器（LOMS），通过交替的列排序阶段和行排序阶段处理输入设置数组，最终生成按定义顺序排列的输出数组。 LOMS 两路排序器，用于合并两个已排序的输入列表，只需要两个归并阶段，并且比Kenneth Batcher之前最先进的两路归并设备——比特onic归并排序器和奇偶归并排序器要快得多。 LOMS 两路排序器在其第一阶段使用了最近引入的单阶段两路归并排序器（S2MS）。 LOMS 和 S2MS 设备都可以合并任何混合的输入列表大小，而 Batcher 的归并排序器除非两个输入列表相等且为 2 的幂次方，否则很难设计。 单独来看，S2MS 设备在本研究的目标 FPGA 设备中实现时是最快的两路归并排序器，但它们往往需要大量的 LUT 资源。 LOMS 两路设备比相应的 S2MS 设备使用的资源更少，使得一些大型 LOMS 设备可以在给定的 FPGA 中实现，而相应的 S2MS 设备却无法在该 FPGA 中容纳。 一个列表偏移两路排序器将两个各含 32 个值的列表合并成一个包含这 64 个值的已排序输出列表，耗时 2.24 nS，相比相应的 Batcher 设备速度提高了 2.63 倍。 一个 LOMS 三路归并排序器，合并三个各含 7 个值的已排序输入列表，完全合并 21 个值耗时 3.4 nS，相比相应的最先进三路归并设备速度提高了 1.36 倍。 显示英文摘要

摘要： A new set of hardware merge sort devices are introduced here, which merge multiple sorted input lists into a single sorted output list in a fast and efficient manner. In each merge sorter, the values from the sorted input lists are arranged in an input 2-D setup array, but with the order of each sorted input list offset from the order of each of the other sorted input lists. In these new devices, called List Offset Merge Sorters (LOMS), a minimal set of column sort stages alternating with row sort stages process the input setup array into a final output array, now in the defined sorted order. LOMS 2-way sorters, which merge 2 sorted input lists, require only 2 merge stages and are significantly faster than Kenneth Batcher's previous state-of-the-art 2-way merge devices, Bitonic Merge Sorters and Odd-Even Merge Sorters. LOMS 2-way sorters utilize the recently-introduced Single-Stage 2-way Merge Sorters (S2MS) in their first stage. Both LOMS and S2MS devices can merge any mixture of input list sizes, while Batcher's merge sorters are difficult to design unless the 2 input lists are equal, and a power-of-2. By themselves, S2MS devices are the fastest 2-way merge sorters when implemented in this study's target FPGA devices, but they tend to use a large number of LUT resources. LOMS 2-way devices use fewer resources than comparable S2MS devices, enabling some large LOMS devices to be implemented in a given FPGA when comparable S2MS devices cannot fit in that FPGA. A List Offset 2-way sorter merges 2 lists, each with 32 values, into a sorted output list of those 64 values in 2.24 nS, a speedup of 2.63 versus a comparable Batcher device. A LOMS 3-way merge sorter, merging 3 sorted input lists with 7 values, fully merges the 21 values in 3.4 nS, a speedup of 1.36 versus the comparable state-of-the-art 3-way merge device.