并行算法编辑本段回目录
正文编辑本段回目录
适用于并行计算机的数值算法。计算机传统结构的显著特征是单指令流单数据流，即每一时刻按一条指令处理一个数据。通常的数值算法适于此类计算机，可称串行算法。20世纪60年代开始发展含大量处理机的并行计算机，它分单指令流多数据流与多指令流多数据流两类，每一时刻分别按一条或多条指令处理多个数据。并行计算机的出现促使了适应其并行这个特点的并行算法的发展。
并行算法依赖一个简单事实：独立的计算可同时执行。所谓独立计算是指其每个结果元只出现一次的计算。例如A8=α1·α2……α8中7个乘法不能同时执行,但可分成三个独立计算组：
第一组
第二组
第三组
。如每组的运算并行执行，计算 A8，只须三步（乘法），其步骤可用图
中的双杈计算树来表示。推广此例，得到由满足结合律的任一运算“。” 形成的表达式
的最优并行算法，称为结合扇入算法。此算法提供了建立并行算法的一种普遍原则：反复将每一计算分裂成具有同等复杂性的两个独立部份，称为递推倍增法。
研究表明，大量数值问题可获得有效的并行算法。一个算法是否有效主要看加速
串行算法与并行算法存在固有差别。有效串行算法一般不能直接变换为并行算法，而且两者在数值性态方面（例如数值稳定性及迭代算法的收敛速度）可以彼此大不相同。
并行算法依赖一个简单事实：独立的计算可同时执行。所谓独立计算是指其每个结果元只出现一次的计算。例如A8=α1·α2……α8中7个乘法不能同时执行,但可分成三个独立计算组：
第一组
第二组
第三组
。如每组的运算并行执行，计算 A8，只须三步（乘法），其步骤可用图中的双杈计算树来表示。推广此例，得到由满足结合律的任一运算“。” 形成的表达式的最优并行算法，称为结合扇入算法。此算法提供了建立并行算法的一种普遍原则：反复将每一计算分裂成具有同等复杂性的两个独立部份，称为递推倍增法。 研究表明，大量数值问题可获得有效的并行算法。一个算法是否有效主要看加速
串行算法与并行算法存在固有差别。有效串行算法一般不能直接变换为并行算法，而且两者在数值性态方面（例如数值稳定性及迭代算法的收敛速度）可以彼此大不相同。
配图编辑本段回目录
