用于执行算术运算的硬件

摘要

用于执行一系列算术运算的硬件。所述硬件包括：计划机，其能够运行以基于指示所述矩阵中的条目是否为零的所述位图来生成指令计划。所述硬件还包括算术线路，所述算术线路构造成根据所述计划来对所述矩阵执行算术运算。

说明书

技术领域

本发明涉及用于执行与数据结构相关的重复性算术或逻辑运算的 硬件。更特别地本发明涉及的硬件包括计划机，所述计划机能够运行以 基于位图产生指令计划以及相关联的地址基准（address references）， 其中所述位图指示矩阵中的条目是否为零，所述硬件进一步包括算术线 路，所述算术线路构造成根据所述计划使用非零值对所述矩阵进行算术 运算。

背景技术

在计算系统的设计中有一个基本问题，即使得存储器访问的时间 成本最小化。

这是对计算机系统的基本限制，其原因在于，不论使用什么存储 器技术来支持计算以及不论使用什么技术来讲所述存储器连接至处理 器，在给定时间内有多少信息能够在处理器和存储器之间传输有最大的 限制，这是可用的存储器带宽，并且可用的存储器带宽对计算机能力的 限制通常称为“存储器壁（memory-wall）”。

已知采用数据压缩来减少“存储器壁”的效应。然而，对于编程 器使用压缩的存储器子系统的问题在于数据必须在器能够在图1所示的 系统操作之前被压缩。这通常涉及从一部分存储器读取压缩数据至处理 器16的寄存器文件14，使用从程序存储器18获得的程序对之进行解压， 并且将解压的数据存储在存储器12的另一非压缩部分中。、

然而，这种方法具有下述缺点：需要附加的存储器带宽来读取压 缩数据库，将其以非压缩形式存储，以及在运算时将其读回至所述处理 器。还需要附加的存储器容量来保持解压的数据，并且解压过程将增加 对处理器寄存器文件的压力。显然，这是不太好的方案，说明此种压缩 的存储器子系统还是停留在学术上而没有进入主流微处理工业。

寄存器分块对于加速矩阵计算（特别是有限元）是有用的技术， 但是它具有下述缺点：对于许多矩阵（例如，用在诸如GOOGLETM 的搜索引擎中），必须增加零，降低了有效的FLOPS，并且增加了存储 器带宽要求，这两项是在现代计算系统中供应不足的。

实际上，处理能力和存储器带宽之间的增长差异（分别以每年50% 和7%的高差别速度增长）如上所述地称为“存储器壁”。已经有许多“破 开”存储器壁的方法，这些方法通常使用高速缓存器来降低必须与芯片 外进行通信的可能性，和/或使用多线程使得响应时间和与芯片外通信 相关联的损失能够被降低。

这些方法仅仅将受限制的外部存储器带宽隐藏起来，而不是解决 这个问题，并且通常依赖于数据组呈现足够的数据局部性，以及程序呈 现足够的线程级并行能力（TLP），以便整体上更加有效。实际上，许 多较大和更主要的问题既不呈现有效的数据局部性，也不呈现足够的 TLP，并且整个系统的能力下降至由外部存储器带宽限制的点，并且已 经加在芯片上的其他硬件不可使用。为此，大的工程应用的处理器性能 下降至制造商标称峰值性能参数的1%或更低并不罕见。

用于计算稀疏矩阵向量产物（SMVM）的现有技术方法在过去的 几十年中进步很小，并且性能改进主要由于处理器和半导体处理技术的 改进。通常SMVM对于主流微处理器的设计的影响微乎其微（如果有 的话），尽管与放大I/O带宽性能的明显问题，特别是芯片多处理器 （CMPs）通过逐渐地放大I/O带宽加剧问题。典型的分块稀疏矩阵中 的条目的可调整数量由零值数量确的。即使这些值（即使不会有助于 SMVM的结果）从存储器获取，并且与功率消耗和系统工作容量方面 的所有相关问题联系在一起。

