背包问题的最优并行算法

利用分治策略,提出一种基于SIMD共享存储计算机模型的并行背包问题求解算法.算法允许使用O(2n/4)1-e个并行处理机单元,0e1,O(2n/2)个存储单元,在O(2n/4(2n/4)e)时间内求解n维背包问题,算法的成本为O(2n/2).将提出的算法与已有文献结论进行对比表明,该算法改进了已有文献的相应结果,是求解背包问题的成本最优并行算法.同时还指出了相关文献主要结论的错误.

Multisets排序的最优并行算法

排序是一个既有十分重要的理论意义又有广泛的实际应用价值的问题 ,其中 ,Multisets排序问题是指对只有k个不同关键字值的n个数据 (记录 )进行排序 ,0 <k <n 基于“中值的中值”思想和“筛选”原理 ,通过在递归过程中不断地“筛选”掉某些具有相同关键字值的数据 ,以及自适应地动态分配处理器以平衡计算负载的方法 ,设计一种确定的稳定的Multisets排序并行算法 在具有 p =n1-ε(0 <ε<1)个处理器的共享存储并行机器上 ,对于CREWPRAM模型 ,算法的时间复杂度为O((n/ p +pε)logk) ,获得最优执行代价O(nlogk) ;对于EREWPRAM模型 ,算法所需时间为O((n/ p+pε+logp)logk) ,当 plogp≤n时 ,其执行代价也是最优的

矩阵乘法的一个最优并行算法

本文给出了向量机上计算两个n阶矩阵乘法的并行算法. 处理机台数P=n; 并行步数T=0(n); 效率=0(1). 此算法从阶上已达到并行矩阵乘法的复杂性下界,同时在保证效率为0(1)的前提下,使处理机台数的上界达到最优.

N-体仿真中的分层树形算法

考虑两种情况 :在 3维空间中给出n个质点 ,计算每一粒子施加在其它粒子上的力 ,成对的相互作用可能有万有引力或者Lennard_Jones.上述两种情况的力 ,当两粒子间的距离达到无限大时消失 .既然n个质点 ,两两相互作用共有 [n(n - 1) ]/ 2对 ,直接算法对力的估算所需时间为O(n2 ) .这对天文中的仿真所用时间是非常大的 .该文提出了一种O(logn)算法 ,使用n/logn处理器CREWPRAM来计算n体仿真中的场 .这种最优并行算法的关键是利用一个相同的非递归自上而下的过程来代替一个递归的自上而下的计算过程 .这种相似的算法对力场计算也产生了一个新的O(n)时间序列算法 .