用于执行向量扫描运算的数据处理设备和方法
用于执行向量扫描运算的数据处理设备和方法
【技术领域】
[0001] 本技术涉及数据处理领域。更具体地，本技术涉及用于执行向量扫描运算的数据 处理设备和方法。
【背景技术】
[0002] 一种改进数据处理设备的性能的已知技术是提供电路来支持向量运算的执行。在 至少一个向量操作数上执行向量运算，其中每个向量操作数包括多个向量元素。执行向量 运算涉及在一个或多个向量操作数内的各种向量元素上重复地应用运算。在支持执行向量 运算的典型数据处理系统中，提供向量寄存器文件用于存储向量操作数。与执行等价的系 列标量运算相比，通过使用向量运算可以实现显著的性能优势。
[0003] -种已知类型的向量运算是向量扫描运算，其中预定的组合运算被重复应用到增 加数目的数据元素。组合运算可以采用多种形式，诸如加法运算、乘法运算、最小值选择运 算、最大值选择运算等。作为执行向量扫描运算的结果，结果序列被生成，其中每个结果与 应用组合运算到不同数目的数据元素有关。作为具体示例，扫描运算可以指定加法运算作 为组合运算，并且这种扫描加法运算有时被称为前缀求和运算。考虑输入数字序列Xd，Xp x2,...，应用扫描加法运算产生了结果序列y(l，yi，y2,...，其中：
[0004] yQ=x〇，yfXQ+Xpy2=XQ+Xi+x"依次类推。
[0005] 在向量扫描运算的一些示例中，额外数据元素S可以与源向量的向量数据元素V 组合以产生一系列结果（在扫描加法运算的情况下）：
[0006] 丫。=S+x。，yfS+Xo+Xpy2=S+Xo+Xi+Xy依次类推。
[0007] 本技术寻求提供用于执行这样的向量扫描运算的改进设备和方法。
【发明内容】
[0008] 根据一个方面，本技术提供了一种数据处理设备，包括：
[0009] 向量寄存器存储器，该向量寄存器存储器被配置为存储包括多个数据元素的向量 操作数；
[0010] 处理电路，该处理电路被配置为处理来自向量寄存器存储器的向量操作数；以及
[0011] 控制电路，该控制电路被配置为控制处理电路对源向量操作数的M个数据元素 V[0]至V[M-1]和至少一个额外数据元素S执行向量扫描运算，以产生结果向量操作数的M 个数据元素R[0]至R[M-1]，其中对于N彡M且0<i<N，结果向量操作数的数据元素R[i] 具有对应于至少一个额外数据元素S和源向量操作数的至少一些数据元素V[0]至V[i]的 组合的值；
[0012] 其中，控制电路被配置为控制处理电路在多个步骤中执行向量扫描运算，每个步 骤用于从第一向量产生第二向量，其中用于第一步骤的第一向量包括源向量操作数的数据 元素，并且用于其他步骤的第一向量包括在前步骤的第二向量，每个步骤包括用于组合第 一向量的数据元素与至少一个额外数据元素S或第一向量的另一个数据元素以产生第二 向量的数据元素的至少一个组合运算；
[0013] 所述多个步骤中的至少一个步骤包括并行执行的多个组合运算；并且
[0014] 所述多个步骤中的至少两个步骤包括用于组合第一向量的数据元素与至少一个 额外数据元素S的组合运算。
[0015] 虽然可以使用串行执行的标量运算来执行向量扫描运算，但是这样做非常慢并且 由于性能原因，并行执行至少一些组合是有用的。然而，虽然已知的并行技术可以相对高效 地组合向量数据元素的两个数字的幂，但是当额外数据元素S同样地需要与向量数据元素 组合时，可能需要额外的步骤。现有技术要么在组合源向量操作数的不同向量元素之前，在 初始步骤中组合额外数据元素S与源向量操作数的数据元素，要么首先执行源向量内的不 同数据元素的全部组合，然后执行额外步骤用于组合额外数据元素与在前面的步骤中产生 的每个数据元素。不论哪种方式，都需要额外步骤。
[0016] 本技术的发明人意识到并不是源向量操作数的全部M个数据元素都是受关注的。 例如，可能没有足够的数据来完全填充源向量操作数的M个数据元素，因此仅需要产生结 果操作数的N个数据元素（其中N<M)。用于执行向量扫描运算的已知并行技术不考虑这 一点并且代替地专注于对全部M个数据元素执行扫描运算。发明人意识到，通过改变执行 向量扫描运算的方式，有可能在仅需要一些结果数据元素的情况下更快地执行运算，并且 在期望全部M个结果数据元素的情况下不需要增加步骤的数目。
[0017] 为了实现这一点，本技术的处理电路在多个步骤中执行向量扫描运算，每个步骤 从第一向量产生第二向量，其中用于第一步骤的第一向量包括来自源向量操作数的数据元 素，并且用于其他步骤的第一向量包括来自在前步骤的第二向量。所述步骤中的至少两个 步骤包括用于组合第一向量的数据元素与至少一个额外数据元素S的组合运算（与此相 反，已知技术仅包括一个这样的步骤）。通过在向量扫描运算的多个步骤中组合至少一个额 外元素S，有可能在最后步骤开始前获得结果向量的更多数据元素，从而可以在需要少于M 个数据元素时更快地执行向量扫描运算。
[0018] M可以是2的幂。当N在M/2和M之间时，现有技术不能比在产生全部M个数据元 素时更快地执行扫描运算，因为使用2的更小幂作为M是不可能的。然而，在本技术中，当 N在M/2和M之间时，可以减少所需步骤的数目。
[0019] 可以执行向量扫描运算以在至少一个组合步骤中产生结果向量操作数的第一G 个数据元素R[0]至R[G-1](其中M/2<G<M)。如果需要多于G个数据元素（N>G)，则 可以通过在至少一个组合步骤外额外执行至少一个进一步步骤了产生结果向量操作数的 其它数据元素R[G]至R[M-1]。这允许在比现有技术更少的向量运算步骤中产生少于M个 数据元素，从而改进性能。
[0020] 如果M/2 <N彡G，则至少一个进一步步骤可以被省略，从而使得该运算可以使用 至少一个组合步骤被更快地执行，并且处理电路可以比至少一个进一步步骤被执行时更快 地开始执行另一个运算。可替换地，即使需要G个以下数据元素，也可以执行至少一个进一 步步骤（如果至少一个进一步步骤是在至少一个组合步骤之后被执行的，则仍能提供性能 改进，因为该G个数据元素仍将比现有技术更早地可用）。当N<M/2时，可以省略向量扫 描运算的更多步骤。对于N<M/2,该处理可以被以与M是2的更小幂时相同的方式对待。
[0021] 至少一个进一步步骤可以包括用于组合第一向量的数据元素与至少一个额外数 据元素的至少一个组合运算，并且可以不包括第一向量的各个数据元素的任意组合。这意 味着可以在相对于至少一个组合步骤的任何时间执行该进一步步骤（在至少一个组合步 骤之前、在至少一个组合步骤之后、或作为穿插在至少一个组合步骤中的中间步骤）。更具 体地，至少一个进一步步骤可以包括用于组合至少一个额外数据元素S与用于该至少一个 进一步步骤的第一向量的数据元素[k]的组合运算，其中G<k<N。这些组合可以对应于 对全部M个数据元素执行向量扫描运算所需要的组合，但是这些组合不是通过至少一个组 合步骤被执行的。
[0022] 另一方面，至少一个组合步骤可以是这样的步骤：在没有进一步步骤被执行的情 况下，该至少一个组合步骤的最后步骤产生结果数据元素R[0]至R[N-1]、和该步骤的第二 向量的数据元素[G]至[M-1]，其中对于G<k<M，第二向量的数据元素[k]具有对应于 源向量操作数的至少一些数据元素V[0]至V[k]的组合的值（即，不与额外数据元素S组 合）。
[0023] 通常，对于M= 2P，至少一个组合步骤可以包括P个步骤，该P个步骤包括用于响 应于第一向量的数据元素[0]至[M-1]产生第二向量的数据元素[0]至[M-1]的组合运算， 从而对于0 <J<P，所述P个步骤中的步骤J包括用于组合第一向量的数据元素[m]与第 一向量的数据元素[m-f]以产生第二向量的数据元素[m]的组合运算，其中f彡m<N。
[0024] 这些组合可以确保数据元素V[0]，V[0]和V[l]，V[0]、V[l]和V[2]等的组合可 以在尽可能的最少步骤中被执行。虽然控制电路被配置为控制处理电路执行这些步骤，但 是每个步骤内的一些组合可以被省略（例如，如果将通过该步骤被处理的数据元素未被选 择用于基于掩码信息的处理）。另外，虽然P个步骤中的每个步骤被定义为具有针对元素 [21至元素[N-1]的组合运算，但是这些组合也可能继续到元素[M-1]，从而使得对正被处 理的M个数据元素的块中的全部数据元素执行该组合，即使当被选择的元素的数目N小于 皿时。
[0025] 在本申请中，数据元素索引[0]、[1]等被用于指代正在被向量扫描运算处理的数 据元素相对于其它元素的位置，其不必与数据元素被存储在向量寄存器中的位置相同。源 向量操作数和结果向量操作数的哪些数据元素对应于元素[0]、[1].....[M-1]可以是任 意的设计选择。例如，一些系统可以将源向量寄存器内的最低有效位上的元素当作元素 [0]，并且将源向量寄存器内的最高有效位上的元素当作元素[M-1]，然而在其它系统中可 以是与之相反的方式。也可以使用数据元素的更多的任意分配。因此，例如，向量扫描运算 中的元素V[0]和V[l]的组合可以实际上对应于向量寄存器内的非相邻位置上的元素。移 位电路可以被用于将数据元素移位到所需位置用于向量扫描运算。
[0026] 另外，用于至少一个组合步骤的各个步骤的索引J被用于限定在该步骤中执行的 组合运算。至少一个组合步骤不是必须按照J的升序被执行。虽然在一个实施例中P个步 骤可以按照J= 〇、1.....P-1的顺序被执行，但是在其它实施例中该P个步骤可以按照不 同的顺序（例如l、2、p-l、0、...）被执行。
[0027] 至少一个组合步骤也可以包括用于组合至少一个额外数据元素S与向量数据元 素的各种组合运算。取决于在至少一个进一步步骤不被执行的情况下需要产生结果向量操 作数的多少个数据元素（G)，额外数据元素S可以被输入并且在不同步骤中与源向量的元 素组合。通常，G可以被选择成使得M-G是2的幂，并且至少一个组合步骤的P个步骤可以 是这样的步骤：对于l〇g2(M-G) <J<P，所述P个步骤中的步骤J包括用于组合第一向量 的数据元素[q]与所述额外数据元素S以产生第二向量的数据元素[q]的组合运算，其中 2J-(M_G) <q< 2J〇
[0028] 该方法允许执行向量扫描运算，从而使得通过执行至少一个组合步骤可获得的结 果数据元素R[0]至R[G_1]的数目与向量扫描运算可以与用于产生至少一个额外数据元素 S的另一个运算相交错的程度均衡。
[0029] 对于较大值的G(例如，G=M-1提供G的最大可能值），结果数据操作数的更多数 据元素可从至少一个组合步骤获得，从而使得当至少一个进一步步骤可以被省略时有更多 机会改进性能（N更可能小于或等于G)。对于G=M-1，只有在结果向量的全部M个数据元 素需要使用扫描运算产生时，才需要至少一个进一步步骤。然而，该方法可能要求额外数据 元素S在更多步骤中被输入，因此额外数据元素S可能需要更早地可获得，从而使得向量扫 描运算可能需要等待早期运算在开始前产生额外数据元素S。
[0030] 另一方面，对于较小值的G(例如，G=M/2)，因为较少的步骤包括涉及额外数据元 素S的组合，所以至少一个额外数据元素S的输入经常被延迟。这有助于允许向量扫描运 算在额外数据元素S准备好之前开始，从而使得向量扫描运算可以更早地完成。然而，对于 较小值的G，相对于较大值的G可能需要更多的组合运算，并且省略至少一个进一步步骤的 性能改进可能不是经常可获得的，因为只有较少的N值不需要至少一个进一步步骤。
[0031] 因此，系统设计者可以根据他们的需要选择G。一些处理电路可以具有针对G的特 定值被硬连接的硬件，该硬件可以使得实现控制电路更简单。其它系统可以具有这样的控 制电路，该控制电路可以动态地配置处理电路根据额外数据元素S是否已经可获得、以及 对于特定运算需要多少数据元素N来针对不同的G值执行处理。
[0032] 除了结果数据元素R[0]至R[N-1]以外，向量扫描运算还可以产生进位值，该进位 值可以被输出用于进一步运算。例如，进位值可以被用作用于随后的向量扫描运算的额外 数据元素S。该进位值可以具有对应于结果向量操作数的数据元素R[N-1]的值。控制电路 可以控制处理电路在至少一个进一步步骤被省略的情况下比在至少一个进一步步骤被执 行的情况下更早地输出进位值，从而使得使用进位值的后续运算可以在不需要至少一个进 一步步骤的情况下更早地开始。
[0033] 所需数据元素的数目N可以小于正在被处理的块中的元素的数目M的原因在于， 向量扫描运算具有识别数据元素为被选择的数据元素或未被选择的数据元素的控制信息， 只有被选择的数据元素将被向量扫描运算处理。该控制信息例如可以是将单个数据元素识 别为被选择的或未被选择的数据元素的掩码信息、指定有多少个数据元素被选择的向量长 度信息、或识别被选择的和未被选择的元素的特定图案的向量格式信息。通常，N的取值使 得源向量操作数的元素V[N-1]是由控制信息指示的最后被选择的数据元素（可能有一些 未被选择的元素的元素索引小于N-1)。
[0034] 对于由控制信息指示的任意未被选择的数据元素，结果向量操作数中的相应数据 元素可以被设置为预定值（例如，〇)，通过利用被设置为预定值（例如，〇)的源向量操作数 的未被选择的数据元素执行向量扫描运算确定的值，或用于存储源向量操作数的源寄存器 或用于存储结果向量操作数的目标寄存器中的相应数据元素的值（在一些情况下，源寄存 器和目标寄存器可以相同）。在一些实施例中，处理未被选择的数据元素的组合运算可以被 禁止。可替换地，对应于未被选择的元素的向量扫描运算的部分可以正常进行。无论哪种 方式，结果都可以被调整为上述值中的一个，例如，通过与向量扫描运算并行地执行将需要 值写入目标寄存器的未被选择的部分的运算。
[0035]上述向量扫描运算可以使用少于M个数据元素的另一个原因在于，可以分割向量 扫描运算以便对M个数据元素内的不同分段执行不同的扫描。在这种情况下，第一分段可 以被以上述方式处理，其中N是第一分段中的数据元素的数目。如果有进一步的分段，则 可以通过组合该进一步分段内的一个或多个数据元素（但不包括至少一个额外数据元素 S)来执行扫描运算。例如，对于额外数据元素S和8个向量元素V[0]至V[7](其中，元素 V[0]至V[2]对应于第一分段，元素V[3]至V[7]对应于第二分段），可以产生如下的一系 列组合：
[0037] 当N<M时，本技术本身很适合分段扫描。如上所述，至少一个组合步骤可以产生 额外数据元素[G]至[M-1]，这些数据元素不包括额外数据元素S并且因此可以对应于第二 分段的结果数据元素。此外，当分段扫描中有至少两个分段时，组合向量的彼此相距甚远的 数据元素所需的运算更少。向量扫描运算可以被设置成使得至少一个进一步步骤提供在分 段扫描的情况下很可能不需要的这些"相距甚远"的组合，从而允许更经常地改进性能。例 如，当G=M-1时，如果有任何分段，则不需要至少一个进一步步骤，因为当G=M-1时该进 一步步骤组合额外数据元素S与最后的数据元素[M]，并且该组合在存在多个分段的情况 下是不需要的。因此，使用本技术可以加快分段扫描。
[0038] 使用如上所述的扫描运算进行处理的M个数据元素不必包括源向量操作数的全 部数据元素。例如，源向量操作数可以包括X个数据元素，其中X多M，并且结果向量操作数 可以包括Y个数据元素，其中Y多M。通常，源向量操作数和结果向量操作数具有相同数目 的数据元素（X=Y)，但是可以在将向量大小转换为更多个元素的同时执行向量扫描运算， 从而使得向量扫描运算填充比源向量大的结果向量的一些元素。
[0039] 更一般地，可以对源向量操作数的L个数据元素执行向量扫描运算，其中L<X并 且L彡Y。如果L>M，则数据元素R[0]至R[M-1]可以与上述讨论的一样，但是对于R[M] 至R[L_1]，结果数据元素可以对应于R[M-1]与索引大于M的至少一些数据元素的组合。如 果L<M，则上述讨论的N值可以对应于L，或者如果L>M，则N=M。
[0040] 以上针对M个数据元素讨论的技术不需要被应用到整个源向量操作数。对于L> M，仅对M个数据元素使用以上讨论的至少一个组合步骤和至少一个进一步步骤进行处理， 并且使用不同技术来产生元素R[M]至R[L-1]。
[0041] 这种情况符合期望的一个原因在于，一些处理电路仅能够并行处理有限数目的数 据元素，该数目可能比要被处理的数据元素的总数目小。如果存在比处理电路能够并行处 理的数据元素多的数据元素，则控制电路可以控制处理电路对源向量操作数内的不同组的 数据元素分别执行分区扫描运算。如果被执行的组合运算是相关联的，则分区扫描运算一 起可以提供与在较大数目的数据元素上执行单个向量扫描运算相同的结果。如果组合运算 不是相关联的（例如，某些浮点运算），则分区扫描运算获得的结果与单个较大扫描获得的 结果存在差异，但是该差异仍是可以接受的。因此，M可以是使用处理器能够并行处理的数 据元素的数目，并且如果L>M，则可以在不同组的M个数据元素或更少的数据元素上执行 分区扫描运算。
[0042] 能够以上述方式对每组M个数据元素执行分区扫描运算，其中额外数据元素在多 个步骤中被输入并且G个数据元素已经准备好而不需要至少一个进一步步骤。然而，发明 人发现这可能降低性能，因为每个后续的分区扫描运算依赖于在先运算的至少一个进一步 步骤的结果，并且因此在进行前需要等待前一个运算的结果。
[0043] 代替地，发明人意识到对于分区扫描，执行向量扫描运算可能是更高效的，因而只 有第一次分区扫描在至少两个不同步骤中输入额外数据元素并且包括上述的至少一个组 合步骤和至少一个进一步步骤。对于至少一个进一步组，替代地，分区扫描运算可以包括至 少一个预备步骤和至少一个额外步骤，该至少一个预备步骤用于组合进一步组的数据元素 的各个数据元素，该至少一个额外步骤用于组合预备步骤的结果与在用于另一组数据元素 的单独扫描运算中产生的数据元素。该方法可以更快地执行全部扫描运算，因为用于进一 步组的元素的至少一个预备步骤可以与用于第一组的数据元素的扫描运算交叉（因为预 备步骤和用于第一组的单独扫描之间没有依赖性）。
[0044] 额外数据元素S可以具有各种形式。例如，额外数据元素可以是标量操作数、来 自向量操作数的数据元素、使用向量操作数的多个数据元素确定的值、或由早期运算产生 的进位值（例如，早期向量扫描运算或同一向量扫描运算内的另一个分区扫描运算的进位 值）。
[0045] 针对向量扫描运算执行的组合运算可以具有各种形式。例如，组合运算可以是下 面运算中的任一种：加法、减法、乘法、除法、逻辑与AND、逻辑或OR、逻辑或非NOR、逻辑异或 XOR、逻辑与非NAND、最大值或最小值选择运算。对于这些运算中的大多数运算，组合运算可 以是组合两个数据元素的二进制组合运算，虽然对于一些诸如加法运算或逻辑与运算之类 的组合运算，可能在每个组合运算中组合三个或更多个数据元素。
[0046] 根据另一个方面，本技术提供了一种数据处理设备，包括：
[0047] 向量寄存器存储装置，用于存储包括多个数据元素的向量操作数；
[0048] 处理装置，用于处理来自向量寄存器存储装置的向量操作数；以及
[0049] 控制装置，用于控制处理装置对源向量操作数的M个数据元素V[0]至V[M_1]和 至少一个额外数据元素S执行向量扫描运算，以产生结果向量操作数的M个数据元素R[0] 至R[M_1]，其中对于N彡M和0彡i<N，结果向量操作数的数据元素R[i]具有对应于至 少一个额外数据元素S和源向量操作数的至少一些数据元素V[0]至V[i]的组合的值；
[0050] 其中，控制装置被配置为控制处理装置在多个步骤中执行向量扫描运算，每个步 骤用于从第一向量产生第二向量，其中用于第一步骤的第一向量包括源向量操作数的数据 元素，并且用于其他步骤的第一向量包括在前步骤的第二向量，每个步骤包括用于组合第 一向量的数据元素与至少一个额外数据元素S或第一向量的另一个数据元素以产生第二 向量的数据元素的至少一个组合运算；
[0051] 所述多个步骤中的至少一个步骤包括并行执行的多个组合运算；并且
[0052] 所述多个步骤中的至少两个步骤包括用于组合第一向量的数据元素与至少一个 额外数据元素S的组合运算。
[0053] 根据又一方面，本技术提供了一种数据处理方法，该数据处理方法用于对源向量 操作数的M个数据元素V[0]至V[M-1]和至少一个额外数据元素S执行向量扫描运算，以 产生结果向量操作数的M个数据元素R[0]至R[M-1]，其中对于N彡M和0彡i<N，结果 向量操作数的数据元素R[i]具有对应于至少一个额外数据元素S和源向量操作数的至少 一些数据元素V[0]至V[i]的组合的值；该 方法被使用处理电路执行并且包括：
[0054] 执行用于从第一向量产生第二向量的多个步骤，其中用于第一步骤的第一向量包 括源向量操作数的数据元素，并且用于其他步骤的第一向量包括在前步骤的第二向量，每 个步骤包括用于组合第一向量的数据元素与至少一个额外数据元素S或第一向量的另一 个数据元素以产生第二向量的数据元素的至少一个组合运算；
[0055] 其中，所述多个步骤中的至少一个步骤包括并行执行的多个组合运算；并且
[0056] 所述多个步骤中的至少两个步骤包括用于组合第一向量的数据元素与至少一个 额外数据元素S的组合运算。
[0057] 本技术也可以通过提供存储计算机程序的计算机可读存储介质以虚拟机形式被 实施，其中，计算机程序在被计算机执行时控制计算机提供根据上述设备的虚拟执行环境。
【附图说明】
[0058] 本技术的特征、示例、以及进一步方面从所附说明书和附图显而易见，其中：
[0059] 图1示意性地示出了用于处理向量操作数的数据处理设备；
[0060] 图2至图4示出了执行向量扫描运算的现有技术；
[0061] 图5示意性地示出了向量扫描运算的第一示例；
[0062] 图6和图7示出了向量扫描运算的第二和第三示例，其中额外数据元素S的输入 对于一个或多个处理步骤可以被延迟；
[0063] 图8和9示出了使用掩码信息控制哪些数据元素在向量扫描运算中被处理的示 例；
[0064] 图10示出了当分区向量扫描运算被应用到图4的现有技术时执行分区向量扫描 运算的对比示例（图10本身不是现有技术）；
[0065] 图11不出了应用分段扫描到图5的实施例的第一不例；
[0066] 图12示出了提供以分区形式执行图5的向量扫描运算的更高效的技术的第二示 例；
[0067] 图13示出了包括用于执行向量扫描运算的多个扫描阶段的向量扫描单元的示 例；
[0068] 图14和15分别示出了图11和12的分区向量扫描运算的流水线利用率的示例；
[0069] 图16示出了应用到图4的现有技术的分段扫描运算的对比示例（图16本身不是 现有技术）；
[0070] 图17示出了应用到图5的向量扫描运算的分段扫描运算的示例；
[0071] 图18示出了执行向量扫描运算的方法；
[0072] 图19-23示出了使用多个分段或使用少于数据元素的最大数目的数据元素的向 量扫描指令的数目的研宄结果，本技术可以为其提供性能改进；以及
[0073] 图24示出了本技术的虚拟机实现。 具体实施例
[0074] 图1示意性地示出了具有支持向量处理的处理电路4的数据处理设备2的示例。 处理电路4可以处理通过输入总线8从向量寄存器文件6接收的源向量操作数，并且对源 操作数的各个数据元素执行相应的数据处理运算以产生通过结果总线10被输出到向量寄 存器文件6的结果向量操作数。处理电路4能够对多个数据元素并行地执行运算。处理电 路4具有用于执行不同类型的处理运算的多个功能单元12。在该示例中，功能单元12包括 用于执行算术运算（诸如，加法、乘法、或移位）和逻辑运算（诸如，逻辑与AND、逻辑或OR、 逻辑异或NOR等）的算术逻辑单元（ALU);用于执行乘法累加运算的乘法累加单元（MAC); 和用于执行浮点运算的浮点单元（FPU)。处理电路4还具有用于执行向量扫描运算的向量 扫描单元12a(将在下面讨论）。应该理解，可以提供其它类型的功能单元。除了能够处理 在输入总线8上接收的操作数以外，一些处理单元12还可以具有将来自功能单元12之一 的输出操作数路由到同一功能单元12或不同功能单元12的输入端口的旁通路径（转发路 径），因而相比所产生的操作数必须被写回到寄存器文件6并且通过输入总线8被读出的情 况所产生的操作数能够在进一步步骤中被更快地处理。例如，图1中存在旁通路径（转发 路径）13,用于将扫描单元12a的输出转发到扫描单元12a的输入或ALU12的输入。还提 供了向量加载/存储单元14,用于将数据从缓存器或存储器加载到向量寄存器文件6并且 将来自向量寄存器存储器6的数据存储到缓存器或存储器。
[0075] 处理电路4对应于处理流水线的执行阶段，该处理流水线还包括指令队列20、解 码电路22、和发布队列24。指令队列20从缓存器或存储器接收指令并且将指令传递到解 码电路22。解码电路22对指令进行解码以产生将由处理电路4处理的微运算，并且将微运 算发送到发布队列24。微运算停留在发布队列24中直到它们的操作数和处理所需的任何 控制信息变成可获得为止，这时微运算被发布供处理电路4的一个处理单元12处理，或者 供加载/存储单元14处理（如果微运算是加载/存储微运算）。在一些示例中，微运算可 以分别对应于整个程序指令，并且在其它示例中，微运算可以对应于指令的一部分。例如， 复杂指令可以被划分成对应于不同处理步骤的微运算、或者用于处理源操作数的不同部分 的微运算。指令队列20、解码电路22、和发布队列24可以被认为是用于控制处理电路4的 控制电路。
[0076] 由设备2执行的一种类型的向量运算是向量扫描运算，其中组合运算被重复地应 用于增加数目的数据元素。组合运算可以采用多种形式，例如加法运算、乘法运算、最小值 或最大值选择运算、逻辑运算等。作为扫描运算的结果，结果序列被产生，每个结果与应用 组合运算（通常是二进制组合）到不同数目的数据元素有关。虽然向量扫描运算可以被串 行执行，但是由于性能原因并行扫描运算是有利的。
[0077] 图2示出了根据现有技术执行向量扫描运算的串行技术，其中被应用的组合运算 是加法运算。向量扫描运算接收包括数据元素V[0]至V[7]的源向量和额外数据元素S作 为输入。扫描运算作为一系列步骤40-54被执行，其中每个步骤执行两个元素的单个组合。 在第一步骤40,额外数据元素S被与第一向量元素V[0]组合。在第二步骤42到第八步骤 54,来自在前步骤的向量元素对的进一步组合被执行，从而到第八步骤54结束为止确定了 一系列总和VfS、Vi+VfS、VfVi+VfS等。虽然图2中所示的方法可以适用于低端系统以 避免与并行执行扫描运算相关联的硬件成本，并且因为其需要相对较少的组合运算（对于 M-元素向量，将需要M个处理步骤）可以是简单和节能的，但是因为该方法需要执行M个单 独步骤，所以该方法相对较慢并且不能利用从并行化可获得的全部性能增益。
[0078] 在并行技术中，执行多个步骤，其中每个步骤接收第一向量并且执行第一向量的 各个元素的一个或多个组合或额外数据元素与第一向量的元素的组合，以产生第二向量。 用于第一步骤的第一向量是源向量，用于其它步骤的第一向量是由在前步骤产生的第二向 量。由最后步骤产生的第二向量是结果向量。
[0079] 图3示出了并行执行向量扫描运算的现有技术。在第一步骤60,额外数据元素S 被与输入向量的第一数据元素V[0]组合。在第二步骤62,向量元素V[l]至V[7]被分别 与相邻元素V[0]至V[6]组合（其中，V[0]已经被与额外数据元素S组合）。类似地，在 第三步骤64,执行第二步骤62产生的向量中的相距两个位置的向量元素的各种组合，并且 在第四步骤66,生成相距四个位置的元素的组合。该方法使得所需处理步骤的数目减少到 log2(M)+l个处理步骤（需要额外步骤处理额外数据元素S)。
[0080] 图4示出了替代的现有技术方法，其中第一到第三步骤实质上与图3的第二到第 四步骤相同，但是额外数据元素S是在最后步骤而不是在第一步骤中被组合。在这种情况 下，因为额外数据元素S在第四步骤中被加入，所以额外数据元素S被加到每个向量数据元 素而不是被加到仅仅一个向量数据元素。然而，步骤的总数目仍与图3中的相同。
[0081] 如图2至图4中所示，现有技术仅包括用于组合额外数据元素S与一个或多个向 量元素V的一个步骤。
[0082] 然而，本技术的发明人意识到现有技术中未考虑的一个问题是，扫描运算可能被 应用到并不是所有数据元素都有效的输入向量。可以使用掩码或相似的控制信息来仅选择 输入向量的一些数据元素供使用扫描运算进行处理（例如，参见下面的图8和9)。使用图 4中所示的技术，结果向量的全部数据元素都是在第四步骤中产生的，因此即使仅仅需要一 些结果数据元素也需要执行全部四个步骤。对于图3,到第三步骤结束为止结果数据元素 0-3是可获得的，但是元素4-7是在第四步骤中产生的。因此，如果需要4个以上元素，则必 须执行全部四个步骤。
[0083] 该问题可以通过包括组合额外数据元素S与一个或多个向量数据元素的向量扫 描运算的多个步骤被解决。以这种方式，向量扫描运算可以包括产生G个结果数据元素的 至少一个组合步骤（其中M/2 <G<M)。如果需要，结果向量的剩余数据元素可以通过执 行至少一个进一步步骤被产生，但是该步骤在需要G个数据元素或更少的数据元素的情况 下可以被省略。
[0084] 在下面的讨论中，索引[0]、[1]等被用于指代正被扫描运算处理的向量内的元素 的位置，而下标索引等指代源向量操作数的相应数据元素内的数值。
[0085] 图5示出了根据本技术执行向量扫描运算的第一示例。使用至少一个组合步骤 (对应于图5的示例中的步骤1-3)和至少一个进一步步骤（对应于图5的示例中的步骤 4)执行向量扫描运算。在该示例中，额外数据元素S在向量扫描运算的每个步骤中被与一 个向量元素组合。在第一步骤100,额外数据元素S被与源向量V的元素V[0]组合，并且 与该组合并行地，源向量的相邻数据元素对被组合（例如，V[l]被与V[0]组合，V[2]被与 V[l]组合等）。在第二步骤102,额外数据元素S被与第一步骤100产生的向量的元素[1] 组合，以生成总和Vi+VfS，并且相距两个元素的元素对[0]/[1]、[1]/[3]等被组合。在第 三步骤，额外数据元素S被与在前步骤生成的向量的元素[3]组合，并且相距四个元素的元 素[0]/[4]、[1]/[5]等被组合。
[0086] 因此，到至少一个组合步骤结束为止，结果数据元素R[0]至R[6]中的除一个以外 的全部结果数据元素已经准备好，因为已经计算出源向量的元素V[0]至V[6]与额外数据 元素S的总和。唯一缺少的元素是R[7]，对于R[7]，总和V7至V0已经被计算出来，但是额 外数据元素S还未被组合（对于元素[7]，在步骤3结束时由括号中的"+S"指示）。因此， 在进一步步骤106,唯一需要的组合是组合额外数据元素S与在前步骤产生的元素[7] 以生 成最后的结果元素R[7]。
[0087] 因此，能够以比图2和图3所示的现有技术少一个步骤产生7个结果数据元素 R[0]至R[6]。如果不需要最后的数据元素R[7]，则该进一步步骤106可以被省略以改进性 能（节省至少一个处理周期）。如果向量ALU被用于扫描单元12a，则处理电路4和扫描单 元12a可能不需要被显著修改以执行图5中所示的修改后的扫描运算，因为通常对于M-元 素向量，扫描单元12a可能已经具有M个并行单元用于执行组合运算，并且图5中所示的步 骤中没有一个步骤需要M个以上的组合运算。移位阶段可以将额外数据元素S和向量元素 V移位到所需要的位置进行处理。
[0088] 图5中所示的方法具有以下优点：8个数据元素中的7个在扫描运算的最后步骤 之前的一个步骤可获得。更一般地说，对于M元素向量，可以比现有技术早一个步骤产生G =M-1个结果元素。然而，这可能需要在每个步骤中输入额外数据元素S，并且如果额外数 据元素S还不可用，则向量运算的第一步骤100将不得不被延迟。
[0089] 图6和7示出了本技术的替代示例，其中在第一步骤中不需要额外数据元素S，因 而使得向量扫描运算可以在额外数据元素可用之前开始从而可以改进性能。
[0090] 在图6的示例中，额外数据元素S可以被延迟一个步骤。在该示例中，在步骤100、 102和104,各个向量元素V的组合与图5中的相同。然而，第一步骤100不组合额外数据 元素S与源向量的元素V[0]。为了确保到第三步骤结束为止产生足够的结果数据元素，第 二步骤102和第三步骤104可以组合额外数据元素S与两个向量数据元素，而不是图5中 的组合额外数据元素S与一个向量数据元素。因此，在第二步骤102,额外数据元素S被与 第一步骤100的结果的元素[0]和[1]组合，并且在第三步骤104,额外数据元素S被与第 二步骤102的结果的元素[2]和[3]组合。这意味着到第三步骤104结束为止，六个结果 数据元素R[0]至R[5]已经准备好，但是有两个元素R[6]和R[7]是使用组合额外数据元 素S与来自步骤104的元素[6]和[7]的进一步步骤106生成的。
[0091] 类似地，在图7中，额外数据元素S可以被延迟进一步的步骤，从而使得仅在步骤 104和106中输入额外数据元素S并且对于步骤100和102不需要额外数据元素S。这允 许向量扫描运算比图6中更早地开始。此外，向量元素的组合与图5和图6中的相同，但是 在这种情况下，额外数据元素S在步骤104中被与最低的四个数据元素[0]至[3]组合并 且在步骤106中被与较高的四个数据元素[4]至[7]组合。因此，到第三步骤结束为止，仅 仅最低的四个数据元素是可用的，所以这次最远的步骤106产生结果向量的的最后四个数 据元素。注意，虽然图3的技术也在第三步骤结束时产生四个元素并且在第四步骤结束时 产生其它四个元素，但是图3的技术需要在第一步骤输入额外数据元素S，而图7的技术可 以延迟两个步骤输入额外数据元素S以允许向量扫描运算在额外数据元素S准备好之前开 始，因而性能可以被改进。
[0092] 因此，在额外数据元素S可以被延迟的周期数目和到至少一个初始步骤结束为止 可用的结果向量R的数据元素的数目G之间存在一个权衡。通常，对于应用到M个数据元 素的向量扫描运算（其中M= 2P，M-G是2的幂），在本技术中的每个步骤执行的组合的一 般描述如下。向量扫描运算可以包括：
[0093] ?包括P个步骤的至少一个组合步骤（例如，图5中的步骤J= 0到J= 2)，其 中：
[0094] 〇对于0 <J<P，该P个步骤中的步骤J包括用于组合提供给该
[0095] 步骤的第一向量的数据元素[m]与[m-2l,以产生由该步骤输出的第二
[0096] 向量的元素[m]的组合运算，其中m <N;
[0097] 〇对于log2(M_G)彡J < P，该P个步骤中的步骤J包括用于组合第一向量 的数据元素[q]与额外数据元素S，以产生第二向量的数据元素[q]的组合运算，其中 2 J-(M-G) ^ q < 2J；
[0098] ?至少一个进一步步骤，包括用于组合该至少一个额外数据元素S与提供给该至 少一个进一步步骤的第一向量的数据元素[k]的组合运算，其中G<k<N。
[0099] N是在该特定步骤中需要产生的结果向量的数据元素的数目（例如，在一些数据 元素被屏蔽的情况下，N可以小于M)。
[0100] 虽然图5-7示出了至少一个组合步骤在至少一个进一步步骤之前被执行的示例， 但是也能够以不同顺序执行这些步骤。例如，进一步步骤可以被首先执行，或穿插在其它步 骤中间被执行。同样，所述P个步骤能够以不同顺序被执行。
[0101] 图8示出了使用掩码信息110控制向量扫描运算的第一示例（该示例对应于图5， 但是其它实施例也能够以类似方式使用掩码）。掩码运算的每一位对应于源向量的一个元 素，并且如果屏蔽位（maskbit)是1，则相应向量元素是要被处理的被选择的（有效）元 素，并且如果屏蔽位是0,则向量元素不被选择用于处理。因此，在图8的示例中，仅选择向 量的最低的五个元素。被选择的元素的处理以与图5的示例中所示的相同方式进行。然而， 屏蔽位0禁止源向量元素V[5]至V[7]的输入，从而使得这些元素中的值被有效地当作x对 待（"不在乎"值一不管它们是〇还是1)。对于每个组合，如果一个输入是"x"并且其它输 入不是"X"，则"非x"输入被转发到输出。如果两个输入都是"X"，则输出也被设置为"X"。 因此，由第一步骤100产生的元素[5]至[7]分别具有V4、x和x的值。第二步骤102和第 三步骤104以与图5相同的方式进行。因为到第三步骤结束为止最低的五个元素的结果是 可用的（S到1的组合已经完成），所以不需要第四步骤106并且因此可以省略该步骤。
[0102] 类似地，图9示出了掩码将位于非相邻位置的多个离散元素设置为未被选择的元 素的示例。在该示例中，向量元素[1]、[5]、和[7]被使用屏蔽位0标记为未被选择。此外， 未被选择的元素被当作X对待（"不在乎")，因此来自这些元素的值VpVjPV7在第一步骤 100中不被向前传播。这意味着对应于被选择的元素的结果元素取仅被选择的元素的总和 的值（跳过未被选择的元素）。例如，结果数据元素R[6]具有值V6+V4+V3+V2+VS，该值不 包括未被选择的元素的值％和Vi。此外，因为到第三步骤104结束为止全部需要的元素已 经准备好，所以不需要进一步步骤106。通常，对于值N被选择从而使得N-1对应于向量的 最后被选择的元素的索引的情况，如果N<G(G是通过仅执行第一步骤到第三步骤100-104 可获得的数据元素的数目），则最后步骤106可以被跳过。
[0103] 图8和图9示出了未被选择的元素的处理正常进行，但是值被设置为0的示例。也 可以完全禁止处理这些元素。图8和图9示出了使用掩码信息限定被选择的元素和未被选 择的元素的示例，但是也可以使用其它类型的控制信息，诸如向量长度参数或向量格式信 息。
[0104] 此外，对应于未被选择的元素的结果数据元素可以被设置为不同的值。图9示出 了可以与向量扫描运算并行或串行执行的写回运算112,该写回运算112将值写入结果向 量的未被选择的元素。由"一"指示的结果向量的元素不被写回运算修改。图9示出了源 寄存器的未被选择的元素的值被写入目标寄存器的相应位置的示例（这可以通过反转掩 码并使用反转后的掩码来控制寄存器写入实现）。在其它示例中，预定值（诸如〇或全部1 位）可以被写到未被选择的元素，或结果向量的未被选择的元素中存储的先前值可以被保 留（例如，如果使用寄存器重命名，则仍需要写回运算）。
[0105] 图5至图9示出了使用能够并行执行8个组合的扫描单元12a处理8元素向量的 示例。也可以使用具有较小数据路径宽度的扫描单元12a使得扫描单元12a仅并行处理一 些数据元素。这对减少执行向量扫描运算的硬件成本是有用的。对于这样的扫描单元12a， 向量扫描运算可以被分成单独的分区运算，上述单独的分区运算一起提供与对全部数据元 素执行扫描运算相同的结果。图10示出了应用到图4的现有技术的分区扫描运算的示例， 但是图10本身不是现有技术。在图10的示例中，扫描运算在多个步骤120-128中被执行。 步骤120至124对应于使用源向量的元素V[0]至V[3]和额外数据元素S执行的第一分区 扫描运算132,步骤126至128对应于使用源向量的较高的四个元素V[4]至V[7]和第一 分区扫描运算132产生的结果元素R[3]的第二分区扫描运算134。当仅应用到较低的四 个元素[0]至[3]时，第一分区132的步骤120、122和124执行与图4的第一、第二和第四 步骤相同的组合。类似地，对于较高的四个元素[4]至[7]，第二分区134的步骤126、127 和128对应于图4的第一、第二和第四步骤。因为在第二分区134的步骤126、127与第一 分区132的步骤120至124之间没有依存关系，所以这些步骤可以被交织从而使用具有较 窄数据路径宽度的扫描处理单元12a来相对高效地执行扫描运算。
[0106] 图11和图12示出了执行应用到图5中所示的本技术的扫描运算的类似分区扫描 的示例。图11示出了第一分区140包括与图5的步骤1至3相同但是仅对元素[0]至[3] 执行的步骤130、131和132的第一示例。这使得第一分区产生的3个元素到步骤131结束 为止已经准备好。然而，如图11所示，如果第二分区142是使用分别对应于与步骤130、131 和132相同的组合运算的步骤133、134和135执行的，则需要第二分区等待直到第一分区 140的最后步骤132结束为止，因为第二分区的步骤133依赖于第一分区的步骤132产生的 元素R[3]。因此，使用该方法，向量扫描需要6个步骤。
[0107] 图12示出了实现使用本技术的分区扫描的更高效的方式。在该示例中，第一分区 140与图11中的相同，其包括步骤130、131和132。然而，第二分区142以与图10中的第二 分区134相同的方式使用步骤126、127和128被执行。这意味着第二分区142的步骤126 和127独立于第一分区的步骤130至132并且因此可以被交织，以便第二分区142可以更 早地开始，从而减少了执行作为整体的运算的周期数目。然而，与图10不同，如果需要少于 4个数据元素，则第一分区的一些步骤可以被省略以改进性能。因此，组合图5的顺序或用 于第一分区的其它实施例与用于后续分区的不同顺序的混合方 法可以改进分区扫描运算 的性能。
[0108] 因此，图5-7所示的顺序或其它示例不需要被应用到扫描运算中正被处理的全部 向量。可以仅向源向量的M个数据元素应用上述技术（例如，在图12中，M= 4)，并且可以 使用不同顺序的组合运算来处理相同向量的剩余数据元素。
[0109] 图13示出了向量扫描单元12a的示例。向量扫描单元12a可以具有多个扫描阶 段150。为了执行前面示例中指示的向量扫描运算的单个步骤，向量可以被传递通过每个扫 描阶段150以便到最后扫描阶段结束为止，扫描运算的该步骤产生的向量是可用的。上述 的旁通路径13可以用于将最后扫描阶段的结果转发回到第一扫描阶段用于后续步骤。在 一些示例中，可以有不止两个扫描阶段。
[0110] 图14示出了当向量扫描运算被以图11中所示的方式分区时，图13中所示的扫 描单元12a的流水线利用率的示例。扫描运算的每个步骤需要两个周期，一个周期在第一 扫描阶段〇中，另一个周期在第二扫描阶段1中。在图11的示例中，扫描运算的不同步骤 之间的依赖性意味着扫描运算的步骤不能相互交错，因为每个步骤必须等待在前步骤的结 果。这意味着需要12个周期。与之相比，图15示出了图12的示例的相应流水线利用率。 在这种情况中，扫描运算的不同扫描分区之间存在较少的依赖性，因此分区的不同步骤可 以交错，从而使得当一个步骤在第二扫描阶段时，对应于另一分区的另一个步骤由第一扫 描阶段处理。如图15中所示，这意味着与图11相比，使用图12的方法，流水线利用率可以 更高并且整体运算可以在更少的周期中被完成。
[0111] 因此，本技术自身非常适于处理分区扫描中的多个分区的第一分区，但是后续分 区可以使用组合运算的不同顺序被更高效地执行。
[0112] 本技术对执行分段扫描的系统也是有用的，其中对向量中的不同分段的数据元素 执行单独扫描。图16示出了应用到图4的现有技术的扫描运算时的分段扫描的概念，但是 图16本身不是现有技术。分段信息200被提供以指示源向量V的数据元素的不同分段之 间的边界。分段掩码200内的每个'1'位指示一个分段和另一个分段之间的边界（标记为 ' 1'位的元素是分段的最后元素，下一个元素将开始新分段）。对于分段0 (在该示例中包 括元素[0]至[3])，使用额外数据元素S和该分段的元素执行扫描运算。对于任何进一步 分段（例如，该示例中的包括元素[4]至[7]的分段1)，该分段的向量元素被组合，但不包 括额外数据元素。组合运算以与图4相同的方式进行，但是掩码被用于禁用不同分段中的 元素之间的任何组合（如图16中的虚线指示的）。这可以通过以图16的顶部所示的方式 对掩码进行移位产生用于随后步骤的掩码来实现。对于第一步骤，掩码以其初始形式被应 用。对于第二步骤，掩码200被向下移位一个位置，并且如图16的202部分所示产生两个 掩码的逻辑或。对于第三步骤，来自第二步骤的掩码被向下移位两个位置，并且被与先前掩 码进行逻辑或运算（参见图16的204部分）。当使用更多数据元素处理向量时，对于任何 后续步骤，掩码将继续以对每个步骤增加2的幂的增量向下移位，然后与之前步骤的掩码 进行逻辑或运算。图16的最后步骤简单地将额外数据元素S加到第一分段0内的任意元 素。也可以使用之前步骤的掩码来控制该步骤。图16中所示的方法意味着需要全部步骤 来执行扫描运算，因为额外数据元素S直到最后步骤才被输入。
[0113] 图17示出了使用图5的实施例的组合运算的顺序的分段扫描的示例。以与图16 相同的方式生成用于每个步骤的掩码。然而，通过改变图5中的组合顺序，到第三步骤结束 为止更多的结果数据元素可用。因为第四步骤仅包括额外数据元素S与第三步骤产生的最 后元素[7]的组合，并且在仅有一个分段（即掩码完全是0)的情况下仅需要该组合，所以 在存在不止一个分段的情况下，不管分段的位置或分段的数目，最后步骤可以被省略。因 此，图5中所示的向量扫描运算自身非常适于分段扫描运算，因为其经常能够减少针对分 段扫描执行的步骤的数目。类似地，图6和图7中的示例可以使用分段扫描运算被实施，并 且当存在多个分段时这有助于减少所需步骤的数目。
[0114] 图18示出了执行向量扫描运算的示例方法。在步骤300,处理电路4接收向量扫 描微运算，该向量扫描微运算将使用源向量的M个元素和额外数据元素S被执行。额外数 据元素S可以是例如，在先运算的进位值、向量元素、或标量值。向量扫描运算具有相关联 的控制信息，该控制信息指定要被扫描的N个元素作为使用额外数据元素的序列（如图8 和图9所示，如果剩余的元素被屏蔽，或者如图16和图17所示，如果剩余的元素是不使用 额外数据元素S的后续分段的部分，则N可以小于M)。
[0115] 响应于向量扫描运算，在步骤302,确定N是否大于G，G是可以使用至少一个组合 步骤产生的结果数据元素的数目。如果N>G，则在步骤304,扫描单元12a执行用于产生 G个结果数据元素的至少一个组合步骤和用于产生元素[G]至[N-1]的至少一个进一步步 骤。换句话说，如果N<G，则在步骤306,扫描单元12a执行至少一个组合步骤，但省略至 少一个进一步步骤。在步骤308,输出包含结果数据元素的结果向量。
[0116] 图19至23示出了当执行不同类型的处理算法时观察向量扫描运算的使用的分 析。图19示出，当被应用到对于不同数据路径宽度的反向传播算法（BackProp)和稀疏矩 阵向量相乘算法（SpMV)时，观察的对于分段向量扫描使用不同数目的分段的指令百分比。 可以看出，与执行使用128位数据路径的SpMV算法不同，大多数分段指令计算至少两个分 段，并且因此将从本技术获益，其中当有两个或更多个分段时，该进一步步骤可以被省略。
[0117] 图20和图21示出了计算出的分段的平均数目和分别执行具有不同大小的矩阵的 SpMV算法的潜在性能优势。如图21所示，当比较相对于标量运算的加速时可以看出，使用 分段扫描获得的性能对大小在25X25和100X100元素之间的矩阵特别有利。通过与图20 进行比较表明，平均在至少1.5个分段上运算的分段指令提供了改进的性能，从而使得性 能收益补偿了与控制分段扫描相关联的计算开销。这支持使用可以加速使用不止一个分段 的分段扫描的本技术。
[0118] 对于未被分段的扫描，图22和图23示出了指令使用的平均向量长度的分析。图 22示出了对不同的基准算法使用256位宽度的数据路径处理的32位数据元素的示例。如 图22中所示，有相当大比例的指令仅使用8数据元素向量的2或5个数据元素。虽然在处 理具有2个有效元素的8元素向量时图3的现有技术能够减少步骤数目，但是该技术对具 有5个有效元素的向量不起作用。与之相比，即使当M元素向量的有效元素的数目在M/2 和M之间时，本技术也可以减少步骤数目。因此，图22支持本技术为相当大数目的指令提 供有用的性能改进的事实。换句话说，如图23中所示，对于256位宽度数据路径处理具有 16位元素的向量，在这种情况下，使用少于全部数目的数据元素的指令的比例是微不足道 的。每当期望有相当多的不全部利用向量大小的指令时，系统设计者可以选择本技术。
[0119] 图24示出了可以使用的虚拟机实现。虽然前面描述的实施例以用于操作支持相 关技术的专用处理硬件的设备和方法实现本发明，但是还可以提供硬件设备的所谓的虚拟 机实现。这些虚拟机实现在通常运行支持虚拟机程序402的主操作系统404的主处理器 406上运行。一般，需要大规模的强大处理器来提供以合理速度执行的虚拟机实现，但是此 方法在某些情况下被证明是合理的，诸如当为了兼容或重复使用的原因希望运行对于另一 处理器而言处于本地的代码。虚拟机程序402能够执行应用程序（或操作系统）400,以提 供与由真实的硬件装置执行程序所提供的结果相同的结果。因此，包括控制上述存储器访 问的程序指令可以在使用虚拟机程序402的应用程序400内部被执行。
[0120] 虽然本发明的示意性实施例已经参考附图在此被详细地描述，但是应该理解本发 明不限于那些明确的实施例，在不偏离由所附权利要求限定的范围和精神的情况下，本领 域的技术人员可以进行多种变化和/或修改。
【主权项】
1. 一种数据处理设备，包括： 向量寄存器存储器，该向量寄存器存储器被配置为存储包括多个数据元素的向量操作 数； 处理电路，该处理电路被配置为处理来自所述向量寄存器存储器的向量操作数；以及 控制电路，该控制电路被配置为控制所述处理电路对源向量操作数的M个数据元素V[0]至V[M-1]和至少一个额外数据元素S执行向量扫描运算，以产生结果向量操作数的M 个数据元素R[〇]至R[M-1]，其中，对于N彡M且O彡i<N，所述结果向量操作数的数据元 素R[i]具有对应于所述至少一个额外数据元素S和所述源向量操作数的至少一些数据元 素V[0]至V[i]的组合的值； 其中，所述控制电路被配置为控制所述处理电路在多个步骤中执行所述向量扫描运 算，每个步骤用于从第一向量产生第二向量，其中，用于第一步骤的第一向量包括所述源向 量操作数的数据元素，并且用于其他步骤的第一向量包括在前步骤的第二向量，每个步骤 包括用于组合所述第一向量的数据元素与所述至少一个额外数据元素S或所述第一向量 的另一个数据元素以产生所述第二向量的数据元素的至少一个组合运算； 所述多个步骤中的至少一个步骤包括并行执行的多个组合运算；并且 所述多个步骤中的至少两个步骤包括用于组合所述第一向量的数据元素与所述至少 一个额外数据元素S的组合运算。2. 根据权利要求1所述的数据处理设备，其中，M是2的幂。3. 根据权利要求2所述的数据处理设备，其中，至少在N>G，M/2 <G<M的情况下， 所述控制电路被配置为控制所述处理电路执行包括至少一个组合步骤和至少一个进一步 步骤的所述多个步骤，所述至少一个组合步骤用于产生所述结果向量操作数的G个数据元 素R[0]至R[G-1]，所述至少一个进一步步骤在除了所述至少一个组合步骤之外被额外执 行时用于产生所述结果向量操作数的数据元素R[G]至R[M-1]。4. 根据权利要求3所述的数据处理设备，其中，在M/2 <N<G的情况下，所述控制电 路被配置为控制所述处理电路执行所述至少一个组合步骤并且省略所述至少一个进一步 步骤。5. 根据权利要求3和4中任一项所述的数据处理设备，其中，所述至少一个进一步步骤 包括用于组合所述第一向量的数据元素与所述至少一个额外数据元素S的至少一个组合 运算，并且不包括任何用于组合所述第一向量的数据元素与所述第一向量的另一个数据元 素的组合运算。6. 根据权利要求3至5 中任一项所述的数据处理设备，其中，至少在N>G的情况下： 所述至少一个组合步骤是这样的步骤：如果所述至少一个组合步骤是由所述处理电路 在不执行所述至少一个进一步步骤的情况下执行的，则所述处理电路将在所述至少一个组 合步骤的最后步骤产生所述第二向量的数据元素[G]至[M-1]，其中，对于G<k<M，所述 第二向量的数据元素[k]具有对应于所述源向量操作数的至少一些数据元素V[0]至V[k] 的组合的值；并且 在所述至少一个进一步步骤中，所述控制电路被配置为控制所述处理电路，对于G<k<N，执行用于组合所述至少一个额外数据元素S与用于所述至少一个进一步步骤的所述 第一向量的数据元素[k]的组合运算。7. 根据权利要求3至6中任一项所述的数据处理设备，其中，M= 2p并且所述至少一个 组合步骤包括用于响应于第一向量的数据元素[0]至[M-1]产生第二向量的数据元素[0] 至[M-1]的P个步骤；并且 对于〇 <J<P，所述P个步骤中的步骤J包括用于组合所述第一向量的数据元素[m] 与所述第一向量的数据元素[m_2l以产生所述第二向量的数据元素[m]的组合运算，其中 2J<m<N08. 根据权利要求7所述的数据处理设备，其中，M-G是2的幂，并且对于log2 (M-G) <J <P，所述P个步骤中的步骤J包括用于组合所述第一向量的数据元素[q]与所述额外数据 元素S以产生所述第二向量的数据元素[q]的组合运算，其中Y-(M-G) <q< 21。9. 根据权利要求3至8中任一项所述的数据处理设备，其中，所述控制电路被配置为控 制所述处理电路输出对应于所述结果向量操作数的数据元素R[N_1]的进位值； 其中，在所述至少一个进一步步骤被省略的情况下，所述控制电路被配置为控制所述 处理电路比在所述处理电路执行所述至少一个进一步步骤的情况下更早地输出所述进位 值。10. 根据上述任一项权利要求所述的数据处理设备，其中，所述向量扫描运算与识别所 述源向量操作数的哪些数据元素是被选择的数据元素的控制信息相关联，并且所述控制电 路被配置为控制所述处理电路在所述向量扫描运算中处理所述被选择的数据元素。11. 根据权利要求10所述的数据处理设备，其中，N的取值使得V[N_1]是由所述控制 信息指示的所述源向量操作数的最后被选择的数据元素。12. 根据权利要求10和11中任一项所述的数据处理设备，其中，所述控制电路被配置 为控制所述处理电路将对应于所述源向量操作数的未被选择的数据元素的所述结果向量 操作数的数据元素设置为下面各项之一： (i) 预定值； (ii) 通过利用被设置为预定值的所述源向量操作数的未被选择的数据元素执行所述 向量扫描运算确定的值； (iii) 用于存储所述源向量操作数的源寄存器中的相应数据元素的值；以及 (iv) 用于存储所述结果向量操作数的目标寄存器中的相应数据元素的值。13. 根据上述任一项权利要求所述的数据处理设备，其中，所述向量扫描运算与识别所 述源向量的一个或多个分段的分段信息相关联，每个分段包括一个或多个数据元素； 其中，在所述分段信息识别多个分段的情况下，所述控制电路被配置为控制所述处理 电路对所述多个分段中的第一分段的数据元素执行所述向量扫描运算。14. 根据权利要求13所述的数据处理设备，其中，N的取值使得V[N-1]是所述第一分 段的最后被选择的数据元素。15. 根据权利要求13和14中任一项所述的数据处理设备，其中，在所述分段信息识别 多个分段的情况下，所述控制电路被配置为控制所述处理电路针对不同于所述第一分段的 进一步分段产生所述结果向量操作数的相应进一步分段内的至少一个结果数据元素，所述 相应进一步分段内的每个结果数据元素具有对应于所述源向量操作数的所述进一步分段 的一个或多个数据元素的组合的值。16. 根据从属于权利要求3的权利要求13至15中任一项所述的数据处理设备，其中， G=M-1，并且在所述分段信息识别多个分段的情况下，所述控制电路被配置为控制所述处 理电路省略所述向量扫描运算的所述至少一个进一步步骤。17. 根据上述任一项权利要求所述的数据处理设备，其中，所述源向量操作数包括X个 数据元素，其中X多M，并且所述结果向量操作数包括Y个数据元素，其中Y多M。18. 根据权利要求17所述的数据处理设备，其中，所述控制电路被配置为控制所述处 理电路对所述源向量操作数的L个数据元素执行所述向量扫描运算，以产生所述结果向量 操作数的L个数据元素，其中L<X并且L<Y;并且 如果L>M，则所述结果向量操作数的L个数据元素包括L-M个进一步数据元素R[M] 至R[L_1]，其中对于MSi<L，结果数据元素R[i]具有对应于结果数据元素R[M-1]与所 述源向量操作数的至少一些数据元素V[M]至V[i]的组合的值。19. 根据权利要求18所述的数据处理设备，其中，在L>M的情况下N=M，并且在 L彡M的情况下N=L。20. 根据权利要求17至19中任一项所述的数据处理设备，其中，在所述多个步骤中的 每个步骤，所述处理电路被配置为并行地产生所述第二向量的最多M个数据元素；并且 如果L>M，则所述控制电路被配置为控制所述处理电路分别针对所述源向量操作数 的多个组的数据元素执行分区扫描运算，每个组包括M个数据元素或更少的数据元素。21. 根据从属于权利要求3的权利要求20所述的数据处理设备，其中，如果L>M，则 所述控制电路被配置为控制所述处理电路利用所述多个步骤中的至少两个步骤针对所述 多个组中的第一组执行所述分区扫描运算，所述至少两个步骤包括用于组合所述第一向量 的数据元素与所述至少一个额外数据元素S的组合运算，并且所述多个步骤包括所述至少 一个组合步骤和所述至少一个进一步步骤。22. 根据权利要求21所述的数据处理设备，其中，如果L>M，则对于不同于所述第 一组的至少一个进一步组，所述控制电路被配置为控制所述处理电路执行所述分区扫描运 算，所述分区扫描运算包括： 至少一个预备步骤，所述至少一个预备步骤包括用于组合所述进一步组的数据元素的 各个数据元素的至少一个组合运算； 至少一个额外步骤，所述至少一个额外步骤包括用于组合在针对所述进一步组的所述 至少一个预备步骤中产生的数据元素与在针对所述第一组的数据元素的所述分区扫描运 算中产生的数据元素的至少一个组合运算。23. 根据权利要求22所述的数据处理设备，其中，所述控制电路被配置为控制所述处 理电路执行与针对所述第一组的数据元素的所述分区扫描运算相交错的针对所述进一步 组的数据元素的所述至少一个预备步骤。24. 根据上述任一项权利要求所述的数据处理设备，其中，所述至少一个额外数据元素 S包括下面各项之一： 标量操作数； 向量操作数的数据元素； 使用向量操作数的多个数据元素确定的值；以及 通过另一个向量运算确定的进位值。25. -种数据处理设备，包括： 向量寄存器存储装置，该向量寄存器存储装置用于存储包括多个数据元素的向量操作 数； 处理装置，该处理装置用于处理来自所述向量寄存器存储装置的向量操作数；以及 控制装置，该控制装置用于控制所述处理装置对源向量操作数的M个数据元素V[0]至V[M-1]和至少一个额外数据元素S执行向量扫描运算，以产生结果向量操作数的M个数据 元素R[〇]至R[M-1]，其中对于N彡M且0彡i<N，所述结果向量操作数的数据元素R[i] 具有对应于所述至少一个额外数据元素S和所述源向量操作数的至少一些数据元素V[0] 至V[i]的组合的值； 其中，所述控制装置被配置为控制所述处理装置在多个步骤中执行所述向量扫描运 算，每个步骤用于从第一向量产生第二向量，其中用于第一步骤的第一向量包括所述源向 量操作数的数据元素，并且用于其他步骤的第一向量包括在前步骤的第二向量，每个步骤 包括用于组合所述第一向量的数据元素与所述至少一个额外数据元素S或所述第一向量 的另一个数据元素以产生所述第二向量的数据元素的至少一个组合运算； 所述多个步骤中的至少一个步骤包括并行执行的多个组合运算；并且 所述多个步骤中的至少两个步骤包括用于组合所述第一向量的数据元素与所述至少 一个额外数据元素S的组合运算。26. -种数据处理方法，用于对源向量操作数的M个数据元素V[0]至V[M-1]和至少 一个额外数据元素S执行向量扫描运算以产生结果向量操作数的M个数据元素R[0]至 R[M_1]，其中，对于N彡M且O彡i<N，所述结果向量操作数的数据元素R[i]具有对应于 所述至少一个额外数据元素S和所述源向量操作数的至少一些数据元素V[0]至V[i]的组 合的值；所述方法被使用处理电路执行并且包括： 执行用于从第一向量产生第二向量的多个步骤，其中用于第一步骤的第一向量包括所 述源向量操作数的数据元素，并且用于其他步骤的第一向量包括在前步骤的第二向量，每 个步骤包括用于组合所述第一向量的数据元素与所述至少一个额外数据元素S或所述第 一向量的另一个数据元素以产生所述第二向量的数据元素的至少一个组合运算； 其中，所述多个步骤中的至少一个步骤包括并行执行的多个组合运算；并且 所述多个步骤中的至少两个步骤包括用于组合所述第一向量的数据元素与所述至少 一个额外数据元素S的组合运算。27. -种存储计算机程序的计算机可读存储介质，所述计算机程序在被计算机执行时 控制所述计算机提供根据权利要求1至24中的任一项所述的设备的虚拟执行环境。28. -种基本上如这里参考附图描述的数据处理设备。29. -种基本上如这里参考附图描述的数据处理方法。30. -种基本上如这里参考附图描述的计算机可读存储介质。
【专利摘要】公开了用于执行向量扫描运算的数据处理设备和方法。向量扫描运算被执行以产生结果向量的M个数据元素，其中每个结果数据元素对应于额外数据元素S与源向量操作数V的至少一些数据元素的组合。向量扫描运算被使用多个步骤执行，每个步骤包括用于组合数据元素的一个或多个组合运算。这些步骤中的至少一个步骤包括两个或多个并行执行的组合运算。这些步骤中的至少两个步骤包括用于组合数据元素与额外数据元素S的组合运算。该方法使得向量扫描运算在少于M个数据元素有效的情况下能够以更少的步骤被执行，从而使得向量扫描运算可以被更快地执行。
【IPC分类】G06F17/16
【公开号】CN104899180
【申请号】CN201510089213
【发明人】马蒂亚斯·伯特歇尔, 贾科莫·加布雷利, 姆布·埃约勒-莫诺诺
【申请人】Arm 有限公司
【公开日】2015年9月9日
【申请日】2015年2月27日
【公告号】US20150254076
【技术领域】
[0001] 本技术涉及数据处理领域。更具体地，本技术涉及用于执行向量扫描运算的数据 处理设备和方法。
【背景技术】
[0002] 一种改进数据处理设备的性能的已知技术是提供电路来支持向量运算的执行。在 至少一个向量操作数上执行向量运算，其中每个向量操作数包括多个向量元素。执行向量 运算涉及在一个或多个向量操作数内的各种向量元素上重复地应用运算。在支持执行向量 运算的典型数据处理系统中，提供向量寄存器文件用于存储向量操作数。与执行等价的系 列标量运算相比，通过使用向量运算可以实现显著的性能优势。
[0003] -种已知类型的向量运算是向量扫描运算，其中预定的组合运算被重复应用到增 加数目的数据元素。组合运算可以采用多种形式，诸如加法运算、乘法运算、最小值选择运 算、最大值选择运算等。作为执行向量扫描运算的结果，结果序列被生成，其中每个结果与 应用组合运算到不同数目的数据元素有关。作为具体示例，扫描运算可以指定加法运算作 为组合运算，并且这种扫描加法运算有时被称为前缀求和运算。考虑输入数字序列Xd，Xp x2,...，应用扫描加法运算产生了结果序列y(l，yi，y2,...，其中：
[0004] yQ=x〇，yfXQ+Xpy2=XQ+Xi+x"依次类推。
[0005] 在向量扫描运算的一些示例中，额外数据元素S可以与源向量的向量数据元素V 组合以产生一系列结果（在扫描加法运算的情况下）：
[0006] 丫。=S+x。，yfS+Xo+Xpy2=S+Xo+Xi+Xy依次类推。
[0007] 本技术寻求提供用于执行这样的向量扫描运算的改进设备和方法。
【发明内容】
[0008] 根据一个方面，本技术提供了一种数据处理设备，包括：
[0009] 向量寄存器存储器，该向量寄存器存储器被配置为存储包括多个数据元素的向量 操作数；
[0010] 处理电路，该处理电路被配置为处理来自向量寄存器存储器的向量操作数；以及
[0011] 控制电路，该控制电路被配置为控制处理电路对源向量操作数的M个数据元素 V[0]至V[M-1]和至少一个额外数据元素S执行向量扫描运算，以产生结果向量操作数的M 个数据元素R[0]至R[M-1]，其中对于N彡M且0<i<N，结果向量操作数的数据元素R[i] 具有对应于至少一个额外数据元素S和源向量操作数的至少一些数据元素V[0]至V[i]的 组合的值；
[0012] 其中，控制电路被配置为控制处理电路在多个步骤中执行向量扫描运算，每个步 骤用于从第一向量产生第二向量，其中用于第一步骤的第一向量包括源向量操作数的数据 元素，并且用于其他步骤的第一向量包括在前步骤的第二向量，每个步骤包括用于组合第 一向量的数据元素与至少一个额外数据元素S或第一向量的另一个数据元素以产生第二 向量的数据元素的至少一个组合运算；
[0013] 所述多个步骤中的至少一个步骤包括并行执行的多个组合运算；并且
[0014] 所述多个步骤中的至少两个步骤包括用于组合第一向量的数据元素与至少一个 额外数据元素S的组合运算。
[0015] 虽然可以使用串行执行的标量运算来执行向量扫描运算，但是这样做非常慢并且 由于性能原因，并行执行至少一些组合是有用的。然而，虽然已知的并行技术可以相对高效 地组合向量数据元素的两个数字的幂，但是当额外数据元素S同样地需要与向量数据元素 组合时，可能需要额外的步骤。现有技术要么在组合源向量操作数的不同向量元素之前，在 初始步骤中组合额外数据元素S与源向量操作数的数据元素，要么首先执行源向量内的不 同数据元素的全部组合，然后执行额外步骤用于组合额外数据元素与在前面的步骤中产生 的每个数据元素。不论哪种方式，都需要额外步骤。
[0016] 本技术的发明人意识到并不是源向量操作数的全部M个数据元素都是受关注的。 例如，可能没有足够的数据来完全填充源向量操作数的M个数据元素，因此仅需要产生结 果操作数的N个数据元素（其中N<M)。用于执行向量扫描运算的已知并行技术不考虑这 一点并且代替地专注于对全部M个数据元素执行扫描运算。发明人意识到，通过改变执行 向量扫描运算的方式，有可能在仅需要一些结果数据元素的情况下更快地执行运算，并且 在期望全部M个结果数据元素的情况下不需要增加步骤的数目。
[0017] 为了实现这一点，本技术的处理电路在多个步骤中执行向量扫描运算，每个步骤 从第一向量产生第二向量，其中用于第一步骤的第一向量包括来自源向量操作数的数据元 素，并且用于其他步骤的第一向量包括来自在前步骤的第二向量。所述步骤中的至少两个 步骤包括用于组合第一向量的数据元素与至少一个额外数据元素S的组合运算（与此相 反，已知技术仅包括一个这样的步骤）。通过在向量扫描运算的多个步骤中组合至少一个额 外元素S，有可能在最后步骤开始前获得结果向量的更多数据元素，从而可以在需要少于M 个数据元素时更快地执行向量扫描运算。
[0018] M可以是2的幂。当N在M/2和M之间时，现有技术不能比在产生全部M个数据元 素时更快地执行扫描运算，因为使用2的更小幂作为M是不可能的。然而，在本技术中，当 N在M/2和M之间时，可以减少所需步骤的数目。
[0019] 可以执行向量扫描运算以在至少一个组合步骤中产生结果向量操作数的第一G 个数据元素R[0]至R[G-1](其中M/2<G<M)。如果需要多于G个数据元素（N>G)，则 可以通过在至少一个组合步骤外额外执行至少一个进一步步骤了产生结果向量操作数的 其它数据元素R[G]至R[M-1]。这允许在比现有技术更少的向量运算步骤中产生少于M个 数据元素，从而改进性能。
[0020] 如果M/2 <N彡G，则至少一个进一步步骤可以被省略，从而使得该运算可以使用 至少一个组合步骤被更快地执行，并且处理电路可以比至少一个进一步步骤被执行时更快 地开始执行另一个运算。可替换地，即使需要G个以下数据元素，也可以执行至少一个进一 步步骤（如果至少一个进一步步骤是在至少一个组合步骤之后被执行的，则仍能提供性能 改进，因为该G个数据元素仍将比现有技术更早地可用）。当N<M/2时，可以省略向量扫 描运算的更多步骤。对于N<M/2,该处理可以被以与M是2的更小幂时相同的方式对待。
[0021] 至少一个进一步步骤可以包括用于组合第一向量的数据元素与至少一个额外数 据元素的至少一个组合运算，并且可以不包括第一向量的各个数据元素的任意组合。这意 味着可以在相对于至少一个组合步骤的任何时间执行该进一步步骤（在至少一个组合步 骤之前、在至少一个组合步骤之后、或作为穿插在至少一个组合步骤中的中间步骤）。更具 体地，至少一个进一步步骤可以包括用于组合至少一个额外数据元素S与用于该至少一个 进一步步骤的第一向量的数据元素[k]的组合运算，其中G<k<N。这些组合可以对应于 对全部M个数据元素执行向量扫描运算所需要的组合，但是这些组合不是通过至少一个组 合步骤被执行的。
[0022] 另一方面，至少一个组合步骤可以是这样的步骤：在没有进一步步骤被执行的情 况下，该至少一个组合步骤的最后步骤产生结果数据元素R[0]至R[N-1]、和该步骤的第二 向量的数据元素[G]至[M-1]，其中对于G<k<M，第二向量的数据元素[k]具有对应于 源向量操作数的至少一些数据元素V[0]至V[k]的组合的值（即，不与额外数据元素S组 合）。
[0023] 通常，对于M= 2P，至少一个组合步骤可以包括P个步骤，该P个步骤包括用于响 应于第一向量的数据元素[0]至[M-1]产生第二向量的数据元素[0]至[M-1]的组合运算， 从而对于0 <J<P，所述P个步骤中的步骤J包括用于组合第一向量的数据元素[m]与第 一向量的数据元素[m-f]以产生第二向量的数据元素[m]的组合运算，其中f彡m<N。
[0024] 这些组合可以确保数据元素V[0]，V[0]和V[l]，V[0]、V[l]和V[2]等的组合可 以在尽可能的最少步骤中被执行。虽然控制电路被配置为控制处理电路执行这些步骤，但 是每个步骤内的一些组合可以被省略（例如，如果将通过该步骤被处理的数据元素未被选 择用于基于掩码信息的处理）。另外，虽然P个步骤中的每个步骤被定义为具有针对元素 [21至元素[N-1]的组合运算，但是这些组合也可能继续到元素[M-1]，从而使得对正被处 理的M个数据元素的块中的全部数据元素执行该组合，即使当被选择的元素的数目N小于 皿时。
[0025] 在本申请中，数据元素索引[0]、[1]等被用于指代正在被向量扫描运算处理的数 据元素相对于其它元素的位置，其不必与数据元素被存储在向量寄存器中的位置相同。源 向量操作数和结果向量操作数的哪些数据元素对应于元素[0]、[1].....[M-1]可以是任 意的设计选择。例如，一些系统可以将源向量寄存器内的最低有效位上的元素当作元素 [0]，并且将源向量寄存器内的最高有效位上的元素当作元素[M-1]，然而在其它系统中可 以是与之相反的方式。也可以使用数据元素的更多的任意分配。因此，例如，向量扫描运算 中的元素V[0]和V[l]的组合可以实际上对应于向量寄存器内的非相邻位置上的元素。移 位电路可以被用于将数据元素移位到所需位置用于向量扫描运算。
[0026] 另外，用于至少一个组合步骤的各个步骤的索引J被用于限定在该步骤中执行的 组合运算。至少一个组合步骤不是必须按照J的升序被执行。虽然在一个实施例中P个步 骤可以按照J= 〇、1.....P-1的顺序被执行，但是在其它实施例中该P个步骤可以按照不 同的顺序（例如l、2、p-l、0、...）被执行。
[0027] 至少一个组合步骤也可以包括用于组合至少一个额外数据元素S与向量数据元 素的各种组合运算。取决于在至少一个进一步步骤不被执行的情况下需要产生结果向量操 作数的多少个数据元素（G)，额外数据元素S可以被输入并且在不同步骤中与源向量的元 素组合。通常，G可以被选择成使得M-G是2的幂，并且至少一个组合步骤的P个步骤可以 是这样的步骤：对于l〇g2(M-G) <J<P，所述P个步骤中的步骤J包括用于组合第一向量 的数据元素[q]与所述额外数据元素S以产生第二向量的数据元素[q]的组合运算，其中 2J-(M_G) <q< 2J〇
[0028] 该方法允许执行向量扫描运算，从而使得通过执行至少一个组合步骤可获得的结 果数据元素R[0]至R[G_1]的数目与向量扫描运算可以与用于产生至少一个额外数据元素 S的另一个运算相交错的程度均衡。
[0029] 对于较大值的G(例如，G=M-1提供G的最大可能值），结果数据操作数的更多数 据元素可从至少一个组合步骤获得，从而使得当至少一个进一步步骤可以被省略时有更多 机会改进性能（N更可能小于或等于G)。对于G=M-1，只有在结果向量的全部M个数据元 素需要使用扫描运算产生时，才需要至少一个进一步步骤。然而，该方法可能要求额外数据 元素S在更多步骤中被输入，因此额外数据元素S可能需要更早地可获得，从而使得向量扫 描运算可能需要等待早期运算在开始前产生额外数据元素S。
[0030] 另一方面，对于较小值的G(例如，G=M/2)，因为较少的步骤包括涉及额外数据元 素S的组合，所以至少一个额外数据元素S的输入经常被延迟。这有助于允许向量扫描运 算在额外数据元素S准备好之前开始，从而使得向量扫描运算可以更早地完成。然而，对于 较小值的G，相对于较大值的G可能需要更多的组合运算，并且省略至少一个进一步步骤的 性能改进可能不是经常可获得的，因为只有较少的N值不需要至少一个进一步步骤。
[0031] 因此，系统设计者可以根据他们的需要选择G。一些处理电路可以具有针对G的特 定值被硬连接的硬件，该硬件可以使得实现控制电路更简单。其它系统可以具有这样的控 制电路，该控制电路可以动态地配置处理电路根据额外数据元素S是否已经可获得、以及 对于特定运算需要多少数据元素N来针对不同的G值执行处理。
[0032] 除了结果数据元素R[0]至R[N-1]以外，向量扫描运算还可以产生进位值，该进位 值可以被输出用于进一步运算。例如，进位值可以被用作用于随后的向量扫描运算的额外 数据元素S。该进位值可以具有对应于结果向量操作数的数据元素R[N-1]的值。控制电路 可以控制处理电路在至少一个进一步步骤被省略的情况下比在至少一个进一步步骤被执 行的情况下更早地输出进位值，从而使得使用进位值的后续运算可以在不需要至少一个进 一步步骤的情况下更早地开始。
[0033] 所需数据元素的数目N可以小于正在被处理的块中的元素的数目M的原因在于， 向量扫描运算具有识别数据元素为被选择的数据元素或未被选择的数据元素的控制信息， 只有被选择的数据元素将被向量扫描运算处理。该控制信息例如可以是将单个数据元素识 别为被选择的或未被选择的数据元素的掩码信息、指定有多少个数据元素被选择的向量长 度信息、或识别被选择的和未被选择的元素的特定图案的向量格式信息。通常，N的取值使 得源向量操作数的元素V[N-1]是由控制信息指示的最后被选择的数据元素（可能有一些 未被选择的元素的元素索引小于N-1)。
[0034] 对于由控制信息指示的任意未被选择的数据元素，结果向量操作数中的相应数据 元素可以被设置为预定值（例如，〇)，通过利用被设置为预定值（例如，〇)的源向量操作数 的未被选择的数据元素执行向量扫描运算确定的值，或用于存储源向量操作数的源寄存器 或用于存储结果向量操作数的目标寄存器中的相应数据元素的值（在一些情况下，源寄存 器和目标寄存器可以相同）。在一些实施例中，处理未被选择的数据元素的组合运算可以被 禁止。可替换地，对应于未被选择的元素的向量扫描运算的部分可以正常进行。无论哪种 方式，结果都可以被调整为上述值中的一个，例如，通过与向量扫描运算并行地执行将需要 值写入目标寄存器的未被选择的部分的运算。
[0035]上述向量扫描运算可以使用少于M个数据元素的另一个原因在于，可以分割向量 扫描运算以便对M个数据元素内的不同分段执行不同的扫描。在这种情况下，第一分段可 以被以上述方式处理，其中N是第一分段中的数据元素的数目。如果有进一步的分段，则 可以通过组合该进一步分段内的一个或多个数据元素（但不包括至少一个额外数据元素 S)来执行扫描运算。例如，对于额外数据元素S和8个向量元素V[0]至V[7](其中，元素 V[0]至V[2]对应于第一分段，元素V[3]至V[7]对应于第二分段），可以产生如下的一系 列组合：
[0037] 当N<M时，本技术本身很适合分段扫描。如上所述，至少一个组合步骤可以产生 额外数据元素[G]至[M-1]，这些数据元素不包括额外数据元素S并且因此可以对应于第二 分段的结果数据元素。此外，当分段扫描中有至少两个分段时，组合向量的彼此相距甚远的 数据元素所需的运算更少。向量扫描运算可以被设置成使得至少一个进一步步骤提供在分 段扫描的情况下很可能不需要的这些"相距甚远"的组合，从而允许更经常地改进性能。例 如，当G=M-1时，如果有任何分段，则不需要至少一个进一步步骤，因为当G=M-1时该进 一步步骤组合额外数据元素S与最后的数据元素[M]，并且该组合在存在多个分段的情况 下是不需要的。因此，使用本技术可以加快分段扫描。
[0038] 使用如上所述的扫描运算进行处理的M个数据元素不必包括源向量操作数的全 部数据元素。例如，源向量操作数可以包括X个数据元素，其中X多M，并且结果向量操作数 可以包括Y个数据元素，其中Y多M。通常，源向量操作数和结果向量操作数具有相同数目 的数据元素（X=Y)，但是可以在将向量大小转换为更多个元素的同时执行向量扫描运算， 从而使得向量扫描运算填充比源向量大的结果向量的一些元素。
[0039] 更一般地，可以对源向量操作数的L个数据元素执行向量扫描运算，其中L<X并 且L彡Y。如果L>M，则数据元素R[0]至R[M-1]可以与上述讨论的一样，但是对于R[M] 至R[L_1]，结果数据元素可以对应于R[M-1]与索引大于M的至少一些数据元素的组合。如 果L<M，则上述讨论的N值可以对应于L，或者如果L>M，则N=M。
[0040] 以上针对M个数据元素讨论的技术不需要被应用到整个源向量操作数。对于L> M，仅对M个数据元素使用以上讨论的至少一个组合步骤和至少一个进一步步骤进行处理， 并且使用不同技术来产生元素R[M]至R[L-1]。
[0041] 这种情况符合期望的一个原因在于，一些处理电路仅能够并行处理有限数目的数 据元素，该数目可能比要被处理的数据元素的总数目小。如果存在比处理电路能够并行处 理的数据元素多的数据元素，则控制电路可以控制处理电路对源向量操作数内的不同组的 数据元素分别执行分区扫描运算。如果被执行的组合运算是相关联的，则分区扫描运算一 起可以提供与在较大数目的数据元素上执行单个向量扫描运算相同的结果。如果组合运算 不是相关联的（例如，某些浮点运算），则分区扫描运算获得的结果与单个较大扫描获得的 结果存在差异，但是该差异仍是可以接受的。因此，M可以是使用处理器能够并行处理的数 据元素的数目，并且如果L>M，则可以在不同组的M个数据元素或更少的数据元素上执行 分区扫描运算。
[0042] 能够以上述方式对每组M个数据元素执行分区扫描运算，其中额外数据元素在多 个步骤中被输入并且G个数据元素已经准备好而不需要至少一个进一步步骤。然而，发明 人发现这可能降低性能，因为每个后续的分区扫描运算依赖于在先运算的至少一个进一步 步骤的结果，并且因此在进行前需要等待前一个运算的结果。
[0043] 代替地，发明人意识到对于分区扫描，执行向量扫描运算可能是更高效的，因而只 有第一次分区扫描在至少两个不同步骤中输入额外数据元素并且包括上述的至少一个组 合步骤和至少一个进一步步骤。对于至少一个进一步组，替代地，分区扫描运算可以包括至 少一个预备步骤和至少一个额外步骤，该至少一个预备步骤用于组合进一步组的数据元素 的各个数据元素，该至少一个额外步骤用于组合预备步骤的结果与在用于另一组数据元素 的单独扫描运算中产生的数据元素。该方法可以更快地执行全部扫描运算，因为用于进一 步组的元素的至少一个预备步骤可以与用于第一组的数据元素的扫描运算交叉（因为预 备步骤和用于第一组的单独扫描之间没有依赖性）。
[0044] 额外数据元素S可以具有各种形式。例如，额外数据元素可以是标量操作数、来 自向量操作数的数据元素、使用向量操作数的多个数据元素确定的值、或由早期运算产生 的进位值（例如，早期向量扫描运算或同一向量扫描运算内的另一个分区扫描运算的进位 值）。
[0045] 针对向量扫描运算执行的组合运算可以具有各种形式。例如，组合运算可以是下 面运算中的任一种：加法、减法、乘法、除法、逻辑与AND、逻辑或OR、逻辑或非NOR、逻辑异或 XOR、逻辑与非NAND、最大值或最小值选择运算。对于这些运算中的大多数运算，组合运算可 以是组合两个数据元素的二进制组合运算，虽然对于一些诸如加法运算或逻辑与运算之类 的组合运算，可能在每个组合运算中组合三个或更多个数据元素。
[0046] 根据另一个方面，本技术提供了一种数据处理设备，包括：
[0047] 向量寄存器存储装置，用于存储包括多个数据元素的向量操作数；
[0048] 处理装置，用于处理来自向量寄存器存储装置的向量操作数；以及
[0049] 控制装置，用于控制处理装置对源向量操作数的M个数据元素V[0]至V[M_1]和 至少一个额外数据元素S执行向量扫描运算，以产生结果向量操作数的M个数据元素R[0] 至R[M_1]，其中对于N彡M和0彡i<N，结果向量操作数的数据元素R[i]具有对应于至 少一个额外数据元素S和源向量操作数的至少一些数据元素V[0]至V[i]的组合的值；
[0050] 其中，控制装置被配置为控制处理装置在多个步骤中执行向量扫描运算，每个步 骤用于从第一向量产生第二向量，其中用于第一步骤的第一向量包括源向量操作数的数据 元素，并且用于其他步骤的第一向量包括在前步骤的第二向量，每个步骤包括用于组合第 一向量的数据元素与至少一个额外数据元素S或第一向量的另一个数据元素以产生第二 向量的数据元素的至少一个组合运算；
[0051] 所述多个步骤中的至少一个步骤包括并行执行的多个组合运算；并且
[0052] 所述多个步骤中的至少两个步骤包括用于组合第一向量的数据元素与至少一个 额外数据元素S的组合运算。
[0053] 根据又一方面，本技术提供了一种数据处理方法，该数据处理方法用于对源向量 操作数的M个数据元素V[0]至V[M-1]和至少一个额外数据元素S执行向量扫描运算，以 产生结果向量操作数的M个数据元素R[0]至R[M-1]，其中对于N彡M和0彡i<N，结果 向量操作数的数据元素R[i]具有对应于至少一个额外数据元素S和源向量操作数的至少 一些数据元素V[0]至V[i]的组合的值；该 方法被使用处理电路执行并且包括：
[0054] 执行用于从第一向量产生第二向量的多个步骤，其中用于第一步骤的第一向量包 括源向量操作数的数据元素，并且用于其他步骤的第一向量包括在前步骤的第二向量，每 个步骤包括用于组合第一向量的数据元素与至少一个额外数据元素S或第一向量的另一 个数据元素以产生第二向量的数据元素的至少一个组合运算；
[0055] 其中，所述多个步骤中的至少一个步骤包括并行执行的多个组合运算；并且
[0056] 所述多个步骤中的至少两个步骤包括用于组合第一向量的数据元素与至少一个 额外数据元素S的组合运算。
[0057] 本技术也可以通过提供存储计算机程序的计算机可读存储介质以虚拟机形式被 实施，其中，计算机程序在被计算机执行时控制计算机提供根据上述设备的虚拟执行环境。
【附图说明】
[0058] 本技术的特征、示例、以及进一步方面从所附说明书和附图显而易见，其中：
[0059] 图1示意性地示出了用于处理向量操作数的数据处理设备；
[0060] 图2至图4示出了执行向量扫描运算的现有技术；
[0061] 图5示意性地示出了向量扫描运算的第一示例；
[0062] 图6和图7示出了向量扫描运算的第二和第三示例，其中额外数据元素S的输入 对于一个或多个处理步骤可以被延迟；
[0063] 图8和9示出了使用掩码信息控制哪些数据元素在向量扫描运算中被处理的示 例；
[0064] 图10示出了当分区向量扫描运算被应用到图4的现有技术时执行分区向量扫描 运算的对比示例（图10本身不是现有技术）；
[0065] 图11不出了应用分段扫描到图5的实施例的第一不例；
[0066] 图12示出了提供以分区形式执行图5的向量扫描运算的更高效的技术的第二示 例；
[0067] 图13示出了包括用于执行向量扫描运算的多个扫描阶段的向量扫描单元的示 例；
[0068] 图14和15分别示出了图11和12的分区向量扫描运算的流水线利用率的示例；
[0069] 图16示出了应用到图4的现有技术的分段扫描运算的对比示例（图16本身不是 现有技术）；
[0070] 图17示出了应用到图5的向量扫描运算的分段扫描运算的示例；
[0071] 图18示出了执行向量扫描运算的方法；
[0072] 图19-23示出了使用多个分段或使用少于数据元素的最大数目的数据元素的向 量扫描指令的数目的研宄结果，本技术可以为其提供性能改进；以及
[0073] 图24示出了本技术的虚拟机实现。 具体实施例
[0074] 图1示意性地示出了具有支持向量处理的处理电路4的数据处理设备2的示例。 处理电路4可以处理通过输入总线8从向量寄存器文件6接收的源向量操作数，并且对源 操作数的各个数据元素执行相应的数据处理运算以产生通过结果总线10被输出到向量寄 存器文件6的结果向量操作数。处理电路4能够对多个数据元素并行地执行运算。处理电 路4具有用于执行不同类型的处理运算的多个功能单元12。在该示例中，功能单元12包括 用于执行算术运算（诸如，加法、乘法、或移位）和逻辑运算（诸如，逻辑与AND、逻辑或OR、 逻辑异或NOR等）的算术逻辑单元（ALU);用于执行乘法累加运算的乘法累加单元（MAC); 和用于执行浮点运算的浮点单元（FPU)。处理电路4还具有用于执行向量扫描运算的向量 扫描单元12a(将在下面讨论）。应该理解，可以提供其它类型的功能单元。除了能够处理 在输入总线8上接收的操作数以外，一些处理单元12还可以具有将来自功能单元12之一 的输出操作数路由到同一功能单元12或不同功能单元12的输入端口的旁通路径（转发路 径），因而相比所产生的操作数必须被写回到寄存器文件6并且通过输入总线8被读出的情 况所产生的操作数能够在进一步步骤中被更快地处理。例如，图1中存在旁通路径（转发 路径）13,用于将扫描单元12a的输出转发到扫描单元12a的输入或ALU12的输入。还提 供了向量加载/存储单元14,用于将数据从缓存器或存储器加载到向量寄存器文件6并且 将来自向量寄存器存储器6的数据存储到缓存器或存储器。
[0075] 处理电路4对应于处理流水线的执行阶段，该处理流水线还包括指令队列20、解 码电路22、和发布队列24。指令队列20从缓存器或存储器接收指令并且将指令传递到解 码电路22。解码电路22对指令进行解码以产生将由处理电路4处理的微运算，并且将微运 算发送到发布队列24。微运算停留在发布队列24中直到它们的操作数和处理所需的任何 控制信息变成可获得为止，这时微运算被发布供处理电路4的一个处理单元12处理，或者 供加载/存储单元14处理（如果微运算是加载/存储微运算）。在一些示例中，微运算可 以分别对应于整个程序指令，并且在其它示例中，微运算可以对应于指令的一部分。例如， 复杂指令可以被划分成对应于不同处理步骤的微运算、或者用于处理源操作数的不同部分 的微运算。指令队列20、解码电路22、和发布队列24可以被认为是用于控制处理电路4的 控制电路。
[0076] 由设备2执行的一种类型的向量运算是向量扫描运算，其中组合运算被重复地应 用于增加数目的数据元素。组合运算可以采用多种形式，例如加法运算、乘法运算、最小值 或最大值选择运算、逻辑运算等。作为扫描运算的结果，结果序列被产生，每个结果与应用 组合运算（通常是二进制组合）到不同数目的数据元素有关。虽然向量扫描运算可以被串 行执行，但是由于性能原因并行扫描运算是有利的。
[0077] 图2示出了根据现有技术执行向量扫描运算的串行技术，其中被应用的组合运算 是加法运算。向量扫描运算接收包括数据元素V[0]至V[7]的源向量和额外数据元素S作 为输入。扫描运算作为一系列步骤40-54被执行，其中每个步骤执行两个元素的单个组合。 在第一步骤40,额外数据元素S被与第一向量元素V[0]组合。在第二步骤42到第八步骤 54,来自在前步骤的向量元素对的进一步组合被执行，从而到第八步骤54结束为止确定了 一系列总和VfS、Vi+VfS、VfVi+VfS等。虽然图2中所示的方法可以适用于低端系统以 避免与并行执行扫描运算相关联的硬件成本，并且因为其需要相对较少的组合运算（对于 M-元素向量，将需要M个处理步骤）可以是简单和节能的，但是因为该方法需要执行M个单 独步骤，所以该方法相对较慢并且不能利用从并行化可获得的全部性能增益。
[0078] 在并行技术中，执行多个步骤，其中每个步骤接收第一向量并且执行第一向量的 各个元素的一个或多个组合或额外数据元素与第一向量的元素的组合，以产生第二向量。 用于第一步骤的第一向量是源向量，用于其它步骤的第一向量是由在前步骤产生的第二向 量。由最后步骤产生的第二向量是结果向量。
[0079] 图3示出了并行执行向量扫描运算的现有技术。在第一步骤60,额外数据元素S 被与输入向量的第一数据元素V[0]组合。在第二步骤62,向量元素V[l]至V[7]被分别 与相邻元素V[0]至V[6]组合（其中，V[0]已经被与额外数据元素S组合）。类似地，在 第三步骤64,执行第二步骤62产生的向量中的相距两个位置的向量元素的各种组合，并且 在第四步骤66,生成相距四个位置的元素的组合。该方法使得所需处理步骤的数目减少到 log2(M)+l个处理步骤（需要额外步骤处理额外数据元素S)。
[0080] 图4示出了替代的现有技术方法，其中第一到第三步骤实质上与图3的第二到第 四步骤相同，但是额外数据元素S是在最后步骤而不是在第一步骤中被组合。在这种情况 下，因为额外数据元素S在第四步骤中被加入，所以额外数据元素S被加到每个向量数据元 素而不是被加到仅仅一个向量数据元素。然而，步骤的总数目仍与图3中的相同。
[0081] 如图2至图4中所示，现有技术仅包括用于组合额外数据元素S与一个或多个向 量元素V的一个步骤。
[0082] 然而，本技术的发明人意识到现有技术中未考虑的一个问题是，扫描运算可能被 应用到并不是所有数据元素都有效的输入向量。可以使用掩码或相似的控制信息来仅选择 输入向量的一些数据元素供使用扫描运算进行处理（例如，参见下面的图8和9)。使用图 4中所示的技术，结果向量的全部数据元素都是在第四步骤中产生的，因此即使仅仅需要一 些结果数据元素也需要执行全部四个步骤。对于图3,到第三步骤结束为止结果数据元素 0-3是可获得的，但是元素4-7是在第四步骤中产生的。因此，如果需要4个以上元素，则必 须执行全部四个步骤。
[0083] 该问题可以通过包括组合额外数据元素S与一个或多个向量数据元素的向量扫 描运算的多个步骤被解决。以这种方式，向量扫描运算可以包括产生G个结果数据元素的 至少一个组合步骤（其中M/2 <G<M)。如果需要，结果向量的剩余数据元素可以通过执 行至少一个进一步步骤被产生，但是该步骤在需要G个数据元素或更少的数据元素的情况 下可以被省略。
[0084] 在下面的讨论中，索引[0]、[1]等被用于指代正被扫描运算处理的向量内的元素 的位置，而下标索引等指代源向量操作数的相应数据元素内的数值。
[0085] 图5示出了根据本技术执行向量扫描运算的第一示例。使用至少一个组合步骤 (对应于图5的示例中的步骤1-3)和至少一个进一步步骤（对应于图5的示例中的步骤 4)执行向量扫描运算。在该示例中，额外数据元素S在向量扫描运算的每个步骤中被与一 个向量元素组合。在第一步骤100,额外数据元素S被与源向量V的元素V[0]组合，并且 与该组合并行地，源向量的相邻数据元素对被组合（例如，V[l]被与V[0]组合，V[2]被与 V[l]组合等）。在第二步骤102,额外数据元素S被与第一步骤100产生的向量的元素[1] 组合，以生成总和Vi+VfS，并且相距两个元素的元素对[0]/[1]、[1]/[3]等被组合。在第 三步骤，额外数据元素S被与在前步骤生成的向量的元素[3]组合，并且相距四个元素的元 素[0]/[4]、[1]/[5]等被组合。
[0086] 因此，到至少一个组合步骤结束为止，结果数据元素R[0]至R[6]中的除一个以外 的全部结果数据元素已经准备好，因为已经计算出源向量的元素V[0]至V[6]与额外数据 元素S的总和。唯一缺少的元素是R[7]，对于R[7]，总和V7至V0已经被计算出来，但是额 外数据元素S还未被组合（对于元素[7]，在步骤3结束时由括号中的"+S"指示）。因此， 在进一步步骤106,唯一需要的组合是组合额外数据元素S与在前步骤产生的元素[7] 以生 成最后的结果元素R[7]。
[0087] 因此，能够以比图2和图3所示的现有技术少一个步骤产生7个结果数据元素 R[0]至R[6]。如果不需要最后的数据元素R[7]，则该进一步步骤106可以被省略以改进性 能（节省至少一个处理周期）。如果向量ALU被用于扫描单元12a，则处理电路4和扫描单 元12a可能不需要被显著修改以执行图5中所示的修改后的扫描运算，因为通常对于M-元 素向量，扫描单元12a可能已经具有M个并行单元用于执行组合运算，并且图5中所示的步 骤中没有一个步骤需要M个以上的组合运算。移位阶段可以将额外数据元素S和向量元素 V移位到所需要的位置进行处理。
[0088] 图5中所示的方法具有以下优点：8个数据元素中的7个在扫描运算的最后步骤 之前的一个步骤可获得。更一般地说，对于M元素向量，可以比现有技术早一个步骤产生G =M-1个结果元素。然而，这可能需要在每个步骤中输入额外数据元素S，并且如果额外数 据元素S还不可用，则向量运算的第一步骤100将不得不被延迟。
[0089] 图6和7示出了本技术的替代示例，其中在第一步骤中不需要额外数据元素S，因 而使得向量扫描运算可以在额外数据元素可用之前开始从而可以改进性能。
[0090] 在图6的示例中，额外数据元素S可以被延迟一个步骤。在该示例中，在步骤100、 102和104,各个向量元素V的组合与图5中的相同。然而，第一步骤100不组合额外数据 元素S与源向量的元素V[0]。为了确保到第三步骤结束为止产生足够的结果数据元素，第 二步骤102和第三步骤104可以组合额外数据元素S与两个向量数据元素，而不是图5中 的组合额外数据元素S与一个向量数据元素。因此，在第二步骤102,额外数据元素S被与 第一步骤100的结果的元素[0]和[1]组合，并且在第三步骤104,额外数据元素S被与第 二步骤102的结果的元素[2]和[3]组合。这意味着到第三步骤104结束为止，六个结果 数据元素R[0]至R[5]已经准备好，但是有两个元素R[6]和R[7]是使用组合额外数据元 素S与来自步骤104的元素[6]和[7]的进一步步骤106生成的。
[0091] 类似地，在图7中，额外数据元素S可以被延迟进一步的步骤，从而使得仅在步骤 104和106中输入额外数据元素S并且对于步骤100和102不需要额外数据元素S。这允 许向量扫描运算比图6中更早地开始。此外，向量元素的组合与图5和图6中的相同，但是 在这种情况下，额外数据元素S在步骤104中被与最低的四个数据元素[0]至[3]组合并 且在步骤106中被与较高的四个数据元素[4]至[7]组合。因此，到第三步骤结束为止，仅 仅最低的四个数据元素是可用的，所以这次最远的步骤106产生结果向量的的最后四个数 据元素。注意，虽然图3的技术也在第三步骤结束时产生四个元素并且在第四步骤结束时 产生其它四个元素，但是图3的技术需要在第一步骤输入额外数据元素S，而图7的技术可 以延迟两个步骤输入额外数据元素S以允许向量扫描运算在额外数据元素S准备好之前开 始，因而性能可以被改进。
[0092] 因此，在额外数据元素S可以被延迟的周期数目和到至少一个初始步骤结束为止 可用的结果向量R的数据元素的数目G之间存在一个权衡。通常，对于应用到M个数据元 素的向量扫描运算（其中M= 2P，M-G是2的幂），在本技术中的每个步骤执行的组合的一 般描述如下。向量扫描运算可以包括：
[0093] ?包括P个步骤的至少一个组合步骤（例如，图5中的步骤J= 0到J= 2)，其 中：
[0094] 〇对于0 <J<P，该P个步骤中的步骤J包括用于组合提供给该
[0095] 步骤的第一向量的数据元素[m]与[m-2l,以产生由该步骤输出的第二
[0096] 向量的元素[m]的组合运算，其中m <N;
[0097] 〇对于log2(M_G)彡J < P，该P个步骤中的步骤J包括用于组合第一向量 的数据元素[q]与额外数据元素S，以产生第二向量的数据元素[q]的组合运算，其中 2 J-(M-G) ^ q < 2J；
[0098] ?至少一个进一步步骤，包括用于组合该至少一个额外数据元素S与提供给该至 少一个进一步步骤的第一向量的数据元素[k]的组合运算，其中G<k<N。
[0099] N是在该特定步骤中需要产生的结果向量的数据元素的数目（例如，在一些数据 元素被屏蔽的情况下，N可以小于M)。
[0100] 虽然图5-7示出了至少一个组合步骤在至少一个进一步步骤之前被执行的示例， 但是也能够以不同顺序执行这些步骤。例如，进一步步骤可以被首先执行，或穿插在其它步 骤中间被执行。同样，所述P个步骤能够以不同顺序被执行。
[0101] 图8示出了使用掩码信息110控制向量扫描运算的第一示例（该示例对应于图5， 但是其它实施例也能够以类似方式使用掩码）。掩码运算的每一位对应于源向量的一个元 素，并且如果屏蔽位（maskbit)是1，则相应向量元素是要被处理的被选择的（有效）元 素，并且如果屏蔽位是0,则向量元素不被选择用于处理。因此，在图8的示例中，仅选择向 量的最低的五个元素。被选择的元素的处理以与图5的示例中所示的相同方式进行。然而， 屏蔽位0禁止源向量元素V[5]至V[7]的输入，从而使得这些元素中的值被有效地当作x对 待（"不在乎"值一不管它们是〇还是1)。对于每个组合，如果一个输入是"x"并且其它输 入不是"X"，则"非x"输入被转发到输出。如果两个输入都是"X"，则输出也被设置为"X"。 因此，由第一步骤100产生的元素[5]至[7]分别具有V4、x和x的值。第二步骤102和第 三步骤104以与图5相同的方式进行。因为到第三步骤结束为止最低的五个元素的结果是 可用的（S到1的组合已经完成），所以不需要第四步骤106并且因此可以省略该步骤。
[0102] 类似地，图9示出了掩码将位于非相邻位置的多个离散元素设置为未被选择的元 素的示例。在该示例中，向量元素[1]、[5]、和[7]被使用屏蔽位0标记为未被选择。此外， 未被选择的元素被当作X对待（"不在乎")，因此来自这些元素的值VpVjPV7在第一步骤 100中不被向前传播。这意味着对应于被选择的元素的结果元素取仅被选择的元素的总和 的值（跳过未被选择的元素）。例如，结果数据元素R[6]具有值V6+V4+V3+V2+VS，该值不 包括未被选择的元素的值％和Vi。此外，因为到第三步骤104结束为止全部需要的元素已 经准备好，所以不需要进一步步骤106。通常，对于值N被选择从而使得N-1对应于向量的 最后被选择的元素的索引的情况，如果N<G(G是通过仅执行第一步骤到第三步骤100-104 可获得的数据元素的数目），则最后步骤106可以被跳过。
[0103] 图8和图9示出了未被选择的元素的处理正常进行，但是值被设置为0的示例。也 可以完全禁止处理这些元素。图8和图9示出了使用掩码信息限定被选择的元素和未被选 择的元素的示例，但是也可以使用其它类型的控制信息，诸如向量长度参数或向量格式信 息。
[0104] 此外，对应于未被选择的元素的结果数据元素可以被设置为不同的值。图9示出 了可以与向量扫描运算并行或串行执行的写回运算112,该写回运算112将值写入结果向 量的未被选择的元素。由"一"指示的结果向量的元素不被写回运算修改。图9示出了源 寄存器的未被选择的元素的值被写入目标寄存器的相应位置的示例（这可以通过反转掩 码并使用反转后的掩码来控制寄存器写入实现）。在其它示例中，预定值（诸如〇或全部1 位）可以被写到未被选择的元素，或结果向量的未被选择的元素中存储的先前值可以被保 留（例如，如果使用寄存器重命名，则仍需要写回运算）。
[0105] 图5至图9示出了使用能够并行执行8个组合的扫描单元12a处理8元素向量的 示例。也可以使用具有较小数据路径宽度的扫描单元12a使得扫描单元12a仅并行处理一 些数据元素。这对减少执行向量扫描运算的硬件成本是有用的。对于这样的扫描单元12a， 向量扫描运算可以被分成单独的分区运算，上述单独的分区运算一起提供与对全部数据元 素执行扫描运算相同的结果。图10示出了应用到图4的现有技术的分区扫描运算的示例， 但是图10本身不是现有技术。在图10的示例中，扫描运算在多个步骤120-128中被执行。 步骤120至124对应于使用源向量的元素V[0]至V[3]和额外数据元素S执行的第一分区 扫描运算132,步骤126至128对应于使用源向量的较高的四个元素V[4]至V[7]和第一 分区扫描运算132产生的结果元素R[3]的第二分区扫描运算134。当仅应用到较低的四 个元素[0]至[3]时，第一分区132的步骤120、122和124执行与图4的第一、第二和第四 步骤相同的组合。类似地，对于较高的四个元素[4]至[7]，第二分区134的步骤126、127 和128对应于图4的第一、第二和第四步骤。因为在第二分区134的步骤126、127与第一 分区132的步骤120至124之间没有依存关系，所以这些步骤可以被交织从而使用具有较 窄数据路径宽度的扫描处理单元12a来相对高效地执行扫描运算。
[0106] 图11和图12示出了执行应用到图5中所示的本技术的扫描运算的类似分区扫描 的示例。图11示出了第一分区140包括与图5的步骤1至3相同但是仅对元素[0]至[3] 执行的步骤130、131和132的第一示例。这使得第一分区产生的3个元素到步骤131结束 为止已经准备好。然而，如图11所示，如果第二分区142是使用分别对应于与步骤130、131 和132相同的组合运算的步骤133、134和135执行的，则需要第二分区等待直到第一分区 140的最后步骤132结束为止，因为第二分区的步骤133依赖于第一分区的步骤132产生的 元素R[3]。因此，使用该方法，向量扫描需要6个步骤。
[0107] 图12示出了实现使用本技术的分区扫描的更高效的方式。在该示例中，第一分区 140与图11中的相同，其包括步骤130、131和132。然而，第二分区142以与图10中的第二 分区134相同的方式使用步骤126、127和128被执行。这意味着第二分区142的步骤126 和127独立于第一分区的步骤130至132并且因此可以被交织，以便第二分区142可以更 早地开始，从而减少了执行作为整体的运算的周期数目。然而，与图10不同，如果需要少于 4个数据元素，则第一分区的一些步骤可以被省略以改进性能。因此，组合图5的顺序或用 于第一分区的其它实施例与用于后续分区的不同顺序的混合方 法可以改进分区扫描运算 的性能。
[0108] 因此，图5-7所示的顺序或其它示例不需要被应用到扫描运算中正被处理的全部 向量。可以仅向源向量的M个数据元素应用上述技术（例如，在图12中，M= 4)，并且可以 使用不同顺序的组合运算来处理相同向量的剩余数据元素。
[0109] 图13示出了向量扫描单元12a的示例。向量扫描单元12a可以具有多个扫描阶 段150。为了执行前面示例中指示的向量扫描运算的单个步骤，向量可以被传递通过每个扫 描阶段150以便到最后扫描阶段结束为止，扫描运算的该步骤产生的向量是可用的。上述 的旁通路径13可以用于将最后扫描阶段的结果转发回到第一扫描阶段用于后续步骤。在 一些示例中，可以有不止两个扫描阶段。
[0110] 图14示出了当向量扫描运算被以图11中所示的方式分区时，图13中所示的扫 描单元12a的流水线利用率的示例。扫描运算的每个步骤需要两个周期，一个周期在第一 扫描阶段〇中，另一个周期在第二扫描阶段1中。在图11的示例中，扫描运算的不同步骤 之间的依赖性意味着扫描运算的步骤不能相互交错，因为每个步骤必须等待在前步骤的结 果。这意味着需要12个周期。与之相比，图15示出了图12的示例的相应流水线利用率。 在这种情况中，扫描运算的不同扫描分区之间存在较少的依赖性，因此分区的不同步骤可 以交错，从而使得当一个步骤在第二扫描阶段时，对应于另一分区的另一个步骤由第一扫 描阶段处理。如图15中所示，这意味着与图11相比，使用图12的方法，流水线利用率可以 更高并且整体运算可以在更少的周期中被完成。
[0111] 因此，本技术自身非常适于处理分区扫描中的多个分区的第一分区，但是后续分 区可以使用组合运算的不同顺序被更高效地执行。
[0112] 本技术对执行分段扫描的系统也是有用的，其中对向量中的不同分段的数据元素 执行单独扫描。图16示出了应用到图4的现有技术的扫描运算时的分段扫描的概念，但是 图16本身不是现有技术。分段信息200被提供以指示源向量V的数据元素的不同分段之 间的边界。分段掩码200内的每个'1'位指示一个分段和另一个分段之间的边界（标记为 ' 1'位的元素是分段的最后元素，下一个元素将开始新分段）。对于分段0 (在该示例中包 括元素[0]至[3])，使用额外数据元素S和该分段的元素执行扫描运算。对于任何进一步 分段（例如，该示例中的包括元素[4]至[7]的分段1)，该分段的向量元素被组合，但不包 括额外数据元素。组合运算以与图4相同的方式进行，但是掩码被用于禁用不同分段中的 元素之间的任何组合（如图16中的虚线指示的）。这可以通过以图16的顶部所示的方式 对掩码进行移位产生用于随后步骤的掩码来实现。对于第一步骤，掩码以其初始形式被应 用。对于第二步骤，掩码200被向下移位一个位置，并且如图16的202部分所示产生两个 掩码的逻辑或。对于第三步骤，来自第二步骤的掩码被向下移位两个位置，并且被与先前掩 码进行逻辑或运算（参见图16的204部分）。当使用更多数据元素处理向量时，对于任何 后续步骤，掩码将继续以对每个步骤增加2的幂的增量向下移位，然后与之前步骤的掩码 进行逻辑或运算。图16的最后步骤简单地将额外数据元素S加到第一分段0内的任意元 素。也可以使用之前步骤的掩码来控制该步骤。图16中所示的方法意味着需要全部步骤 来执行扫描运算，因为额外数据元素S直到最后步骤才被输入。
[0113] 图17示出了使用图5的实施例的组合运算的顺序的分段扫描的示例。以与图16 相同的方式生成用于每个步骤的掩码。然而，通过改变图5中的组合顺序，到第三步骤结束 为止更多的结果数据元素可用。因为第四步骤仅包括额外数据元素S与第三步骤产生的最 后元素[7]的组合，并且在仅有一个分段（即掩码完全是0)的情况下仅需要该组合，所以 在存在不止一个分段的情况下，不管分段的位置或分段的数目，最后步骤可以被省略。因 此，图5中所示的向量扫描运算自身非常适于分段扫描运算，因为其经常能够减少针对分 段扫描执行的步骤的数目。类似地，图6和图7中的示例可以使用分段扫描运算被实施，并 且当存在多个分段时这有助于减少所需步骤的数目。
[0114] 图18示出了执行向量扫描运算的示例方法。在步骤300,处理电路4接收向量扫 描微运算，该向量扫描微运算将使用源向量的M个元素和额外数据元素S被执行。额外数 据元素S可以是例如，在先运算的进位值、向量元素、或标量值。向量扫描运算具有相关联 的控制信息，该控制信息指定要被扫描的N个元素作为使用额外数据元素的序列（如图8 和图9所示，如果剩余的元素被屏蔽，或者如图16和图17所示，如果剩余的元素是不使用 额外数据元素S的后续分段的部分，则N可以小于M)。
[0115] 响应于向量扫描运算，在步骤302,确定N是否大于G，G是可以使用至少一个组合 步骤产生的结果数据元素的数目。如果N>G，则在步骤304,扫描单元12a执行用于产生 G个结果数据元素的至少一个组合步骤和用于产生元素[G]至[N-1]的至少一个进一步步 骤。换句话说，如果N<G，则在步骤306,扫描单元12a执行至少一个组合步骤，但省略至 少一个进一步步骤。在步骤308,输出包含结果数据元素的结果向量。
[0116] 图19至23示出了当执行不同类型的处理算法时观察向量扫描运算的使用的分 析。图19示出，当被应用到对于不同数据路径宽度的反向传播算法（BackProp)和稀疏矩 阵向量相乘算法（SpMV)时，观察的对于分段向量扫描使用不同数目的分段的指令百分比。 可以看出，与执行使用128位数据路径的SpMV算法不同，大多数分段指令计算至少两个分 段，并且因此将从本技术获益，其中当有两个或更多个分段时，该进一步步骤可以被省略。
[0117] 图20和图21示出了计算出的分段的平均数目和分别执行具有不同大小的矩阵的 SpMV算法的潜在性能优势。如图21所示，当比较相对于标量运算的加速时可以看出，使用 分段扫描获得的性能对大小在25X25和100X100元素之间的矩阵特别有利。通过与图20 进行比较表明，平均在至少1.5个分段上运算的分段指令提供了改进的性能，从而使得性 能收益补偿了与控制分段扫描相关联的计算开销。这支持使用可以加速使用不止一个分段 的分段扫描的本技术。
[0118] 对于未被分段的扫描，图22和图23示出了指令使用的平均向量长度的分析。图 22示出了对不同的基准算法使用256位宽度的数据路径处理的32位数据元素的示例。如 图22中所示，有相当大比例的指令仅使用8数据元素向量的2或5个数据元素。虽然在处 理具有2个有效元素的8元素向量时图3的现有技术能够减少步骤数目，但是该技术对具 有5个有效元素的向量不起作用。与之相比，即使当M元素向量的有效元素的数目在M/2 和M之间时，本技术也可以减少步骤数目。因此，图22支持本技术为相当大数目的指令提 供有用的性能改进的事实。换句话说，如图23中所示，对于256位宽度数据路径处理具有 16位元素的向量，在这种情况下，使用少于全部数目的数据元素的指令的比例是微不足道 的。每当期望有相当多的不全部利用向量大小的指令时，系统设计者可以选择本技术。
[0119] 图24示出了可以使用的虚拟机实现。虽然前面描述的实施例以用于操作支持相 关技术的专用处理硬件的设备和方法实现本发明，但是还可以提供硬件设备的所谓的虚拟 机实现。这些虚拟机实现在通常运行支持虚拟机程序402的主操作系统404的主处理器 406上运行。一般，需要大规模的强大处理器来提供以合理速度执行的虚拟机实现，但是此 方法在某些情况下被证明是合理的，诸如当为了兼容或重复使用的原因希望运行对于另一 处理器而言处于本地的代码。虚拟机程序402能够执行应用程序（或操作系统）400,以提 供与由真实的硬件装置执行程序所提供的结果相同的结果。因此，包括控制上述存储器访 问的程序指令可以在使用虚拟机程序402的应用程序400内部被执行。
[0120] 虽然本发明的示意性实施例已经参考附图在此被详细地描述，但是应该理解本发 明不限于那些明确的实施例，在不偏离由所附权利要求限定的范围和精神的情况下，本领 域的技术人员可以进行多种变化和/或修改。
【主权项】
1. 一种数据处理设备，包括： 向量寄存器存储器，该向量寄存器存储器被配置为存储包括多个数据元素的向量操作 数； 处理电路，该处理电路被配置为处理来自所述向量寄存器存储器的向量操作数；以及 控制电路，该控制电路被配置为控制所述处理电路对源向量操作数的M个数据元素V[0]至V[M-1]和至少一个额外数据元素S执行向量扫描运算，以产生结果向量操作数的M 个数据元素R[〇]至R[M-1]，其中，对于N彡M且O彡i<N，所述结果向量操作数的数据元 素R[i]具有对应于所述至少一个额外数据元素S和所述源向量操作数的至少一些数据元 素V[0]至V[i]的组合的值； 其中，所述控制电路被配置为控制所述处理电路在多个步骤中执行所述向量扫描运 算，每个步骤用于从第一向量产生第二向量，其中，用于第一步骤的第一向量包括所述源向 量操作数的数据元素，并且用于其他步骤的第一向量包括在前步骤的第二向量，每个步骤 包括用于组合所述第一向量的数据元素与所述至少一个额外数据元素S或所述第一向量 的另一个数据元素以产生所述第二向量的数据元素的至少一个组合运算； 所述多个步骤中的至少一个步骤包括并行执行的多个组合运算；并且 所述多个步骤中的至少两个步骤包括用于组合所述第一向量的数据元素与所述至少 一个额外数据元素S的组合运算。2. 根据权利要求1所述的数据处理设备，其中，M是2的幂。3. 根据权利要求2所述的数据处理设备，其中，至少在N>G，M/2 <G<M的情况下， 所述控制电路被配置为控制所述处理电路执行包括至少一个组合步骤和至少一个进一步 步骤的所述多个步骤，所述至少一个组合步骤用于产生所述结果向量操作数的G个数据元 素R[0]至R[G-1]，所述至少一个进一步步骤在除了所述至少一个组合步骤之外被额外执 行时用于产生所述结果向量操作数的数据元素R[G]至R[M-1]。4. 根据权利要求3所述的数据处理设备，其中，在M/2 <N<G的情况下，所述控制电 路被配置为控制所述处理电路执行所述至少一个组合步骤并且省略所述至少一个进一步 步骤。5. 根据权利要求3和4中任一项所述的数据处理设备，其中，所述至少一个进一步步骤 包括用于组合所述第一向量的数据元素与所述至少一个额外数据元素S的至少一个组合 运算，并且不包括任何用于组合所述第一向量的数据元素与所述第一向量的另一个数据元 素的组合运算。6. 根据权利要求3至5 中任一项所述的数据处理设备，其中，至少在N>G的情况下： 所述至少一个组合步骤是这样的步骤：如果所述至少一个组合步骤是由所述处理电路 在不执行所述至少一个进一步步骤的情况下执行的，则所述处理电路将在所述至少一个组 合步骤的最后步骤产生所述第二向量的数据元素[G]至[M-1]，其中，对于G<k<M，所述 第二向量的数据元素[k]具有对应于所述源向量操作数的至少一些数据元素V[0]至V[k] 的组合的值；并且 在所述至少一个进一步步骤中，所述控制电路被配置为控制所述处理电路，对于G<k<N，执行用于组合所述至少一个额外数据元素S与用于所述至少一个进一步步骤的所述 第一向量的数据元素[k]的组合运算。7. 根据权利要求3至6中任一项所述的数据处理设备，其中，M= 2p并且所述至少一个 组合步骤包括用于响应于第一向量的数据元素[0]至[M-1]产生第二向量的数据元素[0] 至[M-1]的P个步骤；并且 对于〇 <J<P，所述P个步骤中的步骤J包括用于组合所述第一向量的数据元素[m] 与所述第一向量的数据元素[m_2l以产生所述第二向量的数据元素[m]的组合运算，其中 2J<m<N08. 根据权利要求7所述的数据处理设备，其中，M-G是2的幂，并且对于log2 (M-G) <J <P，所述P个步骤中的步骤J包括用于组合所述第一向量的数据元素[q]与所述额外数据 元素S以产生所述第二向量的数据元素[q]的组合运算，其中Y-(M-G) <q< 21。9. 根据权利要求3至8中任一项所述的数据处理设备，其中，所述控制电路被配置为控 制所述处理电路输出对应于所述结果向量操作数的数据元素R[N_1]的进位值； 其中，在所述至少一个进一步步骤被省略的情况下，所述控制电路被配置为控制所述 处理电路比在所述处理电路执行所述至少一个进一步步骤的情况下更早地输出所述进位 值。10. 根据上述任一项权利要求所述的数据处理设备，其中，所述向量扫描运算与识别所 述源向量操作数的哪些数据元素是被选择的数据元素的控制信息相关联，并且所述控制电 路被配置为控制所述处理电路在所述向量扫描运算中处理所述被选择的数据元素。11. 根据权利要求10所述的数据处理设备，其中，N的取值使得V[N_1]是由所述控制 信息指示的所述源向量操作数的最后被选择的数据元素。12. 根据权利要求10和11中任一项所述的数据处理设备，其中，所述控制电路被配置 为控制所述处理电路将对应于所述源向量操作数的未被选择的数据元素的所述结果向量 操作数的数据元素设置为下面各项之一： (i) 预定值； (ii) 通过利用被设置为预定值的所述源向量操作数的未被选择的数据元素执行所述 向量扫描运算确定的值； (iii) 用于存储所述源向量操作数的源寄存器中的相应数据元素的值；以及 (iv) 用于存储所述结果向量操作数的目标寄存器中的相应数据元素的值。13. 根据上述任一项权利要求所述的数据处理设备，其中，所述向量扫描运算与识别所 述源向量的一个或多个分段的分段信息相关联，每个分段包括一个或多个数据元素； 其中，在所述分段信息识别多个分段的情况下，所述控制电路被配置为控制所述处理 电路对所述多个分段中的第一分段的数据元素执行所述向量扫描运算。14. 根据权利要求13所述的数据处理设备，其中，N的取值使得V[N-1]是所述第一分 段的最后被选择的数据元素。15. 根据权利要求13和14中任一项所述的数据处理设备，其中，在所述分段信息识别 多个分段的情况下，所述控制电路被配置为控制所述处理电路针对不同于所述第一分段的 进一步分段产生所述结果向量操作数的相应进一步分段内的至少一个结果数据元素，所述 相应进一步分段内的每个结果数据元素具有对应于所述源向量操作数的所述进一步分段 的一个或多个数据元素的组合的值。16. 根据从属于权利要求3的权利要求13至15中任一项所述的数据处理设备，其中， G=M-1，并且在所述分段信息识别多个分段的情况下，所述控制电路被配置为控制所述处 理电路省略所述向量扫描运算的所述至少一个进一步步骤。17. 根据上述任一项权利要求所述的数据处理设备，其中，所述源向量操作数包括X个 数据元素，其中X多M，并且所述结果向量操作数包括Y个数据元素，其中Y多M。18. 根据权利要求17所述的数据处理设备，其中，所述控制电路被配置为控制所述处 理电路对所述源向量操作数的L个数据元素执行所述向量扫描运算，以产生所述结果向量 操作数的L个数据元素，其中L<X并且L<Y;并且 如果L>M，则所述结果向量操作数的L个数据元素包括L-M个进一步数据元素R[M] 至R[L_1]，其中对于MSi<L，结果数据元素R[i]具有对应于结果数据元素R[M-1]与所 述源向量操作数的至少一些数据元素V[M]至V[i]的组合的值。19. 根据权利要求18所述的数据处理设备，其中，在L>M的情况下N=M，并且在 L彡M的情况下N=L。20. 根据权利要求17至19中任一项所述的数据处理设备，其中，在所述多个步骤中的 每个步骤，所述处理电路被配置为并行地产生所述第二向量的最多M个数据元素；并且 如果L>M，则所述控制电路被配置为控制所述处理电路分别针对所述源向量操作数 的多个组的数据元素执行分区扫描运算，每个组包括M个数据元素或更少的数据元素。21. 根据从属于权利要求3的权利要求20所述的数据处理设备，其中，如果L>M，则 所述控制电路被配置为控制所述处理电路利用所述多个步骤中的至少两个步骤针对所述 多个组中的第一组执行所述分区扫描运算，所述至少两个步骤包括用于组合所述第一向量 的数据元素与所述至少一个额外数据元素S的组合运算，并且所述多个步骤包括所述至少 一个组合步骤和所述至少一个进一步步骤。22. 根据权利要求21所述的数据处理设备，其中，如果L>M，则对于不同于所述第 一组的至少一个进一步组，所述控制电路被配置为控制所述处理电路执行所述分区扫描运 算，所述分区扫描运算包括： 至少一个预备步骤，所述至少一个预备步骤包括用于组合所述进一步组的数据元素的 各个数据元素的至少一个组合运算； 至少一个额外步骤，所述至少一个额外步骤包括用于组合在针对所述进一步组的所述 至少一个预备步骤中产生的数据元素与在针对所述第一组的数据元素的所述分区扫描运 算中产生的数据元素的至少一个组合运算。23. 根据权利要求22所述的数据处理设备，其中，所述控制电路被配置为控制所述处 理电路执行与针对所述第一组的数据元素的所述分区扫描运算相交错的针对所述进一步 组的数据元素的所述至少一个预备步骤。24. 根据上述任一项权利要求所述的数据处理设备，其中，所述至少一个额外数据元素 S包括下面各项之一： 标量操作数； 向量操作数的数据元素； 使用向量操作数的多个数据元素确定的值；以及 通过另一个向量运算确定的进位值。25. -种数据处理设备，包括： 向量寄存器存储装置，该向量寄存器存储装置用于存储包括多个数据元素的向量操作 数； 处理装置，该处理装置用于处理来自所述向量寄存器存储装置的向量操作数；以及 控制装置，该控制装置用于控制所述处理装置对源向量操作数的M个数据元素V[0]至V[M-1]和至少一个额外数据元素S执行向量扫描运算，以产生结果向量操作数的M个数据 元素R[〇]至R[M-1]，其中对于N彡M且0彡i<N，所述结果向量操作数的数据元素R[i] 具有对应于所述至少一个额外数据元素S和所述源向量操作数的至少一些数据元素V[0] 至V[i]的组合的值； 其中，所述控制装置被配置为控制所述处理装置在多个步骤中执行所述向量扫描运 算，每个步骤用于从第一向量产生第二向量，其中用于第一步骤的第一向量包括所述源向 量操作数的数据元素，并且用于其他步骤的第一向量包括在前步骤的第二向量，每个步骤 包括用于组合所述第一向量的数据元素与所述至少一个额外数据元素S或所述第一向量 的另一个数据元素以产生所述第二向量的数据元素的至少一个组合运算； 所述多个步骤中的至少一个步骤包括并行执行的多个组合运算；并且 所述多个步骤中的至少两个步骤包括用于组合所述第一向量的数据元素与所述至少 一个额外数据元素S的组合运算。26. -种数据处理方法，用于对源向量操作数的M个数据元素V[0]至V[M-1]和至少 一个额外数据元素S执行向量扫描运算以产生结果向量操作数的M个数据元素R[0]至 R[M_1]，其中，对于N彡M且O彡i<N，所述结果向量操作数的数据元素R[i]具有对应于 所述至少一个额外数据元素S和所述源向量操作数的至少一些数据元素V[0]至V[i]的组 合的值；所述方法被使用处理电路执行并且包括： 执行用于从第一向量产生第二向量的多个步骤，其中用于第一步骤的第一向量包括所 述源向量操作数的数据元素，并且用于其他步骤的第一向量包括在前步骤的第二向量，每 个步骤包括用于组合所述第一向量的数据元素与所述至少一个额外数据元素S或所述第 一向量的另一个数据元素以产生所述第二向量的数据元素的至少一个组合运算； 其中，所述多个步骤中的至少一个步骤包括并行执行的多个组合运算；并且 所述多个步骤中的至少两个步骤包括用于组合所述第一向量的数据元素与所述至少 一个额外数据元素S的组合运算。27. -种存储计算机程序的计算机可读存储介质，所述计算机程序在被计算机执行时 控制所述计算机提供根据权利要求1至24中的任一项所述的设备的虚拟执行环境。28. -种基本上如这里参考附图描述的数据处理设备。29. -种基本上如这里参考附图描述的数据处理方法。30. -种基本上如这里参考附图描述的计算机可读存储介质。
【专利摘要】公开了用于执行向量扫描运算的数据处理设备和方法。向量扫描运算被执行以产生结果向量的M个数据元素，其中每个结果数据元素对应于额外数据元素S与源向量操作数V的至少一些数据元素的组合。向量扫描运算被使用多个步骤执行，每个步骤包括用于组合数据元素的一个或多个组合运算。这些步骤中的至少一个步骤包括两个或多个并行执行的组合运算。这些步骤中的至少两个步骤包括用于组合数据元素与额外数据元素S的组合运算。该方法使得向量扫描运算在少于M个数据元素有效的情况下能够以更少的步骤被执行，从而使得向量扫描运算可以被更快地执行。
【IPC分类】G06F17/16
【公开号】CN104899180
【申请号】CN201510089213
【发明人】马蒂亚斯·伯特歇尔, 贾科莫·加布雷利, 姆布·埃约勒-莫诺诺
【申请人】Arm 有限公司
【公开日】2015年9月9日
【申请日】2015年2月27日
【公告号】US20150254076
最新回复(0)