PSRS算法

✍ dations ◷ 2025-12-11 06:11:02 #并发计算,算法

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

并行计算并行排序

相关

波士顿儿童医院波士顿儿童医院（Boston Children's Hospital）是美国麻塞诸塞州波士顿一所拥有395张立案病床的儿童医院，位于波士顿市内医疗院所林立的长木医学区。它是哈佛医学院与丹那-法博癌
L型钙通道L-型钙通道（英文：L-type calcium channel）是一种电压依赖性钙通道的类型钙通道。“L”为“long-lasting”的首字母，表示激活状态的时间持久。和其他同类钙通道一样，α1亚基是决定
奇异原子奇异原子通常是指与一般原子构成不同的原子，普通的原子是由电子e、质子p和中子n这三种长寿的粒子构成，但奇异原子却是以其他的粒子代替这三种稳定粒子中的一个或多个，通过电磁
国家科学院学报《美国国家科学院院刊》（英语：Proceedings of the National Academy of Sciences of the United States of America，通常简称为 PNAS；PNAS USA）是美国国家科学院的官方学术周刊。
景福宫景福宫（朝鲜语：경복궁／景福宮 Gyeongbokgung */?）建于1394年，是朝鲜王朝的正宫，也是朝鲜五大宫阙中规模最大的。位于今韩国首尔市。景福宫位于汉阳城（今首尔）北半部中心偏西的位置
重度抑郁症重性抑郁疾患（英语：Major depressive disorder，缩写MDD），也可简称为抑郁症，是一种精神疾患，特征为超过两周的大多数时间都抑郁不已。常常伴随着没有精神、对一般休闲活动没有兴趣、
维斯蒙特学院维斯蒙特学院（Westmont College）是位于美国加利福尼亚州圣塔芭芭拉的一所私立文理学院，成立于1937年。 2015年《美国新闻与世界报道》将其排在全文理学院中的第96位。
火花塞火花塞（英语：Spark Plug），又称为火星塞或火嘴，通常是指汽油引擎内一个用于点燃油气产生动力的零件。1858年，法国工程师洛纳因发明了世界上第一只用陶瓷绝缘制成的电点火火花塞。火
共动距离在宇宙学中，共动距离和普通距离是两种很相关的距离测量方式，用于定义两个天体之间的距离。普通距离就是我们平常所使用的距离衡量方式，在宇宙时的某个特定时间用一系列的测量手
五十岚喜芳五十岚喜芳（1928年9月8日－2011年9月23日）是出生于日本兵库县的歌唱家。