第六章 向量处理机

6.3.4 基本的多级互连网络

最基本的多级互连网络就是6.3.3提到的前三种单级网络相对应组成多级立方体互连网络、多级混洗交换网络和多级PM2I网络。此外还有基准网络。

不同的多级互连网络,在所用的交换开关。拓扑结构和控制方式上各有不同。

交换开关是具有两个入端和两个出端的交换单元,用作各种多级互连网络的基本构件。无论入端或出端,如果令居于上方的都用i表示,居于下方的都用j表示,则可以定义下列4种开关状态或连接方式:

1)直连,即i连i,j连j

2)交换,即i连j,j连i

3)上播,即i连i和j,j悬空

4)下播,即j连i和j,i悬空

有前两种功能的称而功能交换单元,四种功能的称四功能交换单元。两个入端同时连到一个出端会发生信息传送的冲突,是不允许的。

第五种开关状体即,i连j,i连j,称此为返回。它可用来实现入端和入端相连,出端与出端相连,从而将N个入端和N个出端的网络变为2N个处理单元的互连网络。

拓扑结构是各级间出端与入端互连的模式。

控制方式是对各个交换开关进行控制的方式,以多级立方体网路为例,它可以有3钟:

1)级控制——同一级的所有开关都用一个控制信号控制,同时只能处于同一种状态。

2)单元控制——每一个开关都由自己独立的控制信号控制,可各自处于不同的状态。

3)部分级控制——第i级的所有开关分别用i+1个信号控制,,n为级数。

1.多级立方体网络

多级立方体网络有STARAN网络、间接二进制n立方体网络等。

共同特点是:第i级()交换单元处于交换状态时,实现的是Cubei互连函数,且都采用而功能交换单元。两者的差别仅在于控制方式上,STARAN网络采用级控制(称交换网络)和部分级控制(其中可实现移数功能的称移数网络),而间接二进制n立方网络用单元控制。因此后者具有更大的连接灵活性。

STARAN网络用作交换网络时,采用级控制,实现的是交换函数。

交换(Flip)函数是将一组元素首尾对称地进行交换。如果一组元素包含2s个,则它是将所有第k个元素都与2s-(k+1)个元素相交换。

不管控制信号是什么状态,实现的都是交换函数的功能,任何输入端只要通过不同的级控制信号,总可以接到任何所需要的输出端上。

当STARAN网络做移数网络时,采用部分级控制。

STARAN网络成功地用在巨型相联处理机STARAN中的多维相联存储器与处理部件之间,对存储器中杂错存放的数据在读出后和写入前进行重新排列,以适应处理部件对数据正常位序的需要。利用交换和移数这两种基本功能,加上对数据位进行屏蔽,还可以实现全混、展开、压缩等多种数据变换函数功能。

2.多级混洗交换网络

多级混洗交换网络又称omega网络。它由n级相同的网络组成,每一级都包含一个全混拓扑和随后一列2n-1个四功能交换单元,采用单元控制方式。

omega网络中各级编号的次序与多级立方体网络正好相反,如果把omega网络的入端和出端位置对调,它就等同于间接二进制n方体网络,omega网络与间接二进制n方体网络只有两点差别:前者数据流向是级号n-1,n-2.....1,0,用四功能交换单元。后者数据流向饭,是级号0,1,......,n-1,用而功能交换单元。

3.多级PM2I网络

多级PM2I网络分为:

1.数据变换网络(Data Manipulator)

控制3类连接线的信号,平控H、下控D和上控U。为简化对这3类信号的产生,可将各级的单元分成两组,对于第i级,让控制第i位为0的那些入单元,而控制第i位为1的那些如单元。

2.强化数据变换(Augmented Data Manipulator,ADM)

采用单元控制增强对各级单元公职的灵活性,让每一单元都有自己独立的控制信号H、D、U。

控制线多,成本较高。

ADM的拓扑结构和控制方式使它可以完全模仿omega网络的四功能交换单元。

ADM可以实现omega网络的全部链接,而且其组合数还要更多,利用数据变换网络可以实现各种灵活的移数、重复、间隔、展开等函数变换。


 

