在多处理器系统上对数据集进行划分及排序的方法和装置

摘要

本发明提供了一种在多处理器系统上对数据集进行划分、排序的方法和装置。其中该多处理器系统包括至少一个核心处理器以及多个加速器。该对数据集进行划分的方法包括：迭代地利用多个加速器并行地将上述数据集划分为对应于不同的数据范围的多个块，其中该多个块的每一个能够被该多个加速器的本地存储器所存储；其中在每一次迭代中包括：将上述数据集粗略地划分为多个大块；获取该数据集的能够表明该数据集中数据值的分布的参数；根据该参数，为该数据集确定多个数据范围；利用上述多个加速器并行地将上述多个大块分别划分为与该多个数据范围对应的多个小块，其中该多个加速器的每一个通过计算为其划分的大块中的每一个数据确定所属的数据范围。

说明书

技术领域

本发明涉及数据处理领域，具体地，涉及在多处理器系统上对数据集进行划分的方法和装置以及对数据集进行排序的方法和装置。

背景技术

数据排序是一种常见的处理，其在工业、商业等领域的数据分析中经常应用到。

通常，在如图1所示的单处理器数据处理系统中，数据排序主要涉及以下三个处理阶段：1)从主存储器收集待排序的数据；2)使用处理单元对所获取的数据进行排序；3)将排序后的数据传送回主存储器。

随着半导体工艺接近其极限，增加数据处理系统中处理器的数量，相对于继续通过半导体工艺的进步而提高单个处理器的处理能力，在近期来看是更加可行的。

图2示出了常规的多处理器系统的结构。如图2所示，多处理器系统一般都具有在一个共享的主存储器上进行操作的多个处理器，其中包括一个核心CPU和多个加速器(Accelerated Processing Unit，APU)。

例如，Cell宽频引擎(Cell Broadband Engine，CBE)就是一种单芯片多处理器系统，其具有在一个共享的主存储器上进行操作的9个处理器，其中包括一个主处理器(Power Processing Unit，PPU)和8个协处理器(Synergistic Processing unit，SPU)。在这样的系统结构下，CBE能够提供杰出的数据计算能力。因而，对于大数据集的数据排序来说，如果利用CBE这样的多处理器系统，则将能够使排序处理的性能得到极大提升。

但是，在CBE这样的多处理器系统中，为了使多个加速器并行地对待排序的数据集执行数据排序处理，需要对待排序的数据集进行均匀的划分，以适应各加速器的本地存储器的大小，因而，主要的处理阶段包括：1)对待排序的数据集进行划分，将其从主存储器分发给多个加速器；2)使多个加速器并行地分别对各自的数据进行排序；3)将多个加速器的数据排序结果会聚到主存储器中。

但是，在上述过程中，具体如何划分数据集以及如何会聚数据排序结果，目前仍是难题。

再者，在多处理器系统中，加速器的本地存储器容量一般都是有限的，因为对每一个加速器都配备大容量的本地存储器是非常耗费成本的。例如，在CBE中，每个SPU的本地存储器容量是256KB，这对于大数据集来说是不够的。

这样，如果数据集未被很好地划分，则在各加速器并行地执行各自的排序任务时，就需要利用DMA方式在主存储器与其本地存储器之间重复地进行数据交换操作，大量的数据交换操作将导致主存储器操作的低效率，因为主存储器与多个加速器之间的存储器带宽一般是有限制的。例如，在CBE中，在SPU与主存储器之间仅能够维持大致25.6GB/秒的存储器带宽，该存储器带宽需要被8个SPU所共享。

此外，如果数据集未被很好地划分，则还有可能导致各加速器在执行各自的数据排序任务时，需要不断地与其他加速器进行数据的通信，这也将导致排序的低效率。

从而，应该考虑到，如果在CBE这样的多处理器系统上执行数据排序处理，则应尽量减少主存储器与加速器之间以及各加速器之间的数据交换操作。

再者，在通常的数据排序算法中，存在着大量的分支(比较)操作，但是，对于CBE这样的多处理器系统来说，分支操作的能力是相对较弱的。这也是在CBE这样的多处理器系统上执行数据排序处理应该考虑的一个问题。

基于以上考虑，需要设计出一种适合于CBE这样的多处理器系统的数据划分以及排序方案。

