计算机系统结构(第十一讲).ppt

计算机系统结构 (第十一讲),厦门大学计算机科学系 曾文华 2002年11月13日,第七章 互连网络,7.3 互连网络实例,多处理机的网络： （1）、总线结构 （2）、多级开关网络 （3）、超立方体 （4）、交叉开关 R/C比值：程序的执行时间/用于通信的开销（P503）,7.3.1 总线互连,通过共享总线把各台处理机连接起来 全局存储器 图7.38：总线互连的多处理机框图 克服共享存储器瓶颈的方法：P429 （1）、技术方面 （2）、系统结构方面 （3）、算法方面,图7.39：一种通过一条物理长度较短的总线连接多台处理机的方法（各台处理机通过较长的连线与各自专门接口相连，这些接口再与共享总线相连；短总线的目的是保证传输信号的质量）,7.3.2 环形互连,图7.40：处理机之间点点连接的环型互连网络 IEEE 802.5令牌环（Token ring）标准：发送信息的处理机拥有一个唯一的令牌，在同一时刻只有一台处理机持有这个令牌,7.3.3 交叉开关互连,互连网络最简单，但争用最严重 交叉开关网络争用最低，但连接复杂度最高 图7.41：基于交叉开关连接的多处理机 网络中每个交叉点是一个允许任何一台处理机与任何一个存储器连接的开关 程序7.1：各处理机计算各自本地数据的和，然后再将本地和相加以形成全程和的程序 当处理机Pi“拥有”全程变量Global-Sum期间，任何访问该变量的操作都应被禁止；LOCK(Global-Sum)和UNLOCK(Global-Sum),交叉开关互连的成本与交叉点的数目成正比例，即与N2成正比例 总线互连的成本与N成正比例 C.mmp计算机：采用交叉开关互连 CMU研制，见P412的图7.23(a),7.3.4 混洗交换互连和合并开关,混洗交换互连网络不但能用来连接向量处理机，例如用于循环归约和多重递归，还能用来连接相互独立的处理机 合并开关：它使某些操作在网络一级并行地执行，从而减少了争用现象 图7.42：混洗交换网络 混洗交换网络的带宽高于总线，而低于交叉开关；成本为O(N*logN),7.3.5 Omega网络,Omega网络已经用于Illinois大学的Cedar多处理机、IBM的RP3、New York大学Ultracomputer 图7.43：8个输入端的Omega网络 n个输入端的Omega网络有log2n级 图7.43(b)：出现阻塞（开关F、G、H） 图7.44：Omega网络的广播功能,图7.45：8*8交叉开关构成模块结构的蝶式网络 图7.45(a)：16个8*8交叉开关构成的两级64*64蝶式网络（级间采用8路洗牌连接） 图7.45(b)：192个8*8交叉开关构成的三级512*512蝶式网络 第0、1级共需8*16个8*8交叉开关 第2级共需8*8个8*8交叉开关 总计：8*16+8*8=192,7.3.6 蝶形操作,有限离散傅立叶变换：需要大约N2次复数乘法和N*(N-1)次复数加法 快速傅立叶变换(FFT)：只需要Nlog2N次运算 FFT比常规算法提高：N2/Nlog2N=N/log2N 在多处理机上进行FFT运算需要两类通信： （1）、蝶形操作 （2）、二进制反向传输 图7.46：在有16台处理机和16 个存储器的网络上的二进制反向传输,二进制反向传输的性能很差，采取如下处理步骤： （1）、使用FFT把时域变成频域 （2）、在频域中进行处理 （3）、使用FFT把频域变回时域 N N/log2N n1/2 1 Pfister-Norton模型： 访问“热”存储器的请求次数=r*(1-h)+r*h*N 最大有效请求率R=r/r*(1-h)+r*h*N=1/ (1+h(N-1) 1+0.01*(1024-1)=11.23 1+0.001*(1024-1)=2.023 结论：冲突使网络出现如图7.47所示的树形饱和,7.3.7 合并网络和取与加指令,什么是合并网络？ 两个或多个访问同一共享单元的请求在某种条件下可以合并成一个，这样就减少了对共享存储单元的访问率，从而减少冲突和由于冲突而带来的带宽的下降。 合并网络提供了一组新的指令，其中一条称为Fetch-and-Add指令，叫做取与加指令,举例（排队问题）：假使N个请求每一个都要将一个数据项加到队列中 Fetch-and-Add指令： Definition:Fetch-and-Add(Address,Increment) Temp:=MemoryAddress; MemoryAddr