CN102508803A

CN102508803A - 一种矩阵转置存储控制器

Info

Publication number: CN102508803A
Application number: CN2011103936607A
Authority: CN
Inventors: 李丽; 潘红兵; 郑艳丽; 王佳文; 沙金; 何书专; 郑维山
Original assignee: Nanjing University
Current assignee: Nanjing University
Priority date: 2011-12-02
Filing date: 2011-12-02
Publication date: 2012-06-20

Abstract

本发明公开了一种矩阵转置存储控制器，该矩阵转置存储控制器包括处理器、总线、直接内存存取、网络接口、存储单元、中断和程序存储器；处理器通过总线与直接内存存取、网络接口，中断、程序存储器进行数据传输；存储单元通过直接内存存取与总线及网络接口连接；网络接口与总线连接，并通过片上网络与外部存储器连接。本发明选择SRAM作为存储器，控制简单，读写操作容易，在处理器的控制下，能充分发挥SRAM作为存储器的优势。本发明提供了三种转置模式；使用处理器控制完成矩阵转置，能灵活地选择转置方法，适用于对各种大小的矩阵进行转置，并具有很好的扩展性。同时，本发明使用DMA作为数据通道，可提供高速的数据传输速率。本发明适用于片上网络中。

Description

一种矩阵转置存储控制器

技术领域

本发明涉及一种应用于矩阵转置的转置存储控制器，尤其是一种适合对多种尺寸的矩阵，采用软硬件协同设计的方法能灵活选择转置算法进行矩阵转置的转置存储控制器；具体地说，是一种适用于片上网络的矩阵转置存储控制器。

背景技术

矩阵数据结构常用工程计算、图像和信号处理等各种领域，常常涉及到矩阵转置这种数据处理过程。而矩阵转置的速度对数据处理效率有很大的影响。

对于大规模矩阵转置，如果直接将矩阵读入高速缓存中，必须频繁访问外部存储器，这样会极大降低转置效率。所以一般采用硬件来完成矩阵转置。

使用SDRAM做存储器的时候，由于SDRAM的列读写速率很低，这导致每次访问内存都消耗大量的时间。而使用SRAM集成规模小、价格高。如何正确的选择存储器并且使它们能高效的完成矩阵转置是矩阵转置常见的一个问题。

目前，实现矩阵转置主要使用可编程逻辑器件控制存储单元实现转置存储，或者采用微控制器控制实现转置存储；前者实现转置控制较为复杂，而后者数据传输速率往往较低。合理的利用这两种方法共同完成矩阵转置，可以很好地融合两种方法的优点。同时，目前实现矩阵转置，主要是在确定了矩阵大小和存储器大小后，再合理地选择转置方法，所以这些矩阵转置控制器是对固定大小的矩阵来实现矩阵转置的，而不能对多种尺寸的矩阵灵活的选择转置算法来实现矩阵转置。

片上网络（Network-on-chip，NoC）是片上系统的一种设计方法。基于NoC的系统能很好地适应在现在复杂片上系统设计中常使用的是全局异步局部同步的时钟机制。NoC方法带来了一种全新的片上通信方法，显著改善了传统总线式系统的性能。它被认为是未来集成工艺下多核技术发展的必然方向。

发明内容

本发明的目的是提供一种矩阵转置存储控制器，该矩阵转置存储控制器采用软硬件协同的方法，能对多种尺寸的矩阵，灵活的选择转置方法进行转置，并且能提供高速的数据传输速率。

本发明的目的是通过以下技术方案来实现的：

一种矩阵转置存储控制器，其特征在于：该矩阵转置存储控制器包括处理器、总线、直接内存存取（DMA）、网络接口(NI)、存储单元（SRAM）、中断和程序存储器；处理器通过总线与直接内存存取、网络接口，中断、程序存储器进行数据传输；存储单元通过直接内存存取与总线及网络接口连接；网络接口与总线连接，并通过片上网络与外部存储器连接。

本发明中，控制器数据的传输有数据输入与数据输出两种过程，它们是在处理器的控制下进行的；数据输入时，在处理器的控制下，DMA完成对数据地址的配置，NI在处理器的控制下，从外部存储器读取数据，根据DMA产生的地址，将数据存入SRAM；数据读入SRAM后，处理器配置DMA，产生地址，将数据从SRAM读出，完成对读入矩阵的转置，然后将数据通过NI输出。

矩阵转置由矩阵大小与存储单元的存储空间大小的关系决定，分三种模式，分别为：

