PSRS算法

✍ dations ◷ 2024-12-22 13:21:53 #并发计算,算法

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)$ 个；这样引起的直接后果是处理器负载不均匀，那么在归并排序中可能会引起排序时间的不均匀。

并行计算并行排序

相关

无限大N ⊆ Z ⊆ Q ⊆ R ⊆
迦太基迦太基（腓尼基语：
狼母狼母乐队（Wolfmother）是一队澳大利亚有名的3人音乐组合。狼母乐队（Wolfmother）是一队来自澳洲悉尼的乐队，成立于2003年，风格为迷幻摇滚，而且经常被人们拿齐柏林飞船（Led Zeppelin）和
法兰绒法兰绒（英语：Flannel）是一种用粗梳毛纱织成的柔软且有绒面的毛织品。起源尚有争议，可能源于16世纪的威尔士。早期一般使用羊毛制作，现在也使用绵及化纤制作。此布料多数用来制做
罗萨里奥罗萨里奥（西班牙语：Rosario，西班牙语发音：.mw-parser-output .IPA{font-family:"Charis SIL","Doulos SIL","Linux Libertine","Segoe UI","Lucida Sans Unicode","Code2000","G
新闻晨报《新闻晨报》，是中华人民共和国上海市出版的综合性都市报，由新闻报社编辑出版（初由解放日报报业集团主管主办，现由上海报业集团主管主办）。该报于1998年11月试刊，1999年1月1日正式
英国恐怖故事《英国恐怖故事》（英语：）是由约翰·洛根（英语：John Logan (writer)）替Showtime电视网和Sky（英语：Sky UK）创作的英美恐怖电视连续剧。同时，约翰·洛根跟萨姆·门德斯一起担任此剧的执行
科学怪人之子《科学怪人之子》（Son of Frankenstein），又称《弗兰肯斯坦之子》，是环球影业制作的科学怪人系列第三部，鲍里斯·卡洛夫饰演怪物，《科学怪人的新娘》的续集。《科学怪人之子》在193
斯科特·威廉·卡特斯科特·威廉·卡特（英语：Scott William Carter）是一位美国科幻文学、奇幻文学、青少年与儿童文学作家。卡特出生在明尼苏达州与在俄勒冈州的威拉米特谷成长。在他成为一位职业
沈孟化沈孟化，字观瀛，福建永定县人，明朝政治人物。隆庆五年（1571年）辛未科贡士，因丁外艰回籍。万历二年（1574年）甲戌科补应殿试，成进士，授江浦县知县，县丞原无城郭，沈孟化节缩千余金，留治筑城。