发明内容

鉴于上述问题，本发明提供了一种在多处理器系统上对数据集进行划分的方法和装置以及对数据集进行排序的方法和装置，以便在CBE这样的多处理器系统上尽可能通过数据的计算而不是数据之间的比较以及数据的逻辑聚合而不是数据的物理移动来执行大数据集的划分、排序处理，从而充分发挥这样的多处理器系统所具有的高计算能力的优点。

根据本发明的一个方面，提供了一种在多处理器系统上对数据集进行划分的方法，其中该多处理器系统包括至少一个核心处理器以及多个加速器，该方法包括：迭代地利用上述多个加速器并行地将上述数据集划分为对应于不同的数据范围的多个块，其中该多个块的每一个能够被上述多个加速器的本地存储器所存储；其中在每一次迭代中包括：将上述数据集粗略地划分为多个大块；获取上述数据集的能够表明该数据集中数据值的分布的参数；根据上述参数，为上述数据集确定多个数据范围；以及利用上述多个加速器并行地将上述多个大块分别划分为与上述多个数据范围对应的多个小块，其中该多个加速器的每一个通过计算为其划分的大块中的每一个数据确定上述多个数据范围中该数据所属的数据范围。

根据本发明的另一个方面，提供了一种在多处理器系统上对数据集进行排序的方法，其中该多处理器系统包括至少一个核心处理器以及多个加速器，该方法包括：利用上述的在多处理器系统上对数据集进行划分的方法，将待排序的数据集划分为对应于不同的多个数据范围的多个块；将上述多个块从主存储器分发给上述多个加速器；上述多个加速器并行地对上述多个块分别进行数据排序；以及按上述不同的多个数据范围的大小，上述多个加速器分别将其排序后的块写回到主存储器中。

附图说明

相信通过以下结合附图对本发明具体实施方式的说明，能够使人们更好地了解本发明上述的特点、优点和目的。

图1是单处理器系统的框图；

图2是多处理器系统的框图；

图3是根据本发明实施例的在多处理器系统上对数据集进行划分的方法的流程图；

图4是图3的方法的总体图示说明；

图5是根据本发明实施例的、图3的方法中将大块划分为多个小块的步骤320的详细流程图；

图6是图5的过程的图示说明；

图7是图3的方法中步骤330、340的图示说明；

图8是根据本发明实施例的在多处理系统上对数据集进行排序的方法的流程图；

图9是图8的过程的图示说明；

图10是根据本发明实施例的在多处理器系统中对数据集进行划分的装置的方框图；以及

图11是根据本发明实施例的在多处理器系统中对数据集进行排序的装置的方框图。

具体实施方式

下面就结合附图对本发明的各个优选实施例进行详细说明。

图3是根据本发明实施例的在多处理器系统上对数据集进行划分的方法的流程图。其中，该多处理器系统具有至少一个核心处理器以及多个加速器。具体地，该多处理器系统例如可以是前述具有一个PPU(核心处理器)和8个SPU(加速器)的CBE。并且，待划分的数据集预先存储在上述多处理器系统的主存储器中。

本实施例的在多处理器系统上对数据集进行划分的方法，迭代地利用上述多个加速器并行地对上述数据集进行划分，直到将该数据集划分为对应于不同的数据范围并且均小于该多个加速器的本地存储器容量的多个小块。

具体地，如图3所示，首先在步骤305，获取上述待划分的数据集的、能够大致表明该数据集中数据值的分布的参数，该参数例如是该数据集中数据值的均值或方差，或者是最小值和最大值。当然该参数也可以既包括数据值的均值或方差又包括数据值的最小值和最大值。

并且，在优选实施例中，上述数据集的参数是根据该数据集估计出的。在另一个实施例中，该参数也可以是根据该数据集计算得出的。

在步骤310，根据上述参数，为上述数据集确定多个数据范围。

例如，在上述参数是根据该数据集估计出的数据值均值并且该均值是500的情况下，可以为该数据集确定步距固定是100的多个数据范围0-99、100-199、200-299、……、900-999。当然，并不限于此，还存在多种数据范围的确定方式。例如可以为数据的二进制表示中最高的四位分别设置权值，诸如从最高位开始，分别设置权值2⁰、2¹、2²、2³，并根据这最高四位的加权和的不同而确定16个不同的数据范围，即加权和为1的数据范围、加权和为2的数据范围，等等。