图2是现有技术的分块压缩稀疏行（BCSR）数据结构的状态的示 例性说明，该数据结构由3个阵列组成。行阵列（row_start）保持含有 非零片的行条目，第二col阵列（col_idx）含有所述非零片的列地址， val（value）阵列含有稀疏矩阵中所有非零值的实际非零条目（带有内 容）——以逐片的顺序设置。如果A矩阵条目是零，然后处理器将不必 使用零值执行计算，从而不会导致不必要的带宽和功率消耗。

由处理器执行的许多计算包括大量的简单运算。结果，乘法运算 会占用大量的时钟循环来进行。尽管该运算不能算作复杂计算，同样也 不能称为细微运算，例如一个数乘以0、+1或-1，答案可以非常简单的 方式获得。

JP 60247782公开了一种技术方案，其中稀疏矩阵被加载，然后被 检查以识别矩阵内的微小值。然而，该方法不能克服下述限制：必须从 存储器加载完整的矩阵。JP 61025275公开了一种处理器，所述处理器 询问矩阵内的值，以减小矩阵运算所需的时间。类似地，JP 58022446 公开了一种处理器，其中根据寄存器内含有的值避免算术运算。JP 58109971检查寄存器内的值以减少管线处理器结构内用于计算的整体 计算时间——当在计算期间产生的中间值是微小值时。类似地，GB 1479404公开了一种技术方案，其中检查矩阵内的数据值，以确定它们 是否含有微小值，以及该确定结果是否在计算性能中使用。所有这些 方法还是涉及从存储器加载完整矩阵。

在一些应用中，涉及稀疏矩阵，执行的微小运算能够使非常显著 的，原因在于大量零的存在。稀疏矩阵中零的数量能够被减少或消除通 过将所述矩阵存储为诸如压缩行存储（CRS）格式的稀疏形式，然而， 由于地址产生方面的开销，此种存储格式经常导致商用计算机系统具有 非常差的性能。

因此需要一种解决方案来解决现有技术的至少一些缺点。

发明内容

通过提供用于执行算术运算的硬件来解决这些问题，所述硬件包 括：计划机，其能够运行以基于指示矩阵中的条目是否为零的位图来生 成指令计划和相关的地址（阵列基准）；以及算术线路，其构造成根据 所述计划来使用非零值对所述矩阵执行算术运算。

所述硬件不需要执行由于矩阵中含有的零值而导致的琐碎运算。 消除了对下述运算的需求：将零值存储至存储器以及从存储器载入零 值，通过共享的总线移动所述零值，或者实际上使用这些零值执行算术 运算。

相应地，本发明的第一实施例提供如权利要求1中限定的硬件。 本发明还提供如权利要求50中限定的硬件组件。此外，本发明涉及如 权利要求55中所限定的方法。附加地，本发明提供如权利要求56中所 限定的方法。有利的实施例在从属权利要求中提供。

参考附图将更好地理解这些和其他特征，所述附图是为了辅助理 解本发明的教示而提供的。

附图说明

下面将结合附图对本发明进行说明。在所述附图中：

图1是现有技术中已知的处理器结构的框图。

图2是现有技术中已知的分块压缩稀疏行（BCSR）数据结构的图 示。

图3是根据本发明一实施例的硬件的框图。

图4是包括图3的硬件和其它硬件元件的硬件组件的框图。

图5是由图3的硬件所使用的位图分块压缩稀疏行（BBCSR）数 据结构的图示。

图6是图3的硬件的控制寄存器的的图示。

图7是用于的压缩所述计划的示例性位图。

图8是图3的硬件的元件的示意性线路图。

图9是图3的硬件的元件的示意性线路图。

图10是带有相关数据结构的示例性矩阵的图示。

图11是示出由图3的硬件所执行的操作的控制逻辑时序图。

