【文档说明】计算机体系结构金星阵列处理机课件.pptx，共(48)页，414.883 KB，由小橙橙上传

转载请保留链接：https://www.ichengzhen.cn/view-77486.html

以下为本文档部分文字说明：

计算机体系结构金星阵列处理机课件1、SIMD基本构形•(1)分布式存储器•(2)集中式存储器LM0互连网络……PE0CULM1PE1LMn-1PEn-1IOP……分布式存储器PE0互连网络……CUPE1PEn-1IOPSM0……SM1SMk-1集中式存储器2、阵列

处理机与流水线机比较性能阵列处理机向量处理机冗余情况资源重复时间重叠并行类型同时性并发性设备利用率低高提高速度的措施增大处理单元数缩短时钟周期单元连接方法简单规整的互连网络一般连接机型专用机通用机二、并行算法•1、ILLIACIV的处理单元阵列结构PU56P

U57PU63PU6323456PU8PU81011121314PU1616171819202122232425262728293031323334353637383940414243444546474849505152535455PU555859606162PU0PU0PU1

PU7PU0PU1PU8PU9PU56PU57PU7PU15PU63ILLIACIV的处理单元阵列结构特点•N=64处理单元数构成8*8阵列•第i个处理单元PUi与以下四个单元连接•上:(i–8)mo

d64•下:(i+8)mod64•左:(i-1)mod64•右:(i+1)mod64•网络直径：网络中任意两个结点间最短路径长度的最大值。•对于n*n的阵列，网络直径为n-12、并行算法举例矩阵加：C=A+B，其中A，B，

C为8*8的矩阵并行算法对数据存储的要求：不同向量相同位置的元素放在同一个存储器内，同一向量的各元素放在不同存储器的同一地址单元中。…A(0,1)B(0,1)C(0,1)……A(0,0)B(0,0)C(0,0)……A(7,7)B(7,7)C(7,7)…aa+1a+2PEM0PEM1PEM63…

LDAALPHAADRNALPHA+1STAALPHA+2三、SIMD计算机的互连网络1、基本概念(1)互连网络的定义互连网络是一种由开关元件按照一定的拓扑结构和控制方式构成的网络，用于实现计算机系统内部多个处理机或多

个功能部件之间的相互连接。(2)互连网络的设计目标•结构简单，降低成本•互连灵活，满足应用要求•步距小，提高速度•结构规整，扩充性好(3)互连网络的分类•静态连接网络：使用直接链路连接各结点，并且构成

后结点间的连接方式就固定不变的网络。用于构造通信模式可预测或可用静态连接实现的计算机系统。•动态连接网络：结点之间的连接不固定，使用开关或仲裁器实现结点之间的互连，根据程序要求动态连接开关，常用于集中式共享存储器多处理系统。(4)互连函数互连

函数(路由函数)：N个输入端的结点号与N个输出端的结点号的一种对应关系可以用一个映射函数表示，称为互连函数。它是处理单元集合对于自身的双射映射，所以又称为“置换”，或者“循环”。把互连网络的n个结点用0,…,n-1表示，则f(x)表示以结点x为入端的通道的出端。互连函数有多

种表示方式，如下例所示：f(0)=1f(1)=2f(2)=0f(3)=3a.枚举法01230123b.开关状态图f=(0,1,2)(3)d.循环函数一个网络通过开关切换可以形成多个映射关系，所以要用“互连函数族”来定义一个网络。f=01231203c.列表法2基本

的单级互连网络•立方体•PM2I•混洗交换(1)立方体网络连接规律：每个处理单元只能直接连接到它的二进制编号某位取反的处理单元上。Cube0(P2P1P0)=P2P1P0Cube1(P2P1P0)=P2P1P0Cube2(P2P1P0)=P2P1P0Cube0:(01)(23)(45

)(67)Cube1:(02)(13)(46)(57)Cube2:(04)(15)(26)(37)一般情况下，一个n()维超立方体共有n个互连函数(分别由n位地址中的每一位求反位值来确定)：Cube0，Cube1，……，Cuben-1C

