并行排序
并行排序算法是计算机并行计算能力大大发展之后，为了提高排序效率而提出的算法。 划分的设计方法 PSRS算法 Viliant归并算法 对数划分 串行算法直接并行化 模拟快速排序 *二叉树上模拟快速排序 串行算法简介：快速排序是一种较为高效的排序算法，它通过不断的划分待排序列为两段，使得前一段总小于或等于某个数，而后一段总大于某个数，这样每次划分就能确定一个数的最终位置。一般情况下，如果每次划分的两个子列大致等长，那么它的时间复杂度是O \…
标签：#并发计算
共 84 篇文章
超立方体连接
超立方体连接可以作为格雷码的一个几何解释。一个4维的超立方体在三维空间中的投影是由两个立方体连接而成的，编号平面的方向和连接方向是一样的。对于一个N=2^n节点的n维超立方连接，显然它的网络直径是n，对剖宽度为N/2， 参阅 并行计算
并行快速傅里叶变换
串行算法回顾 在快速傅里叶变换（FFT）的并行算法中使用了蝶形连接网络。 并行算法 二维网孔连接网络上的FFT： 将n个处理器排成\sqrt {n}\times\sqrt {n}的二维网孔连接网络，假设输入序列\{a_0,a_1,......,a_{n-1}\}已经存放在了各个处理器中。 下面以16点变换来解释这个问题，连成的网络及编号如下图所示： 根据快速傅里叶变换的算法，我们来研究这16个点计算时四次循环的具体执行情况。 #同一列间…
执行时间
基本定义 并行执行时间是由三部分组成的：计算时间，通信时间和并行开销时间，在并行计算中，他们分别记作：T_{comp},T_{comm},T_{paro}。 并行开销时间主要包括操作系统进行进程管理的时间等；通信时间则主要是处理器间进行消息，数据传递等所要的延迟。 参阅 并行计算