设一个数列S[N], 其中S[0] = 0; S[k] = S[k - 1] + k ( 1 <= k < N).
对于这个问题的求解串行算法相当简单,O(N)时间复杂度,不再解释。
并行:
假设有 M 个线程, 其中 M << N;
S[K] = S[K - 1] + K
= S[K - 2] + K - 1 + K
= S[K - 3] + K - 2 + K - 1 + k
...
= S[K - M] + M * K - M * (M - 1)/ 2
假设 M = 2
则S[K] = S[K - 2] + 2 * K - 1, 所以
S[0] , S[2] , S[4] .... S[2 * T] 和 S[1] , S[3] , S[5] .... S[2 * T + 1]为两个独立的序列,因此可以使用两个线程进行并行计算。
同理,M 为其它值时也一样, 如此就实现的并行计算的算法。
分享到:
相关推荐
快速排序的并行实现,提高效率。快速排序算法并行化的一个简单思想是,对每次划分过后所得到的两个序列分别使用两个处理器完成递归排序。
随着并行处理硬件性能的迅速提高,人们对...对并行算法的研究现在已发展为一个独立的研究领域。很多用串行算法解决的问题也已经有了相应的并行算法。在本文中,我们将阐述一些简单的并行算法以说明一些基本概念和技术。
提出了一种基于着色算法的并行碰撞检测算法,利用AABB包围盒较好的紧密性和包围球计算简单的优点以及并行算法中的分治策略构建物体的混合包围体层次(S-AABB);然后采用破对称技术中的典型算法——着色算法,将每棵...
针对旅行商问题(Travelling Salesman Problem,TSP)的遗传算法的大规模操作,需要大量运算时间而且容易造成局部最优解,提出一种并行混合遗传算法。该方法基于MPI并行环境,利用种群中选择、交叉、变异操作的并行...
蒙特卡洛算法背景知识,算法描述,算法步骤,算法程序,简单明了。
枚举排序、快速排序、归并排序的串行算法及对应的简单并行算法,java实现,可自由选择线程数。代码仅供参考。
对该算法的并行化是很简单的,假设对一个长为n的输入序列使用n个处理器进行排序,只需使每个处理器负责完成对其中一个元素的定位,然后将所有的定位信息集中到主进程钟,由主进程负责完成所有元素的最终排位。
这是一个简单的并行遗传算法源代码,由Denis Cormier (North Carolina State University)的串行程序修改得到的
对于一个简单的图,可以使用CRCW PRAM上的O(m + n)个处理器在O(log n)时间内解决生成树问题。 通常,已知可以通过限制图的类别来开发更有效的并行算法。 在本文中,我们将提出一种并行算法,该算法在EREW PRAM...
里面有几个文档是介绍相关背景,threadpool.h和threadpool.c文件包含了简单线程池的库函数,ant_pthread.c是并行蚁群算法的源代码
做的毕业设计,是基于hadoop平台的,关于MapReduce云平台下贝叶斯算法的并行化设计,通过查资料设计出简单有效的算法,可以对数据进行分类,虽然简单但对初学者很有帮助,希望对大数据的学习有帮助。
简单并行遗传算法代码,由串行遗传算法改编而来。
简单遗传算法 纯 Haskell 中的简单并行遗传算法实现
论文研究-用并行遗传算法求复函数方程根的设计和实现.pdf, ...提出了一种基于并行遗传算法的复函数方程求根算法,并得到令人满意的结果算法简单实用.给出了该算法的设计和具体实现.
介绍工程实用简单图论问题的并行算法及其MPI编程实现
本次实验的目的是对一个程序进行并行化处理,并对并行化处理后的效果进行分析,与非并行化的时候进行比较。 二、 实验内容 选择枚举排序算法为此次实验需要并行化处理的算法,然后对其进行并行化处理,最后再分析...
简单的主从式并行遗传算法,使得实现速度更快
可以使用启发式搜索算法来解决该问题以找到最佳解决方案,但它仅适用于简单的情况。对于更复杂的输入和要求,找到一个相当好的解决方案可能需要一段时间,或者可能是不可能的。这就是遗传算法进入游戏的地方。 在...
给定具有n个顶点,m个边和k个连通分量的简单图G。 生成树问题是为G的每个连接的组件找到生成树。...在本文中,我们提出了一种带有处理器的时间并行算法,用于在EREW PRAM上的适当圆图G上构建跨越森林。
MapReduce是一种流行的分布式并行计算模型,因其使用简单、伸缩性好、自动负载均衡和自动容错等优点,得到了广泛的应用。对已有的基于MapReduce计算模型的并行关联规则挖掘算法进行了分类和综述,对其各自的优缺点和...