PSRS算法

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

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

并行计算并行排序

相关

语态语态（genus verbi，英语：voice）是在语法学中描述句子中动词和参与此动作之主语之间关系的一个术语。当主语是动作的发起者（或之一）时，称为主动语态；如果主语为动作之承受者，称为被动语
尼亚加拉尼亚加拉瀑布城（英语、法语：Niagara Falls），当地华人旧译尼加伙，是一座位于加拿大安大略省南部金马蹄地区尼亚加拉区的城市，坐落尼亚加拉河西岸的尼亚加拉半岛，与美国尼亚加拉瀑布
神奈川县知事神奈川县知事列表包括神奈川县的历代知事。
酒精去氢酶醇脱氢酶（英语：Alcohol dehydrogenase，缩写ADH， EC 1.1.1.1），是一种以NAD+或NADP+为受体、作用于供体CH-OH基团上的氧化还原酶。这种酶能催化以下两种酶促反应：醇脱氢酶是一种锌蛋
新型冠状病毒感染应变协调中心新型冠状病毒感染应变协调中心是澳门特别行政区政府为了因应新型冠状病毒感染疫情的进一步发展，于2020年1月21日举行新闻会宣布成立的机构。协调中心直接隶属行政长官运作，由
两双两双是篮球的术语，指一场比赛中球员的个人表现在以下任何两项中达到两位数：得分、篮板、助攻、抢断和盖帽。大多数的两双表现都是得分和篮板达到两位数，其次是得分和助攻。两双
墨西哥总统墨西哥总统（西班牙语：Presidente de los Estados Unidos Mexicanos）墨西哥实行总统制，总统是国家元首、政府首脑和墨西哥军队总司令。办公地点位于国家宫。现任总统是洛佩斯·奥
炸大虾炸大虾（海老フライ、エビフライ），将虾去壳、去泥肠、留下虾尾，包裹上厚厚一层调味用的油炸粉后，下油锅油炸至呈现金黄色酥脆外皮。常搭配高丽菜丝。常见的调味用沾酱是辣酱油，或柠
浊齿龈后无咝塞擦音浊齿龈后无咝塞擦音是一个辅音，被用于一些口语中。国际音标写作或。此音通常作为同位异音使用。浊齿龈后无咝塞擦音的特征包括：当符号成对出现时，左边的是清音，右边的是浊音。阴
LocusLocus可以指：