图12是图3的硬件的元件的示意性线路图。

图13是由图3的硬件所实施的示例性计划结构。

具体实施方式

现在将结合示例性硬件来对本发明进行说明，所述示例性硬件是 提供用来辅助理解本发明的教示的。

参见附图，首先参见图3和图4，在图3和图4中提供硬件100用 于执行算术运算。硬件100设计成在处理矩阵时避免对零条目进行操作。 这需要执行诸如存储或加载零值至存储器的操作，避免通过共享的总线 移动它们或者避免实际上使用零值进行算术运算。图4的硬件组件108 包含能够通过处理器总线110偶联至外部硬件元件的硬件100。处理器 总线110允许在硬件100和外部硬件元件之间进行数据交换，所述外部 硬件元件例如可以包含处理器、缓冲储存器（cache）、SDRAM控制器、 SDRAM等。

稀疏数据结构在计算机科学和工程应用中的一个主要用途是存储 稀疏矩阵，系数矩阵的主要应用是直接或迭代方法的联立式的系统的解 决。在这些直接或迭代方法的核心的中心操作是通过对稀疏矩阵乘以密 集向量来产生密集结果向量。所述计算的形式是y=Ax，其中A是稀疏 矩阵，y和x是密集向量。下面是示例的稀疏矩阵-向量乘法。

$y\left(\begin{array}{c}0\\ 1\\ 2\\ 3\end{array}\right)=A\left(\begin{array}{cccc}00& 01& 02& 03\\ 10& 11& 12& 13\\ 20& 21& 22& 23\\ 30& 31& 32& 33\end{array}\right)*x\left(\begin{array}{c}0\\ 1\\ 2\\ 3\end{array}\right)$

对于以行执行的4x4稀疏矩阵-向量乘法的详细计算由式1提供。

式1

y₀＝a₀₀*x₀+a₀₁*x₁+a₀₂*x₂+a₀₃*x₃

y₁＝a₁₀*x₀+a₁₁*x₁+a₁₂*x₂+a₁₃*x₃

y₂＝a₂₀*x₀+a₂₁*x₁+a₂₂*x₂+a₂₃*x₃

y₃＝a₃₀*x₀+a₃₁*x₁+a₃₂*x₂+a₃₃*x₃

在基于行的式中，y结果向量中的元素是经过计算的一行——A- 矩阵的一行乘以x向量。整体上，乘法和求和的形式如式2所示。

式2

y[row]＝a[row，col0]*x[col0]+a[row，col1]*x[col1]+a[row，col2]*x[col2]+a[row，col3]*x[col3]

密集矩阵向量计算涉及的步骤为：

.将x向量预加载至处理器内的寄存器（对于所有的y条目重复 使用）。

.对y向量进行初始化。

.根据数据总线的宽度，将A-矩阵一个元素一个元素地或者一行 一行地读入处理器内的寄存器中。

.将a[row，col]乘以x[col],并与y[row]求和。

.重复进行，直到已经处理所有的行和列。

在稀疏矩阵的情况下，在式2中，A和x条目中的许多将明显是零， 因为稀疏矩阵A的行和列中的许多将是零。常规的稀疏矩阵-向量乘法 器不考虑获知和/或避免零乘法（其中A矩阵的元素是稀疏的），从而对 于总的矩阵-向量乘法而言导致相当长的耗时和功率消耗。

本发明使用位图压缩来压缩所述稀疏矩阵。所述位图指明哪个矩 阵元素是零，允许避免零乘法，从而构成中间产物的y向量元素的求和 得到简化。如果位图全部是1位的，乘法操作简化成逻辑与（AND）。

式3

y₀＝bm₀₀*a₀₀*x₀+bm₀₁*a₀₁*x₁+bm₀₂*a₀₂*x₂+bm₀₃*a₀₃*x₃

y₁＝bm₀₄*a₁₀*x₀+bm₀₅*a₁₁*x₁+bm₀₆*a₁₂*x₂+bm₀₇*a₁₃*x₃

