并行语句

• par do:算法的若干布要并行执行
• for all:几个处理器同时执行相同的操作

并行算法的指标

• 运行时间t=计算时间+通信时间
• 处理器个数p
• 成本c=t*p

如果求解一个问题的并行算法之成本，在数量级上等于最坏情况下串行求解此问题所需的执行步数，则称此并行算法是成本最优（ＣｏｓｔＯｐｔｉｍａｌ）的。

• 总运算量w：总的操作数量
• Brent定理：令 Ｗ（ｎ）是某并行算法Ａ在运行时间 Ｔ（ｎ）内所执行的运算量，则 Ａ使用ｐ台处理器可在$t(n)=O(\frac{W(n)}{p}+T(n))$时间 内执行完毕。$c(n)=t(n)p=O(W(n)+pT(n))$，当$p=O(\frac{W(n)}{T(n)})$时，w和c是渐进一致的