PSRS算法

✍ dations ◷ 2025-07-02 09:06:14 #并发计算,算法

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

并行计算并行排序

相关

大大部，为汉字索引里为部首之一，康熙字典214个部首中的第三十七个（三划的则为第八个）。就繁体和简体中文中，大部归于三划部首。大部通常是从上、中、下方为部字，且无其他部首可用者
陈华顺陈华顺（1849年－1913年），中国武术家，广东顺德人，花名找钱华、爪钱华，是清朝末年咏春宗师梁赞（“赞先生”）之入室弟子，在佛山公开教授咏春拳术。他生于顺德，据说少年时在米店打工，一开始是
武陵源区武陵源区是中国湖南省张家界市所辖的一个市辖区。总面积398平方公里，总人口5万。张家界(金鞭溪、黄狮寨、砂刀沟、金鞭岩、黄龙洞)、袁家界、杨家界、溪布街等风景名胜皆在本
定陶区定陶区，为中国山东省菏泽市的一个市辖区，位于万福河上游。定陶区原为定陶县，2016年2月，撤县设区。早在原始社会末期，定陶区境内生活着一支古老的部落鬷夷氏，是东夷人中擅长制陶的
不净动物本条目是在伊斯兰教、犹太教和基督教里被定义为不净动物的清单。其他东方的宗教，如佛教、道教、儒教等，则没有不净动物的概念。这些动物包括以下种类：以下列出的动物没有在圣经
穆罕默德·巴拉迪穆罕默德·巴拉迪（阿拉伯语：محمد البرادعي‎，1942年6月17日－），埃及人，曾为国际原子能机构总干事，于2005年获诺贝尔和平奖。他通晓阿拉伯语、英语和法语，育有一子一女。穆
齐格蒙特·克拉辛斯基齐格蒙特·克拉辛斯基（Zygmunt Krasiński）（1812年2月- 1859年2月23日），波兰贵族，伟大的浪漫主义诗人。齐格蒙特·克拉辛斯基与亚当·密茨凯维奇和尤利乌什·斯沃瓦茨基并列为波兰
AbiWordAbiWord是一个以GNU通用公共许可证许可的免费文字处理软件，名称"AbiWord"是派生自意谓开放的西班牙语单词"Abierto"；支持Linux、Mac OS X（PowerPC）、Microsoft Windows、ReactOS
赵璧烜赵璧烜，云南承宣布政使司大理府人。明朝解元、政治人物。明神宗万历四十三年（1615年），中式乙卯科云南乡试第一名举人（解元）。
林格尔巴赫河 (费尔希巴赫河支流)坐标：49°5′6.26″N 11°3′46.36″E / 49.0850722°N 11.0628778°E / 49.0850722; 11.0628778林格尔巴赫河（德语：Ringelbach），是德国的河流，位于该国东南部，由巴伐利亚负责管辖，