PSRS算法

✍ dations ◷ 2025-11-26 00:50:22 #并发计算,算法

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

并行计算并行排序

相关

CAS号CAS编号（CAS Registry Number，或称CAS Number，CAS Rn，CAS #），又称CAS登录号或CAS登记号码，是某种物质（化合物、高分子材料、生物序列（Biological sequences）、混合物或合金）的唯一的数
形式系统在逻辑与数学中，一个形式系统（英语：Formal system）是由两个部分组成的，一个形式语言加上一个推理规则或转换规则的集合。大卫·希尔伯特在1921年推动以形式系统来描述数学知识。
生物学的一切都没有道理，除非放在进化的光芒之下生物学的一切都没有道理，除非用演化的眼光来看。（英文：Nothing in Biology Makes Sense Except in the Light of Evolution）是演化生物学家和东正教教徒费奥多西·多布然斯基在1
人格异常人格障碍（英语：personality disorders），或人格（性格）疾患／异常／违常。是精神疾病中，对于一群特定拥有长期而僵化思想及行为病患的分类。这类疾患常可因其人格和行为的问题而导致社会
托马斯·曼保罗·托马斯·曼（Paul Thomas Mann，1875年6月6日－1955年8月12日），德国作家，1929年获得诺贝尔文学奖。保罗·托马斯·曼生于德国吕贝克，是商人托马斯·约翰·亨利希·曼的儿子，亨利
麦克·摩尔迈克尔·肯尼思·穆尔（英语：Michael Kenneth Moore，1949年1月28日－2020年2月2日），新西兰工党籍政治家，1972年当选为新西兰国会议员进入政界。曾担任新西兰外交部长、工党领袖并于19
鞑靼海峡鞑靼海峡（俄语：Татарский пролив），日本称为间宫海峡（日语：間宮海峡／まみやかいきょう Mamiya kaikyō），俄语亦名涅维尔斯科依海峡，中国古代文献则称之为赛哥小海、鲸
张令涛张令涛（1903年－1988年），宁波人，连环画大师，与胡若佛齐名。张令涛与胡若佛长期合作，人称“黄金搭档”，他们的作品在20世纪五、六十年代风靡一时。常常是张令涛打稿，胡若佛勾描。张令涛
徐士高徐士高（1908年5月16日－1990年12月31日），中国高电压技术专家。山东黄县人。1933年毕业于北平大学工学院。1943年获德国柏林工业大学博士学位。曾任电力工业部电力科学研究院总工
龟田鹏斋龟田鹏斋（日语：亀田鵬斎／かめだぼうさい ?，1752年10月21日－1826年4月15日）是江户时代中后期、化政文化时期的书法家、南画家（日语：南画）、儒学家。“鹏斋”是其号；本名“翼”，后改