以上多级网络,灵活性由低到高的次序是:

级控制立方体、部分级控制立方体、间接二进制n方体、omega、ADM

而复杂性和成本的次序也相应增高。

4.基准网络

它与二进制立方体网络的逆网络相似,只是在第1级的级间连接不同,它采取从输入到输出的级间互连为恒等、逆全混、子逆全混和恒等置换。所用交换单元均为二功能的。采取单元控制。

基准网络在多级网络中可作为中间介质,模拟一种网络的拓扑和功能。

5.多级交叉开关网络

多级交叉开关(CLOS)网络是一种非阻塞式网络,一个三级交叉开关网络的结构,其网络的入、出端口均为n*r,输入级有r个n*m的交叉开关,钟建吉有m个r*r的交叉开关,输出级有r个m*n的交叉开关,当时,它就成了非阻塞网络。

非阻塞网络:同时实现两对或多对入出端间的连接,均不会发生传送路径上的冲突,表示成N(m,n,r)

N(m,n,r)的多级交叉开关交叉结点总数为:

一级交叉开关结点数为n2个,因此,当n值较大时,使mr(2n+r)<n2,这时采用多级交叉开关网络互连,既保证了无阻塞连接,也降低了互连网络成本,便于工程实现。

6.多级蝶式网络

蝶式网络不能实现播送,只是omega网络的一个有限制的子集。

6.3.5 全排列网络

如果互连网络是从N个入端到N个出端的一到一的映射,就可以把它看成是对此N个端的重新排列,因此互连网络的功能实际上就是用新排列来置换N个入端原有的排列。其他基本多级网络都能实现任意一个入端与任意一个出端间的连接,但要同时实现两对或多对入、出端间的连接时,就有可能发生争用数据传送路径的冲突。称有这类性质的互联网络为阻塞式网络(Blocking Network)。称没有这类性质的互连网络为非阻塞式网络或全排列网络。

非阻塞式网络连接灵活,但连线多、控制复杂、成本高。

阻塞式网络在一次传送中不可能实现N个端的任意排列。N个端的全部排列有N!种。可是用单元控制的n=log2N 级间接二进制n方体网络,每级有N/2个开关,n级互连网络共用(N·log2N)/2个二功能的交换开关。这样,全部开关处于不同状态的总数为NN/2种。当N为大于2的整数时,总有NN/2<N!,就是说它无法实现所有N!种排列。多对入、出端要求同时连接时就可能发生冲突。

只要经过重新排列已有入、出端对的连接,就可完成所有可能的入、出端间的连接而不发生冲突的互连网络称为可重排列网络(Rearrangeable NetWork)。实现时,可以再上述任何一种基本多级互连网络的出端设置锁存器,使数据在时间上顺序通行两次,这实际上就是循环多级互连网络的实现思路。

用多级网络也可以实现全排列网络,将log2N 级的N个入端和N个出端的互连网络和它的逆网络连在一起,省去中间完全重复的一级,得到总数为2log2N -1级的全排列网络。称此网络为Benes网络。该网络至少有两个以上的通道能满足一对结点的连接要求,即数据寻经不唯一,有较多的冗余,这有利于选择合适的路径传送,可靠性、灵活性较好。

6.4 共享主存构形的阵列处理机中并行存储器的无冲突访问。

在共享主存构形的阵列处理机中,存储器频宽要与多个处理单元的速率匹配,存储器就必须采用多体并行组成,保证在各种访问模式下,存储器都能实现无冲突的工作,只有这样,存储器的实际频宽才不会下降,从而使阵列处理机的数组并请处理的性能不至于下降。对数组访问的模式是多样的,可能要访问数据的行、列、主对角线、次对角线的全部元素或其中某个子方阵。

情况1:并行存储器的分体数m应取成质数,才能较好地避免存储器访问的冲突。只要编址跳距与m互质,存储器访问就总能无冲突的进行。

情况2:使并行存储器分体数m大于每次要访问的向量或数组元素的个数n(n在阵列处理机上就是处理单元数),且等于质数,同时在多维数组的行、列等方向上采取不同的错开距离。