y₂＝bm₀₈*a₂₀*x₀+bm₀₉*a₂₁*x₁+bm₁₀*a₂₂*x₂+bm₁₁*a₂₃*x₃

y₃＝bm₁₂*a₃₀*x₀+bm₁₃*a₃₁*x₁+bm₁₄*a₃₂*x₂+bm₁₅*a₃₃*x₃

bm_n∈{0，1}

基于位图压缩，所述稀疏矩阵-向量乘法能够分解成下述步骤：

1.将x向量预加载至处理器内的寄存器（对于所有的y条目重复 使用）。

2.对y向量进行初始化。

3.从外部存储器将位图读入至内部寄存器中。

4.将位图扩展成未压缩清单，用于SMVM并存储在寄存器内。

5.对计划进行压缩，以使用位图仅仅进行非零乘法。

6.将a[row，col]乘以x[col],并使用压缩的清单与y[row]求和。

7.重复进行，直到已经处理所有的行/列。

硬件100构造成执行如上所述的步骤1-7。这样，硬件100能够执 行诸如式3中列出的算术运算（其仅仅是以示例的方式给出的）。硬件 100构造成通过软件接口114读取位图分块压缩稀疏行数据结构 （BBCSR）112。BBCSR 112数据机构增大图2的BCSR阵列（row start, col_idx和值），bitmap_idx阵列含有位图。位图中的每个条目表明在矩 阵的片中是否存在零值。BBCSR 112数据结构的值阵列内容与图2的 BCSR数据结构中的值阵列内容的不同之处在于仅仅实际的非零值条目 被存储，而没有填充任何的零（除非对位图中的1位条目进行计数）对 于稀疏矩阵中的所有非零数据，一片一片地设置。图5的bitmap_idx 阵列中的位图条目是16位进制的值。

BBCSR 112的四个阵列中含有的值通过偶联至总线110的映射的 储存器结构118写入硬件100的内部寄存器116。一旦所有的值被载入， 通过对命令寄存器写开始指令，计算可以被使能。用于包括所述命令寄 存器的软件接口的寄存器映射在图6中示出。命令寄存器允许开始加速 的稀疏矩阵向量（SMVM）产生、SMVM计算暂停，暂停的SMVM继 续，或者硬件100停止以及所有寄存器复位。所有的寄存器可以复位， 只有NZ计数（其显示在当前SMVM中由硬件100处理成数据的A矩 阵非零内容的数量）和循环计数（其显示在当前SMVM操作中经过的 循环的数量）除外。如果所需的附加的寄存器能够容易地添加，以允许 计划机通过询问X和Y向量片段和硬件100内的其它寄存器而对 SMVM码进行调试。

软件接口114允许用于矩阵-向量生成物的下述参数如图3中所示 被加载至硬件100的寄存器116内。

.BM是A矩阵122中的位图分块的片的数量。

.Arows是A矩阵122中的行的数量。

.Acols是A矩阵122中的列的数量。

.Brows是A矩阵122中的分块的片124中行的数量。

.Bcols是A矩阵122中的分块的片124中列的数量。

.VALaddr是值阵列126的基本地址。

.RSTaddr是row-start阵列128的基本地址。

.CIXaddr是col idx阵列130的基本地址。

.BIXaddr是位图阵列132的基本地址。