在步骤315，将上述数据集粗略地划分为多个大块。在图4中，如(a)、(b)所示，示例性地将数据集划分为四个大块。

在本步骤中，将该数据集粗略地划分为多个大块的目的是使上述多个加速器能够并行地对这多个大块分别进一步进行划分，所以只要能够使多个加速器并行地在该数据集上工作，本发明对划分的方式没有特别的限制。

在一个实施例中，在本步骤中，将上述数据集均等地划分为与上述多个加速器的数量对应的多个大块。例如，在上述具有8个SPU的CBE的情况下，将上述数据集划分为均等的8个大块。但是，这仅是示例性的。在其他实施例中，也可以将该数据集划分为更多或更少的多个大块，并且这些大块的数据量也可以是不均等的。

在步骤320，如图4中的(c)所示，利用上述多个加速器，并行地通过计算将上述多个大块分别划分为与上述多个数据范围对应的多个小块，同时统计各个小块的能够准确表明其数据值的分布的参数。

例如在前述0-99、100-199、200-299、……、900-999的多个数据范围的情况下，使上述多个加速器并行地通过计算将上述多个大块分别划分为与这些数据范围对应的多个小块。也就是说，对于上述多个大块的每一个，通过计算将其中值处于0-99之间的所有数据划分为一个小块、将值处于100-199之间的所有数据划分为一个小块，依此类推，从而形成分别与数据范围0-99、100-199、200-299、……、900-999对应的多个小块。

下面结合附图详细描述该步骤320的过程。图5是以上述多个加速器中的任意一个对于分配给其的大块进行划分为例、根据本发明一个实施例的该步骤320的过程的详细流程图，图6是该过程的图示说明。

在本实施例中，如图6所示，在上述多个加速器的每一个的本地存储器中以及在主存储器中分别设置有用于将属于一个数据范围的数据链接起来的链表。在一个实施例中，该链表是反向链表，由一个索引表和一个尾指针表构成。其中，索引表中包括多个条目，条目的数量可以根据存储器容量来设定。此外，尾指针表也包括多个条目，条目的数量至少与上述多个数据范围的个数相等，也就是说，对于该多个数据范围中的每一个，该尾指针表中至少包括一个与其对应的条目。此外，初始，该索引表以及尾指针表中的条目均置为0。

如图5所示，根据本实施例的步骤320的过程首先在步骤505，对上述多个数据范围进行特定的编号。

例如在前述0-99、100-199、200-299、……、900-999的多个数据范围的情况下，将数据范围0-99编号为1，将数据范围100-199编号为2，依此类推。

此外，在前述为数据的二进制表示中最高的四位分别设置权值2⁰、2¹、2²、2³并根据该最高四位的加权和的不同而确定16个不同的数据范围的情况下，可以将加权和为1的数据范围编号为1，将加权和为2的数据范围编号为2，依此类推。

在步骤510，从存储在主存储器中的上述数据集的、分配给上述加速器的大块中获取部分数据到该加速器的本地存储器中。其中，该部分数据的量是根据该加速器的本地存储器容量而确定的。

在一个实施例中，可以将该加速器的本地存储器划分为两部分，分别用于存储从主存储器获取的数据和经过了划分后的数据。在此情况下，考虑到上述索引表以及尾指针表所占的空间，上述部分数据的量应小于该加速器的本地存储器容量的一半。但是，并不限于此，本领域技术人员可以利用本领域的技术知识以任何合理的方式来安排该加速器的本地存储器的空间。

在步骤515，使上述加速器从其本地存储器中获取一个未经划分的数据，通过计算将该数据与其所属的数据范围的编号对应起来。

例如，在前述0-99、100-199、200-299、……、900-999的多个数据范围并分别编号为1、2……的情况下，将所获取的数据除以该多个数据范围的步距、即100，并对结果求整，所得到的结果便是该数据所属的数据范围的编号。其中，可以利用CEILING(数值表达式)函数来对除的结果进行求整。例如，CEILING(512/100)的结果将返回6，从而可以确定512属于第6个数据范围，即数据范围500-599。

