PSRS算法

✍ dations ◷ 2025-04-30 03:32:22 #并发计算,算法

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

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

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

并行计算并行排序

相关

  • 真核延伸因子真核延伸因子有两种:真核延伸因子1(eEF-1)和真核延伸因子2(eEF-2)。氨酰-tRNA合成酶 · 阅读框架 · 起始密码子 · 终止密码子 · 核糖体结合位点:夏因-达尔加诺序列(+/-) · 科扎
  • 法兰克福大学歌德 - 美茵河畔法兰克福大学(德语:Goethe-Universität Frankfurt am Main),德文简称为“法兰克福大学”(Uni Frankfurt)或“歌德大学”(Goethe Uni)﹔据此,中文亦有称作“歌大”或“
  • 酸碱理论酸碱理论指阐述酸、碱及酸碱反应本质的各种理论。在历史上曾有多种酸碱理论,其中重要的包括:拉瓦锡是最早提出酸碱概念的人。他在1776年左右提出一套酸碱理论。在那时,强酸主要
  • 黑钙土黑钙土(英语:Chernozem),名字源于俄罗斯语,意指“黑色的土”,又称“黑土”。由于含有大量的磷酸、腐植质、磷、氨、镁、还有钙等矿物质,黑钙土在农业上是属于一种上好的土质,农产量
  • 寄生植物寄生植物指的是其营养乃全部或部分于来自其他生物(其他植物)者。目前已发现营寄生的开花植物大约有19科,4,100种。寄生植物具特化的根,吸器(haustorium),会穿过宿主的组织达到木质
  • 生物滤化生物滤化(英语:Bioleaching)是指利用微生物将金属元素从矿物中提取出来的过程。这比传统的氰化物堆浸法要更为清洁。生物滤化是生物湿法冶金(英语:Biohydrometallurgy)的几种应用
  • 伊瓦尔·雅各布森伊瓦尔·亚尔玛·雅各布森(瑞典语:Ivar Hjalmar Jacobson,1939年9月2日-),又译伊万·雅各布森,是一位计算机科学家与软件工程师,在软件工程领域有很大贡献。曾参与设计统一建模语言(U
  • 秋田县坐标:39°43′7″N 140°6′9″E / 39.71861°N 140.10250°E / 39.71861; 140.10250秋田县(日语:秋田県/あきたけん Akita ken */?)位处日本东北地方。首府为秋田市。农业生产
  • 埃迪·康托尔埃迪·康托尔(英语:Eddie Cantor,1892年1月31日-1964年10月10日),本名伊拉尔·伊茨科维茨(Israel Itzkowitz),是一名美国“插图歌曲(英语:Illustrated song)”表演者、喜剧演员、舞蹈演
  • 汤米·马基宁汤米·马基宁(芬兰语:Tommi Antero Mäkinen,或译为麦基宁;1964年6月26日-),外号涡轮,芬兰拉力赛车车手,出生于芬兰小镇普波拉(Puuppola,现为于韦斯屈莱的一部分)。马基宁算是世界拉力锦