1）SRAM可以存储一个矩阵所有的数据；转置控制器将数据读入，处理器配置DMA，按照行方向将矩阵存入SRAM，然后按照列方向，将矩阵读出，完成矩阵的转置；

2）矩阵的数据大于SRAM的存储空间；转置控制器按照矩阵行数据方向读满SRAM，接着配置外部存储器的地址，按列方向，将读入的数据依次输出到外部存储器对应的地址；然后读取原始矩阵下一部分数据到SRAM，并且输出到外部存储器对应的地址中；重复以上过程，直到矩阵所有的数据输出，完成矩阵的转置；

3）矩阵的数据远大于SRAM的存储空间；可以将矩阵分块，每块矩阵的大小正好等于SRAM的存储空间大小；分行将块矩阵的数据全部读入到SRAM 中；与第二种转置模式相同，转置控制器按列方向输出SRAM数据到外部存储器中；接着读取第二块矩阵，将数据按行方向写入SRAM，按列方向读出，输出到外部存储器中；重复以上过程，直到矩阵所有的数据输出，完成矩阵的转置。

以上对矩阵的转置有三种算法，对转置算法的选择，是由处理器控制DMA完成选择的。处理器配置的主要内容包括：矩阵行数，矩阵列数，矩阵转置算法选择。

转置模式3）中，需要确定分块矩阵的行数H和列数P。它们是由数据输入时建立数据通道所用时间T1，与数据输出建立数据通道所用时间T2决定的。矩阵转置建立数据通道所用总时间为H*T1+P*T2，由于H*P是固定的，等于SRAM的存储空间，所以利用不等式

Figure 2011103936607100002DEST_PATH_IMAGE001

可以计算得出H与P的值。

本发明是一种使用SRAM作为存储器，使用微控制器与可编程逻辑器件共同实现的转置存储。选择SRAM作为存储器，控制简单，读写操作容易，不存在列读写速度比行读写速度慢的问题，在处理器的控制下，能充分发挥SRAM作为存储器的优势。本发明使用处理器控制完成矩阵转置，所以能灵活的选择转置方法，适用于对各种大小的矩阵进行转置，并且具有很好的扩展性。同时，本发明使用DMA作为数据通道，能提供高速的数据传输速率。

本发明可以通过网络接口挂接在片上网络路由器上，如图1所示。通过片上网络与外部存储器建立数据通道，进行数据传输。本发明是一种适用于片上网络的矩阵转置存储控制器。

附图说明

图1是本发明挂接在片上网络结构上的示意图；

图2是本发明的结构示意图；

图3是本发明转置存储控制器的数据流图；

图4是转置功能实现图；

图5是转置算法一原理图；

图6是转置算法二原理图；

图7是转置算法二的数据输出流程图；

图8是转置算法三原理图。

具体实施方式

下面结合附图和实施例对本发明作进一步说明。

一种适用于片上网络的矩阵转置存储控制器，如图2所示，该矩阵转置存储控制器包括处理器1，总线2，直接内存存取(DMA)3，网络接口(NI)4，SRAM5，中断6，程序存储器7；该转置控制器采用总线结构，嵌入式处理器1通过总线协议与DMA 3、NI 4，中断6，程序存储器7等功能模块进行通讯；其中SRAM 5通过DMA 3与其他模块相连；NI 4在连接到总线2的同时，一端直接与DMA 3相连，另一端与外部存储器连接。该转置存储控制器使用ARM核作为处理器，选用AHB总线协议。

图3是本发明转置存储控制器的数据流图；数据的传输有数据输入与数据输出两种过程，它们是在处理器的控制下进行的。数据输入的时候，在ARM核的控制下，DMA完成对数据地址的配置，NI模块在ARM的配置控制下，从外部存储器读取数据，根据DMA产生的地址，将数据存入SRAM；数据读入SRAM以后，ARM核配置DMA，产生地址，将数据从SRAM读出，完成对读入矩阵的转置，然后将数据通过NI输出。

通过对数据流的介绍，可以看出矩阵的转置主要是，在处理器的控制下，DMA产生地址，实现对SRAM地址的控制，完成矩阵的转置，图4是该转置功能实现图。数据输入时，DMA产生地址，将数据存入相应SRAM相应的地址中。这个过程中，SRAM的地址是从地址0开始依次累加。数据输出的时候，由ARM控制DMA产生地址，从SRAM中读取相应的数据，完成矩阵的转置。所以，矩阵转置的控制主要是在数据输出时，由DMA产生的地址控制的。

