功能划分技术 *问题背景 米 假定欲从长为n的序列中选取前m个最小者，此即所谓 的(m,n)选择问题，那么应如何对原序列施行划分以 便并行处理呢？ *此时可以使用所谓功能划分法，即将长为的序列划 分成等长的一些组，每组中的元素应大于或等于m (最后一组除外)。然后各组可并行处理。 2011/10/25 18
功能划分技术 问题背景 假定欲从长为 n的序列中选取前 m个最小者，此即所谓 的(m,n) ‐选择问题，那么应如何对原序列施行划分以 便并行处理呢？ 此时可以使用所谓功能划分法，即将长为 n的序列划 分成等长的一些组，每组中的元素应大于或等于 m （最后一组除外）。然后各组可并行处理。 18 2011/10/25
功能划分技术 划分方法 n个元素A[1n分成等长的p组，每组满足某种特性。 * 示例：m,n)选择问题（求出n个元素中前m个最小者） *功能划分：要求每组元素个数必须大于m; *算法： 输入：A=(a1,…,an;输出：前m个最小者； Begin (I)功能划分：将A划分成g=n/m组，每组含m个元素； (2)局部排序：使用Batcher.排序网络将各组并行进行排序； (③)两两比较：将所排序的各组两两进行比较，从而形成MN序 列； (4)排序-比较：对各个MN序列，重复执行第（②）和第(3)步，直至 选出m个最小者。 End 2011/10/25 19
功能划分技术 划分方法 n个元素A[1..n]分成等长的p组，每组满足某种特性。 示例：(m, n)选择问题(求出n个元素中前m个最小者) 功能划分：要求每组元素个数必须大于m； 算法： 输入：A=(a1,…,an); 输出：前m个最小者； Begin (1) 功能划分：将A划分成g=n/m组，每组含m个元素； (2) 局部排序：使用Batcher排序网络将各组并行进行排序； (3) 两两比较：将所排序的各组两两进行比较，从而形成MIN序 列； (4) 排序-比较：对各个MIN序列，重复执行第(2)和第(3)步，直至 选出m个最小者。 End 19 2011/10/25