但是，并不限于此，也可以在步骤505将数据范围0-99编号为0，将数据范围100-199编号为1，依此类推，并利用floor(数值表达式)函数对所获取的数据与上述步距的除的结果求整。例如，floor(512/100)的结果将返回5，从而可以确定512属于第5个数据范围，在此情况下同样也是数据范围500-599。

此外，在前述根据数据的二进制表示中最高四位的加权和的不同而确定16个不同的数据范围并分别编号为1、2……的情况下，可以求取所获取的数据的二进制表示中最高四位的加权和，所得到的结果便是该数据所属的数据范围的编号。

但是，上述对多个数据范围依次进行编号、通过对所获取的数据进行计算使计算结果与数据范围的编号相对应来确定该数据所属的数据范围的方式仅是示例性的，只要能够通过计算将数据与其所属的数据范围对应起来，任何方法都是可以使用的。

在步骤520，根据上述计算的结果，将所获取的数据划分到与该结果相对应的编号的数据范围内，即划分到对应的小块中。

在本实施例中，如图6右侧所示，在上述加速器的本地存储器中，为上述多个数据范围、即小块的每一个均分配了一个固定大小的存储区(图6的APU中被标识为1、2……、7的部分)，例如128B，用于存储划分到该数据范围内的数据。并且，在一个实施例中，该存储区的分配是通过为该多个数据范围的每一个均设定一个固定长度、例如128B的数组来实现的。

从而，在本步骤中，将所获取的数据划分到与计算结果相对应的编号的数据范围内也就是将该数据存储到该加速器的本地存储器中、与该数据范围对应的存储区内。

在步骤525，在将上述数据划分到对应的编号的数据范围、即对应的小块中之后，确定能够准确表明当前该小块中数据值的分布的参数，例如该小块中数据值的均值或方差以及最小值和最大值等。当然，该参数也可以仅是数据值的均值或方差，或者仅是数据值的最小值和最大值。

由于在该加速器将其所负责划分的大块划分为多个小块的过程中，需要逐个数据地进行遍历，所以在遍历的过程中能够同时确定各小块当前的最小值和最大值以及该小块中数据值的均值、方差等。这样，在该大块中的所有数据均被划分到相应的小块中之后，便能够得到各小块最终的最小值、最大值以及数据值的均值或方差等，作为能够准确表明该小块中数据值的分布的参数。

在步骤530，判断上述加速器的本地存储器中、与上述小块对应的存储区是否已满。如果是，则前进到步骤535，否则转到步骤555。

在步骤535，将已满的上述存储区中的数据作为一个数据条写回到上述主存储器中。

具体地，上述加速器将该数据条写回到主存储器中、该加速器所划分的大块中上一次写回的数据条之后。也就是说，该加速器所划分出的各数据条是依次覆写在主存储器中、这些数据条所属的大块原始所在的位置处的。即，由一个大块划分出的各数据条仍被写回到该大块的位置处。从而，从图6可以看出，各加速器所划分出的数据条是依这些数据条所属大块的不同而分别存储的。

在步骤540，更新上述加速器的本地链表。

由于在该加速器的本地存储器的、为上述多个数据范围分配的多个存储区中，每有一个满时该加速器便将其中的数据条写回到主存储器中，所以从图6可以看出，在主存储器中，在由同一个加速器写回的、属于一个大块的数据条中，与同一数据范围对应、即构成一个小块的数据条可能并不是连续存储的，这样，就需要将这些数据条链接起来，形成逻辑上与一个数据范围对应的小块。

在本实施例中，如前所述由索引表和尾指针表构成的反向链表便是用来完成该任务的。

具体地，该加速器的本地索引表中的多个条目与该加速器写回到主存储器中的多个数据条按顺序一一对应，用于存储所对应的数据条的相关索引，该相关索引指示该数据条的、由同一个大块划分出并属于同一数据范围的前一数据条在主存储器中的位置，即指示该数据条的前一数据条是被写回到其所属大块中的第几个数据条。由于如上所述各数据条的大小是相等的，例如均是128B，所以根据该索引很容易在主存储器的相应大块中定位该前一数据条。

此外，该加速器的本地尾指针表中的多个条目各对应于上述多个数据范围中的一个，用于指示对应的数据范围的最后一个数据条在主存储器的其所属大块中的位置。