矩阵转置分三种模式，是由矩阵大小与SRAM的存储空间大小的关系决定的，选择SRAM大小为64Mbit，每个数据为64bit，这样SRAM可以存储1M数据，矩阵的行数为C，列数为R。矩阵转置分三种模式，是由矩阵大小决定的，分别为：

1）SRAM可以存储一个矩阵所有的数据：4K*256 = 1M；

如图5所示，C=4K，R=256，一个矩阵可以完全读入。转置控制器将数据读入后，处理器配置DMA，按照行方向将矩阵存入SRAM，这时候按照列方向，将矩阵读出，完成了对矩阵的转置。

2）矩阵的数据大于SRAM的存储空间：4K*1K=4M>1M，C=4K，R=1K；此时，转置控制器需要多次从外部存储器读取数据，多次输出，才能完成转置。如图6所示，下面具体介绍该怎样完成矩阵转置。

a，SRAM可以存储1M个数据，因此首先只能顺次读取矩阵1M个数据。矩阵的列数为R=1K，读满SRAM需要N行数据，R*N=M。即首先读入N=1K行数据到SRAM。

b，转置控制器将SRAM中第一列数据输出到外部存储器中。配置外部存储的地址是从A开始存储，顺序存储N=1K个数据。接着，控制器重新配置给外部存储器地址，输出SRAM中第二列N个数据到外部存储器中。这时，外部存储器的地址要从A加上原矩阵列数开始，即A+R，依次加一，存储该列数据。

c，后面的数据也进行以上传输，重复R=1K次后，转置控制器将SRAM中的数据全部输出到外部存储器中。数据输出的流程如图7所示。

d，接着，转置控制器从原始矩阵按照行方向读取第二组数据，也就是原始矩阵的第N+1行到第2N行之间的数据，将SRAM写满。数据读入以后，开始重复以上数据输出过程，将数据输出到外部存储器。其中，每列数据存储到外部存储器时，地址紧接着上次输出数据的该列的最后一个数据开始。直到数据全部输出。

e，重复以上过程，直到矩阵所有的数据输出，完成矩阵的转置。

3）矩阵的数据远大于SRAM的存储空间：4K*8K >>1M，C=4K，R=8K；矩阵过大的时候，尤其是矩阵的列数R过大时，多次访问外部存储器建立数据通道，会消耗大量的时间。所以，转置控制器可以将矩阵分块，完成矩阵转置。

如图8所示，下面具体介绍该转置算法。

a，将矩阵分块，每块矩阵的大小正好等于SRAM的存储空间大小，分块矩阵行数为N，列数为P，N*P=M。分块矩阵的行数H和列数P的计算方法会在下面介绍。

b，分行将块矩阵的数据读入到SRAM中。转置控制器首先读取第一行从d(0,0)到d(0,P-1)的P个数据，然后再读取第二行的d(1,0)到d(1,,P-1)的P个数据……直到第N行数据，写满SRAM。

c，与第二种转置模式相同，转置控制器按列方向输出SRAM中的数据到外部存储器中。

d，接着读取第二块矩阵，从每列的第P+1个数据开始，直到第2P个数据。

第一行是从d(0,P)到d(0,2P-1)，第二行从d(1,P)到d(1,2P-1)……直到第N行从d(N-1,P)到d(N-1,2P-1)。重复以上过程，将数据按行方向写入SRAM。数据输出也与上面相同，每列数据在外部存储器中的地址都是承接前一组进行的。

在第三种转置算法中，需要计算分块矩阵的行数和列数。它们是由数据输入时建立数据通道所用时间T₁，与数据输出时建立数据通道所用时间T₂决定的。分块矩阵从外部存储器读取每行数据时，都需要建立数据通道，输出每列数据时也要建立数据通道，每个分块矩阵所以矩阵转置建立数据通道所用总时间为H*T₁+P*T₂。最合适的H和P是使得H*T₁+P*T₂最小的解。由于H*P=1M，是固定的，所以利用不等式

可以计算得出H与P的值，可以取整得到最合适的结果。取T₁=700个时间周期，T₂=400个时间周期为例，得到H=1K，P=1K。

