合并网络是可以将两个排序的输入序列合并为一个排序的输出序列的网络。我们使用BITONIC-SORTER [n]创建合并网络MERGER [n]。
合并网络基于以下假设：
给定两个排序的序列, 如果我们颠倒第二个序列的顺序, 然后连接两个序列, 则得到的序列是双音调的。
例如：给定两个已排序的零一序列X = 00000111和Y = 00001111, 我们将Y反转以获得YR =11110000。将X和YR串联可得到0000011111110000, 这是双音调的。
分类网络SORTER [n]需要合并网络来实现并行版本的合并排序。 SORTER [n]的第一阶段由MERGER [2]的n / 2个副本组成, 它们并行工作以合并一个1元素序列的对以产生长度为2的排序序列。第二阶段存在n / 4个副本。 MERGER [4]的描述, 它们合并这两个2元素排序的序列对以生成长度为4的排序序列。通常, 对于k = 1, 2 …
.. log n, 阶段k由MERGER的n / 2k个副本组成[2k]合并2k-1个元素排序序列对以产生length2k排序序列。在最后阶段, 将生成一个由所有输入值组成的排序序列。该归类网络可以通过归纳来表示, 以对零一序列进行排序, 因此, 根据零一原理, 它可以对任意值进行归类。
给定SORTER的深度[n]
文章图片
【图论（合并网络）】谁的解是D（n）=θ（log2n）。因此, 我们可以在?（log2n）时间内并行排序n个数字。
推荐阅读
- 图论（比较网络）
- 图论（最大二分匹配）
- Ford-folkerson算法
- 图论（网络流量问题）
- 图论之流网络和流
- PyTorch与TensorFlow差异比较（有什么区别（哪个更好？））
- Helm与Terraform差异比较（有什么区别（哪个更好？））
- Ansible vs Terraform vs Puppet差异比较（有什么区别（选择哪个？））
- 14种云成本管理和优化工具合集（如何选择（））