并且，本步骤中更新该反向链表的过程是：首先根据在步骤535中写回到主存储器中的数据条所属的数据范围，确定尾指针表中对应的条目；其次，将尾指针表中该条目的值写入到索引表中与上述写回到主存储器中的数据条对应的条目内，以指示该数据条的前一数据条的位置；再次，用上述写回到主存储器中的数据条在主存储器的其所属大块中的位置更新尾指针表的上述条目的值，以指示该数据范围中当前的最后一个数据条的位置。

这样，利用上述索引表和尾指针表构成反向链表，能够将属于一个小块的多个数据条从后向前依次链接起来，从而构成如图4中的(c)所示逻辑上聚合但物理上分散的小块。

在步骤545，判断该加速器的本地索引表是否已满。如果是，则前进到步骤550，否则，转到步骤555。

在步骤550，将该加速器的本地索引表中的内容写入到主存储器的索引表中。

由于如前所述各加速器写回的数据条是依这些数据条所属大块的不同而分别存储的，所以主存储器的索引表中与这些数据条对应的索引也相应地是依大块而相互独立的。

这样，在该步骤中，需要使该加速器将其本地索引表中的内容添加到主存储器的索引表中、与该加速器所负责划分的大块对应的部分中。

在步骤555，判断该加速器的本地存储器中是否还存在未经划分的数据，若存在，则返回到步骤515，继续处理下一个数据，否则，前进到步骤560。

在步骤560，判断主存储器中分配给该加速器的大块中是否还存在未经划分的数据，若存在，则返回到步骤510，继续从主存储器的该大块中获取下一部分数据到该加速器的本地存储器中，否则，该过程结束。

以上就是对根据本发明实施例的、图3的步骤320的过程的详细描述。

接着，返回到图3，在步骤325，在将上述多个大块分别划分为多个小块之后，如图4中的(d)所示，在这多个大块之间，进行对应于同一数据范围的小块的合并。从而，如图4中的(e)所示，上述数据集被最终划分为与上述多个数据范围对应的多个合并后的块。

例如，在前述0-99、100-199、200-299、……、900-999的多个数据范围的情况下，将上述多个大块中对应于数据范围0-99的小块合并为一个块，将对应于数据范围100-199的小块合并为一个块，依此类推。

在本步骤中，所谓对应于同一数据范围的小块的合并，并不是物理上将这些小块合并在一起，而是通过主存储器中索引表和尾指针表的规整，利用该索引表和尾指针表将上述数据集中所有属于同一数据范围的数据条逻辑上全局链接起来，形成与该数据范围对应的、合并后的块。

具体地，如前所述，各加速器所生成的索引内容在主存储器的索引表中是依各个大块而相互独立的，并且，各加速器的本地尾指针表中记录的是其相对应的大块中各个小块的最后一个数据条的位置。

所以在该步骤中，首先对于主存储器中的索引表，从其中对应于第二个大块的索引开始，使各索引从原本指示对应的数据条在相应的大块中的位置变为指示该数据条在整个数据集中的全局位置。这可以通过利用索引表统计出各大块的总数据条数，并从第二个大块开始，在各大块所对应的索引的值的基础上增加该块之前的所有大块的总数据条数来实现。参照图6，假设第一个大块中包含8个数据条，这样则使主存储器的索引表中对应于第二个大块的所有条目的索引值增加8。并且，假设该第二个大块也包含8个数据条，这样则使第三个大块所对应的所有索引的值增加16，依此类推，来实现索引表中的索引值从局部指示到全局指示的变化。

此外，对于上述多个加速器的每一个的本地尾指针表来说，与上述主存储器中的索引表同样，也要进行其中各个条目的值从原本指示相应的数据条在其所属大块中的位置到指示该数据条在整个数据集中的全局位置的改变。