位图计划机134读取位图阵列132以从带有相应函和列基准的所 述位图产生指令计划138。由位图计划机134产生的示例的计划138在 图13A中示出。位图计划机134产生一系列非零部分产物来与它们相关 的列和行地址进行求值。所述计划还包括将由控制器140使用的非零计 数。如图7中所示，位图计划机138根据位图142被压缩。位图计划机 134可以使用多个位片段146以及一个阵列的多路器144来构造。计划 是通过控制一组多路器144而获得的。在示例实施例中，位图计划机134 可以通过二输入多路器以一个阵列的（N²+N）/2,4位构成，其中，N是 位图位的数量，并且对应于需计划的时段。如同从图8能够看出的，位 图计划机134由120个4位、2：1多路器134以及相应的查询表（LUT） 构成。如果位图计划机134被包括作为可编程处理器管线的一部分，它 还能够用作通用64位移位器（在4位或4位的倍数的步骤中）——如 果附加的2：1多路器被包括在输入中来在LUT输出和输入寄存器或总 线之间进行选择。

位图计划机134的最终元素是迭代计数器151，迭代计数器151确 定使用N元宽SIMN FPU执行SMVM计算而必须的算法迭代的数量。 迭代计数器151的示例实施例在图9中示出，其包括19个全地址156 和单个或（OR）门158。

硬件100的控制器140将所有的相关控制信号与来自位图生成计 划的列和行地址施加至所述多路器，以确保正确的结果被计算、求和和 存储回正确的y寄存器。控制逻辑信号包括能够影响下述操作的信号：

.将y向量条目加载至对应于A矩阵上片的各行的内寄存器 （load_y control signal）

.将用于片的位图加载至寄存器（load_bmp）。

.从片位图产生计划。

.将x-向量条目加载至对应于各A矩阵片的内部寄存器中 （load_x）。

.从储存器流注（读取）A矩阵条目（load_a）。

.选择正确的x向量条目来与各A矩阵条目相乘。

.顺次地计算个A.x部分产物（amultx）。

.选择正确的y值来进行更新，通过在浮点（FP）加法器中增加A。 x部分产物。

.更新正确的y向量寄存器。

.将y向量寄存器内容写回至A矩阵行端部处的寄存器。

执行算术运算所需的硬件由算术线路141提供，所述算术运算诸 如是A矩阵中的非零条目与适当的元相乘。在示例实施例中，算术线路 141包括浮点单元（FPU）。本领域普通技术人员可以理解的是，浮点单 元通常形成计算系统的一部分，并且构造成执行诸如乘法、除法、加法、 减法和开方之类的运算。所述算术线路141可以提供单指令多数据 （SIMD）FPU。可以包含在算术线路141内的硬件元件的示例实施例 在图12中示出。在图12中，A-dly表示通过浮点加法器进行延迟来匹 配时钟循环中的延迟，M-dly表示通过浮点乘法器进行延迟来匹配时钟 循环中的延迟。这些延迟是为了排列多路器选择信号到达的时间，以及 数据到达浮点加法器和乘法器。

将结合图10和图11说明硬件100的示例实施例的运算。示出的时 序图的片段假定4x 4分块的片和单个FP乘法器和FP加法器（各自具 有单个时钟循环延迟，而不是SIMD单元，用于简化），并且控制信号 的时长示出为对应于前两个片和相关的位图。图11的位图被简化，且 不包括从所述计划产生的数据路径源和目的地多路器控制信号。

y寄存器初始被夹在四个值，保持在先的两个矩阵片。一旦这些值 已经被加载，对应于在先的矩阵片的位图被获取，并产生计划。接着， 在先的四个x寄存器值在接下来的四个时钟循环中被加载。接着，在先 的四个非零A矩阵值从储存器内的值阵列126获取，并且乘以x寄存器 条目，以产生四个部分产物。这些部分产物然后在四个循环中与存储在 y寄存器内的四个y向量条目求和。接下来，第二片和相关的条目被处 理，更新y寄存器以完成矩阵向量产物。最后，对应于A矩阵片的第一 行的y向量值被从y寄存器写回至储存器，并且对应于A矩阵片的下一 个行的SMVM产物的计算能够被进行。

由控制器140产生的控制逻辑还可以包含逻辑来检测数据依赖性， 所述数据依赖性能够导致RAW危险，以及导致使数据路径停止，知道 这些依赖性已经被解决。相同地，控制器140可以使得硬件100的运行 停止（暂停）来等待来自外部总线、数据高速缓存器或真正的外部 SDRAM的数据。

