使用给定的线程数进行并行基数排序
使用给定的线程数进行并行基数排序
提问于 2016-10-29 01:03:52
我很难理解使用线程进行并行基数排序的概念。
如果我们使用最重要的数字方法，我们可以从创建桶1到9开始，并使用它们的MSD将数字划分为桶。
您可以通过每个桶拥有一个线程来并行地对其进行排序。
但是，如果我们必须使用给定数量的处理器(例如4个处理器)，那么如何将这9个桶分成4个处理器呢？
我在网上看到的一个图表似乎表明，首先要将数字划分为x个分区的数目(不进行任何排序)，然后每个处理器对给定分区的所有数字进行排序。但是，这样就会留下x个数字桶，每个桶按自身排序，而不是整个向量/数字数组排序，我不知道接下来要做什么。
回答 1
Stack Overflow用户
回答已采纳
发布于 2016-10-29 01:30:24
在对x分区进行排序之后，您将合并x分区。这可以通过log2(x)传递进行2路合并，或通过一次执行x方式合并来完成。X方式合并通常使用堆来加速确定x元素中的哪一个(以及该元素属于哪个分区)最小。除了初始化之外，元素一次从堆中移除并添加到堆中。最终达到一个x分区的结束，合并成为一个x-1合并。最后，只剩下一个分区，并将其复制到输出数组中。
如果数组太大，以至于它的分区比特定于核心的L1和L2缓存大得多，那么由于冲突，并行基排序不会有多大帮助，因为所有核心共享公共L3 (如果存在的话还有L4 )缓存和主内存。例如，每个核心的L1缓存可能是32 L2，每个核心的L2缓存可能是256 L2。
另一种方法是将数组拆分为z 256 up分区，然后对z分区一次进行x基排序。最后一步是z排序256 be分区的z方式合并。
至于基排序，您可能想要将基256用于8位字段，而不是使用基数10 (您可以将元素分割成字段)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/40315036
复制相关文章
相似问题
腾讯云开发者