此外，在该步骤中，还在主存储器中的索引表中使上述多个大块之间首尾索引相互链接起来。即对于主存储器中的索引表，根据上述多个加速器的每一个的本地尾指针表中修改后的内容，从其中对应于第二个大块的索引开始，将后一个大块的各个小块中的第一个数据条的索引修改为指向前一个大块中对应的小块的最后一个数据条的位置。具体地，从第二个大块开始，根据各大块所对应的加速器的本地尾指针表中的内容，找到该大块中各个小块的第一个数据条，并根据前一个大块所对应的加速器的本地尾指针表中的内容，将这些第一个数据条的索引项修改为指向该前一个大块中相应小块的最后一个数据条。例如，假设第二个大块中与数据范围0-99的小块中的第一个数据条对应的索引的值原本为0，表示其前面不再有数据范围0-99内的数据条，并且假设根据第一个大块所对应的加速器的本地尾指针表中的内容确定第一个大块中数据范围0-99的小块中的最后一个数据条的位置是5，则将第二个大块中与数据范围0-99的小块中的第一个数据条对应的索引的值从0修改为5，以使其与第一个大块中数据范围0-99的小块中的最后一个数据条链接起来。

此外，在该步骤中，还将最后一个大块所对应的加速器的本地尾指针表中的内容写入到主存储器的尾指针表中，作为整个数据集的总体尾指针。

这样，通过修改主存储器中的索引表和尾指针表，可以将该数据集中属于一个数据范围的所有数据条逻辑上链接起来，而无需物理上将这些数据条合并在一起。

在步骤330，根据在步骤320为各个小块统计出的、能够准确表明该小块中数据值的分布的参数，为上述多个合并后的块的每一个合并出能够准确表明该块中数据值的分布的参数。

例如，根据各个小块的数据值的均值或方差以及最小值和最大值，统计出上述多个合并后的块的每一个的数据值的均值或方差以及最小值和最大值。

在步骤335，判断上述多个合并后的块中是否存在大于上述多个加速器的本地存储器容量的块。

在该步骤中，对于上述多个合并后的块的每一个，只要通过利用主存储器中的索引表和尾指针表统计出该块中所包含的数据条的总数，并乘以一个数据条的大小、例如前述的12B，即可得出该合并后的块的大小。

并且，如果在该步骤中判断为存在大于上述多个加速器的本地存储器容量的合并后的块，例如图7中的块2，则该过程前进到步骤340，否则，该过程结束。

在步骤340，对于大于上述多个加速器的本地存储器容量的合并后的块的每一个，根据在步骤330获得的、能够准确表明该块中数据值的分布的参数，为该块确定多个数据范围，然后，返回到步骤315，将该块作为新的数据集进行进一步划分，直到最终得到的块的大小均小于上述多个加速器的本地存储器容量。这样，由于在其后的迭代中所使用的参数都是根据数据集本身计算出的，所以数据的划分会更加精确。

以上就是对本实施例的在多处理器系统上对数据集进行划分的方法的详细描述。在本实施例中，由于通过数据的计算来将数据集划分为多个块，而不是通过数据之间的比较，所以对于分支能力较弱的CBE这样的多处理器系统来说是非常适合的，能够提升在这样的多处理器系统上进行数据集的划分的性能。此外，由于通过链表将属于一个数据范围的多个数据条逻辑上链接为一个块，而不是通过数据的物理移动将属于同一数据范围内的数据聚合为一个块，所以能够极大地降低数据集的划分过程中的数据移动成本，提升数据划分性能。

下面描述本发明的利用上述在多处理器系统上对数据集进行划分的方法的对数据集进行排序的方法。

图8是根据本发明实施例的在多处理器系统上对数据集进行排序的方法的流程图。其中，该多处理器系统具有至少一个核心处理器以及多个加速器。具体地，该多处理器系统例如可以是前述具有一个PPU(核心处理器)和8个SPU(加速器)的CBE。

如图8所示，首先，在步骤805，获取待排序的数据集，并将其存储在主存储器中。

在步骤810，利用图3-7中在多处理器系统上对数据集进行划分的方法，将该待排序的数据集划分为对应于不同的多个数据范围的多个块。

其中，如图9所示，该多个块中的每一个都包括多个数据条，并且这些数据条是逻辑聚合而物理上分散的，这些数据条依靠主存储器中由索引表和尾指针表组成的链表链接起来，形成一个块。

接着，在步骤815，将上述多个块从主存储器分发给上述多个加速器。

