精选优质文档-倾情为你奉上93 SIMD互连网络模型的并行算法（一） 网孔上的随机序列搜索算法给定一整数序列S=(s1,sn)和一整数x，S不一定有序且各元素不一定相异，确定S中是否有数等于x。在网孔连接的SIMD机器上，令si,j表示P(i,j)中保存的记录的s域，指定P(1,1)为输入和输出端口。算法思想： 展开：P(1,1)读取x (如x=s1,1则产生输出b1,1=1，否则为0)，(b1,1,x)与P(1,2)通信 (如x=s1,2或b1,1=1则b1,2=1，否则为0)，两个相邻行之间，P(1,1)和P(1,2)分别同时发送(b1,1,x)和(b1,2,x)给P(2,1)和P(2,2)，一旦计算出b2,1和b2,2则两个相邻列之间P(1,2)和P(2,2)分别同时发送(b1,2,x)和(b2,2,x)给P(1,3)和P(2,3)，这种行列交替的展开过程一直继续到x到达P(,)为止； 折叠：展开结束后，每个处理器都有机会看到x，并将其与自己保存的s相比较，折叠式展开的逆过程，即输出响应位经逐行、逐列，以