以上共介绍了三种矩阵转置算法。在选择转置算法时根据矩阵的大小，正确的选择转置算法进行转置。本发明中对转置算法的选择，是由处理器控制DMA完成选择的。处理器配置的主要内容包括：矩阵行数，矩阵列数，以及矩阵转置算法选择。DMA根据处理器配置的算法选择，对矩阵给出正确的转置方法。

下面计算三种情况下，转置所用的时间。

(1)4K*256矩阵，转置时间包括一次读数据建立数据通道，一次写数据建立数据通道，以及输入输出数据所用时间，所以需要的时钟周期为：

N1=2M+700+400

(2) 4K*1K矩阵，转置控制器需要往SRAM输入输出数据八次。每次过程，消耗的时间包括一次读数据建立数据通道，1K次写数据建立数据通道，以及输入输出数据，所以需要的时钟周期为：

N2=(2M+700+400*1K)*4

(3)4K*8K矩阵，转置控制器需要向SRAM输入输出数据32次。每次过程，消耗的时间包括1K读数据建立数据通道，1K次写数据建立数据通道，以及输入输出数据，所以需要的时钟周期为：

N3=(2M+700*1K+400*1K)*32

本发明通过网络接口挂接在片上网络路由器上，通过片上网络与外部存储器建立数据通道，进行数据传输。

Claims

1.一种矩阵转置存储控制器，其特征在于：该矩阵转置存储控制器包括处理器(1)、总线(2)、直接内存存取(3)、网络接口(4)、存储单元(5)、中断(6)和程序存储器(7)；处理器(1)通过总线(2)与直接内存存取(3)、网络接口(4)，中断(6)、程序存储器(7)进行数据传输；存储单元(5)通过直接内存存取(3)与总线(2)及网络接口(4)连接；网络接口(4)与总线(2)连接，并通过片上网络与外部存储器连接。

2.根据权利要求1所述的矩阵转置存储控制器，其特征在于：处理器(1)对数据传输进行控制，数据传输包括数据输入和数据输出两种过程；数据输入时，在处理器（1）的控制下，直接内存存取(3)完成对数据地址的配置；网络接口(4)从外部存储器读取数据，并根据直接内存存取(3)产生的地址，将数据存入存储单元(5)；数据读入数据存入存储单元(5)后，处理器（1）配置直接内存存取(3)产生地址，将数据从存储单元(5)读出，完成对读入矩阵的转置，并将数据通过网络接口(4)输出。

3.根据权利要求1所述的矩阵转置存储控制器，其特征在于：矩阵转置由矩阵大小与存储单元(5)的存储空间大小的关系决定，分三种模式，分别为：

1）存储单元(5)存储一个矩阵所有的数据；转置控制器将数据读入，处理器（1）配置直接内存存取(3)，按照行方向将矩阵存入存储单元(5)，然后按照列方向，将矩阵读出，完成矩阵的转置；

2）矩阵的数据大于存储单元(5)的存储空间；转置控制器按照矩阵行数据方向读满存储单元(5)，接着配置外部存储器的地址，按列方向，将读入的数据依次输出到外部存储器对应的地址；然后读取原始矩阵下一部分数据到存储单元(5)，并且输出到外部存储器对应的地址中；重复以上过程，直到矩阵所有的数据输出，完成矩阵的转置；

3）矩阵的数据远大于存储单元 (5)的存储空间；可以将矩阵分块，每块矩阵的大小正好等于存储单元(5)的存储空间大小；分行将块矩阵的数据全部读入到存储单元(5)中；与2）转置模式相同，转置控制器按列方向输出存储单元(5)数据到外部存储器中；接着读取第二块矩阵，将数据按行方向写入存储单元(5)，按列方向读出，输出到外部存储器中；重复以上过程，直到矩阵所有的数据输出，完成矩阵的转置。

4.根据权利要求3所述的矩阵转置存储控制器，其特征在于：处理器（1）控制直接内存存取(3)完成对转置算法的选择；处理器（1）配置的内容包括：矩阵行数，矩阵列数，矩阵转置算法选择。

5.根据权利要求3所述的矩阵转置存储控制器，其特征在于：在转置模式3）中，确定分块矩阵的行数H和列数P；分块矩阵的行数H和列数P是由数据输入时建立数据通道所用时间T₁，与数据输出建立数据通道所用时间T₂决定的；矩阵转置建立数据通道所用总时间为H*T₁+P*T₂，H*P是固定的，并等于存储单元SRAM(5)的存储空间，利用不等式

Figure 2011103936607100001DEST_PATH_IMAGE002

得出H与P的值；并取整得到最合适的结果。