在分发的过程中，对于上述多个块的每一个，根据主存储器的尾指针表中的相应条目的值定位该块中的最后一个数据条，并利用索引表依次定位前一数据条，从而依次从主存储器获取这些数据条，如图9右侧所示传送到相应的加速器的本地存储器中，作为分发给该加速器的块。

在步骤820，使该多个加速器并行地对上述多个块分别进行数据排序。其中，在本发明中，对于在该多个加速器中所使用的数据排序算法并没有特别的限制，任何现在已知的数据排序算法，例如插入排序、冒泡排序、选择排序算法等，或将来可知的数据排序算法，都是可以使用的。

在步骤825，如图9所示，按上述不同的多个数据范围的大小，上述多个加速器分别将其排序后的块写回到主存储器中。

以上就是对本实施例的在多处理器系统上对数据集进行排序的方法的详细描述。在本实施例中，由于利用上述图3-7中在多处理器系统上对数据集进行划分的方法，将待排序的数据集划分为对应于不同的多个数据范围的、上述多个加速器的本地存储器容量所允许的大小的多个块，所以能够使上述多个加速器并行地对该数据集进行数据排序，并减少加速器与主存储器之间的数据交换，所以能够极大地提升数据排序性能。

在同一发明构思下，本发明提供一种在多处理器系统中对数据集进行划分的装置。下面结合附图对其进行描述。

图10是根据本发明实施例的在多处理器系统中对数据集进行划分的装置的方框图。其中，该多处理器系统具有至少一个核心处理器以及多个加速器。具体地，该多处理器系统例如可以是前述具有一个PPU(核心处理器)和8个SPU(加速器)的CBE。

如图10所示，本实施例的在多处理器系统中对数据集进行划分的装置10包括：粗略划分单元101、参数获取单元102、数据范围确定单元103、精细划分单元104、块合并单元105以及再划分块确定单元106。

其中，粗略划分单元101在每一次迭代中，将待划分的数据集粗略地划分为多个大块。

参数获取单元102在每一次迭代中，获取上述数据集的能够表明该数据集中数据值的分布的参数。

在优选实施例中，第一次迭代中的上述数据集的能够表明该数据集中数据值的分布的参数是根据该数据集估计出的、大致表明该数据集中数据值的分布的参数，在其后的迭代中的参数是在上一次迭代中统计出的精确参数。

在另一个实施例中，第一次迭代中的上述参数也是根据该数据集计算出的、能够准确表明该数据集中数据值的分布的参数。

数据范围确定单元103在每一次迭代中，根据上述参数，为上述数据集确定多个数据范围。

在一个实施例中，数据范围确定单元103为上述数据集确定具有固定步距的多个连续的数据范围。在另一个实施例中，数据范围确定单元103依数据的二进制表示中多个位的加权和的不同而确定多个数据范围。

精细划分单元104在每一次迭代中，利用上述多个加速器并行地将上述多个大块分别划分为与上述多个数据范围对应的多个小块，其中该多个加速器的每一个通过计算为其划分的大块中的每一个数据确定上述多个数据范围中该数据所属的数据范围。

在本实施例中，在上述多个加速器的每一个的本地存储器中，为上述多个数据范围分别设置有存储区。

并且，如图10所示，精细划分单元104进一步包括数据范围编号单元1041、计算单元1042、数据归类单元1043。

其中，数据范围编号单元1041在每一次迭代中，对上述多个数据范围进行编号。

计算单元1042在每一次迭代中，使上述多个加速器的每一个从其负责划分的大块中依次获取每一个数据并对其进行能够使计算结果与该数据所属的数据范围的编号对应起来的计算。

在一个实施例中，计算单元1042使上述多个加速器的每一个对其所获取的每一个数据，进行将该数据除以上述多个数据范围的固定步距的值并求整的计算，以使求整结果与该数据所属的数据范围的编号相对应。在另一个实施例中，计算单元1042使上述多个加速器的每一个对其所获取的每一个数据，进行求取该数据的二进制表示中多个位的加权和的计算，以使该加权和的值与该数据所属的数据范围的编号相对应。

数据归类单元1043在每一次迭代中，使上述多个加速器的每一个根据计算单元1043的计算结果，将其负责划分的大块中的每一个数据存储到其本地存储器的、与该数据所属的数据范围对应的存储区中。

