1673多处理机的并行和性能

1673多处理机的并行和性能内容摘要：

* 1 2 6 = 5 Z  分配给 2个处理机，需 3级运算 递归程序的并行性  是研究并行算法的重要课题  这里只讨论线性递归 线性递归的例子 1 2 1 21 1 2 201( , , .. ., ) , ( , , .. ., )* .. .0,1nnnni i i iA a a a B b b bA B a b a b a bxx x a b i n      给定向量求欧几里得内积这可归结为下列递归关系：线性递归的例子（续） 10 1 1001...,1nnn n ni i ip a x a x a x aH orn e rpap a x p i n       计算多项式写成 法则形式，归结为下列递归关系：线性递归的例子（续） 121211011,3... ...0( ) , 1i i inni i i i i iFi b o n a c c ifff f f i nn a a a b b bcc a b a b c i n         计算 数列，计算 位二进制数 和 相加时的进位线性递归的例子（续） 111 1 12 2 21 23 3 31 32 31 2 30 , 0,10 0 0 . 00 0 . 00 . 0. . . . . . . ..0iii i ij jj i nn n n n n nxix c a x i nx c xx c a xx c a a xx c a a a x                                                             用矩阵形式：列扫算法 112 1 1 3 1 1 1 12 2 2 1 1 3 3 1 1 1 123 2 2 4 2 2 2 23 3 3 1 1 3 2 2 1 1 2 21. , ( 1 ), , ...,。 2. ( 1 ), , ...3. ( 2), , ...,。 4. ( 2), ...。 .nnnnn n nx c x na x a x a xnx c a x c a x c a xxna x a x a xnx c a x a x c a x a x       1先算 并将 播送到其余各式，用 个处理机计算用 个处理机计算把 播送到其余各式，用 个处理机计算用 个处理机计算......知道计算全部结果。 需用（ n1）个处理机计算 2（ n1）步 例如：如 n=4，则需 3个处理机，用 6步 乘积形式递归算法  当 n=4时，右边只有 4种是不同，需用 4个处理机经 2步算出，再用 2个处理机经 3步算出  比上一算法，少用 1步，多用 1个处理机  N较大时，快速。 112 2 21 13 3 31 1 32 2 21 14 4 41 1 43 3 31 1 42 43 32 2 21 1( ) ( )( ) ( ) ( ) ( ). .. .. ..xcx c a cx c a c a c a cx c a c a c a c a a a c a c                                程序举例 DO 4 I=1,N 1 E(I)=3*F(I)+SIN(P(I)) 2 B(I)+D(I1)+Q(I) 3 D(I)=E(I)+B(I) 4 CONTINUE 语句 1提到循环前， 3构成循环 1 3 2 3 F P D Q B D E 数据相关图 程序的并行性分析  假定一个程序包含 P1,P2,… ,Pi,… Pj,… Pn等 n个程序段，设 Pi和 Pj程序段都是一条语句， Pi在 Pj之前执行。  数据相关  数据反相关  数据输出相关 数据相关  如果 Pi的左部变量在 Pj的右部变量集内，。