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