由控制器140产生的控制信号可以设计成管线以及来叠置可能的 话能够同时执行的操作，导致26/28或93%的高总线带宽利用率。实际 上，一旦考虑在典型的处理器核心中使用的高频浮点单元的长的等待时 间，能够获得的总线利用率将低于上述利用率。

存储器接口118由控制器140控制，且递增四个地址指针，并产生 存储器读和写信号，以确保硬件100所需的所有数据以适时的方式从存 储器或硬件100外的高速缓存器内的适当地址到达，以及确保硬件100 产生的结果被写回至存储器或硬件100外的高速缓存器内的正确地址。

A矩阵的非零元乘以x的相应元（其是使用来自相应计划条目的列 参引而从寄存器查询获得的）。A矩阵的元直接地从存储器读取，并且 随着他们进入硬件100而被施加乘法操作。在稀疏矩阵通过向量乘法运 算的情况下，不需要存储A稀疏矩阵的元，由于A稀疏矩阵中的条目 仅仅使用一次。

本领域技术人员将理解的是，不将A矩阵的元存储在寄存器文件 中与现有技术相比有数个优点：

.节省与将A矩阵的行写至寄存器文件相关联的功率和时间（反 应时间）

.节省与从寄存器文件读取A矩阵的行相关联的功率和时间（反 应时间）

.避免与A矩阵条目在寄存器文件中的临时存储相关联的寄存器 压力

还将理解的是，将x向量存储在临时寄存器中而不是作为多端口 寄存器文件具有优点：与对于待被乘的A矩阵的各行读取x向量相关联 的相当高的功率得以节省，因为简单的临时寄存器能够用于保持x的条 目。

位图计划机134可以构造成执行前瞻，以解决依赖性。在原则上 如果计划能够在一个时钟周期内产生，并且得到的SMVM占用NZ周 期，那么位图计划机134能够在下一个N位图进行前瞻，以评估是否能 够消除数据依赖性和相关的RAW风险。

如同在图13中示出的示例中能够看出的，如果计划是在一个时间 内在位图上独立地执行的，依赖性和相关的RAW风险与y[1]的和相关 地出现——由于在所述片中行1的每个元是非零的。如果计划被处理， 将与部分产物加至y[1]的每次相加相关联地出现停止。在图13中示出 的方法是对于相同矩阵行中的两个位图相关地计算所述计划，进行前瞻 来看第二位图计划中的哪些段（slots）会与来自第一位图计划的那些段 交错。这个前瞻计划能够在如图所示的相同基础上被扩展至其他位图， 以适应浮点加法器逐渐较高的反应时间，如果不解决的话，所述逐渐较 高的反应时间导致成正比的较高的停止补偿。

可以理解的是，文中说明的内容是示例性的硬件。尽管本发明是 参考一些示例方案进行说明的，但是可以理解的是，并非意在将本发明 的教示限制与这些方案，能够在不脱离本发明的主旨和范围的情况下进 行修改。本领域普通技术人员将理解的是，通过将所述硬件与硬件组件 中的硬件元件借助总线进行通信，所述硬件能够被改造成含有硬件元件 的现有硬件组件。以此方式，可以理解的是，本发明将仅仅必须如所附 权利要求书中所限定的方式被限制。类似地，将理解的是，尽管是以稀 疏矩阵向量产品的方式对所述方法和硬件进行的说明，但是相同的方法 和硬件也可以用于使用算术和逻辑运算来支持具有一个列或行的矩阵 和矩阵-矩阵产物的特殊情况的浓密矩阵、向量。

类似的词语包括/包含在用在说明书中时是用于表示存在所述的特 征、组成部分、步骤或成分，但是不排除一个或更多附加特征、组成部 分、步骤、成分或其组合的存在或添加。