PSRS算法

✍ dations ◷ 2025-11-25 11:54:44 #并发计算,算法

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

并行计算并行排序

相关

运动创伤运动损伤又称运动创伤或运动伤害（英语：Sports injuries），指在体育运动或体能锻炼过程中发生的创伤。例如在美国，据估计有三千万青少年参与过某种形式的有组织运动，其中每年又有三
德斯蒙德·莫利斯德斯蒙德·莫利斯（Desmond Morris，全名Desmond John Morris，1928年1月24日－）英国著名动物学家。出生于英国威尔特郡，中学毕业后，就读英国伯明翰大学，得学士学位。后又入牛津大学继续
酒精发酵酒精发酵是指微生物通过发酵过程产出酒精的化学过程。酵母以及其它微生物经过发酵作用，反应物中的糖，如葡萄糖、果糖和蔗糖转化成能量、乙醇和二氧化碳，但根据反应物的不同，微生
罗姆语罗姆语（罗姆语：Romani，又称吉卜赛语或茨冈语）是罗姆人和信德（Sinti）社群的语言。罗姆语属于印度-雅利安语支语言。分析罗姆语得知，它与印度北部的语言相近，尤其是旁遮普语。在语言学
1893年
叶公杼叶公杼（英语：Lily Yeh Jan，1947年1月20日－），原籍台湾的美国华裔生物物理学家，美国国家科学院院士，台湾中央研究院院士，旧金山加州大学教授，以完成钾离子通道的分子选殖的工作而最为知
巴西合众国巴西第一共和国，又称旧共和国（葡萄牙语：República Velha），是巴西在1889年至1930年间的历史时期。随着1930年巴西革命爆发而结束。1889年，佩德罗二世被废黜，由德奥多罗·达·丰塞卡
莱特纳系统莱特纳系统是1970年代由德国评论家瑟巴斯坦·莱特纳提出，是一种广泛有效使用抽认卡的学习方法。它是以简单间隔复习的原理来实现，其中抽认卡以增加的时间间隔进行复习，以达到
乔治·帕潘德里欧乔治·帕潘德里欧（希腊语：Γιώργος Παπανδρέου；1952年6月16日－），希腊政治家，前任希腊总理及现任民主社会主义者运动领导人。他的祖父乔治奥斯·帕潘德里欧和父亲安
知识贬值知识贬值是指知识所带来的经济价值随时间而不断减低的现象。虽然这种现象早在20世纪初就已出现，但最先把这种现象作具体描述的，应该是日本前经济企划厅厅长堺屋太一。根据堺屋