一、简答题

1. 如果一台SIMD计算机和一台流水线处理机具有相同的计算性能，对构成它们的主要部件分别有什么要求？

2. 在有n*n*n个节点的三维网格中，求n*n*n个数据相加的和，假设所有的数据已经被平均分配到了各个节点中，加法运算时间忽略不计，数据传递操作一次需要单位时间，问最小时间开销是多少？

二、计算题

1. 今有K对向量，其中第i对由行向量Ri和列向量Ci组成，每个维数为N =2n，可按下式计算第i对向量的内积：
　　　　
　　下面是完成IP[i]（i = 1，2，…，K）的算法。
　　　　
　　忽略初始化、下标修正和测试等所需的时间，试计算在单处理机上实现上述算法总共需多少时间，并表达成K和N的函数，假定完成乘法与加法需用相同的单位时间。

三、应用题

1. 设计一种采用加、乘和数据寻径操作的算法，分别在下面两种计算机系统上用最短的时间来计算表达式s=A1*B1+A2*B2+…A32*B32。假设加法和乘法分别需要两个和四个单位时间，从存储器取指令，取数据、译码的时间忽略不计，所有的指令和数据已装入有关的PE。试确定下列每种情况的最小计算时间：
(1) 一台串行计算机，处理机中有一个加法器和乘法器，同一时刻只有其中一个可以使用。这种单处理机系统不需要数据寻径操作。
(2) 一台有8个PE（PE0，PE1，…，PE7）的SIMD计算机，8个PE连成双向环结构。每个PE用一个单位时间可以把数据直接送给它的相邻PE。操作数Ai和Bi最初存放在PEi mod 8中，其中i=1，2，…，32。每个PE可在不同时刻执行加法或乘法。