PSRS算法

✍ dations ◷ 2025-11-23 06:35:27 #并发计算,算法

PSRS算法（Parallel Sorting by Regular Sampling）：首先设待处理里序列长n，并行机上有p个处理器。为了使问题简单，我们假设n是p的整倍数。于是将这n个元素划分为p段，每段中有n/p个元素，将这p段分给p个处理器。注意，执行PSRS算法的并行机必须是多指令流多数据流（MIMD）的。

如果注意到一个好的串行排序算法的时间复杂度为 $O(nlogn)$ $O(nlogn)$ 那么，容易证得上述PSRS算法的时间复杂度在 $n>p^{3}$ $n>p^{3}$ 时为 $O({\frac {n}{p}}log{n})$ $O({\frac {n}{p}}log{n})$ 。

缺点：我们注意到，在第五步进行主元划分时时可能会引起不均匀性，即位于某两个主元之间的元素可能要多一些（多于 ${\frac {n}{p}}$ ${\frac {n}{p}}$ 个）。我们可以证明，在算法中进行到第六步全局交换时，可能会有某一个处理器中数据达到 ${\frac {2n}{p}}-{\frac {n}{p^{2}}}-(p-1)$ ${\frac {2n}{p}}-{\frac {n}{p^{2}}}-(p-1)$ 个；这样引起的直接后果是处理器负载不均匀，那么在归并排序中可能会引起排序时间的不均匀。

并行计算并行排序

相关

东洋文库坐标：35°43′52.61″N 139°44′54.82″E / 35.7312806°N 139.7485611°E / 35.7312806; 139.7485611财团法人东洋文库是日本最大、也是全球第五大的亚洲研究图书馆，位于东
玉米赤霉醇玉米赤霉醇（英文名Zeranol），又称右环十四酮酚，折仑诺，α-玉米赤霉醇，是一种在镰刀菌属（Fusarium genus）中发现的属于二羟基苯甲酸内脂的合成非甾体雌激素，主要用作兽药中的合成代谢剂
涅涅茨自治区涅涅茨自治区（俄语：Нене́цкий автоно́мный о́круг，罗马化：Nenetsky avtonomny okrug，涅涅茨语：Ненёцие автономной ӈокрук），是俄
中国老龄化人口老龄化又称人口老化或人口高龄化、老龄化社会，是指因出生率降低和/或预期寿命延长导致年龄中位数增加的现象。大多数发达国家人口长寿，老龄人群变多；但发展中国家目前也出
白鹿潭白鹿潭是位于韩国济州岛汉拏山山顶火山口的湖泊，海拔1850米，湖面直径约30米，周长1公里，深约6米，是韩国最大的天然湖泊。传说在很久以前，神仙们曾骑着白鹿来到汉拏山游玩。“白鹿潭
收听时段时段（Dayparts）指的是在电台或电视台节目安排中，将一天划分成不同的部分，在不同的时段里播送不同类型的电视节目或电台节目。在电视时段安排中，某个时段的电视节目往往是针对该时
唐纳德·艾文森任期 January 8, 1973－January 8, 1991(1944-09-16)1944年9月16日 Minneapolis, Minnesota, U.S.2017年5月19日(2017-05-19)（72岁） North Platte, Nebraska, U.S.Democratictoo
尼特拉尼特拉（斯洛伐克语：Nitra、德语：Neutra、匈牙利语：Nyitra）是位于斯洛伐克西部的一个城市，于公元9世纪时曾为大摩拉维亚公国的首都。尼特拉有人口约8.5万，是斯洛伐克第四大城市。尼
三河地区三河，中国古地名。三河指河东、河内、河南。河东大约相当于现在山西的临汾、运城；河内郡大约相当于现在河南的焦作、济源、新乡、安阳、鹤壁；河南不是现在的河南省，而是河南洛阳
连续X射线谱连续X射线谱是指某些带电粒子(例如电子、质子等等)因为与物质相互作用而让他的速度骤减，而带电粒子的能量就以辐射的方式放出。当粒子的速度从V1降到V2时释放出的辐射波长为: