CN102053816A

CN102053816A - 具有开关矩阵存储器的数据混洗单元及其混洗方法

Info

Publication number: CN102053816A
Application number: CN2010105592888A
Authority: CN
Inventors: 陈书明; 刘胜; 万江华; 陈海燕; 陈跃跃; 孙永节; 彭元喜; 杨惠; 刘祥远; 李振涛
Original assignee: National University of Defense Technology
Current assignee: National University of Defense Technology
Priority date: 2010-11-25
Filing date: 2010-11-25
Publication date: 2011-05-11
Anticipated expiration: 2030-11-25
Also published as: CN102053816B

Abstract

本发明公开了一种具有开关矩阵存储器的数据混洗单元，包括交叉开关、输入逻辑单元、输出逻辑单元、主控逻辑单元以及开关矩阵存储器，主控逻辑单元与所述输入逻辑单元相连，开关矩阵存储器的输出端与所述交叉开关的开关选择信号端相连。以及一种上述的数据混洗单元的混洗方法，在预处理时将用户程序中的混洗请求转化为开关矩阵存储器中的开关矩阵，执行混洗指令时，主控逻辑单元控制从开关矩阵存储器读出所需要的混洗模式对应的开关矩阵，进而直接控制交叉开关进行数据选择和重组。本发明具有结构简单、混洗灵活高效、关键电路延时短且可适用于任意混洗操作的特点。

Description

具有开关矩阵存储器的数据混洗单元及其混洗方法

技术领域

本发明涉及SIMD技术的数字信号处理器领域，尤其涉及一种数据混洗单元及其混洗方法。

背景技术

SIMD（单指令流多数据流，Single Instruction stream Multiple Data streams）技术一般包括子字并行技术和向量技术，两者分别从微观和宏观两个方向开发应用程序的数据级并行性。SIMD技术能够在执行一条指令的情况下处理多个并行的数据，其高功效性在解决运算密集型的应用中具有很大的优势，因而得到了广泛的应用和发展，受到了处理器尤其是DSP（数字信号处理器，Digital Signal Processor）的青睐。图1为典型的采用SIMD技术的DSP结构示意图，由图1可见，取指及译码单元从程序存储器中读取指令并进行译码，派发到地址产生单元、向量运算单元和数据混洗单元当中。其中地址产生单元根据指令在向量数据存储器和向量寄存器之间传递数据。向量运算单元根据指令从向量寄存器中读取源操作数，进行相应的运算再写入到向量寄存器中。将每一簇的向量运算单元和向量寄存器合并称之为PE（处理单元，Process Element），图1中PE_0, PE_1,…, PE_N-1表示共有N个PE。数据混洗单元是独立于向量运算单元的，主要负责PE间寄存器的数据交互，在基于SIMD技术的DSP当中作用非常关键。

在执行数据混洗指令时，由每个向量寄存器提供一个数据组成源操作数向量，经过数据混洗单元重新排布后，再写入到各个向量寄存器中。这样各个向量单元之间就通过数据混洗单元完成了数据交互。这在一些嵌入式应用的核心算法（如快速傅里叶变换、Viterbi解码等）中的作用非常关键。嵌入式实时应用程序既需要DSP提供丰富的混洗模式支持，又具有较强的数据实时性要求，因而必须设计一种高效灵活的数据混洗方案。

如图2所示，传统的混洗单元通常包含混洗网络（以交叉开关（Crossbar）为主）、译码逻辑、混洗模式寄存器及其它辅助的控制逻辑，如摩托罗拉公司的采用AltiVec指令集的处理器的混洗单元或飞利浦公司的EVP处理器中的混洗单元。这种结构需要用户提前对混洗模式寄存器进行配置，在执行混洗指令时，硬件首先对混洗模式寄存器中混洗模式进行译码，译码之后的逻辑再驱动交叉开关对输入的向量进行选择和重组，从而完成混洗。如图3所示，传统的混洗单元中的典型的混洗操作指令为Shuffle VR2，VR3，该指令中的VR2表示待混洗的源操作数来自于每个向量寄存器的2号寄存器，即如图1中PE_0， PE_1, …PE_N-1的2号寄存器组成了待混洗的数据，如图3所示，设该数据为abcdefgh；该指令中的VR3表示从交叉开关输出的已经重排布的数据需要写入到每个向量寄存器的3号寄存器中。混洗指令希望将abcdefgh混洗为efghcdab，则用户需要在执行混洗操作之前将混洗模式寄存器填充为0_10_0_11_0_01_0_00（本示例向量宽度较窄，导致混洗模式寄存器的宽度也比较窄，实际的向量处理器混洗模式寄存器一般在几十位到几百位之间）。在传统的数据混洗指令执行时，默认使用混洗模式寄存器，并且需要将混洗模式中的寄存器进行译码，如图3所示需要将混洗模式寄存器中的数值0_10_0_11_0_01_0_00译码为0010_0001_0100_1000才能驱动交叉开关的每一个开关进行数据重排布。

由以上分析可见，传统的混洗方案需要用户在程序中提前配置混洗模式寄存器，同时在执行混洗指令时需要对混洗模式寄存器中的数值进行译码。这种方案存在两个问题：1.用户配置混洗模式寄存器的过程较为不便。如果通过控制寄存器配置总线配置混洗模式寄存器则需要花费比较多的节拍数（混洗模式寄存器通常有几十到几百位，而配置总线的宽度通常只有32位）；如果通过访存指令将混洗模式从片内存储器加载到混洗模式寄存器中，也需要花费一定的节拍数，并且由于该配置过程和普通的访存请求竞争存储带宽资源，将会影响应用程序的访存效率；2. 混洗模式需经译码后再进入交叉开关。传统的混洗单元需要首先对混洗模式寄存器中的混洗模式进行译码，形成了控制交叉开关每一个节点开关导通或断开的01值，然后这些译码之后的01值再驱动交叉开关进行数据选择，这一过程的关键路径延时较大，不利于混洗单元的高频或可扩展性设计。

从目前公开的文献来看，关于混洗网络本身的改进、简化研究较多，还没有专门的文献设计到改进混洗模式的配置过程这一问题。

发明内容

本发明所要解决的技术问题是：针对现有技术存在的不足，提供一种结构简单、混洗灵活高效、关键电路延时短，且可适用于任意混洗操作的具有开关矩阵存储器的数据混洗单元及其混洗方法。

为解决上述技术问题，本发明采用以下技术方案：

一种具有开关矩阵存储器的数据混洗单元，包括交叉开关、控制所述交叉开关从向量寄存器输入数据的输入逻辑单元、以及控制所述交叉开关输出数据到向量寄存器的输出逻辑单元，其特征在于：所述数据混洗单元还包括与向量寄存器相连的用于控制转化混洗请求和执行混洗操作的主控逻辑单元，以及与主控逻辑单元相连的用于存储混洗请求转化结果的开关矩阵存储器，所述主控逻辑单元与所述输入逻辑单元相连并控制待混洗的源操作数向量从输入逻辑单元输入到所述交叉开关中，所述交叉开关由位于其开关选择信号端的开关矩阵存储器控制对所述源操作数向量进行混洗，混洗结果由输出逻辑单元输出到向量寄存器。

作为上述数据混洗单元的进一步改进：

所述主控逻辑单元包括用于将混洗请求转化为开关矩阵并写入开关矩阵存储器的自举态模块，以及用于根据混洗指令读取开关矩阵存储器以控制交叉开关执行混洗操作的执行态模块。

本发明还提供一种具有开关矩阵存储器的数据混洗单元的混洗方法，其特征在于包括以下步骤：

1）预处理：在交叉开关的开关选择信号端设置开关矩阵存储器，将用户程序中的混洗请求转化为开关矩阵存储器中的开关矩阵；

2）执行混洗：从向量寄存器读取待混洗的源操作数向量分配到交叉开关的输入端口上，从开关矩阵存储器中读取需要的开关矩阵，输出到交叉开关的开关选择信号端以控制交叉开关对输入的源操作数向量进行选择和重组操作后，将操作结果输出到向量寄存器，完成混洗。

作为上述混洗方法的进一步改进，所述预处理具体包括以下步骤：

1.1）将用户程序中的当前的混洗操作请求的需要的开关矩阵与开关矩阵表中的开关矩阵进行匹配，所述开关矩阵表存储在开关矩阵存储器中，如果能够匹配，则转入1.2），否则转入1.3）；

1.2）根据匹配的开关矩阵在开关矩阵表中的位置更新当前混洗操作的表达方式，转入1.4）；

1.3）在开关矩阵表中增加一个新的开关矩阵，转入1.2）；

1.4）判断当前混洗操作是否为最后一个混洗操作，如果不是则转入1.5），否则转入1.6）；

1.5）处理下一个混洗操作，转入1.1）；

1.6）完成预处理，结束当前操作。

所述混洗指令为Shuffle Addr_i, VR_j, VR_k，其中Addr_i为混洗操作对应的开关矩阵在开关矩阵存储器中的地址，VR_j为混洗操作的源操作数信息，VR_k为混洗操作的目的操作数信息。

与现有技术相比，本发明的优点在于：

1、本发明的具有开关矩阵存储器的数据混洗单元，采用主控逻辑单元与开关矩阵存储器，结构简单，在程序进行预处理时，将一个应用程序所需要的所有混洗模式译码之后的逻辑值存放在开关矩阵存储器中，可以节约用户进行配置的时间，使混洗更加灵活高效。从开关矩阵存储器读出的内容无需译码可以直接驱动交叉开关进行数据选择，硬件电路更加简单、并可以减少关键电路的延时，有利于混洗单元的高频或可扩展性设计。

2、本发明的具有开关矩阵存储器的数据混洗单元的混洗方法，在预处理（自举态）时将将用户程序中的混洗请求转化为开关矩阵存储器中的数值，引入带开关矩阵存储器地址的混洗指令，使用户在程序执行当中不需要输入配置模式从而能够更加灵活高效地实现数据混洗；在执行每一条混洗指令时，由主控逻辑单元控制从开关矩阵存储器读出所需要的混洗模式对应的开关矩阵，进而直接控制交叉开关进行数据选择；采用本混洗方法可减少了应用程序的代码长度，使混洗单元应用更方便。这种方式也为改进混洗模式的配置过程提供了新的思路。

附图说明

图1是典型的采用SIMD技术的DSP的总体结构示意图；

图2是传统的采用混洗模式寄存器的混洗单元结构示意图；

图3是传统的混洗单元中的典型的混洗指令及其执行示意图；

图4是本发明具体实施例的具有开关矩阵存储器的混洗单元的结构示意图；

图5是本发明具体实施例的混洗指令及其执行示意图；

图6是本发明具体实施例的混洗操作预处理的处理流程示意图。

具体实施方式

以下将结合说明书附图和具体实施例对本发明作进一步详细说明。

如图4所示，本发明的具有开关矩阵存储器的数据混洗单元，包括交叉开关、控制交叉开关从向量寄存器输入数据的输入逻辑单元、以及控制交叉开关输出数据到向量寄存器的输出逻辑单元，数据混洗单元还包括与向量寄存器相连的用于控制转化混洗请求和执行混洗操作的主控逻辑单元，以及与主控逻辑单元相连的用于存储混洗请求转化结果的开关矩阵存储器，主控逻辑单元与输入逻辑单元相连并控制待混洗的源操作数向量从输入逻辑单元输入到交叉开关中，交叉开关由位于其开关选择信号端的开关矩阵存储器控制对源操作数向量进行混洗，混洗结果由输出逻辑单元输出到向量寄存器。

本实施例中，主控逻辑单元包括用于将混洗请求转化为开关矩阵并写入开关矩阵存储器的自举态模块，以及用于根据混洗指令读取开关矩阵存储器以控制交叉开关执行混洗操作的执行态模块。开关矩阵存储器由SRAM（单端口的静态随机访问存储器，Static Random Access Memory）组成，其深度由用户程序的混洗模式数目所决定，本实施例中，SRAM深度选择为64，SRAM的宽度等于SIMD通路包含的最小混洗粒度的数目的平方，即w²/g²。其中w为SIMD通路的宽度（单位：bits），g为混洗的最小粒度（单位：bits），且w为g的2的整数次幂。本实施例中，交叉开关的规模为交叉开关的规模为N*N（其中N=w/g），且每个端口的宽度为g bits。

如图6所示，上述的具有开关矩阵存储器的数据混洗单元的混洗方法，包括以下步骤：

1.预处理：

1.1 将用户程序中的当前的混洗操作请求的需要的开关矩阵（开关矩阵即控制交叉开关每一个节点开关导通或断开的01值组成的矩阵）与开关矩阵表中的开关矩阵进行匹配，开关矩阵表存储在开关矩阵存储器中，如果能够匹配，则转入1.2，否则转入1.3；

1.2 根据匹配的开关矩阵在开关矩阵表中的位置更新当前混洗操作的表达方式，转入1.4；

1.3在开关矩阵表中增加一个新的开关矩阵，转入1.2；

1.4判断当前混洗操作是否为最后一个混洗操作，如果不是则转入1.5，否则转入1.6；

1.5处理下一个混洗操作，转入1.1；

1.6完成预处理，结束当前操作。

2. 执行混洗指令：从向量寄存器读取待混洗的源操作数向量分配到交叉开关的输入端口上，从开关矩阵存储器中读取需要的开关矩阵，输出到交叉开关的开关选择信号端以控制交叉开关对输入的源操作数向量进行选择和重组操作后，将操作结果输出到向量寄存器，完成混洗。

上述完成混洗操作的步骤中，从开关矩阵存储器读出开关矩阵和程序的访存指令读写向量存储器是两个完全独立、无干扰的过程。

本实施例中，混洗指令为Shuffle Addr_i, VR_j, VR_k，其中Addr_i为混洗操作对应的开关矩阵在开关矩阵存储器中的地址，用来指示当前的混洗指令的混洗模式存放在开关矩阵存储器的起始位置。VR_j为混洗操作的源操作数信息（由每个PE的VR_j寄存器组成源操作数向量），VR_k为混洗操作的目的操作数信息（经过混洗之后的向量分别写入到每个PE的VR_k寄存器中）。如图5所示，图中的混洗指令为Shuffle #3,VR2,VR3，该指令中的VR2和VR3和图3中的指令的VR2、VR3意义相同，该指令中的#3表示该条混洗指令对应的开关矩阵在开关矩阵存储器的3号位置，如图5所示，在开关矩阵存储器的第3行存储的是0010_0001_0100_1000。在执行该条混洗指令之前，用户不需要在程序的执行当中配置混洗模式寄存器（开关矩阵存储器中的数据已在程序预处理时加载完毕）。此外由于从开关矩阵存储器读出的开关矩阵可以直接驱动交叉开关将abcdefgh重排为efghcdab，减少了复杂的译码逻辑，降低了关键路径延时。

综上所述，本发明的具有开关矩阵存储器的数据混洗单元，采用开关矩阵存储器取代了传统的混洗模式寄存器，使混洗操作的执行更加高效，同时也能够使整个混洗过程的关键路径延时变得较短，因而适用于采用SIMD技术的DSP，同时其它的面向视频和多媒体应用的采用SIMD技术的处理器均可采用。

以上所述仅是本发明的优选实施方式，本发明的保护范围并不仅局限于上述实施例，凡属于本发明思路下的技术方案均属于本发明的保护范围。应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明原理前提下的若干改进和润饰，应视为本发明的保护范围。

Claims

1.一种具有开关矩阵存储器的数据混洗单元，包括交叉开关、控制所述交叉开关从向量寄存器输入数据的输入逻辑单元、以及控制所述交叉开关输出数据到向量寄存器的输出逻辑单元，其特征在于：所述数据混洗单元还包括与向量寄存器相连的用于控制转化混洗请求和执行混洗操作的主控逻辑单元，以及与主控逻辑单元相连的用于存储混洗请求转化结果的开关矩阵存储器，所述主控逻辑单元与所述输入逻辑单元相连并控制待混洗的源操作数向量从输入逻辑单元输入到所述交叉开关中，所述交叉开关由位于其开关选择信号端的开关矩阵存储器控制对所述源操作数向量进行混洗，混洗结果由输出逻辑单元输出到向量寄存器。

2.根据权利要求1所述的具有开关矩阵存储器的数据混洗单元，其特征在于：所述主控逻辑单元包括用于将混洗请求转化为开关矩阵并写入开关矩阵存储器的自举态模块，以及用于根据混洗指令读取开关矩阵存储器以控制交叉开关执行混洗操作的执行态模块。

3.一种具有开关矩阵存储器的数据混洗单元的混洗方法，其特征在于包括以下步骤：

4.根据权利要求3所述的具有开关矩阵存储器的数据混洗单元的混洗方法，其特征在于：所述预处理具体包括以下步骤：

1.3）在开关矩阵表中增加一个新的开关矩阵，转入1.2）；

1.5）处理下一个混洗操作，转入1.1）；

1.6）完成预处理，结束当前操作。

5.根据权利要求3或4所述的具有开关矩阵存储器的数据混洗单元的混洗方法，其特征在于：所述混洗指令为Shuffle Addr_i, VR_j, VR_k，其中Addr_i为混洗操作对应的开关矩阵在开关矩阵存储器中的地址，VR_j为混洗操作的源操作数信息，VR_k为混洗操作的目的操作数信息。