ubei的功能是对入端结点编号二进制形式的第i位取反Cubei(Pn-1…Pi+1PiPi-1…P0)=Pn-1…Pi+1PiPi-1…P0，其中0≤i≤n-1Nn2log网络直径：立方体网络直径为n立方体网络是一个可逆网络连接规律：j号处理单元

直接连接到j±2i号处理单元PM2I函数定义：功能是对入端结点编号加或减2i，然后再作模N运算。PM2+i（j）=(j+2i)modNPM2-i（j）=(j-2i)modN其中j=0～N-1，i=0～n-1。PM2I函数共有n对成员，分别是PM2±0，PM2±1，……，PM2±(n-1)。由于

PM2±(n-1)的函数值相等，所以只有2n-1个函数网络直径：(2)PM2I网(移数网、单级加减2i网）2/nN=8时，有5个不同的互连函数•PM2+0：(01234567)•PM2-0：(76543210)•PM2+1：(0246)(1357)•PM2-1：(6420)(7531)•

PM2+2：(04)(26)(15)(37)(3)均匀混洗交换网络该网络由混洗函数(shuffle)与交换函数(exchange即Cube0)定义.混洗函数：将结点的二进制编号循环左移一位shuffle（Pn-1Pn-2……P0）=Pn-2……P0Pn-1f=0123456702

461357n=3的混洗网络拓扑形状如下图绿线所示，可以看出它不是一个连通图，所以还需要增加一个交换函数（图中红线所示），才能构成完整的单级混洗—交换网络。单级混洗—交换网络的直径是2n-1。f=01234567024613573、多级互连网定义：多级ICN使用多级开关，将多个单级网络串联，以

实现任意两个处理单元之间的连接。将多级互连网络循环使用可实现复杂的互连。通常在N个结点的网络中，多级ICN由n级构成（n=log2N）。经典的多级互连网有多级立方体网、多级混洗—交换网和多级PM2I网。多级网络的三个参数：(1)交换开关：二元交换开关的基本接通状态有“直连”

、“交换”、“上播”和“下播”。直通交换上播下播(2)拓扑结构(3)控制方式(3)控制方式各开关的控制信号可采用3种分配方式之一：级控方式、部分级控方式和单元控制方式。级控方式就是同一级（即同一列）开关共用一个

控制信号，动作保持一致；部分级控方式在第i级设置i+1个独立的控制信号，每个信号管辖若干开关；单元控制方式为每个开关独自设置一个控制信号，各开关动作独立，性能比前两种方式都更灵活，结构也更复杂。(1)多级立方体•它由n级构成，每一级包含N/2可控的二元交换开关•采用二功能交换单元:直连和交

换•当第I级开关处理交换状态时，实现的是Cubei函数多级立方体网络结构ABCDEFGHIJKL0123456701234567k=0k=1k=20011223344556677多级立方体网络特点续：•采作三种不同的控制方式

，可以构成三种不现的互连网络：–级控制构成STARAN交换网络–部分级控制构成STARAN移数网络–单元控制构成间接立方体网络灵活性好STARAN交换网络级控制信号(二进制)：K2K1K0Ki=0表示第i级的开关为直连状态，Ki=1表示第i级的开关为交换状态例：已知入端号和控制

信号，求出端号若控制信号Ki=1，则入端号的第i位取反例：已知入端号和出端号，求控制信号控制信号=入端号和出端号异或恒等4组2元+2组4元4组2元(2)多级混洗—交换网络多级混洗—交换网络又称为Omega网。多级混洗—交换网络结构：它由n级构成，每一级包含一个全混拓扑线路和一列(N

/2个)可控的二元交换开关四功能交换单元控制方式：单元控制多级混洗—交换网络结构IJKLEFGHABCD0123456701234567多级混洗—交换网络的特点续：在多级混洗—交换网络中，单独一级混洗拓扑线路可完成一次数据混洗（shuffle）

，而单独一列二元交换开关在处于“交换”状态时可完成一次交换操作（Cube0）。如果各级二元交换开关都处于“直连”状态，N个结点的数据通过网络仅经过n次混洗操作，排列顺序最终恢复输入状态；如果各级二元交换开关都处于“交换”状态，则N个结点的数据在每次混洗之

后紧接着一次交换（Cube0），也就是地址码的最低位取反，最后n位地址均被取反。程序员根据数据置换或复制的需要，可以灵活地设置各开关的状态。多级混洗—交换网络与多级立方体网络的关系k=0k=1k=2012345670426153702134657IJKLEFG

HABCD0123456701234567(3)多级PM2I•包含n级单元间连接，每一级前后两列的单元都按PM2I拓扑连接。•第I级的每一个入端都连接到三个出端：j、(j+2i)modN、(j-2i)modN•控制方式：–部分级控制构成数据变换网络DM–采用单元控制构成强化数据变换

网络ADM(4)全排列网络•非阻塞式网络：所有入端、出端的连接都不发生冲突的网络，又称为全排列网络•N个结点的全部排列有N!种•阻塞式网络(Blocking):在实现两对或多对入出端连接时，都因可能因争用数据传送路径而发生冲突的网

络。立方体网络、PM2I、Omega网络都是阻塞式网络•N个结点的多级阻塞式网络在一次传送这中能实现的排列有NN/2种Benes网络：三维立方体多级网络和它的可逆网络构成的全排列网络k=0k=1k=2ABCDEFGHIJKL

01234567012345670123456702134657Benes网络：三维立方体多级网络和它的可逆网络构成的全排列网络k=0k=1k=2ABCDEFGHIJKL0123456701234567012345

6702134657Benes网络：三维立方体多级网络和它的可逆网络构成的全排列网络k=0k=1k=2ABCDEFGHIJKL01234567012345670123456702134657k=0k=1k=2ABCDEFGHIJKL012345670123456701234567021

34657四、并行存储器的无冲突访问•阵列处理机中，存储器要采用多体并行，才能保证其频宽与多个处理单元速度匹配，还要保证实现无冲突访存操作(即要访问的数据不在同一体内)•以数组为例：数组的访问模式：行、列、主对角线、次对角线、子方阵1、一维数组•连续访问m=4个元素，无冲突•按2i变址

，冲突，存储器频宽降低一半•为了避免冲突，M应取质数(只要变址跳距与m互质)2、二维数组•同时访问某一行、主对角线、次对角线上的所有元素时，无冲突•同时访问某一列时，冲突，存储器频宽降低为1/4错位存放•方案一中主对角线和次对角线并行访问冲突•方案二中当访问模式为行、列、主对角线、次对角线

、子方阵时均无冲突(1)无冲突访问错位存放方案的一种实现思想：数据交叉存储在m个存储体中，并且使存储体M大于每次要访问的全部向量元素N，且为质数。δ1表示同列相邻元素错开的距离δ2表示同行相邻元素错开的距离M确定：

m=22p+1(p为正整数)实现无冲突访问的充分条件：δ1=2p,δ2=1对于一个n*n维的二维数组，元素Aab存放的地址：体号:j=(aδ1+bδ2+c)modm体内:i=a(2)无冲突访问错位存放方案的第二种实现•有n个处理单元的并行处理机，为了能并行访问n个元素,存储体数m

为大于n最小质数•将多维数组行或列的顺序变换为一维数组，形成一个一维线性地址空间，地址用s表示。–如果按行展开：S=元素的行号*行数+元素的列号–如果按列展开：S=元素的列号*列数+元素的行号•地址s所对应的元素在m个分体数的存储器中存放的地址为：体号：j=smodm体内：j=s

/n向下取整总结•选择适当的存储体数m达到无冲突访问最基本的条件：存储体数是大于处理单元数的最小质数•一维向量：顺序存放，防止与m成比例，m取质数，且与步长互质•多维向量：错位存放，满足行、列、对角线等方式•常用方法：存储体数为质数，将向量变换成一维数组S，再对S进行

处理