4.1并行算法的基础知识 4.1.1并行算法的定义和分类 4.1.2并行算法的表达 4.1.3并行算法的复杂性度量 4.1.4并行算法中的同步和通讯
4.1 并行算法的基础知识 4.1.1 并行算法的定义和分类 4.1.2 并行算法的表达 4.1.3 并行算法的复杂性度量 4.1.4 并行算法中的同步和通讯
并行算法的复杂性度量 *串行算法的复杂性度量 *最坏情况下的复杂度(Norst-CASE Complexity) *期望复杂度(Expected Complexity) *并行算法的几个复杂性度量指标 *运行时间t():包含计算时间和通讯时间，分别用计算时 间步和选路时间步作单位。为问题实例的输入规模。 米 处理器数p(n) *并行算法成本c(n):c(n)=t(n)p(n) *如果一个求解问题的并行算法之成本，在数量级上等于最坏情况 下串行求解此问题所需的执行步数，则称此并行算法是成本最优 (Cost Optimal)的。 *总运算量W():并行算法求解问题时所完成的总的操作步 数。 14 2011/9/27
串行算法的复杂性度量 最坏情况下的复杂度(Worst‐CASE Complexity) 期望复杂度(Expected Complexity) 并行算法的几个复杂性度量指标 运行时间t(n):包含计算时间和通讯时间，分别用计算时 间步和选路时间步作单位。n为问题实例的输入规模。 处理器数p(n) 并行算法成本c(n): c(n)=t(n)p(n) 如果一个求解问题的并行算法之成本，在数量级上等于最坏情况 下串行求解此问题所需的执行步数，则称此并行算法是成本最优 （Cost Optimal）的。 总运算量W(n): 并行算法求解问题时所完成的总的操作步 数。 14 2011/9/27 并行算法的复杂性度量
并行算法的复杂性度量 *Brent定理 令W(n)是某并行算法A在运行时间T(n)内所执行的运算 量，则A使用p台处理器可在t(n)=O(W(n)/p+T(n)时间 内执行完毕。 *W(n)和c(n)密切相关，c(n)=t(n)*p=O(W(n)+p*T(n) * p=O(W(n)T(n)时，W(n)和c(n)两者是渐进一致的 *对于任意的p,c(n)W(n)。这说明一个算法在运行过程中， 不一定都能充分的利用有效的处理器去工作。 15 2011/9/27
Brent定理 令W(n)是某并行算法A在运行时间T(n)内所执行的运算 量，则A使用p台处理器可在t(n)=O(W(n)/p+T(n))时间 内执行完毕。 W(n)和c(n)密切相关，c(n)=t(n)*p=O(W(n)+p*T(n)) p=O(W(n)/T(n))时，W(n)和c(n)两者是渐进一致的 对于任意的p，c(n)›W(n)。这说明一个算法在运行过程中， 不一定都能充分的利用有效的处理器去工作。 15 2011/9/27 并行算法的复杂性度量