在这种方案里,要访问的数组中各元素的排列次序是乱的,为此,系统需要有专门的互连网络(排列网络或对准网络)来将其恢复成正常的顺序。

对于一个n*n二维数组A中的任意一个元素Aab应放在下列地址处

上为体号地址,下为体内地址。

其中,,C为起始元素A00所在体号地址。

情况3:有n个处理单元的并行处理机,为了能并行访问n个元素,且适应任意规模的数组,可以先将多维数组或非n*n仿站的二维数组按行货咧的顺序变为一维数组,形成一维线性地址空间,地址用a表示,然后,将地址a所对应的元素存放在体号地址j=a mod m,体内地址为 的单元中,就可以满足无冲突访问的要求。

 6.5 脉动阵列流水处理机

为满足计算量很大的信号/图像处理及科学计算的特定算法的需求,1978年提出了有脉动阵列结构的脉动阵列(Systolic Array)处理机的思想。

它对特定问题具有极高的计算并行性,是一种解题速度很高的处理机。

6.5.1 脉动阵列结构的原理

脉动阵列结构是一组处理单元(PE)构成的阵列。每个PE的内部结构相同。一般由一个加法/逻辑运算部件或加法/乘法预算部件再加上若干锁存器构成,可完成少数基本的算术逻辑运算操作。阵列内所有处理单元的数据锁存器都受同一个时钟控制。运算时,数据在阵列结构处理单元间沿各自的方向同步向前推进。

为了执行多种计算,脉动型系统内的输入数据流和结果数据流可以再多个不同方向上以不同的速度向前搏动,阵列内部的各个单元只接收前一组处理单元传来的数据,并向后一组处理单元发送数据,只有位于阵列边缘的处理单元才与存储器I/O端口进行数据通信,根据具体计算的问题不同,脉动阵列可以有一维线形、二维矩形/六边形/二叉树形/三角形等阵列互连构形。除此之外还有不少变形。

脉动式阵列的结构与解题算法有关,如果要解的矩阵规模较大,可通过软件把大矩阵拆分成多个小矩阵,分别在脉动阵列上求解,再在主机商作进一步处理。

脉动阵列结构具有以下特点:

1.结构简单、规整、模块化强、可扩充性好,非常适合用超大规模集成电路实现。

2.PE间数据通信距离短、规则,使数据流和控制流的设计、同步控制等均简单规整

3.脉动阵列中所有PE能同时运算,具有极高的计算并行性,可通过流水获得很高的运算效率和吞吐率,输入数据能被多个处理单元重复使用,大大减轻了阵列与外界的I/O通信量,降低了对系统主存和I/O系统频宽的要求。

4.脉动阵列结构的构型与特定计算任务和算法密切相关,具有某种专用性,限制了应用范围,这对VLSI不利。

6.5.2 通用脉动阵列机构

造成脉动阵列处理机应用范围有限的关键因素是:受阵列机构的通用性及I/O带宽约束所限制的阵列结构的规模大小,不同的算法往往要求能有不同的阵列结构,以及大小不同的阵列,为了克服脉动阵列结构通用性差的缺点,近年来已研究和发展了一些可有效执行多种算法的较为通用的脉动阵列结构。

第一种途径是通过增设附加的硬件,对阵列的拓扑结构和互连方式用可编程开关进行重构,即经程序重新配置阵列的结构。

第二种途径是用软件把不同的算法影响到固定的阵列结构上,这一方法依赖于面向并行运算所采用的编程语言、操作系统、编译程序和软件开发工具的设计。

第三种途径是探寻与问题无关的脉动处理方法,以及VLSI运算系统的分割矩阵算法,使他们可以客服阵列只能求解固定大小题目的缺陷。同时探寻发展适合一类计算问题的通用算法和相应的设置方案。

与本文相关的文章
版权声明
转载保留版权: 大D综合研究院 | 《《计算机系统结构》读书笔记(十七)》
本文链接地址:https://www.dadclab.com/archives/3225.jiecao
转载须知:如果您需要转载本文,请将版权信息,版权授权方式,以及本文的链接地址注明,谢谢合作。
本文被贴上了: , , , , 标签