非常规计算智慧：并行计算的性能分析与通用计算机的探索

### 非常规计算智慧：并行计算的性能分析与通用计算机的探索 在计算领域，对并行随机访问机（PRAM）的性能研究，以及通用计算机存在性的探讨，一直是重要的研究方向。下面将深入分析不同处理器数量的PRAM在各种计算任务中的表现，并探讨通用计算机的可能性。 #### 不同处理器数量PRAM的性能对比 - **n个处理器的PRAM**：假设$k = n/2$，$D = n/4$，要求在时间单元1内报告当前内存中值的总和。若未准备好，则在时间$D$报告新值总和，以此类推。n个处理器的PRAM使用一条SUM CW指令在一个时间单元内完成求和，在第一个截止日期前交付结果并终止。而随机访问机（RAM）在时间$D$时仅添加了$n/4$个数，未准备好交付总和，即使到时间$2D$也未完成。当所有$n/2$个值发生变化时，需重新计算总和。经过$n$次变化，即时间$n^2/2$时，RAM最多再用$n$个时间单元，在时间$(2n + 4)D$交付总和。其加速比为$O(n^2)$，大于加速比民间定理预测的$O(n)$。 - **少于n个处理器（p < n）的PRAM**：n个处理器能在一个时间单元内完成求和并满足第一个截止日期。设$D = (n/2) + (1/n^2)$，$k > n/2 > p$，p个PRAM处理器计算总和需要$O(n/p)$时间。这意味着数据变化时，p个处理器无法在下一个截止日期前交付总和。在$n^2/2$个时间单元结束时，p个处理器还需$O(n/p)$时间计算最终总和，总时间为$O(n^2+(n/p))$，大于减速民间定理预测的$1 × (1 + (n/p))$时间单元。 #### 数组元素设置问题 给定大小为n的数组A，初始$A[i] = 0$（$1 ≤ i ≤ n$），要求将$A[i]$设置为$T = n^x$（$x > 1$为正整数常量），且更新过程中A的任意两个元素差值不超过常量$w$。 - **n个处理器的PRAM**：能在常量时间内解决问题，即$t_n = O(1)$。 - **RAM**：每次将A的每个元素更新$w$个单位，完成任务需要$t_n = O(n^x + 1)$时间。加速比$t_1/t_n$为$O(n^x + 1)$，而加速比民间定理预测为$n$。 - **少于n个处理器（p < n）的PRAM**：每次以p个元素为一组，将元素更新$w$个单位，总时间$t_n = O((n/p) × (n^x/p))$，$t_1/t_n = O((n/p) × (n^x/p) + 1)$，减速民间定理预测的比率为$1 + (n/p)$。 #### 多数据流问题 考虑n个独立数据流作为计算机输入，每个流包含序列$S = \{s_1, s_2, …, s_n\}$的不同循环排列。例如$n = 4$时，四个输入流可能为$<s_1, s_2, s_3, s_4>$，$<s_2, s_3, s_4, s_1>$，$<s_3, s_4, s_1, s_2>$和$<s_4, s_1, s_2, s_3>$。且流中第$i$个值与第$i + 1$个值间隔$2^i$时间单元，流只有在其第一个值被处理器读取并存储后才保持活跃。 - **单处理器**：只能监控一个流的值。当读取并存储所选流的第一个值时，已无法处理其他流同时到达的剩余$n - 1$个值。 - **RAM**：选择一个流，读取连续值并记录到目前为止遇到的最小值。处理$n$个输入需要$n$个时间单元，加上连续输入之间的等待时间$2^