在本实施例中，在上述多个加速器的每一个的本地存储器中分别设置有用于将该加速器所负责划分的大块中属于同一数据范围的数据链接起来构成小块的链表，该链表由索引表和尾指针表构成。

如图10所示，精细划分单元104还包括数据条回写单元1044、链表更新单元1045。

其中，数据条回写单元1044在每一次迭代中，在确定上述多个加速器中的一个的上述存储区已满时，使该加速器将该存储区中的数据作为一个数据条写回到主存储器中、该加速器所负责划分的大块的位置处。

链表更新单元1045在每一次迭代中，在数据条回写单元1144使上述多个加速器中的一个向主存储器写回了一个数据条时，使该加速器更新其本地存储器中的上述链表，以将该数据条与该加速器所负责划分的大块中属于同一数据范围的其他数据条链接起来。

在本实施例中，在主存储器中设置有用于将上述数据集中属于同一数据范围的数据链接起来的链表，该链表由索引表和尾指针表构成。

如图10所示，精细划分单元104还包括：索引回写单元1046，用于在每一次迭代中，在确定上述多个加速器中的一个的本地索引表已满时，使该加速器将其索引表中的内容写入到主存储器的上述索引表中、与该加速器所负责划分的大块对应的部分中。

如图10所示，精细划分单元104还包括：参数统计单元1047，用于在每一次迭代中，使上述多个加速器的每一个在划分的过程中，实时地为其划分出的多个小块的每一个统计出能够准确表明该小块中当前数据值的分布的参数。该参数包括数据值的均值或方差、最小值和最大值中的一个或多个。

块合并单元105在每一次迭代中，在上述多个大块中，进行对应于同一数据范围的多个小块的合并。

如图10所示，块合并单元105进一步包括索引合并单元1051、参数合并单元1052。

索引合并单元1051在每一次迭代中，修改主存储器中的上述索引表和尾指针表，以使其中的各条目从原本指示相应的数据条在其所属大块中的位置变为指示该数据条在整个数据集中的全局位置，并使上述多个大块之间首尾索引相互链接起来。

参数合并单元1052在每一次迭代中，对于合并后的块的每一个，根据其中所包含的多个小块的、由精细划分单元104中的参数统计单元1047统计出的参数，合并出能够准确表明该合并后的块中数据值的分布的参数。

再划分块确定单元106在每一次迭代中，确定合并后的块中大于上述多个加速器的本地存储器容量的块，作为新的待划分数据集进行下一次迭代。

以上就是对本实施例的在多处理器系统中对数据集进行划分的装置的详细描述。

下面描述本发明的应用了上述在多处理器系统中对数据集进行划分的装置10的对数据集进行排序的装置。

图11是根据本发明实施例的在多处理器系统中对数据集进行排序的装置的方框图。其中，该多处理器系统具有至少一个核心处理器以及多个加速器。具体地，该多处理器系统例如可以是前述具有一个PPU(核心处理器)和8个SPU(加速器)的CBE。

如图11所示，本实施例的在多处理器系统中对数据集进行排序的装置11包括：数据集获取单元111、图10的在多处理器系统中对数据集进行划分的装置10、数据分发单元113、排序单元114以及数据回写单元115。

其中，数据集获取单元111获取待排序的数据集，并将其存储在主存储器中。

图10的在多处理器系统中对数据集进行划分的装置10将上述待排序的数据集划分为对应于不同的多个数据范围的多个块。

数据分发单元113将上述多个块从主存储器分发给上述多个加速器。

排序单元114使上述多个加速器并行地对上述多个块分别进行数据排序。

数据回写单元115按上述不同的多个数据范围的大小，使上述多个加速器分别将其排序后的块写回到主存储器中。

以上就是对本实施例的在多处理器系统中对数据集进行排序的装置的详细描述。其中，上述装置10及11及其各个组成部分，可以由专用的电路或芯片构成，也可以通过计算机(处理器)执行相应的程序来实现。

以上虽然通过一些示例性的实施例对本发明的在多处理器系统上对数据集进行划分的方法和装置以及对数据集进行排序的方法和装置进行了详细的描述，但是以上这些实施例并不是穷举的，本领域技术人员可以在本发明的精神和范围内实现各种变化和修改。因此，本发明并不限于这些实施例，本发明的范围仅以所附权利要求为准。