第第 6 6 章章 阵列处理机和相联处理机阵列处理机和相联处理机 6.1 阵列处理机的原理阵列处理机的原理 6.2 SIMD计算机的互连网络计算机的互连网络6.3 并行存储器的无冲突访问并行存储器的无冲突访问6.4 脉动阵列处理机脉动阵列处理机 本章要点本章要点v阵列处理机的构型及特点阵列处理机的构型及特点v基本的单级互联网络结构图及互联函数基本的单级互联网络结构图及互联函数v两功能交换开关及四功能交换开关两功能交换开关及四功能交换开关v多级立方体网络拓扑结构图的画法多级立方体网络拓扑结构图的画法v多级混洗交换网络拓扑结构图的画法多级混洗交换网络拓扑结构图的画法v并行存储器的无冲突访问并行存储器的无冲突访问 1.阵列处理机的构形阵列处理机的构形 阵列机通常由一个控制部件阵列机通常由一个控制部件CU、、N个处理器单元个处理器单元PE、、M个个存储模块以及一个互连网络部件存储模块以及一个互连网络部件(IN)组成 根根据据存存储储器器模模块块是是以以分分布布式式方方式式存存取取还还是是集集中中方方式式存存取取，，阵阵列列机机可可分分为为两两种种基基本本结结构构：：分分布布式式存存储储器器的的阵阵列列机机和和共共享享存存储器的阵列机。
储器的阵列机6.1 阵列处理机的原理阵列处理机的原理 6.1.1 阵列处理机的构形与特点阵列处理机的构形与特点 PEM0PE0PEM1PE1PEMN-1PEN-1INCUCUMI/O接口接口DSC分布存储器的阵列机结构分布存储器的阵列机结构 （（1）分布式存储器的阵列机）分布式存储器的阵列机 各个处理单元设有各个处理单元设有局部存局部存储储器器存放分布式数据，只能被本存放分布式数据，只能被本处理单元直接访问在控制部件处理单元直接访问在控制部件CU内设有一个用来存放程序和内设有一个用来存放程序和数据的主存数据的主存储储器器CUM各个PE同步执行来自同步执行来自CU的操作命令，的操作命令，各处理单元通过各处理单元通过IN来交换数据来交换数据 …INPE0PE1PEN-1MM0MM1MMK-1CUSCI/O-CHI/OSM……具有共享存储器的阵列机结构具有共享存储器的阵列机结构 （（2）集中式共享存储器的阵列机）集中式共享存储器的阵列机 每个每个PE没有局部存没有局部存储储器器，存储模块以集中形式为所有，存储模块以集中形式为所有PE共共享互连网享互连网IN受受CU控制，用来构成控制，用来构成PE和和MM的数据交换通路的数据交换通路 ，，具有双向性。
具有双向性 2 阵列机的特点阵列机的特点并行处理机有如下特点：并行处理机有如下特点：（（1）） 利用利用资源重复资源重复（空间因素）而非时间重叠空间因素）而非时间重叠2）） 利用利用同时性同时性而非并发性它的每个处理单元在同一时刻要而非并发性它的每个处理单元在同一时刻要同等地担负起各种运算功能同等地担负起各种运算功能3）提高运算速度主要是靠）提高运算速度主要是靠增大处理单元个数增大处理单元个数，比起向量流水，比起向量流水线处理机主要依靠缩短时钟周期来说，速度提高的潜力要大得多线处理机主要依靠缩短时钟周期来说，速度提高的潜力要大得多（（4）使用简单而又规整的）使用简单而又规整的互连网络互连网络来确定多个处理单元之间的来确定多个处理单元之间的连接模式连接模式 （（5）） 并行处理机（阵列机）研究必须并行处理机（阵列机）研究必须与并行算法研究密切结合与并行算法研究密切结合，使之适应性更强，应用面更广使之适应性更强，应用面更广 6.1.2 ILLIAC-IV处理单元阵列结构处理单元阵列结构•处理单元阵列由处理单元阵列由64个个PUi构成构成,每个每个PUi包括包括(PEi、、PEMi和和MLU) 由由64个结构完全相同的处理单元个结构完全相同的处理单元PEi 构成，每个处理单元构成，每个处理单元PEi字长字长64位，位，PEMi为隶属于为隶属于PEi的局部存储器，全部的局部存储器，全部PEi由由CU统一管理，统一管理，PEi都有一根方式位线，用来向都有一根方式位线，用来向CU传送每个传送每个PEi的方的方式寄存器式寄存器D中的方式位，使中的方式位，使CU能了解各能了解各PEi的状态是否活动，作的状态是否活动，作为控制它们工作的依据。
为控制它们工作的依据 •阵列控制器阵列控制器CU 相当一台小型控制计算机相当一台小型控制计算机 对处理单元阵列实现控制对处理单元阵列实现控制,(发控制信号发控制信号,广播公共地址广播公共地址,(广播公广播公共数据共数据)）对指令流进行译码控制）对指令流进行译码控制,利用利用CU内部资源可以进行标内部资源可以进行标量操作量操作,接受和处理各类中断，其他输入输出操作接受和处理各类中断，其他输入输出操作•I/O系统系统 由磁盘文件系统由磁盘文件系统DFS，输入输出子系统和宿主计算机，输入输出子系统和宿主计算机S/C构成构成 ILLIAC Ⅳ的组成的组成 PU16PU0PU8PU7PU55PU63PU0PU1PU7PU8PU9PU15PU56PU57PU63PU0PU1PU7PU56PU57PU58ILLIAC-IV的处理单元互连结构的处理单元互连结构 特点特点: (1)闭合螺线阵列闭合螺线阵列 (2)任意单元的最短距离不超过任意单元的最短距离不超过7步步将将PU63传送到传送到PU10，最快可经，最快可经PU63→PU7→PU8→PU9→PU10。
(3)一般来讲：一般来讲： 个处理单元组成的阵列中，任个处理单元组成的阵列中，任意两个处理单元之间的最短距离不会超过意两个处理单元之间的最短距离不会超过 步步（（4 4））处理单元为通常的累加型运算器，把累加寄存器处理单元为通常的累加型运算器，把累加寄存器RGARGA中的数据和存储器来的数据进行运算操作，数据传送寄存器中的数据和存储器来的数据进行运算操作，数据传送寄存器RGRRGR收发数据，实现数据在处理单元之间的传送收发数据，实现数据在处理单元之间的传送 一．一． 矩阵加矩阵加 矩阵加矩阵加(配比加配比加)是最简单的情况假定两个是最简单的情况假定两个8*8的矩阵的矩阵A、、B相加，所得结果矩阵相加，所得结果矩阵C也是一个也是一个8*8的矩阵的矩阵 设A、、B的分量元素分别存在的分量元素分别存在PEM i的的Z,Z+1单元中单元中,所得结果矩阵所得结果矩阵C各分量存在各分量存在PEM i 的的Z+2单元中单元中用下面三条指令可一次完成用下面三条指令可一次完成(64个处理单元并行个处理单元并行)LDA Z；全部（；全部（Z）由）由PEMi送到送到PE的累加器的累加器RGAi ADRN Z+1；全部（；全部（Z+1）与（）与（RGAi）进行浮点加，结果）进行浮点加，结果 送送RGAi STA Z+2；全部（；全部（RGAi）由）由PE送到送到PEMi的（的（Z+2）单元）单元这里0≤ i ≤63 6.1.3 ILLIAC Ⅳ的并行算法举例的并行算法举例 矩阵加存储器分举例矩阵加存储器分举例 A(0,0)B(0,0)C(0,0)PEM0aa+1a+2A(0,1)B(0,1)C(0,1)PEM1A(7,7)B(7,7)C(7,7)PEM63处理速度为顺序处理的处理速度为顺序处理的64倍倍 二．二． 矩阵乘矩阵乘a0,0 a0,1 … a0,7a1,0 a1,1 … a1,7……a7,0 a7,1 … a7,7b0,0 b0,1 … b0,7b1,0 b1,1 … b1,7……b7,0 b7,1 … b7,7a0,0×b0,0+a0,1×b1,0+…+a0,7×b7,0 … a0,0×b0,7+a0,1×b1,7+…+a0,7×b7,7a1,0×b0,0+a1,1×b1,0+…+a1,7×b7,0 … a1,0×b0,7+a1,1×b1,7+…+a1,7×b7,7 ……a7,0×b0,0+a7,1×b1,0+…+a7,7×b7,0 … a7,0×b0,7+a7,1×b1,7+…+a7,7×b7,7 =× 如果顺序执行如果顺序执行C=A×B，那么，计算每个元素，那么，计算每个元素cij需要做需要做8次次乘法，乘法，7次加法，共需做次加法，共需做15次乘次乘/加运算。
加运算 在在ILLIAC IV的处理机上，操作数的处理机上，操作数B的的64个元素存储在个元素存储在64个个PEM中当每次计算元素中当每次计算元素cij时，就把操作数时，就把操作数A的的8个元素个元素aik(0<=k<=7)播送到相应的播送到相应的8个个PE中，然后并行地中，然后并行地一次一次完成完成8个个中间积的运算最后对中间积的运算最后对8个中间积做个中间积做7次加法，累加得到次加法，累加得到cij A(0,0)A(1,0)...A(7,0)B(0,0)B(1,0)...B(7,0)C(0,0)C(1,0)...C(7,0)A(0,1)A(1,1)...A(7,1)B(0,1)B(1,1)...B(7,1)C(0,1)C(1,1)...C(7,1)A(0,7)A(1,7)...A(7,7)B(0,7)B(1,7)...B(7,7)C(0,7)C(1,7)...C(7,7) PE0 PEM2 PEM7...矩阵乘存储器分配举例矩阵乘存储器分配举例 （设用八个处理单元即（设用八个处理单元即PU并行）并行）………………………...八个局部存储器八个局部存储器PEM i,每个连续存放每个连续存放A,B和结果向量和结果向量C的一列元素的一列元素 三、三、累加和累加和 （成对递归）（成对递归）这是一个将这是一个将N个数的顺序相加过程转变为并行相加过程的问题。
个数的顺序相加过程转变为并行相加过程的问题设N为8，即有，即有8个数个数A（（I））顺序累加，其中序累加，其中0≦≦I ≦≦ 7 在在SISD计算机上可写成下列程序：算机上可写成下列程序： C=0 DO 10 I=0，，7 10 C=C+A（（I））用成对递归算法，只需用成对递归算法，只需 Log2 8=3在在在在SIMDSIMD计算机上可写成下列程序计算机上可写成下列程序计算机上可写成下列程序计算机上可写成下列程序 C=A DO 10 K=0, Log2 8 - 110 C=C+SHFTR(C,2**K) 其中其中SHFTR(C,2**K)是向是向量传送语句量传送语句,C向量各向量各分量向右传送步距为分量向右传送步距为2的的K次幂次幂 用成对递归算法求累加和的步骤：用成对递归算法求累加和的步骤：1.置全部置全部PEi为活跃状态，为活跃状态， 0≦≦i ≦≦ 72.全部全部A（（i）从）从PEMi的的a单元读到相应单元读到相应PEi的累加寄存器的累加寄存器RGAi中，中，0≦≦i ≦≦ 7；；3.令令k=0；；4.将全部将全部PEi的（的（RGAi）传送到寄存器）传送到寄存器RGRi，，0≦≦i ≦≦ 7；；5.将全部将全部PEi的（的（RGRi）经过互连网络向右传送）经过互连网络向右传送2k步距，步距， 0≦≦i ≦≦ 7；；6.令令j= 2k-1；；7.置置PE0至至 PEj为不活跃状态；为不活跃状态；8.处于活跃状态的所有处于活跃状态的所有PEj执行（执行（RGAi））:= (RGAi)+（（RGRi）） ，， j≦≦i ≦≦ 7；；9.k:=k+1;10.如如k<3,则转回则转回4,否则往下继续执行否则往下继续执行;11.置全部置全部PEi为活跃状态，为活跃状态， 0≦≦i ≦≦ 7,存结果至存结果至a + 1单元。
单元设原始数据设原始数据A（（I）分别存在）分别存在8个个PEM的某的某a单元中单元中 设原始数据设原始数据A（（I）分别存在）分别存在PEM的某个单元中的某个单元中步距步距1 步距步距2 步距步距4 K=0 K=1 K=2PE0 A0 A0 A0 A0 PE1 A1 A0+A1 A0+A1 A0+A1PE2 A2 A1+A2 A0+A1+A2 A0+A1+A2PE3 A3 A2+A3 A0+A1+A2+A3 A0+A1+A2+A3PE4 A4 A3+A4 A1+A2+A3+A4 A0+A1+A2+A3+A4PE5 A5 A4+A5 A2+A3+A4+A5 A0+A1+A2+A3+A4+A5PE6 A6 A5+A6 A3+A4+A5+A6 A0+A1+A2+A3+A4+A5+A6PE7 A7 A6+A7 A4+A5+A6+A7 A0+A1+A2+A3+A4+A5+A6+A7 二、递归折叠求和二、递归折叠求和用递归折叠方法来求累加和过程如下图所示。
用递归折叠方法来求累加和过程如下图所示 上述求累加和算法虽然使计算次数减少，但是速度的提高的倍上述求累加和算法虽然使计算次数减少，但是速度的提高的倍数只是数只是N/ Log2 N，速度并没有提高多少速度并没有提高多少PE 值值 步步1 步步2 步步40 A0 A0+A1 A0+A1+A2+A3 A0+A1+A2+A3+ 1 A1 A4+A5+A6+A72 A2 A2+A3 3 A3 4 A4 A4+A5 A4+A5+A6+A7 5 A5 6 A6 A6+A7 7 A7 8 8个个PEPE的递归折叠求和的递归折叠求和长度为长度为N的递归计算的递归计算时间正比于时间正比于Log2 N 例：例：A和和B都是元素为浮点表示的都是元素为浮点表示的64×64的二维数组，一次浮点的二维数组，一次浮点加法的计算过程由取数、求阶差、对阶、尾数加、规格化和存加法的计算过程由取数、求阶差、对阶、尾数加、规格化和存数共数共6个段组成。
若每个段的执行时间均为个段组成若每个段的执行时间均为Δt，，请分别求出在下请分别求出在下列结构不同的处理机上完成列结构不同的处理机上完成C=A+B所需时间及相对于顺序处理所需时间及相对于顺序处理的加速比的加速比1)顺序处理方式的处理机顺序处理方式的处理机(2)具有浮点加法流水线的流水处理机，且浮点加法流水线分为具有浮点加法流水线的流水处理机，且浮点加法流水线分为6个段，各段执行时间均为个段，各段执行时间均为Δt3)8×8的阵列处理机，且处理阵列上的每个处理器只能顺序处理的阵列处理机，且处理阵列上的每个处理器只能顺序处理浮点加运算浮点加运算4)8×8的阵列处理机，且处理阵列上的每个处理器均能流水处理的阵列处理机，且处理阵列上的每个处理器均能流水处理浮点加运算浮点加运算4)64×64的阵列处理机的阵列处理机 a0,0 a0,1 … a0,63a1,0 a1,1 … a1,63……a63,0 a63,1 … a63,63b0,0 b0,1 … b0,63b1,0 b1,1 … b1,63……b63,0 b63,1 … b63,63+ a0,0 + b0,0 a0,1 + b0,1 … a0,63 + b0,63 a1,0 + b1,0 a1,1 + b1,1 … a1,63 + b1,63……a63,0+b63,0 a63,1+b63,1 … a63,63+b63,63=解：解：(1)顺序处理方式下，需要顺序执行的浮点加法次数为顺序处理方式下，需要顺序执行的浮点加法次数为64×64=4096，每次浮，每次浮点加运算所需时间为点加运算所需时间为6Δt ，则全部运算所需时间为：，则全部运算所需时间为：T1=4096×6Δt=24576Δt(2)需要流水执行的浮点加法次数为需要流水执行的浮点加法次数为64×64=4096，则一个，则一个K=6段浮点加法流段浮点加法流水线处理全部运算所需时间为：水线处理全部运算所需时间为：T2=(k+n-1)Δt=(6+4096-1)Δt=4101Δt加速比：加速比：S2=T1/T2=5.9 (3)对于对于8×8的处理阵列，每个处理器需要处理的处理阵列，每个处理器需要处理64×64二维数组中的一个二维数组中的一个8×8子子数组，因此，每个处理器需要执行的浮点加法次数为数组，因此，每个处理器需要执行的浮点加法次数为8×8。
每次浮点加法运每次浮点加法运算需要时间算需要时间6Δt 每个处理器顺序执行每个处理器顺序执行64次浮点加法所需时间为次浮点加法所需时间为64×6Δt=384Δt64个处理器并行处理，同时完成各自的个处理器并行处理，同时完成各自的64次浮点加运算，次浮点加运算，所以，全部运算所需时间为：所以，全部运算所需时间为：T3=384Δt加速比：加速比：S2=T1/T3=64(4)对于对于8×8的处理阵列，每个处理器需要处理的处理阵列，每个处理器需要处理64×64二维数组中的一个二维数组中的一个8×8子子数组，因此，每个处理器需要执行的浮点加法次数为数组，因此，每个处理器需要执行的浮点加法次数为8×8K=6段的浮点加段的浮点加法流水线处理法流水线处理64次浮点加运算需要时间次浮点加运算需要时间(k+n-1)Δt=(6+64-1)Δt=67Δt 64个个处理器并行处理，同时完成各自的处理器并行处理，同时完成各自的64次浮点加运算，所以，全部运算所需时次浮点加运算，所以，全部运算所需时间为：间为：T4=67Δt加速比：加速比：S2=T1/T4=366.8 (5) 对于对于64×64的处理阵列，每个处理器只需执行一次浮点加运的处理阵列，每个处理器只需执行一次浮点加运算，所需时间为算，所需时间为6Δt ，所以，全部运算所需时间为：，所以，全部运算所需时间为：T5=6Δt加速比：加速比：S2=T1/T5=4096 6.2 SIMD计算机的互连网络计算机的互连网络 6.2.1 互连网络的设计目标及互连函数互连网络的设计目标及互连函数 1.1.互联网络的设计目标互联网络的设计目标 a.采采取取让让相相邻邻的的处处理理单单元元之之间间只只用用有有限限的的几几种种直直连连方式实现任何两个处理单元之间所需要的信息传送。
方式实现任何两个处理单元之间所需要的信息传送 b.设设计计目目标标：：结结构构不不要要太太复复杂杂；；灵灵活活性性高高；；信信息息交交换换所所需需传传送送步步数数尽尽可可能能少少；；能能用用规规整整单单一一的的基基本构件组合而成，模块性好；本构件组合而成，模块性好； 2.互连函数互连函数 互连网络的连接特征一般用一组互连网络的连接特征一般用一组互连函数互连函数表示互连函数：出端编码是入端编码的排列、组合、移位、取反互连函数：出端编码是入端编码的排列、组合、移位、取反等操作的结果表示等操作的结果表示所有入端所有入端与出端的连接关系与出端的连接关系互连函数有互连函数有2 2种表示方法：种表示方法：(1)(1)输入输出对应表示法输入输出对应表示法互连互连 0 1 N-10 1 N-1函数函数 f f(0) (0) f f(1)(1) f f(N-1)(N-1)(2)(2)函数式表示法：函数式表示法： 入端编码表示：入端编码表示： x = bn-1…b0 n=log2N 出端编码表示：出端编码表示：f(x) = 基于基于bn-1…b0的操作的结果。
的操作的结果自变量和函数可以用二进制表示，也可以用十进制等表示自变量和函数可以用二进制表示，也可以用十进制等表示输入输入: 0 1 2 3 4 5 6 7: 0 1 2 3 4 5 6 7输出输出: 1 0 3 2 5 4 7 6: 1 0 3 2 5 4 7 6 6.26.2.2 .2 互联网络的应选择的几个问题互联网络的应选择的几个问题（（1 1）操作方式：有同步、异步、同异组合三种；）操作方式：有同步、异步、同异组合三种； （（2 2）控制策略：集中和分布两种；）控制策略：集中和分布两种； （（3 3）交换方法：有线路交换、包交换及线路与包交换组合三种交换方法：有线路交换、包交换及线路与包交换组合三种4 4）网络拓扑：）网络拓扑：互联网络入、出端可以实现连接的模式互联网络入、出端可以实现连接的模式有静有静态和动态两种；动态网络又有单级循环网络和多级互连网络两态和动态两种；动态网络又有单级循环网络和多级互连网络两类；类；6.2.3 基本的单级互连网络基本的单级互连网络 立方体、立方体、PM2I和混洗交换和蝶形单级网络和混洗交换和蝶形单级网络 三维立方体结构三维立方体结构 处理单元处理单元Z Y X三位二进制码编号三位二进制码编号 每个处理单元只能直接连到其每个处理单元只能直接连到其二进制编号的某一位取反二进制编号的某一位取反的其的其他他 3 个处理单元上。
个处理单元上1. 立方体单级网络立方体单级网络( (交换互连网络交换互连网络) ) 互连函数：互连函数： Cube Cube0 0 (b2b1b0)=(b=(b2 2b b1 1b b0 0) )；；CubeCube1 1(b2b1b0)=(b=(b2 2b b1 1b b0 0) ) CubeCube2 2(b2b1b0)=(b=(b2 2b b1 1b b0 0) ) 互连特性：互连特性： 交换功能交换功能----互连函数可逆；互连函数可逆； 互连函数个数互连函数个数= =loglog2 28=38=3；；最大连接度最大连接度=log=log2 28=38=3；； 结点最大间距结点最大间距=log=log2 28=38=3 互连函数：互连函数：Cubei函数表示相连的入端和出端的二进制编号只在函数表示相连的入端和出端的二进制编号只在右起第右起第i i位位(i=0, 1, 2)上有差别，即仅在该位上的代码上有差别，即仅在该位上的代码“0”、、“1”互反，其余各位代码都相同互反，其余各位代码都相同 立方体单级网络连接图立方体单级网络连接图 CubeCube0 0=(b=(b2 2b b1 1b b0 0) ) （（0 0，，1 1）（）（2 2，，3 3）（）（4 4，，5 5）（）（6 6，，7 7））CubeCube1 1=(b=(b2 2b b1 1b b0 0) ) （（0 0，，2 2）（）（1 1，，3 3）（）（4 4，，6 6）（）（5 5，，7 7））CubeCube2 2=(b=(b2 2b b1 1b b0 0) ) （（0 0，，4 4）（）（1 1，，5 5）（）（2 2，，6 6）（）（3 3，，7 7））其连接方式如下图中的其连接方式如下图中的实线实线所示。
所示100110注意：立方体坐标编号不能标错注意：立方体坐标编号不能标错 推广到推广到n维的情形，维的情形，N个节点的立方体单级网络共有个节点的立方体单级网络共有n=log2N种互连函数，种互连函数， 即即 式式中中，，0≤i≤n-1，，bi为为入入端端号号二二进进制制码码的的第第i位位当当维维数数n＞＞3时时，，称称为为超超立立方方体体(Hyper Cube)网网络络它它的的最最大大距距离离为为n n，，任任意意两个结点间有至少两个结点间有至少n n条路径，容错性较强条路径，容错性较强 PM2I单单级级网网络络是是“加加减减2i” 单单级级网网络络的的简简称称能能实实现现与与j号号处理单元直接相连的是号为处理单元直接相连的是号为j±2i的处理单元，的处理单元， 即即 2. PM2I单级网络单级网络 对于对于N=8的三维的三维PM2I互连网络的互连函数有互连网络的互连函数有PM2+0、、 PM2-0、、PM2+1、、PM2-1、、PM2±2等等 5 个不同的互连函数，它个不同的互连函数，它们分别为：们分别为：PM2+0: (0 1 2 3 4 5 6 7)PM2-0: (7 6 5 4 3 2 1 0)PM2+1: (0 2 4 6)(1 3 5 7)PM2-1: (6 4 2 0)(7 5 3 1)PM2±2: (0 4)(1 5)(2 6)(3 7) 式式中中，，0≤j≤N-1, 0≤i≤n-1, n=log2N。
因因此此，，它它共共有有2n个个互互连连函函数数由由于于总总存存在在PM2+(n-1)=PM2-(n-1)，，所所以以实实际际上上，，PM2I互互连网络只有连网络只有2n-1种不同的互连函数种不同的互连函数 PM2I互连网络的部分连接图互连网络的部分连接图 PM2I单单级级网网络络的的最最大大距距离离为为[n/2](向向上上取取整整)以以上上面面的的三三维维PM2I互互连连网网络络的的例例子子就就可可以以看看出出，，最最多多只只要要二二次次使使用用，，即即可可实实现现任任意意一对入、一对入、 出端号之间的连接出端号之间的连接 应用：应用：几种几种PM2IPM2I变换的组合，可实现某结变换的组合，可实现某结点到任意结点的连接，组合不同效率不同点到任意结点的连接，组合不同效率不同 例：例：闭合螺旋结构为闭合螺旋结构为PM2IPM2I±0±0( (横向横向) )及及PM2IPM2I±n/2±n/2( (纵向纵向) )互连函数互连函数 3. 混洗交换混洗交换互连互连网络网络 8 个处理单元的全混连接个处理单元的全混连接 这种互连网络由全混洗和交换两种互连函数组成：这种互连网络由全混洗和交换两种互连函数组成：全混全混Shuffle(bn-1bn-2...b1b0)=(bn-2...b1b0bn-1)相当于将处理单元的二进制地址位中的相当于将处理单元的二进制地址位中的最左位移到最右位最左位移到最右位的循的循环移位。
下图示出了有环移位下图示出了有8个个PE的全混洗连接的全混洗连接000001010011100101110111001010011100101110111000 由于全混洗互连网络不能实现全由于全混洗互连网络不能实现全0和全和全1单元与其他单元单元与其他单元的连接，因此引入交换网络中的的连接，因此引入交换网络中的Cube0交换互连函数，表达形交换互连函数，表达形式如下：式如下： Exchange(bn-1bn-2...b1b0)=bn-1bn-2...b1b0 两函数复合后为：两函数复合后为：Exchange[Shuffle(bn-1bn-2...b1b0)]=(bn-2...b1b0 bn-1)下图示出了这种混洗交换互连网络的连接图实线表示交换下图示出了这种混洗交换互连网络的连接图实线表示交换，虚线表示全混），虚线表示全混）N=8 时全混交换互连网络连接图时全混交换互连网络连接图 在混洗交换网络中，最大距离为在混洗交换网络中，最大距离为2n-1最远的两个最远的两个PE（全（全0和全和全1 ）连接需要）连接需要n次交换和次交换和n-1次混洗 4 4、蝶式置换、蝶式置换 ----编码最高位和最低位位交换位置编码最高位和最低位位交换位置 互连函数：互连函数：β(bβ(bn-1n-1b bn-2n-2…b b1 1b b0 0)=(b)=(b0 0b bn-2n-2…b b1 1b bn-1n-1) )；；000001010011100101110111N=8蝶式置换000001010011100101110111N=8 β(1)子蝶式置换000001010011100101110111000001010011100101110111 子蝶式置换：子蝶式置换： ββ(k)(k)(b(bn-1n-1…b bk+1k+1b bk kb bk-1k-1…b b0 0)=(b)=(bn-1n-1…b bk+1k+1b b0 0b bk-1k-1…b b1 1b bk k) ) β β(k)(k)( (b bn-1n-1…b bn-kn-kb bn-k-1n-k-1b bn-k-2n-k-2…b b0 0)=()=(b bn-k-1n-k-1b bn-2n-2…b bn-kn-kb bn-1n-1b bn-k-2n-k-2…b b0 0) ) 5 5、移数置换、移数置换 ----编码值移位编码值移位 互连函数：互连函数：α(X)=(X+k) mod Nα(X)=(X+k) mod N，，0≤k≤N-10≤k≤N-1；；000001010011100101110111k=1移数置换000001010011100101110111000001010011100101110111k=2移数置换000001010011100101110111 互连特性：互连特性：互连函数不可逆互连函数不可逆(k=0(k=0除外除外) )；； n n位编码有位编码有2 2n n个移数变换功能。
个移数变换功能 例例：编号为：编号为0、、1、、…15的的16个处理器用单级互连网络互连个处理器用单级互连网络互连，当互连函数分别为，当互连函数分别为:（（1））Cube3 （（2））PM2+3 （（3）） PM2+2（（ Cube1 ）） （（4））Shuffle(Cube2 (PM2-3)) 时，第时，第13号处理器各连至哪一号处理器各连至哪一个处理器？个处理器？解解：编号为：编号为0、、1、、..15的的16个处理器，所以可用个处理器，所以可用4位二进制码位二进制码b3 b2b1 b0 表示第13号处理器的二进制编号为号处理器的二进制编号为1101所以（（1）） Cube3（（1101））=0101，即连接到，即连接到5号处理器上号处理器上2））PM2+3 （（13+23））mod 16=5，即连接到，即连接到5号处理器上号处理器上3）） PM2+2( Cube1 (1101)) =3 ，即连接到，即连接到3号处理器上号处理器上4））Shuffle (Cube2 (PM2-3(13))) = Shuffle(Cube2 (0101)) = Shuffle（（0001））=0010，即连接到，即连接到2号处理器上。
号处理器上 6.2.4 基本的多级互连网络基本的多级互连网络 v交换开关交换开关 交换开关是组成互连网络的基本构件通常，它是二功能交换开关是组成互连网络的基本构件通常，它是二功能或四功能的二功能是直连或交换四功能就是在二功能基础或四功能的二功能是直连或交换四功能就是在二功能基础上在加上上播和下播上在加上上播和下播，，开关状态连接方式如下图所示；开关状态连接方式如下图所示； 决定多级互连网络的特性的主要因素有以下三个方面：决定多级互连网络的特性的主要因素有以下三个方面：交交换开关、拓扑结构和控制方式换开关、拓扑结构和控制方式 a. 直连直连——i入入连连i出出，， j入入连连j出出；；b. 交换交换——i入入连连j出出，， j入入连连i出出；；i入入 j入入i出出j出出i入入j入入i出出j出出 c.上播上播——i入入连连i出出和和j出出，， j入入悬空；悬空；d.下播下播——j入入连连i出出和和j出出，， i入入悬空v拓扑结构拓扑结构是指各级之间出端和入端相互连接的模式是指各级之间出端和入端相互连接的模式可将单级互连网络的那些连接模式进行不同的组合，构成多可将单级互连网络的那些连接模式进行不同的组合，构成多种不同的多级互连网络。
种不同的多级互连网络i入入j入入i出出j出出i入入i出出j入入j出出 控控制制方方式式是是对对各各个个交交换换开开关关进进行行控控制制的的方方式式，，以以多多级级立立方体网络为例，它可以有方体网络为例，它可以有 3 种：种： (1) 级级控控制制——同同一一级级的的所所有有开开关关只只用用一一个个控控制制信信号号控控制制，， 同时只能处于同一种状态；同时只能处于同一种状态； (2) 单单元元控控制制——每每一一个个开开关关都都有有自自己己独独立立的的控控制制信信号号控控制制，， 可各自处于不同的状态；可各自处于不同的状态； (3) 部部分分级级控控制制——对对不不同同的的级级采采用用不不同同数数量量的的控控制制信信号号第第i级级的的所所有有开开关关分分别别用用i+1个个信信号号控控制制，， 0≤i≤n-1, n为为级级数数是前面两种方式的折衷是前面两种方式的折衷 v控制方式控制方式 1. 1. 多级立方体网络多级立方体网络（（ STARANSTARAN和间接二进制和间接二进制n n方体网络方体网络 ））以以8 8个处理单元为例，其结构如下图所示。
个处理单元为例，其结构如下图所示 共同特点共同特点：第：第i i级交换单元处于交换状态时，实现的级交换单元处于交换状态时，实现的是是CubeCubei i互连函数，且都采用二功能交换单元互连函数，且都采用二功能交换单元区别：控制方式不同，区别：控制方式不同， STARANSTARAN网络采用级控制和部网络采用级控制和部分级控制，间接二进制分级控制，间接二进制n n方体网络采用单元控制方体网络采用单元控制 常用的多级互连网络有：常用的多级互连网络有：多级立方体网络、多多级立方体网络、多级混洗交换网络又称级混洗交换网络又称omegaomega网络网络和和多级多级PM2IPM2I网络网络 N=8 多级立方体互连网络多级立方体互连网络 Cube0Cube1Cube2 具具有有N个个入入端端和和N个个出出端端的的多多级级立立方方体体网网络络拓拓扑扑结结构构图图 的画法为：的画法为： 先求出该多级立方体网络的级数先求出该多级立方体网络的级数n，每级画，每级画N/2个二功能个二功能交换开关；级编号从输入到输出依次是：交换开关；级编号从输入到输出依次是：0,1,…i…n-1;让所有让所有第第i级各交换开关的两个出入端均按级各交换开关的两个出入端均按Cubei的关系配对编上号；的关系配对编上号；再将各级开关同一编号的端用线连上。
再将各级开关同一编号的端用线连上 STARANSTARAN网络用作交换网络时，采用级控制，实现的是交换网络用作交换网络时，采用级控制，实现的是交换函数所谓函数所谓交换交换(Flip)(Flip)函数函数，是将一组元素首尾对称地进行，是将一组元素首尾对称地进行交换如果一组元素包含有交换如果一组元素包含有2 2s s个，则它是将所有第个，则它是将所有第k k个元素都个元素都与第与第(2(2s s-(-(k k+1))+1))个元素相交换如下表个元素相交换如下表1 1列出级控信号采用各列出级控信号采用各种不同组合情况下种不同组合情况下3 3级交换网络所实现的入、出端的连接级交换网络所实现的入、出端的连接 K0控制控制Cube0K1控制控制Cube1K2控制控制Cube2Ki=0,直连直连Ki=1,交换交换表表 1三级三级STARAN交换交换网络实现网络实现的入出端的入出端连接及所连接及所执行的交执行的交换函数功换函数功能能(Ki为第为第I级控制级控制信号信号) (1)(1)交换功能的控制与实现交换功能的控制与实现 开关组合控制方式：开关组合控制方式：级控制。
级控制 (2)(2)移位功能的控制与实现移位功能的控制与实现 开关组合控制方式：开关组合控制方式：部分级控制部分级控制( (第第i i级有级有i+1i+1种控制信号种控制信号) ) Mod Mod的作用：的作用：不同不同ModMod可用于不同的分组操作可用于不同的分组操作3)(3)网络功能的应用网络功能的应用 交换功能很适合于双向互连交换功能很适合于双向互连( (对称对称) )要求的实现；要求的实现； 移数功能很适合于累加求和等要求的实现移数功能很适合于累加求和等要求的实现 例例1 1：：阵列有阵列有0~70~7共共8 8个处理单元，要求按（个处理单元，要求按（0 0，，5 5）、（）、（1 1，，4 4）、（）、（2 2，，7 7）、（）、（3 3，，6 6）配对通信配对通信 (1)(1)写出实现此功能的互连函数一般式写出实现此功能的互连函数一般式2 2）画出用三级立方体网络实现互联函数的网络拓扑结构图，）画出用三级立方体网络实现互联函数的网络拓扑结构图，标出各级交换开关状态标出各级交换开关状态解：解：f（（b2b1b0））= b2b1b0交换交换直连直连交换交换 例例2 2：：1616个个PEPE采用采用STARANSTARAN网络互连时，实现相当于网络互连时，实现相当于4 4组组4 4元交元交换，然后换，然后2 2组组8 8元交换，再元交换，再1 1组组1616元交换功能。
写出互连函数一般元交换功能写出互连函数一般式式, ,画出相应多级网络拓扑结构图，标出各级交换开关状态画出相应多级网络拓扑结构图，标出各级交换开关状态 答：答：因需实现交换功能，故选择因需实现交换功能，故选择STARANSTARAN的交换功能的交换功能( (级控制级控制方式） 4 4组组4 4元交换元交换 CubeCube0 0+Cube+Cube1 1 2 2组组8 8元交换元交换 CubeCube0 0+Cube+Cube1 1+Cube+Cube2 2 1 1组组1616元交换元交换 CubeCube0 0+Cube+Cube1 1+Cube+Cube2 2+Cube+Cube3 3 相加相加 CubeCube0 0+Cube+Cube1 1 +Cube+Cube3 3 互连函数：互连函数：f(bf(b3 3b b2 2b b1 1b b0 0)=(b)=(b3 3b b2 2b b1 1b b0 0) ) 各级开关状态：各级开关状态：k k3 3k k2 2k k1 1k k0 0=(1011)=(1011)由此得出第由此得出第0 0、、1 1、、3 3级开关状态为交换，第级开关状态为交换，第2 2级为直连级为直连 交换交换交换交换交换交换直连直连级级 k0 k1 k2 k30123456789ABCDEF0123456789ABCDEF ∵∵共有共有1616个结点，编码需要个结点，编码需要4 4位，位，∴∴开关共开关共4 4级。
级 例例3 3：：现有现有1616个个PE(PE(编号编号0~F)0~F)与网络连接，程序在某个时刻与网络连接，程序在某个时刻需实现下列通信配对：需实现下列通信配对：7←→D7←→D、、6←→C6←→C、、5←→F5←→F、、4←→E4←→E、、3←→93←→9、、2←→82←→8、、1←→B1←→B、、0←→A0←→A请画出互连网络结构图，请画出互连网络结构图，并写出控制方式及各开关状态并写出控制方式及各开关状态 答：答：因需实现双向交换功能，选择因需实现双向交换功能，选择STARANSTARAN网络的交换功能网络的交换功能( (级控制方式级控制方式) )可满足要求可满足要求 网络拓扑结构：网络拓扑结构： ∵∵共有共有1616个结点，编码需要个结点，编码需要4 4位，位，∴∴开关共开关共4 4级 配对要求：配对要求：(7,D),(6,C),(5,F),(4,E),(3,9),(2,8),(1,B),(0,A)(7,D),(6,C),(5,F),(4,E),(3,9),(2,8),(1,B),(0,A) 开关控制：开关控制： ∵≤ ∵≤7 7的结点的结点←→←→＞＞7 7的结点，的结点，∴∴需需1 1组组1616元交换元交换；； 注意：组内交换后结点次序已经镜像注意：组内交换后结点次序已经镜像 ∵0~3 ∵0~3的结点的结点←→←→8~B8~B的结点，的结点，∴∴需需2 2组组8 8元交换元交换；； ∵0~1 ∵0~1的结点的结点←→←→A~BA~B的结点，的结点，∴∴需需4 4组组4 4元交换元交换；； ∵0 ∵0结点结点←→←→A A结点配对，已经过结点配对，已经过3 3次镜像次镜像 ∴ ∴需需8 8组组2 2元交换元交换。
各级开关状态：各级开关状态：k k3 3k k2 2k k1 1k k0 0=(1010)=(1010) 1 1组组1616元交换元交换 CubeCube0 0+Cube+Cube1 1+Cube+Cube2 2+Cube+Cube3 3 2 2组组8 8元交换元交换 CubeCube0 0+Cube+Cube1 1+Cube+Cube2 2 4 4组组4 4元交换元交换 CubeCube0 0+Cube+Cube1 1 8 8组组2 2元交换元交换 CubeCube0 0 相加相加 CubeCube1 1+ Cube+ Cube3 3 级级 k0 k1 k2 k30123456789ABCDEF0123456789ABCDEF由此得出第由此得出第1 1、、3 3级开关状态为交换，第级开关状态为交换，第0 0、、2 2级为直通级为直通 交换开关：交换开关：四功能；四功能；拓扑结构：拓扑结构：多级多级ShuffleShuffle；；Omega网络中各级编号的次序与网络中各级编号的次序与多级立方体网络正好相反，多级立方体网络正好相反，把把Omega网络的入、出端对调，就网络的入、出端对调，就等于多级立方体网络。
等于多级立方体网络2.多级混洗交换网络多级混洗交换网络( omega网络网络) ABCDEFGHIJKL012345672级012345671级0级 开关组合控制：开关组合控制： 级控制、开关二功能级控制、开关二功能----STARANSTARAN交换网络的逆网络；交换网络的逆网络； 部分级控制、开关二功能部分级控制、开关二功能—STARANSTARAN移数网络的逆网络移数网络的逆网络; ; 单元控制、开关二、四功能单元控制、开关二、四功能----更强大的功能更强大的功能 网络关系：按全混方法网络关系：按全混方法ShuffleShuffle（（p pn-1 n-1 p pn-2 n-2 … p p0 0））= p= pn-2 n-2 … p p0 0 p pn-1n-1则有：则有： 入入 0 →0 0 →0 出出 入入 4→1 4→1 出出 1 →2 5→31 →2 5→3 2 →4 6→5 2 →4 6→5 3 →6 7→7 3 →6 7→7 混洗拓扑就是将编号为混洗拓扑就是将编号为0 0，，1 1….N-1.N-1的入端分成的入端分成前后个数相等的两半，前一半和后一半在连至前后个数相等的两半，前一半和后一半在连至输出时顺次一一相隔。
各级画好后，再将连线输出时顺次一一相隔各级画好后，再将连线沿途所经过的端号均标成同一端号即可沿途所经过的端号均标成同一端号即可 例：画出例：画出0—7号共号共8个处理器的三级混洗交换网络，在该图个处理器的三级混洗交换网络，在该图上标出实现将上标出实现将6号号处理器数据播送给处理器数据播送给0—4号，同时将号，同时将3号号处理处理器数据播送给器数据播送给其余其余3个处理器个处理器时的各有关交换开关的控制状态；时的各有关交换开关的控制状态； 3. 多级多级PM2I网络（数据交换网络）网络（数据交换网络） N=8三级三级PM2I网络网络 2jj+2i mod Nj-2i mod N 结构：结构：n级，每一级把前后各级，每一级把前后各N=2n个单元按个单元按PM2I拓扑互连接拓扑互连接对第对第i级，每一个单元级，每一个单元j（（0≦≦ j ≦≦N-1）都有）都有3根连线分别连到根连线分别连到出端单元出端单元j、、 j+2i mod N和和j-2i mod N，图中分别用不同的线，图中分别用不同的线段表示控制这三类连接线的信号分别为控制这三类连接线的信号分别为平控平控H、上控、上控D、下控、下控U。
若采用单元控制方式，每一级都有自己独立的控制信号若采用单元控制方式，每一级都有自己独立的控制信号H、、D、、U，称此，称此PM2I网络为网络为强化数据交换网络（强化数据交换网络（ADM）） 6.2.5 6.2.5 全排列网络全排列网络(1)(1)多级网络比较多级网络比较 灵活性灵活性( (低低→→高高) )：：STARANSTARAN、间接二进制、间接二进制n n方体、方体、 Omega(ω)Omega(ω)、、ADM(ADM(混洗四功能混洗四功能) ) 成本成本( (低低→→高高) )：：同上同上 用途：用途： STARANSTARAN、、Omega PE←→PMOmega PE←→PM 间接二进制间接二进制n n方体方体 PE--→PEPE--→PE 功能：功能：同时同时只能实现只能实现部分互连函数部分互连函数功能 (2)(2)全排列网络全排列网络 定义：定义：所有入端、出端的连接均不发生冲突的网络，又称所有入端、出端的连接均不发生冲突的网络，又称非阻塞型网络，即：非阻塞型网络，即：N N入入→→N N出出有有N N！种排列。
种排列 常规多级网络常规多级网络( (如如STARANSTARAN、、ωω等等) )属于阻塞型网络属于阻塞型网络 证明：证明：对对n=logn=log2 2N N级网络，开关数级网络，开关数=N/2×n=N/2×n排列数排列数回下页 DTRMUX循环循环单单级级/多多级级网网络络PE0来来去去PE0PEN-1来来去去PEN-1…DTRMUX(3)(3)全排列网络实现全排列网络实现 方法：方法：a.a.原有多级网络通过锁存器运行两次即可；原有多级网络通过锁存器运行两次即可；思想：思想：N!N!＜＜N NN/2N/2×N×NN/2N/2＜＜N NN N b. b.两个两个loglog2 2N N网络背靠背串联网络背靠背串联Benes网络网络 6.3 6.3 并行存储器无冲突访问并行存储器无冲突访问一、访问需求一、访问需求 并行存取向量中各分量信息；并行存取向量中各分量信息； 对矩阵可按行、列、对角线等方法访问对矩阵可按行、列、对角线等方法访问( (步长不一致步长不一致) )二、存在问题二、存在问题 存储器带宽限制存储器带宽限制—存储器带宽达不到向量带宽；存储器带宽达不到向量带宽； 访存方式访存方式( (步长步长) )不同，产生访存冲突。
不同，产生访存冲突 三、解决方法三、解决方法1 1、采用多体交叉存储器、采用多体交叉存储器 使存储体数超过使存储体数超过PEPE数，保证数，保证PEPE所需要的带宽所需要的带宽2 2、对向量分组操作、对向量分组操作 解决解决MEMMEM带宽小于向量长度问题，提高处理效率带宽小于向量长度问题，提高处理效率3 3、选择适当的存储体数、选择适当的存储体数m m 使存储体数使存储体数m≥PEm≥PE数，达到无冲突访问数，达到无冲突访问 （（1 1））一维向量：一维向量： 顺序存放，防止步长与顺序存放，防止步长与m m成比例；成比例； m m取质数取质数, ,与步长互质与步长互质 一维数组的存贮一维数组的存贮(m=4) 假设假设并行存贮器的分体数并行存贮器的分体数m=4，交叉存放一维向量，交叉存放一维向量a0..，如下左，如下左图所示a. 每次访问每次访问m个相连的元素，无冲突；个相连的元素，无冲突；b. 若跳跃式访问，步距为若跳跃式访问，步距为2：：a0,a2,a4,a6，有冲突；，有冲突； 步距为步距为4：：a0,a4,a8,a12，有冲突；，有冲突；c. 把存贮器的体数取成一个质数，只要变址步距与把存贮器的体数取成一个质数，只要变址步距与m互质，存贮互质，存贮器器总总能能无无冲冲突突访访问问；；（（如如下下例例所所示示，，只只要要变变址址步步长长不不是是5的的倍倍数数就可以实现无冲突访问。
就可以实现无冲突访问一维数组的存贮一维数组的存贮(m=5) 存贮器的体号存贮器的体号43210 如如果果设设m=n=4, 一一个个4×4 的的二二维维数数组组直直接接按按行行存存贮贮，，方方案案如如下下图图所所示示虽虽然然，，同同时时访访问问某某一一行行、、主主对对角角线线或或次次对对角角线线上上的的所所有有元元素素时时，，都都可可以以做做到到无无冲冲突突地地访访问问，，但但要要同同时时访访问问某某一一列列的的各各元元素素时时，，由由于于它它们们集集中中存存放放在在同同一一存存贮贮分分体体内内，，会会产产生生访访存存冲冲突突，，所所以以每每次次只只能能顺顺序序访访问问该该列列中中其其中中的的一一个个元元素素，，致致使使实际频宽降低成实际频宽降低成 1/4 4×4 数组的直接按行存贮数组的直接按行存贮(m=n=4) （（2）多维向量）多维向量冲突冲突 4×4 数组一种错位存放的方案数组一种错位存放的方案为了使行或列的各元素都能并行访问，若如下图所示的将为了使行或列的各元素都能并行访问，若如下图所示的将数据错位存放，但这样造成主对角线上各元素的并行访问冲突数据错位存放，但这样造成主对角线上各元素的并行访问冲突。
把存贮器的分体数把存贮器的分体数m m取成大于每次要访问的向量或数组的个数取成大于每次要访问的向量或数组的个数n n，，且等于质数，同时在多维数组的行、列等方向上采取不同的错开且等于质数，同时在多维数组的行、列等方向上采取不同的错开距离 错位存放，满足行、列、对角线等访问要求；错位存放，满足行、列、对角线等访问要求； 对矩阵而言对矩阵而言(m(m大于大于PEPE数时数时)--)-- 设设m=2m=22P2P+1+1，，δδ1 1=2=2P P，同一列不同行错开距离，同一列不同行错开距离 δ 2 2=1=1，同一行不同列错开距离，同一行不同列错开距离 对对A Aabab，体号：，体号： j=(a j=(a δ 1 1+b +b δ 2 2+C) mod m+C) mod m 体内序号：体内序号：i=a i=a C C为起始元素为起始元素A A0000所在体号地址所在体号地址4×4 数组错位存放的例子数组错位存放的例子(m=5, n=4, δ1=2, δ2=1) 4×5 二维数组在并行存贮器中存放的例子二维数组在并行存贮器中存放的例子(m=7, n=6) 让地址让地址ɑ所对应所对应的元素存放在的元素存放在体号地址体号地址j= ɑ mod m，，体内地址为体内地址为i= ɑ/n 的单元中的单元中，就可实现无，就可实现无冲突访问。
冲突访问 当向量元素不固定，或非当向量元素不固定，或非n×nn×n时时---- 将多维变换成一维数组将多维变换成一维数组S S，再对，再对S S进行处理进行处理 6.4 脉动阵列处理机和脉动阵列处理机和6.5 相联处理机（自己看）相联处理机（自己看）本章小结本章小结1阵列处理机的原理阵列处理机的原理 （（1）阵列机的分类及特点）阵列机的分类及特点（（2））ILLIAC Ⅳ的结构的结构2SIMD计算机的互连网络计算机的互连网络（（1）掌握各种互连函数，找出各处理单元的入出段连接掌握各种互连函数，找出各处理单元的入出段连接2）掌握多级网络拓扑结构图的画法）掌握多级网络拓扑结构图的画法（（3）根据要求标出各级开关的状态）根据要求标出各级开关的状态3并行存贮器的无冲突访问并行存贮器的无冲突访问 多维数组无冲突访问的条件以及各元素存放的具体位置多维数组无冲突访问的条件以及各元素存放的具体位置。