PSRS算法

✍ dations ◷ 2025-12-03 09:10:23 #并发计算,算法

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

并行计算并行排序

相关

膳食补充剂营养补充品，又称营养补充剂、膳食补充剂、营养剂、饮食补充剂、保健食品、健康食品等，是一种成分是从食物中萃取对人体有益的营养素（如氨基酸、微量元素、维生素、矿物质等）的补
果糖不耐症遗传性果糖不耐症是一种遗传病，其会导致患者缺乏醛缩酵素，由此无法将果糖-1-磷酸转变成为甘油醛，无法行成果糖1-6二磷酸、葡萄糖和乳酸，并造成果糖-1-磷酸堆积。此遗传病的发生
强力集团强力集团（俄语：Могучая кучка），又称五人乐派、俄国五人组，是一个在1856年到1870年之间俄国圣彼得堡建立的音乐创作小圈子，成员有巴拉基列夫、穆索尔斯基、李姆斯基—
均田制均田制是中国古代一项重要的土地制度，产生于北魏，北魏分裂出来的东魏西魏及继之后的北齐、北周以及隋唐都承袭了这一制度。随着地主经济的发展壮大，土地兼并也随之日益严重。武
素万那普泰国中部：泰国北部：泰国南部：素攀地（梵语：सुवर्णभूमि，转写：Suvarṇabhūmi；巴利语：Suvaṇṇabhūmi；缅甸语：သုဝဏ္ဏဘူမိ，转写：suwannabhuumi；泰语：สุวรรณภูมิ
幻龙目幻龙目（Nothosauroidea）又名孽子龙目，是群三叠纪的海生爬行动物，属于鳍龙超目，可能类似现代的海豹，在水中捕抓食物而回到岸边的岩石与海滩。它们的身长平均约3米，有长的身体与尾巴
沉管式隧道沉管式隧道一种建造隧道的方法。这种方法只适用于建造海底隧道或水底隧道。注：建造水底隧道无需修复海床
令伍特 (维多利亚州)令伍特（英语：Ringwood）位于澳大利亚维多利亚州墨尔本的东郊。邮政编码为3134，人口约为一万四千人。离墨尔本市区约22公里。
塔罗萨王国塔罗萨王国（塔罗萨语：Regipäts Talossan）是一个私人国家。塔罗萨王国于1979年12月26日由一名14岁的美国密尔沃基少年罗伯特·本·麦迪逊（英语：Robert Ben Madison）在其母死后不
蔡祯蔡祯，明初进士，四川嘉定州（今属乐山市）人。蔡祯为国子监生，洪武二十四年（1391年）中式辛未科许观榜二甲进士。官至广东左参政。