CN101133414B - 多处理器系统及其信息处理方法 - Google Patents

Abstract

使用两个以上的处理器对共享内存上的大规模表格形式数据进行并行排序。首先，分割待处理的记录并将其分配给两个以上的处理器。其次，各处理器累计与待处理的记录相关联的项目值编号的本地出现次数。然后，将各处理器累计出的项目值编号的本地出现次数变换成项目值编号的全局累计数，即：在各处理器之间被共享使用的累计数。最后，各处理器将全局累计数做为指针使用，调换被分配的记录的顺序。

Description

多处理器系统及其信息处理方法

技术领域

本发明涉及一种由两个以上的处理器共享内存进行并行处理的共享内存型多处理器系统的信息处理方法，特别地，涉及一种利用2个以上的处理器对共享内存上的大规模表格形式的数据进行并行排序的信息处理方法。

本发明还涉及一种执行上述信息处理方法的共享内存型多处理器系统。

本发明还涉及一种用于实现上述信息处理方法的程序。

本发明另外还涉及一种用于存储上述程序的存储介质。

背景技术

近年，计算机在整个社会得到了迅速普及，以互联网为首的计算机网络也已渗透到了经济和生活的各个领域，其中，对大规模数据进行存储和处理更是随处可见。

另一方面，也开发出了一些用于处理大规模数据的、具有较高效率的算法。处理大规模数据，特别是处理大规模表格形式的数据时，常常被用到的处理是排序。一般来说，作为效率较高的排序算法，基数排序(Radix Sort)法和记数排序(Counting Sort或者DistributionCounting Sort)法已为大家所熟知。记数排序法有时也被应用到基数排序法中的各位的排序上，它是一种高效的排序算法，但是，使用记数排序法时需要满足下面几个前提条件：

1)排序的对象是整数；

2)需要事先知道作为排序对象的整数的上限值和下限值；

3)作为排序对象的整数的上限值和下限值之差不能太大。

对此，本发明人已经提出了一种适用于对大规模表格形式数据进行高速检索、合计、排序的数据管理结构(参考国际公开WO 00/10103号公报)。该数据管理结构具有用于表示表格形式数据的项目的各项目值的信息块。在该信息块中，属于表格形式数据的项目的项目值，由被赋予给各项目值的项目值编号以及根据项目值编号的顺序排列的实际项目值的数组来表示。生成一数组，其中，与各记录的项目值相对应的项目值编号按记录编号的顺序排列，各记录的项目值就可以通过从项目值的数组中找到与该记录的项目值编号对应的值的方法来确定。另外，作为表格形式数据中的处理对象的记录则由按顺序排列了记录编号的数组来确定。

信息块是用于按照表格形式数据的各项目的项目值的项目值编号的顺序保存与所述项目值编号相对应的项目值的表格，其中，各项目值的项目值编号是被赋予在各项目的项目值上的顺序(整数)。项目值本身可以是数值(包括整数、定点小数、浮点小数等)，也可以是文字串等各类型的数据。所以，该数据管理结构具有可以用整数的项目值编号来处理各种类型的数据的值的特点。也就是说，依据这个数据管理结构，例如，当对文字串类型数据进行排序时，可以不将文字串类型数据本身作为对象进行排序，而将与文字串类型数据的值相对应的项目值编号作为对象进行排序。此时，排序的结果由按顺序排列了记录编号的数组来表示。因此，本发明人提出的基于信息块的数据管理结构在满足上述记数排序的1)至3)的前提条件方面具有优点。

另一方面，为了高速地实现处理大规模数据所必需的庞大的计算，还尝试使用了并行处理。另外，对于排序也提出了各种各样的并行排序算法。一般地，并行处理的体系结构大致可以分为“分散内存型”和“共享内存型”两种。分散内存型体系结构是各处理器分别具有本地内存，将这些处理器和内存结合起来构成一个系统。在这种方式中，从理论上说是可以实现由数百至数万个处理器组成的硬件系统的设计，但是，在分散内存型体系结构中也存在着一些例如数据管理困难、处理器间的通讯效率低等的技术问题。与此相对的，共享内存型体系结构则是2个以上的多个处理器共享一个巨大容量的内存空间的方式。但是，在这种方式中，处理器群和共享内存之间的流量(Traffic)问题是一个瓶颈，因此，实际上使用一百个以上的处理器来构成系统并非易事。

尽管如此，近年，也出现了一种具有由多个CPU构成的共享内存型多处理器系统的个人计算机。这种个人计算机中所使用的标准的CPU以内存总线(Memory Bus)的5至6倍的内部时钟频率来工作，其内部具有自动并行执行功能以及管道(Pipeline)处理功能，大致使用一个时钟频率(内存总线)来处理一个数据。

发明内容

综上所述，为了处理大规模表格形式数据，需要将高效的排序算法和共享内存型多处理器系统相结合。

记数排序法作为一种为人熟知的高效排序算法，因为其被上述1)至3)所述的前提条件所制约，所以如果不采用本发明人提出的基于上述信息块的数据管理结构，很难将其应用于大规模表格形式数据处理中。另外，使用共享内存型多处理器系统对大规模表格形式数据进行并行排序的技术还不为人所熟知。

因此，本发明的目的在于，提供一使用基于上述信息块的数据管理结构的、使用多个处理器并行地对保存在共享内存内的大规模表格形式数据进行排序的信息处理方法。

另外，本发明的目的还在于，提供一执行上述信息处理方法的共享内存型多处理器系统。

另外，本发明的目的还在于，提供一用于实现上述信息处理方法的程序。

另外，本发明的目的还在于，提供一用于保存上述程序的存储介质。

为了实现上述目的，本发明采用如下技术手段。

本发明依据所述基于信息块的数据管理结构，该信息块是用于按照表格形式数据的各项目的项目值的项目值编号的顺序保存与所述项目值编号相对应的项目值的表格，其中，各项目值的项目值编号是被赋予在各项目的项目值上的顺序(整数)。项目值本身可以是数值(包括整数、定点小数、浮点小数等)，也可以是文字串等类型的数据。通过使用这种数据管理结构，可以用整数的项目值编号来处理各种类型的数据的值。也就是说，依据这个数据管理结构，对任意类型的数据进行排序时，可以不将该任意类型的数据本身作为对象进行排序，而将与该任意类型的数据的值相对应的项目值编号作为对象来进行排序。因此，基于这样的信息块的数据管理结构满足上述记数排序的前提条件。另外，作为表格形式数据中的处理对象的记录由按顺序排列了记录编号的数组来确定，所以排序的结果是由按顺序排列了记录编号的数组来表示的。

通过将上述数据管理结构应用于共享内存型多处理器系统，本发明可以得到一使用多个处理器对保存在共享内存内的大规模表格形式数据进行并行排序的信息处理方法、以及、一用于执行该信息处理方法的共享内存型多处理器系统。因此，本发明的信息处理方法的步骤为，首先，对作为处理对象的记录进行分割，并将其分配给多个处理器；然后，各处理器累计与作为处理对象的记录编号相关联的项目值编号的本地出现次数；其次，将由各处理器累计的项目值编号的本地出现次数变换成项目值编号的全局累计数，即：多个处理器共同使用的累计数；最后，各处理器通过将该全局累计数作为指针来使用，调换被分配的记录的顺序。因此，由本发明可知，在共享内存型多处理器系统中，可以基于记录的某项目的项目值(例如，整数值、定点小数值、浮点小数值、文字串等)对记录进行并行排序。

分配作为处理对象的记录给多个处理器、累计本地出现次数、以及、调换被分配的记录的顺序可以通过由多个处理器并行处理来实现。另外，全局累计数的计算也可以由多个处理器并行处理来实现，但是，因为需要按顺序访问内存，这样导致了访问高速缓冲存储器(Cache)的访问率比较高，因此，可以只使用一个或一部分的处理器来进行处理以保持高速性。

本发明的上述原理可以由以下具体形态来实施。

本发明的第一形态是在共享内存型多处理器中依据记录的预定的项目的项目值来调换记录顺序的信息处理方法。共享内存型多处理器系统包括一共享内存以及能够向该共享内存进行访问的多个处理器，其中，该共享内存用于存储记录编号数组、项目值编号数组以及项目值数组，该记录编号数组用于依据预定的记录顺序保存表格形式数据的记录的记录编号，该项目值编号数组用于依据记录编号保存与表格形式数据的记录的预定的项目的项目值相对应的项目值编号，该项目值数组用于依据与表格形式数据的项目值相对应的项目值编号的顺序保存该项目值。本发明的信息处理方法包括如下步骤：

分割上述记录编号数组并将其分配给第一组的多个处理器(以下简称为“第一组处理器”)的步骤；

在上述第一组处理器的各处理器上，累计与被分配的记录编号数组的一部分中所包含的记录相对应的项目值编号的出现次数的步骤；

分割上述项目值编号的范围并将其分配给第二组的多个处理器(以下简称为“第二组处理器”)的步骤；

在上述第二组处理器的各处理器上，依据在所述项目值编号的顺序，在所述项目值一致的范围内，按照所述记录编号数组的一部分的顺序，将所述被分配的项目值编号的各自的出现次数变换成累计数的步骤；

在上述第一组处理器的各处理器上，将与所述被分配的记录编号数组的一部分中所包含的记录相对应的所述项目值编号的累计数作为指针来使用，将所述被分配的记录编号数组的一部分中所包含的记录编号保存至另一记录编号数组中的步骤。

上述信息处理方法可以实现项目值编号出现次数累计的并行化处理、将出现次数变换至累计数的并行化处理、以及、生成另一记录编号数组的并行化处理。因此，通过将记数排序技术扩张至共享内存型多处理器系统，本发明可以在共享内存型多处理器系统中对大规模表格形式数据进行并行排序。另外，需要说明的是，构成多处理器系统的多个处理器中，任意的第一组处理器都可以用来处理记录编号数组的各部分，任意的第二组处理器都可以用来处理项目值编号范围内的各部分。另外，需要注意的是，第一组处理器的处理器个数和第二组处理器的处理器个数可以是构成多处理器系统的处理器的总数，也可以是其中的一部分。

另外，本发明的信息处理方法，通过对项目值编号导入基数排序的概念，在共享内存型多处理器系统中，可以对大规模表格形式数据进行分阶段并行排序。例如，在项目值编号数组较大的情况下，如果能够对项目值编号数组进行压缩后再使用，就可以实现高速处理。因此，本发明的信息处理方法包括：

依据上述项目值编号的范围设定上述项目值编号的基数的步骤；

对于上述项目值编号的当前位，按照由上述基数所表示的上述项目值编号的最下位至最上位的顺序，反复进行第一次将上述记录编号数组作为当前的记录编号数组，从第二次开始将另一记录编号数组作为当前的记录编号数组的排序处理的步骤。

这样，按最下位至最上位的顺序，并行排序处理在每个项目值编号处都被进行。该排序处理包括以下步骤：

分割上述当前记录编号数组并将其分配给第一组处理器的步骤；

在上述第一组处理器的各处理器上，累计与被分配的记录编号数组的一部分中所包含的记录相对应的项目值编号的当前位的值的出现次数的步骤；

分割上述项目值编号的当前位的值的范围并将其分配给第二组处理器的步骤；

在上述第二组处理器的各处理器上，按照上述项目值编号的当前位的值的顺序，在上述项目值编号的当前位的值一致的范围内，按照上述记录编号数组的一部分的顺序，将被分配的项目值编号的当前位的值的各自的出现次数变换成累计数的步骤；

在上述第一组处理器的各处理器上，将与被分配的记录编号数组的一部分中所包含的记录相对应的上述项目值编号的当前位的值的累计数作为指针，将被分配的上述记录编号数组的一部分中所包含的记录编号保存至另一记录编号数组中的步骤。

由本发明可知，因为与项目值编号的当前位相关的排序处理被按最下位至最上位的顺序反复进行，所以可以实现基于基数排序概念的项目值编号的排序。因此，在共享内存型多处理器系统上，可以对大规模表格形式数据进行并行排序。

在上述多阶段并行排序中，将项目值编号的当前位的值的各自出现次数换算成累计总数的步骤由第二组处理器并行执行。但是，该步骤如果不采用多个处理器并行执行，同样也可以被高速处理。其原因在于该步骤的处理是顺序进行的，对高速缓冲存储器的访问率较高。因此，本发明的信息处理方法包括如下步骤：

依据上述项目值编号的范围设定上述项目值编号的基数的步骤；

对于上述项目值编号的当前位，按照由上述基数所表示的上述项目值编号的最下位至最上位的顺序，反复进行第一次将上述记录编号数组作为当前的记录编号数组，从第二次开始将另一记录编号数组作为当前的记录编号数组的排序处理的步骤。

该排序处理包括以下步骤：

分割上述当前记录编号数组并将其分配给多个处理器的步骤；

在各处理器上，累计与被分配的记录编号数组的一部分中所包含的记录相对应的项目值编号的当前位的值的出现次数的步骤；

至少在一个处理器上，按照上述项目值编号的当前值的顺序，在与上述项目值编号的当前位的值一致的范围内，依据上述记录编号数组的一部分的顺序，将被分配的项目值编号的当前位的值的各自的出现次数变换成累计数的步骤；

在上述各处理器上，将与被分配的记录编号数组的一部分中所包含的记录相对应的上述项目值编号的当前位的值的累计数作为指针，将被分配的上述记录编号数组的一部分中所包含的记录编号保存至另一记录编号数组中的步骤。

在该信息处理方法中，项目值编号的当前位的范围也可以不分割给多个处理器，可以使用至少一个处理器，最好是一个处理器，将项目值编号的当前位的值的出现次数按顺序变换成累计数。此时，因为与项目值编号的当前位相关的排序处理也是按照最下位至最上位的顺序被反复执行的，同样也可以实现基于基数排序概念的项目值编号的排序。因此，在共享内存型多处理器系统上，可以对大规模表格形式数据进行并行排序。

另外，为了实现上述目的，本发明还提供一依据记录的预定的项目的项目值调换记录顺序的信息处理方法，该信息处理方法应用于一共享型多处理器系统，该系统包括一共享内存以及能够访问该共享内存的多个处理器，其中，该共享内存用于存储记录编号数组、项目值编号数组以及项目值数组，该记录编号数组用于依据预定的记录顺序保存表格形式数据的记录的记录编号，该项目值编号数组用于依据记录编号保存与表格形式数据的记录的预定的项目的项目值相对应的项目值编号，该项目值数组用于依据与表格形式数据的项目值相对应的项目值编号的顺序保存该项目值，该信息处理方法包括如下步骤：

分割上述记录编号数组并将其分配给上述多个处理器的步骤；

在上述多个处理器的各处理器上，将被分配的记录编号数组的一部分中所包含的记录的顺序依据与该记录相对应的项目值编号进行替换，并将该记录的记录编号保存至另一记录编号数组的步骤。

另外，为了实现上述目的，本发明还提供一根据记录的预定的项目的项目值调换记录顺序的信息处理方法，该信息处理方法应用于一共享内存型多处理器系统中，该共享内存型多处理器系统包括一共享内存和能够访问该共享内存的多个处理器，其中，该共享内存用于存储记录编号数组、项目值编号数组以及项目值数组，该记录编号数组用于依据预定的记录顺序保存表格形式数据的记录的记录编号，该项目值编号数组用于依据记录编号保存与表格形式数据的记录的预定的项目的项目值相对应的项目值编号，该项目值数组用于依据与表格形式数据的项目值相对应的项目值编号的顺序保存该项目值，该信息处理方法包括如下步骤：

依据上述项目值编号的范围设定上述项目值编号的基数的步骤；

对于由上述基数所表示的上述项目值编号的上面的位进行替换上述记录编号数组中的记录编号，并生成按上述项目值编号的上面的位的值的顺序所区分的中间记录编号数组的步骤；

依据上述中间记录编号数组的每个区间来分配处理器的步骤；

上述依据每个区间所分配的各处理器，按照上述项目值编号的下面的位的值的顺序，替换上述中间记录编号数组的上述区间内的记录编号的步骤。

本发明的第二形态是一具有共享内存和能够访问该内存的多个处理器的、执行上述本发明的信息处理方法的共享内存型多处理器系统。在本发明的共享内存型多处理器系统中，该共享内存用于存储记录编号数组、项目值编号数组以及项目值数组，该记录编号数组用于依据预定的记录顺序保存表格形式数据的记录的记录编号，该项目值编号数组用于依据记录编号保存与表格形式数据的记录的预定的项目的项目值相对应的项目值编号，该项目值数组用于依据与表格形式数据的项目值相对应的项目值编号的顺序保存该项目值。因此，本发明的共享内存型多处理器可以使用基于块信息的数据管理结构。

各处理器具有如下单元：

用于决定上述记录编号数组中的、自处理器负责处理的一部分的决定单元；

用于累计与上述记录编号数组的一部分中所包含的记录相对应的项目值编号的出现次数的累计单元；

按照上述项目值编号的顺序，在上述项目值编号一致的范围内，依据上述记录编号数组的一部分的顺序，将上述负责处理范围内的项目值编号的各自的出现次数变换成累计数的变换单元；

将与上述记录编号数组的一部分中所包含的记录相对应的上述项目值编号的累计数作为指针来使用，将上述记录编号的一部分中所包含的记录编号保存至另一记录编号数组的保存单位。

因为各处理器可以并行工作，因此可以实现出现次数累计的并行化处理、将出现次数变换成累计总数的并行化处理、以及、生成另一记录编号数组的并行化处理。

在进行将项目值编号的出现次数变换成累计数时，需要使得到的累计数按项目值编号的顺序移动。为此，负责将上述项目值编号范围内的领先范围的处理器的上述出现次数变换成累计数的变换单元所得到的上述累计数，要被负责将其后范围的处理器的上述出现次数变换成累计数的变换单元所参照。

另外，本发明的共享内存型多处理器还可以通过对项目值编号导入基数排序的概念对大规模表格形式数据进行多阶段排序，因此，各处理器包含以下单元：

依据上述项目值编号的范围设定上述项目值编号的基数的基数设定单元；

按照由上述基数所表示的上述项目值编号的最下位至最上位的顺序设定当前位，反复进行第一次将上述记录编号数组设定为当前的记录编号数组，从第二次开始将另一记录编号数组设定为当前的记录编号数组的排序处理的反复处理单元。

这样，从项目值编号的最下位至最上位的每位的并行处理都按顺序被执行。上述反复处理单元还包括以下单元：

用于决定上述记录编号数组中的、自处理器负责处理的一部分的记录编号决定单元；

用于累计与上述记录编号数组的一部分中所包含的记录相对应的项目值编号的当前位的值的出现次数的出现次数累计单元；

用于决定上述项目值编号的当前位的值的范围内的、自处理器负责处理的范围的项目值编号范围决定单元；

按照上述项目值编号的当前位的值的顺序，在上述项目值编号的当前位的值一致的范围内，依据上述记录编号数组的一部分的顺序，将上述负责处理的范围内的项目值编号的当前位置的值的出现次数变换成累计数的累计数变换单元；

将与上述记录编号数组的一部分中所包含的记录相对应的上述项目值编号的当前位的值的累计数作为指针来使用，将上述记录编号数组的一部分中所包含的记录编号保保存至另一记录编号数组的另一记录编号保存单位。

因此，本发明可以实现项目值编号的各位的并行排序处理。由本发明可知，在项目值编号的各位的排序处理中，多个处理器可以实现出现次数的累计、出现次数向累计总数的变换、以及、另一记录编号数组的生成的并行处理。

另外，由于出现次数向累计数的变换由多个处理器分别负责执行，因此，在本发明中，负责将上述项目值编号的当前位的范围内的领先范围的处理器的上述出现次数变换成累计数的变换单元所得到的上述累计总数，要被负责将其后范围的处理器的上述出现次数变换成累计总数的变换单元所参照。

另外，基于对大规模表格形式数据进行多阶段并行排序的本发明的共享内存型多处理器系统也可以使用至少一个，最好是一个处理器来进行当前位的值的各自出现次数的累计数累计。因此，在本发明的共享内存型多处理器系统中，各处理器包括如下单元：

依据上述项目值编号的范围设定上述项目值编号的基数的基数设定单元；

按照由上述基数所表示的上述项目值编号的最下位至最上位的顺序设定当前位，反复进行第一次将上述记录编号数组设定为当前的记录编号数组，从第二次开始将另一记录编号数组设定为当前的记录编号数组的排序处理的反复处理单元。

执行各处理器的上述排序处理的反复处理单元包括以下单元：

用于决定上述记录编号数组中的、自处理器负责处理的一部分的记录编号决定单元；

用于累计与上述记录编号数组的一部分中所包含的记录相对应的项目值编号的当前位的值的出现次数的出现次数累计单元。

另外，执行至少一个处理器的上述排序处理的反复处理单元还包括累计数变换单元，该累计数变换单元按照上述项目值编号的当前位的值的顺序，在上述项目值编号的当前值一致的范围内，依据上述记录编号数组的一部分的顺序，将上述项目值编号的当前位的值的各自出现次数变换成累计数。

另外，执行上述排序处理的上述反复处理单元还包括另一记录编号保存单位，该另一记录编号保存单位将与上述记录编号数组的一部分中所包含的记录相对应的上述项目值编号的当前位的值的累计数作为指针来使用，将上述记录编号数组的一部分中所包含的记录编号保保存至另一记录编号数组。

由本发明可知，由于各处理器可以不需要决定项目值编号的当前位的值的范围内的自处理器负责处理的范围，也不需要采用多个处理器来并行执行出现次数向累计数的变换处理，因此可以简化共享内存型多处理器系统的构成。

另外，本发明的第三形态是提供一用于实现上述信息处理方法的程序。

再有，本发明的第四形态是提供一储存上述程序的存储介质。

综上所述，本发明可以提供一在共享内存型的并行处理环境下能够实现大规模表格形式数据的高速并行排序的信息处理装置。

附图概述

图1是本发明的一个实施例的计算机系统概要图。

图2是用于说明数据管理结构的表格形式数据的一个例子的示意图。

图3是本发明的一个实施例的数据管理结构的说明图。

图4A和图4B是本发明的一个实施例的作为排序对象的数据结构的说明图。

图5是本发明的一个实施例的并行排序方法的流程图。

图6是本发明的一个实施例的并行排序方法的初始化步骤的说明图。

图7A和图7B是本发明的一个实施例的并行排序方法的计数步骤的说明图之一。

图8A和图8B是本发明的一个实施例的并行排序方法的计数步骤的说明图之二。

图9A和图9B是本发明的一个实施例的并行排序方法的计数步骤的说明图之三。

图10A和图10B是本发明的一个实施例的升序的并行排序方法的累计数处理步骤的说明图。

图11A和图11B是本发明的一个实施例的升序的并行排序方法的传送步骤的说明图之一。

图12A和图12B是本发明的一个实施例的升序的并行排序方法的传送步骤的说明图之二。

图13A和图13B是本发明的一个实施例的升序的并行排序方法的传送步骤的说明图之三。

图14A至图14C是对图4B所示的数据结构利用本发明的一个实施例的升序的并行排序方法进行排序后的结果的示意图之一。

图15A和图15B是对图4B所示的数据结构利用本发明的一个实施例的升序的并行排序方法进行排序后的结果的示意图之二。

图16A和图16B是本发明的一个实施例的降序的并行排序方法的累计数处理步骤的说明图。

图17A和图17B是本发明的一个实施例的降序的并行排序方法的传送步骤的说明图之一。

图18A和图18B是本发明的一个实施例的降序的并行排序方法的传送步骤的说明图之二。

图19A和图19B是本发明的一个实施例的降序的并行排序方法的传送步骤的说明图之三。

图20A和图20B是对图4B所示的数据结构利用本发明的一个实施例的降序的并行排序方法进行排序后的结果的示意图之一。

图21A至图21C是对图4B所示的数据结构利用本发明的一个实施例的降序的并行排序方法进行排序后的结果的示意图之二。

图22是本发明的一个实施例的多阶段并行排序方法的流程图。

图23A和图23B是本发明的一个实施例的多阶段并行排序方法的第一阶段的计数步骤的说明图之一。

图24A和图24B是本发明的一个实施例的多阶段并行排序方法的第一阶段的计数步骤的说明图之二。

图25A和图25B是本发明的一个实施例的多阶段并行排序方法的第一阶段的计数步骤的说明图之三。

图26A和图26B是本发明的一个实施例的升序的多阶段并行排序方法的第一阶段的累计数处理步骤的说明图。

图27A和图27B是本发明的一个实施例的升序的多阶段并行排序方法的第一阶段的传送步骤的说明图之一。

图28A和图28B是本发明的一个实施例的升序的多阶段并行排序方法的第一阶段的传送步骤的说明图之二。

图29和图29B是本发明的一个实施例的升序的多阶段并行排序方法的第一阶段的传送步骤的说明图之三。

图30是本发明的一个实施例的多阶段并行排序方法的第二阶段的初始化步骤的说明图。

图31A和图31B是本发明的一个实施例的多阶段并行排序方法的第二阶段的计数步骤的说明图之一。

图32A和图32B是本发明的一个实施例的多阶段并行排序方法的第二阶段的计数步骤的说明图之二。

图33A和图33B是本发明的一个实施例的多阶段并行排序方法的第二阶段的计数步骤的说明图之三。

图34是本发明的一个实施例的升序的多阶段并行排序方法的第二阶段的累计数处理步骤的说明图。

图35A和图35B是本发明的一个实施例的升序的多阶段并行排序方法的第二阶段的传送步骤的说明图之一。

图36A和图36B是本发明的一个实施例的升序的多阶段并行排序方法的第二阶段的传送步骤的说明图之二。

图37A和图37B是本发明的一个实施例的升序的多阶段并行排序方法的第二阶段的传送步骤的说明图之三。

图38A至图38C是对图4B所示的数据结构利用本发明的一个实施例的升序的并行排序方法进行排序后的结果的示意图之一。

图39A和图39B是对图4B所示的数据结构利用本发明的一个实施例的升序的并行排序方法进行排序后的结果的示意图之二。

图40是用于说明多阶段排序的数据结构图。

图41A至图41D是多阶段排序的第一阶段的计数处理以及累计数处理的说明图。

图42A和图42B是多阶段排序的第一阶段的记录编号传送的说明图。

图43是多阶段排序的第一阶段的记录编号传送结果的说明图。

图44是多阶段排序的第二阶段的初始状态的示意图。

图45A至图45C是多阶段排序的第二阶段的计数处理以及累计数处理的说明图。

图46A和图46B是多阶段排序的第二阶段的记录编号传送的说明图。

本发明的最佳实施方式

以下参考附图说明本发明的最佳具体实施例。

[计算机系统构成]

图1是用于执行本发明的、依据记录的预定项目的项目值进行调换记录顺序的信息处理方法的计算机系统的一个实施例的概略图。如图1所示，该计算机系统10包括：用于通过执行程序对系统全体以及各组成部分进行控制的p个处理器(CPU)12-1，12-2，...12-p、用于保存工作数据等的共享内存(例如、RAM：Random Access Memory)14、用于保存程序等的ROM(Read Only Memory)16、用于访问硬盘等固定存储介质18和CD-ROM19的CD-ROM驱动器20、用于CD-ROM驱动器20等与外部网络(图中未表示)相连接的外部端子间设置的接口(I/F)22、由键盘和鼠标组成的输入装置24、以及、CRT显示装置26。CPU12、RAM14、ROM16、外部存储介质18、I/F22、输入装置24以及显示装置26经由总线(Bus)28相互连接。尽管图中未表示，各CPU也可以包含其本身固有的本地内存。

本实施例的、依据记录的预定项目的项目值调换记录顺序的程序，其可以被保存在CD-ROM19内，然后由CD-ROM驱动器20所读取，也可以被预先保存在ROM16内。另外，也可以暂时将从CD-ROM19读出的程序保存在外部存储介质18的预定领域内。或者，上述程序也可以经由网络(图中未表示)、外部端子以及I/F22由外部供给。

另外，本发明的实施例中的共享内存型多处理器系统是通过使计算机系统10执行依据记录的预定项目的项目值调换记录顺序的程序来实现的。

[基于信息块的数据管理结构]

图2是用于说明数据管理结构的表格形式数据的一个例子的示意图。通过采用上述国际公开第WO 00/10103号中提出的数据管理结构，该表格形式数据在计算机内被保存成如图3所示的数据结构。

如图3所示，在与表格形式数据的各记录的排列顺序的编号以及内部数据的排列顺序的编号相对应的数组301(以下将该数组简称为“OrdSet”)中，按表格形式的每个记录将内部数据的排列顺序的编号设置为数值。该例中，所有的表格数据都被表示为内部数据，所以表格形式数据的记录编号和内部数据的排列顺序的编号一致。

例如，关于性别，与表格形式数据的记录0相对应的内部数据的排列顺序的编号由数组OrdSet301可知其为“0”。排列顺序的编号为“0”的记录的实际性别值，也就是“男”或“女”，可以通过参照指向按照预定顺序将实际值排序后得到的数值列表(以下将该数值列表简称为“VL”)303的指针数组(以下将该指针数组简称为“VNo”)302得到。指针数组302根据保存在数组OrdSet301内的排列顺序编号的顺序保存指向实际数值列表303中的元素的指针。因此，与表格形式数据的记录“0”相对应的性别的项目值可以通过如下步骤取得：(1)从数组OrdSet301中取出与记录“0”相对应的排列顺序编号“0”；(2)从指向数值列表的指针数组302中取出与记录“0”相对应的元素“1”；(3)从数值列表303中取出由从指向数值列表的指针数组302中取出的元素“1”所指向的元素“女”。

对于其他记录以及年龄和身高等，也可以采用同样的方法取出其项目值。

如上所述，表格形式数据由数值列表VL和指向该数值列表的指针数组VNo的组合来表示，该组合被称为“信息块”。图3中，与性别、年龄以及身高相关的信息块被分别表示为信息块308、309和310。

单一的一台计算机，如果其只具有单一内存(实际上也可以有多个内存，但其都被设置在一个地址空间并被访问，从这个意义上说就是单一内存)，可以在该单一内存内保存顺序集合的数组OrdSet、构成各信息块的数值列表VL、以及、指针数组VNo。但是，为了保存大量的记录，内存容量也将随之变得很大，因此，最好是能够对这些大量的记录进行并行处理。

因此，本实施例中，保存在共享内存内的记录数据被多个处理器所访问，通过多个处理器的并行处理实现高速排序。

[并行排序]

其次，对本发明的一个实施例的、在共享内存型多处理器系统上依据记录的预定项目的项目值调换记录顺序的信息处理方法、即并行排序方法进行说明。图4A和图4B是作为排序对象的数据结构的示意图。图4A所示表格形式数据401采用行列形式来表示，作为排序对象的数据构造，其包含从记录0到记录19的20个记录，各记录由年龄和地区两个项目构成。图4B所示数据结构402表示保存在计算机系统10的共享内存14内的数据结构。图4B的记录编号数组(OrdSet：表示顺序的集合)403是按照预定顺序保存记录编号0至19的数组。本例中，记录编号是按照0至19的顺序保存的。年龄和地区的数据，分别以信息块404和信息块405的形式保存。年龄信息块404由依据记录编号的顺序保存了与年龄的项目值相对应的项目值编号的项目值编号数组(以下也简称数值编号VNo)406、以及、依据与年龄的项目值相对应的项目值编号的顺序保存了该项目值的项目值数组(以下也简称数值列表VL)407构成。同样，地区信息块405由依据记录编号的顺序保存了与地区的项目值相对应的项目值编号的项目值编号数组408、以及、依据与地区的项目值相对应的项目编号的顺序保存了该项目值的项目值数组409构成。计算机系统10的p个处理器12-1，...，12-p能够对共享内存上的这些数据进行访问。

图5是本发明的一个实施例的并行排序方法的流程图。本实施例中，CPU为4个，并且所有CPU都并行工作。需要注意的是，系统内的CPU的总数以及并行工作的CPU的个数并不局限于本例。另外，下面为了便于说明，关于年龄的项目，按年龄的升序来排序。另外，年龄的项目值数组的元素是按年龄的升序来排列的。并行排序方法由步骤501至505的5个步骤构成。

步骤501：将记录编号数组分割成4部分并将各部分分配给4个CPU(参考图6)。

步骤502：各CPU并行地累计与被分配的记录编号数组的一部分中所包含的记录相对应的项目值编号的出现次数(参考图7A、图7B至图9A、图9B)。

步骤503：将项目值编号的范围，即从项目值编号0至项目值编号4的5个值分配给4个CPU。例如，项目值编号0和1被分配给CPU-0，项目值编号2至4被分别分配给CPU-1至CPU3(参考图10A)。

步骤504：4个CPU分别按照项目值编号的顺序，在项目值编号一致的范围内，依据记录编号数组的一部分的顺序，将被分配的项目值编号的各自的出现次数变换为累计数(参考图10A和图10B)。

步骤505：4个CPU将与被分配的记录编号数组的一部分中所包含的记录相对应的项目值编号的累计数作为指针，将被分配的记录编号数组的一部分中所包含的记录编号保存至另一记录编号数组(参考图1IA、图11B至图13A、图13B)。

下面对上述各步骤进行详细说明。

图6是并行排序方法的初始化步骤501的说明图。从记录编号数组开头开始的每4个记录被分别分配给了CPU-0至CPU-3的4个CPU。例如，CPU-0负责从记录编号数组的开头的OrdSet[0]开始至第5个的OrdSet[4](OrdSet[x]中的x表示数组OrdSet的下标)。另外，共享内存14中设置了用于累计项目值编号的出现次数的累计数组Count-0、Count-1、Count-2以及Count-3，并对应于各CPU。Count数组的个数与CPU的个数相同。Count数组的数组大小与VL数组的数组大小相同。Count数组的元素被初始化为0。

图7A、图7B至图9A、图9B是并行排序方法的累计步骤502的说明图。图7A的子步骤1中，例如，CPU-0首先读出OrdSet[0]的值0，然后用读出的值0做下标读出VNo[0]的值1，接下来用该值1做下标将Count-0[1]的值0加1至1。同样，CPU-1首先读出OrdSet[5]的值5，然后用读出的值5做下标读出VNo[5]的值2，接下来用该值2做下标将Count-1[2]的值0加1至1。对于CPU-2和CPU3也相同。图7B的子步骤2中，例如，CPU-0首先读出OrdSet[1]的值1，然后用读出的值1做下标读出VNo[1]的值3，接下来用该值3做下标将Count-0[3]的值0加1至1。对于CPU-1、CPU-2、CPU-3也相同。各处理器如图8A、图8B和图9A所示，首先读出各自处理器负责的数组OrdSet的各元素，然后以该元素为下标读出数组VNo的元素，接下来，以读出的元素为下标将对应的Count数组的元素加1。这样得到的累计结果如图9B所示。图9A和图9B的数组Count-0的元素Count-0[i]表示的是与CPU-0负责的数组OrdSet的OrdSet[0]至OrdeSet[4]范围内的各记录相对应的年龄的项目值编号i的出现次数。例如，Count-0[0]表示CPU-0的负责范围内的项目值编号0的出现次数为1次，Count-3[1]表示CPU-3的负责范围内的项目值编号1的出现次数为2次。

图10A和图10B是并行排序方法的累计数处理步骤503和504的说明图。本例中，对应于升序排序，进行的是项目值编号的升序的累计数处理。CPU-0负责数组Count的第一行和第二行(即：项目值编号为0和1)的累计数处理，CPU-1至CPU-3分别负责数组Count的第三行至第五行(即：项目值编号3至5)的累计数处理。如图10A所示，累计数处理首先在数组Count的横方向(即：下标相同的行)上优先进行，然后，通过将领先行的累计数加到后续行的累计数上得到全体的累计数。需要注意的是，横方向的累计数处理可以采用各CPU并行执行。

一般地，如果将第i个(0≤i≤p-1)CPU的CPU-i累计的项目值编号j(0≤j≤q-1)的累计值用Count[i][j]来表示，累计数用Count’[i][j]来表示，那么累计数处理可以描述如下：

Count’[0][0]＝0

Count’[i][0]＝Count’[i-1][q-1]+Count[i-1][q](i＞1)

Count’[i][j]＝Count’[i][j-1]+Count[i][j-1](j＞1)

如上所述，在进行累计数计算时，需要将Count’[i-1][q-1]从上一行向下一行移动。因此，本实施例中，尽管累计数之计算由CPU分担执行，也可以选择一个CPU使其单独进行累计数的计算。

图10B是将累计数的顺序按竖方向表示成一列的示意图。例如，在图10B中，(1)Count-0：0行表示的是数组Count-0的开头的元素Count-0[0]的累计值1变换成累计数0。也就是说，将下面的累计值的序列：

1，2，2，0，2，0，2，2，0，2，0，1，1，1，0，1，1，0，1，1

进行累计数处理后，可以得到下面的结果：

0，1，3，5，5，7，7，9，11，11，13，13，14，15，16，16，17，18，18，19。

图11A、图11B至图13A、图13B是将记录编号保存至另一记录编号数组中的传送步骤505的说明图。传送步骤中，各CPU首先从记录编号数组OrdSet中读出各自负责的范围内的记录编号，然后，以该记录编号为下标从指针数组VNo中读出项目值编号，接下来，以该项目值编号为下标从与各处理器相对应的、进行了累计数处理的Count数组中读出累计数值，再以读出的该累计数值为指针将记录编号保存至另一记录编号数组OrdSet’中，同时，将Count数组的累计数值各加1。

例如，在图11A的子步骤1中，CPU-0首先读出OrdSet[0]的值0(即：记录编号0)，然后读出VNo[0]的值1，接下来读出相应的Count数组的Count-0[1]的值5，然后将记录编号0赋给OrdSet’[5]，同时，将Count-0[1]的值加1至6。该记录编号的传送处理同样被应用于图11B所示的子步骤2、图12A和图12B所示的子步骤3和4、以及、图13A的子步骤5中，最后得到如图13B所示的另一记录编号数组OrdSet’。

图14A至图14C以及图15A和图15B是将本发明的一个实施例的并行排序方法应用于图4所示的数据结构的结果示意图。本例中，因为对年龄进行升序排序，从结果可以看出，作为结果的记录编号数组OrdSet’内，具有作为年龄的项目值的16岁、18岁、20岁、21岁以及23岁的记录是按照年龄的顺序来排列的。另外，年龄一致的记录的顺序是按照原来的记录编号数组OrdSet中的顺序被保存的。

以上对采用并行排序方法对年龄按升序排序的例子进行了说明，该并行排序方法对年龄按降序进行排序也同样适用。降序排序也和升序排序同样进行，但累计数处理的顺序与升序的不同。图16A和图16B是本发明的一个实施例的并行(降序)排序方法的累计数步骤的说明图。如图16A所示，累计数处理首先在数组Count的横方向(即：下标相同的行)上优先进行，然后，通过将后续行的累计数加到先前行的累计数来得到全体的累计数。另外，需要注意的是，横方向的累计数处理也可以由各CPU并行执行。

一般地，如果将第i个(0≤i≤p-1)CPU的CPU-i累计的项目值编号j(0≤j≤q-1)的累计值用Cpunt[i][j]来表示，累计数用Count’[i][j]来表示，那么累计数处理可以描述如下：

Count’[p-1][0]＝0

Count’[i][0]＝Count’[i+1][q-1]+Count[i+1][q](i＞1)

Count’[i][j]＝Count’[i][j-1]+Count[i][j-1](j＞1)

如上所述，在进行累计数计算时，需要将Count’[i+1][q-1]从后一行向前一行移动。因此，本实施例中，尽管累计数的计算由CPU分担执行，也可以选择一个CPU使其单独进行该累计数的计算。图16B是将累计数的顺序按竖方向表示成一列的示意图。在图16B中，例如，(1)Count-0：4行表示的是数组Count-0的开头的元素Count-0[4]的累计值1被变换成累计数0。

图17A和图17B至图19A和图19B是降序的并行排序方法的传送步骤505的说明图。传送步骤中，各CPU首先从记录编号数组OrdSet中读出各自负责的范围内的记录编号，然后，以该记录编号为下标从指针数组VNo中读出项目值编号，接下来，以该项目值编号为下标，从与自处理器相对应的、进行了累计数处理的Count数组中读出累计数值，再以读出的该累计数值为指针将记录编号保存至另一记录编号数组OrdSet’中，同时，将Count数组的累计数值各加1。

图20A、图20B以及图21A至图21C是将本发明的一个实施例的降序的并行排序方法应用于图4所示的数据结构的结果示意图。本例中，因为是对年龄进行降序排序，所以，从结果可以看出，作为结果的记录编号数组OrdSet’内，具有作为年龄的项目值的23岁、21岁、20岁、18岁以及16岁的记录是按照年龄的顺序来排列的。另外，年龄相同的记录的顺序是按照原来的记录编号数组OrdSet中的顺序被保存的。

[并行累计数计算]

下面对上述实施例中说明的累计数处理步骤504进行更详细的说明。在得到图9B所示的累计结果时，进行图10A和图10B所示的累计数计算。为了并行地进行累计数计算，各CPU中被分配了作为对象的项目值编号的值的范围。CPU-0中的项目值编号为0和1，CPU-1中的项目值编号为2，CPU-2中的项目值编号为3，CPU-3中的项目值编号为4。因此，如果将Count数组的元素如上所述用Count[i][j]的形式表示(i表示负责累计的CPU的编号，j表示项目值编号)，那么各CPU的累计数处理的负责范围如下：

·CPU-0的负责范围(项目值编号为0和1)

Count[0][0]＝1

Count[1][0]＝2

Count[2][0]＝2

Count[3][0]＝0

Count[0][1]＝2

Count[1][1]＝0

Count[2][1]＝2

Count[3][1]＝2

·CPU-1的负责范围(项目值编号为2)

Count[0][2]＝0

Count[1][2]＝2

Count[2][2]＝0

Count[3][2]＝1

·CPU-2的负责范围(项目值编号为3)

Count[0][3]＝1

Count[1][3]＝1

Count[2][3]＝0

Count[3][3]＝1

·CPU-3的负责范围(项目值编号为4)

Count[0][4]＝1

Count[1][4]＝0

Count[2][4]＝1

Count[3][4]＝1

如上所述确定好负责范围之后，首先，计算各CPU-i负责的范围内的累计的小计Sum[i]，得到的小计结果如下：

Sum[0]＝11

Sum[1]＝3

Sum[2]＝3

Sum[3]＝3

上述小计的计算采用并行处理。

然后，将上述小计从CPU-0向CPU-3顺序移动，计算小计的累计数Aggr_sum[i]，其结果如下：

Aggr_sum[0]＝0

Aggr_sum[1]＝Aggr_sum[0]+sum[0]＝11

Aggr_sum[2]＝Aggr_sum[1]+sum[1]＝14

Aggr_sum[3]＝Aggr_sum[2]+sum[2]＝17

其中，小计的累计数的第一个值被定义为0。

最后，各CPU-i将负责范围内的Count值变换为累计数，然后通过将算出的小计的累计数Aggr_sum[i]加到该Count值的累计数上，得到最终累计的累计数Count’。该Count’的计算也是并行处理。因此，可以得到如下结果：

·CPU-0的负责范围(项目值编号为0和1)

Count’[0][0]＝0+Aggr_sum[0]＝0+0＝0

Count’[1][0]＝Count’[0][0]+Count[0][0]＝0+1＝1

Count’[2][0]＝Count’[1][0]+Count[1][0]＝1+2＝3

Count’[3][0]＝C0unt’[2][0]+Count[2][0]＝3+2＝5

Count’[0][1]＝Count’[3][0]+Count[3][0]＝5+0＝5

Count’[1][1]＝Count’[0][1]+Count[0][1]＝5+2＝7

Count’[2][1]＝Count’[1][1]+Count[1][1]＝7+0＝7

Count’[3][1]＝Count’[2][1]+Count[2][1]＝7+2＝9

·CPU-1的负责范围(项目值编号为2)

Count’[0][2]＝0+Aggr_sum[1]＝0+11＝11

Count’[1][2]＝Count’[0][2]+Count[0][2]＝11+0＝11

Count’[2][2]＝Count’[1][2]+Count[1][2]＝11+2＝13

Count’[3][2]＝Count’[2][2]+Count[2][2]＝13+0＝13

·CPU-2的负责范围(项目值编号为3)

Count’[0][3]＝0+Aggr_sum[2]＝0+14＝14

Count’[1][3]＝Count’[0][3]+Count[0][3]＝14+1＝15

Count’[2][3]＝Count’[1][3]+Count[1][3]＝15+1＝16

Count’[3][3]＝Count’[2][3]+Count[2][3]＝16+0＝16

·CPU-3的负责范围(项目值编号为4)

Count’[0][4]＝0+Aggr_sum[3]＝0+17＝17

Count’[1][4]＝Count’[0][4]+Count[0][4]＝17+1＝18

Count’[2][4]＝Count’[1][4]+Count[1][4]＝18+0＝18

Count’[3][4]＝Count’[2][4]+Count[2][4]＝18+1＝19

上述结果与图10B所示累计数的计算结果相同。

[多阶段并行排序]

上述基于计数排序的并行排序还可以与基数排序的概念组合使用。项目值数组VL较大时，即：项目值编号的个数较多时，通过将项目值编号用基数来表达，在每位上进行上述并行排序，可以实现高效率的排序。下面对上述多阶段并行排序的方法进行说明。特别地，本实施例的多阶段排序是对从最下位开始顺序地至当前位进行排序处理，最后通过对最上位进行排序处理以完成最终的排序。

本发明实施例的多阶段并行排序方法的一个例子也是采用上述并行排序方法的实施例中使用的图4B的数据结构。本实施例中，CPU的个数为4个，并且这些CPU都并行工作。另外，需要注意的是，系统内的CPU总数以及并行工作的CPU的个数并不局限于本实施例。另外，以下为了便于说明，关于年龄的项目，以年龄的升序来排序。另外，年龄的项目值数组的元素也是按年龄的升序来排列的。图4B的数据结构中，与年龄相关的项目值编号VNo为0至4的值，所以，将基数设为4(即：基数＝4)并将项目值编号分解后，项目值编号就被分解为上位和下位的2位。具体地，将对项目值编号进行取模计算(Modulo)(MOD(4))后得到的结果作为下位的值，将项目值编号除以4的商为上位的值。

图22是本发明的一个实施例的多阶段并行排序方法的流程图。该多阶段并行排序方法由步骤2201至步骤2205的5个步骤组成。

步骤2201：依据项目值编号的范围选择项目值编号的基数(本例中，基数为4，即：基数＝4)，将初始的记录编号数组OrdSet设置为当前记录编号数组，将项目值编号的最下位(本例中，即：对项目值编号进行取模计算(MOD(4))后的值)设置为当前位。

步骤2202：分割当前记录编号数组，并将其分配给4个处理器。

步骤2203：在4个处理器的各处理器上，累计与被分配的记录编号数组的一部分中所包含的记录相对应的项目值编号的当前位的值的出现次数。

步骤2204：分割项目值编号的当前位的值的范围，并将其分配给4个处理器。

步骤2205：在4个处理器的各处理器上，按项目值编号的当前位的值的顺序，在项目值编号的当前位的值一致的范围内，依据记录编号数组的一部分的顺序，将被分配的项目值编号的当前位的值的各出现次数变换成累计数。

步骤2206：在4个处理器的各处理器上，将与被分配的记录编号数组的一部分中所包含的记录相对应的项目值编号的当前位的值的出现次数的累计数作为指针来使用，将被分配的记录编号数组的一部分所包含的记录编号保存至另一记录编号。

步骤2207：判断排序处理是否被进行至用基数所表示的项目值编号的最上位，如果排序已经被进行至最上位，则结束多阶段并行排序处理。

步骤2208：如果还留有未处理的位，则将该位设置为当前位，并将另一记录编号数组设置为当前记录编号数组，然后返回步骤2202。

在上述本发明的实施例的多阶段并行排序方法中，步骤2202至步骤2206的排序处理与上述本发明的并行排序方法基本相同，唯一不同的一点在于项目值编号被项目值编号的当前位的值所取代。

以下，具体说明本发明的实施例的多阶段并行排序方法。本例中，使用4个CPU，将图4B所示数据按年龄的升序进行排序。初始化步骤2201中，作为第1阶段的排序处理，其为与对年龄的项目值编号进行取模计算(MOD(4))后得到的值(下位的值)相关的排序处理，作为第2阶段的排序处理，其为与年龄的项目值编号除以4的商(DIV 4)相关的排序处理。

初始化步骤2201中，生成一与图6所示的Count数组相同的数组。但是，本例中，该数组用于累计项目值编号的当前位的值的出现次数。

图23A、图23B至图25A、图25B是多阶段并行排序方法的第1阶段的累计步骤2203的说明图。图23A的子步骤1中，例如，CPU-0首先读出OrdSet[0]的值0，然后将读出的该值0作为下标，读出VNo[0]的值1，然后再对读出的该值1进行取模运算(MOD 4)，并将其结果1作为下标，将Count-0[1]的值0加1至1。同样，CPU-1首先读出OrdSet[5]的值5，然后以该值5为下标，读出VNo[5]的值2，然后再以该值2的MOD(4)的值2为下标，将Count-1[2]的值0加1至1。下面是执行图23B的子步骤2、图24A的子步骤3、图24B的子步骤4以及图25A的子步骤5后所得到的如图25B所示的累计结果。图23A、23B至图25A、25B的数组Count-0的元素Count-0[i]表示的是与CPU-0负责的数组OrdSet的OrdSet[0]至OrdSet[4]范围内的各记录相对应的年龄的项目值编号的下位的值i的出现次数。例如，Count-0[0]表示CPU-0负责的范围内的项目值编号的下位的值0的出现次数为1次，Count-3[1]表示CPU-3负责的范围内的项目值编号的下位的值1的出现次数为2次。

图26A、26B是多阶段并行排序方法的第1阶段的累计数步骤的说明图。本例中，对应于升序排序，按项目值编号的下位的值的升序进行累计数处理。CPU-0负责数组Count的第1行(即：项目值编号的下位的值0)的累计数处理，CPU-1至CPU-3各自负责数组Count的第2至4行(即：项目值编号的下位的值1至3)的累计数处理。如图26A所示，累计数处理在数组Count的横方向(即：下标一致的行)上优先进行，然后，通过将上一行的累计数加到下一行的累计数来求得全体的累计数。另外，需要注意的是，如上所述，该处理既可以由各CPU并行执行，也可以由一个CPU负责。

图27A、27B至图29A、29B是在多阶段并行排序方法的第1阶段中将记录编号保存至另一记录编号数组的传送步骤的说明图。在传送步骤中，各CPU首先从记录编号数组OrdSet中读出自己负责范围内的记录编号，然后，以该记录编号为下标，从指针数组VNo中读出项目值编号的下位的值，然后，再以该项目值编号的下位的值为下标，从与自处理器相关的累计数处理后的Count数组中读出累计数值，以读出的该累计数值作为指针，将记录编号保存至另一记录编号数组OrdSet’中，同时，将Count数组的累计数值各加1。图29B表示的是作为上述传送步骤的结果的、在第1阶段中所得到的记录编号数组OrdSet’。

在第2阶段中，把第1阶段中所得到的记录编号数组OrdSet’作为初始条件，对年龄的项目值编号的上位的值(除以4(DIV 4)的商)进行升序排序。

图30是本发明的一个实施例中的多阶段并行排序方法的第2阶段的步骤2202中的、将当前记录编号数组OrdSet’分配给4个CPU并生成各自的Count数组的状态的示意图。

图31A、31B至图33A、33B是多阶段并行排序方法的第2阶段的累计说明图。图31A的子步骤中，例如，CPU-0首先读出OrdSet’[0]的值2，然后，将读出的该值2作为下标，读出VNo[2]的值，然后再以该值除以4的商(DIV 4)的值1为下标，将Count-0[1]的值0加1至1。同样，CPU-1首先读出OrdSet’[5]的值12，然后以这个值12为下标，读出VNo[12]的值4，然后再以该值4除以4的商的值1为下标，将Count-1[1]的值0加1至1。下面是执行图31B的子步骤2、图33A的子步骤3、图32B的子步骤4以及图33A的子步骤5后得到的如图33B所示的第2阶段的累计结果。图31A、31B至图33A、33B中，数组Count-0的元素Count-0[i]表示的是与CPU-O负责的数组OrdSet’的OrdSet’[0]至OrdSet’[4]的范围内的各记录相对应的年龄的项目值编号的上位的值i的出现次数。例如，Count-0[0]表示的是CPU-0负责范围内的项目值编号的上位的值0的出现次数为4次，Count-3[1]表示的是CPU-3负责范围内的项目值编号的上位的值1的出现次数为0次。

图34是多阶段并行排序方法的第2阶段的累计数处理步骤的说明图。本例中，对应于升序排序，进行项目值编号的上位的值的升序的累计数处理。由于多阶段化，项目值编号的上位的值的个数减少了2个，所以，本例中，例如，CPU-0负责所有的值的累计数处理。如图34A所示，CPU-0按Count[0][0]、Count[1][0]、Count[2][0]、Count[3][0]、Count[0][1]、Count[1][1]、Count[2][1]以及Count[3][1]的顺序进行累计数处理。当然，本例中，也可以将项目值编号的上位的值0和1分配给CPU-0和CPU-1两个CPU，使用2个CPU来进行累计数计算。

图35A、35B至图37A、37B是将多阶段并行排序方法的第2阶段的记录编号保存至另一记录编号数组的传送步骤的说明图。传送步骤中，各CPU首先从记录编号数组OrdSet中读出自己负责范围内的记录编号，然后，然后，以该记录编号为下标，从指针数组VNo中读出项目值编号的上位的值，之后，以该项目编号的上位的值为下标，从与自处理器相关的累计数处理后的Count数组中读出累计数值，然后将读出的该累计数值做为指针，并将记录编号保存至另一记录编号数组OrdSet”中，同时，将Count数组的累计数值各加1。图37B表示的是作为上述传送步骤的结果的、在第2阶段中所得到的记录编号数组OrdSet”。

本实施例的多阶段并行排序方法是由项目值编号的上面的位和下面的位的2个阶段构成，所以不能进行该范围外的排序处理。但是，第2阶段得到的记录编号数组OrdSet”是将初始的记录编号数组OrdSet关于年龄按升序进行排序的结果。

图38A至38C以及图39A、39B是将本发明的实施例的升序的多阶段并行排序法应用于图4B所示的数据结构后得到的结果的示意图。本例中，因为是关于年龄进行升序排序的，所以，从结果可以看出，在作为结果的记录编号数组OrdSet”中，具有作为年龄的项目值的16岁、18岁、20岁、21岁以及23岁的记录是按年龄的顺序被排列的。另外，年龄相同的记录的顺序也是按照原来的记录编号数组OrdSet中的顺序被保存的。该结果与图14A至14C以及图15A、15B所示的、将上述本发明的实施例中的升序的并行排序方法应用于图4B所示的数据结构后得到的结果一致。

另外，上述的多阶段并行排序方法尽管是升序排序，但是，本发明的多阶段并行排序在降序排序中也进行相同的处理。另外，如上所述，多阶段并行处理的各阶段的累计数计算既可以使用多个处理器并行处理，也可以使用至少一个，更好地，仅使用一个处理器来单独进行处理。

[多阶段排序]

上述多阶段并行排序进行的是对从最下位开始按顺序至当前位的排序，最后，通过对最上位进行排序处理来完成最后的排序。对此，也可以进行从最上位开始按顺序至当前位的排序，最后，通过对最下位进行排序处理来完成最后的排序。下面对按照从最上位至最下位的顺序进行排序处理的多段化处理方法进行简单的说明。

本例中，使用图40所示的数据结构。另外，本例中，CPU的个数设为1个。另外，以下叙述中，关于年龄的项目，按年龄的升序进行排序。记录的总数为从记录编号0至记录编号19的20个，项目值编号为从0至8的9个。也就是说，实际的年龄的值为15、16、18、19、20、21、23、25和28的9个。图40的数据结构中，与年龄相关的项目值编号VNo为0至8的值，所以，用基数4(即：基数＝4)对项目值编号进行分解后，项目值除以4的商为上位的值，项目值编号的模运算(4)的值为下位的值。项目值编号的上位是0、1以及2的3个值，下位是0、1、2以及3的4个值。

初始时，在第1阶段，生成用于累计上位的值0、1以及2的出现次数的数组Count-1，并将其元素初始化为0。例如，Count-1[0]是用于累计项目值编号的上位的值为0的记录的个数的领域。

然后，按从记录编号数组OrdSet的领先的元素(即：记录)开始的顺序，从数组VNo中读出与该元素相对应的项目值编号，将该项目值编号除以4的商的值作为指针，将数组Count-1的元素的值加1。图41A至41D是对OrdSet[0]＝0、OrdSet[7]＝7以及OrdSet[19]＝19的3个记录进行项目值编号的上位的值进行计算并累计，然后再进行累计数处理的例子的说明图。从图41C可知，通过第1阶段的累计处理，项目值编号的上位的值为0的记录的数目为12个，上位的值为1的记录的数目为7个，上位的值为2个的记录的数目为1个。另外，如图41D所示，对该累计值进行累计数处理。

接下来，使用对项目值编号的上位的值的出现次数进行累计数处理了的数组Aggr-1，将记录编号数组OrdSet变换至另一记录编号数组OrdSet’。具体地，如果OrdSet[i]＝j，则读出VNo[j，然后将该VNo[j]除以4的商(VNo[j]DIV 4)设为k，读出Aggr-1[k]的值，然后，将记录编号j赋给OrdSet[Aggr-1[k]]，并将Aggr-1[k]加1。图42A、24B是该多阶段排序的记录编号传送处理的说明图。图42A表示的是传送OrdSet[0]，图42B表示的是传送OrdSet[19]。图43表示的是第1阶段的记录编号的传送结果的记录编号数组OrdSet’以及上位的值的分布范围。例如，上位的值为0的记录分布于记录编号数组OrdSet’的OrdSet’[0]至OrdSet’[11]的范围(区间0)内，上位的值为1的记录分布于记录编号数组OrdSet’的OrdSet’[12]至OrdSet’[18]的范围(区间1)内，上位的值为2的记录则存在于记录编号数组的OrdSet’的OrdSet’[19](区间2)内。

接下来，在多阶段排序的第2阶段，于各区间内，依据项目值编号的下位的值对记录编号进行排序。例如，OrdSet’的区间1被传送至与OrdSet”相对应的区间1。在第2阶段的排序中，因为已经用上面的位规定了区间，记录编号不可能传送至区间外。

图44是多阶段排序的第2阶段的初始状态的示意图。下面是关于OrdSet’的区间1的说明。例如，当多个处理器存在时，通过按区间分配处理器，也可以对下面的处理进行并行处理。Count-2用于累计项目值编号的下位的值(0、1、2、3)的出现次数。

图45A至45C是多阶段排序的第2阶段的累计以及累计数处理的说明图。从图45A开始按顺序地进行累计，就可以得到如图45B所示的累计数组。该数组如45C所示被进行累计数处理。

最后，将第2累计数数组Aggr-2作为指针使用，通过将记录编号数组OrdSet’的区间1传送至记录编号数组OrdSet”的区间1，完成多阶段排序。图46A、46B是多阶段排序的第2阶段的记录编号传送的说明图。具体地，如果OrdSet’[i]＝j，则读出Vno[j]，然后，将该VNo[j]除以4的余数(VNo[j]MOD 4)设为k，读出Aggr-2[k]的值，然后，将记录编号j赋给OrdSet”[Aggr-2[k]]，并将Aggr-2[k]加1。图46A表示OrdSet’[14]的传送，图46B表示OrdSet’[18]的传送。图46B的OrdSet”的区间1表示的是区间1的最终的排序结果。

与区间1同样，对于其他区间0和区间2，也可以通过进行第2阶段的累计、累计数处理以及记录编号的传送，将记录编号数组OrdSet的全体传送至记录编号数组OrdSet”，然后结束排序。

如上所述，在本发明的实施例中，使计算机系统10执行依据记录的预定的项目的项目值调换记录顺序的程序。更具体地，在本实施例中，如下所述，程序是使各CPU执行上述处理步骤、或者、实现上述功能。

在本实施例中，计算机系统中装载了OS(例如，Linux(登录商标))。初始时，一CPU(例如、CPU12-1)在OS的控制下，将程序装载至内存(例如、共享内存14)中。程序转载至内存后，CPU12-1、12-1、…、12-p的各CPU需要执行处理时，在OS的控制下，使各CPU执行预定的功能。也就是说，各CPU读出保存在共享内存14内的程序中的预定的处理步骤，并执行该处理步骤。另一方面，需要指定CPU处理时，在OS的控制下，使被指定的CPU实现其他预定的功能。也就是说，只让指定的CPU读出保存在共享内存14内的程序中的其他的预定的处理步骤，并执行所述其他的预定的处理步骤。另外，需要注意的是，各CPU执行的程序的保存场所并不局限于上述共享内存14，也可以使用各CPU自身固有的本地内存(图中未表示)。

综上所述，在本实施例中，程序在OS的控制下使各CPU实现预定的功能，同时，根据实际要求，也可以使指定的CPU实现其他预定的功能。

本发明并不局限于上述具体实施例，只要不脱离权利要求书的范围，亦可采用其他变化形式代替，但那些变化形式仍属于本发明所涉及的范围。

Claims (10)

1.一种在共享内存型多处理器系统中根据记录的预定项目的项目值排列记录的顺序的信息处理方法，该共享内存型多处理器系统包括：

共享内存，其用于保存记录编号数组、项目值编号数组以及项目值数组，该记录编号数组用于按照预定的记录顺序保存表格形式数据的记录的记录编号，该项目值编号数组用于与记录编号相关联地保存与表格形式数据的记录的预定项目的项目值相对应的项目值编号，该项目值数组用于按照与表格形式数据的项目值相对应的项目值编号的顺序保存该表格形式数据的项目值；以及

n个处理器，可以访问所述共享内存，其中n≥2，

所述信息处理方法包括：

将所述记录编号数组分割成n1个部分，将所述被分割的记录编号数组的n1个部分分别分配给所述n个处理器中的n1个处理器的步骤，其中，n1≤n；

使用所述n1个处理器中的各处理器，累计与所述被分配的记录编号数组的一部分中所包含的记录编号相关联的项目值编号的出现次数的步骤；

将所述项目值编号的范围分割成n2个范围，将所述被分割的项目值编号的n2个范围分别分配给所述n个处理器中的n2个处理器的步骤，其中，n2≤n；

使用所述n2个处理器中的各处理器，按照所述项目值编号的顺序，在所述项目值编号一致的范围内，根据所述记录编号数组的一部分的顺序，将由所述n1个处理器累计的所述项目值编号的各自的出现次数变换成累计数的步骤；以及

使用所述n1个处理器中的各处理器，将与所述被分配的记录编号数组的一部分中所包含的记录编号相关联的所述项目值编号的累计数作为指针使用，将所述被分配的所述记录编号数组的一部分中所包含的记录编号保存至另一记录编号数组中的步骤。

2.一种在共享内存型多处理器系统中根据记录的预定项目的项目值排列记录的顺序的信息处理方法，该共享内存型多处理器系统包括：

共享内存，其用于保存记录编号数组、项目值编号数组以及项目值数组，该记录编号数组用于按照预定的记录顺序保存表格形式数据的记录的记录编号，该项目值编号数组用于与记录编号相关联地保存与表格形式数据的记录的预定项目的项目值相对应的项目值编号，该项目值数组用于按照与表格形式数据的项目值相对应的项目值编号的顺序保存该表格形式数据的项目值；以及

n个处理器，可以访问所述共享内存，其中n≥2，

所述信息处理方法包括：

根据所述项目值编号的范围设定所述项目值编号的基数的步骤；以及

按照以所述基数表示的所述项目值编号的最下位至最上位的顺序，对于当前位，反复进行第一次将初始的记录编号数组做为当前记录编号数组，第二次以后将另一记录编号数组做为当前记录编号数组的排序处理的步骤，

所述排序处理包括：

将所述当前记录编号数组分割成n1个部分，将所述被分割的当前记录编号数组的n1个部分分别分配给所述n个处理器中的n1个处理器的步骤，其中n1≤n；

使用所述n1个处理器中的各处理器，累计与所述被分配的记录编号数组的一部分中所包含的记录编号相关联的项目值编号的当前位的值的出现次数的步骤；

将所述项目值编号的当前位的值的范围分割成n2个范围，将所述被分割的项目值编号的当前位的值的n2个范围分别分配给所述n个处理器中的n2个处理器的步骤，其中，n2≤n；

使用所述n2个处理器中的各处理器，按照所述项目值编号的当前位的值的顺序，在所述项目值编号的当前位的值一致的范围内，根据所述记录编号数组的一部分的顺序，将由所述n1个处理器累计的项目值编号的当前位的值的各自的出现次数变换成累计数的步骤；以及

使用所述n1个处理器中的各处理器，将与所述被分配的记录编号数组的一部分中所包含的记录编号相关联的所述项目值编号的当前位的值的累计数作为指针使用，将所述被分配的所述记录编号数组的一部分中所包含的记录编号保存至另一记录编号数组中的步骤。

3.一种在共享内存型多处理器系统中根据记录的预定项目的项目值排列记录的顺序的信息处理方法，该共享内存型多处理器系统包括：

共享内存，其用于保存记录编号数组、项目值编号数组以及项目值数组，该记录编号数组用于按照预定的记录顺序保存表格形式数据的记录的记录编号，该项目值编号数组用于与记录编号相关联地保存与表格形式数据的记录的预定项目的项目值相对应的项目值编号，该项目值数组用于按照与表格形式数据的项目值相对应的项目值编号的顺序保存该表格形式数据的项目值；以及

两个以上的处理器，可以访问所述共享内存，

所述信息处理方法包括：

根据所述项目值编号的范围设定所述项目值编号的基数的步骤；以及

按照以所述基数表示的所述项目值编号的最下位至最上位的顺序，对于当前位，反复进行第一次将初始的记录编号数组做为当前记录编号数组，第二次以后将另一记录编号数组做为当前记录编号数组的排序处理的步骤，

所述排序处理包括：

分割所述当前记录编号数组，将被分割的当前记录编号数组的部分分配给所述两个以上的处理器的步骤；

使用各处理器累计与所述被分配的记录编号数组的一部分中所包含的记录编号相关联的项目值编号的当前位的值的出现次数的步骤；

使用至少一个处理器，按照所述项目值编号的当前位的值的顺序，在所述项目值编号的当前位的值一致的范围内，根据所述记录编号数组的一部分的顺序，将所述被分配的项目值编号的当前位的值的各自的出现次数变换成累计数的步骤；以及

使用所述各处理器，将与所述被分配的记录编号数组的一部分中所包含的记录编号相关联的所述项目值编号的当前位的值的累计数做为指针使用，将所述被分配的所述记录编号数组的一部分中所包含的记录编号保存至另一记录编号数组中的步骤。

4.一种在共享内存型多处理器系统中根据记录的预定项目的项目值排列记录的顺序的信息处理方法，该共享内存型多处理器系统包括：

共享内存，其用于保存记录编号数组、项目值编号数组以及项目值数组，该记录编号数组用于按照预定的记录顺序保存表格形式数据的记录的记录编号，该项目值编号数组用于与记录编号相关联地保存与表格形式数据的记录的预定项目的项目值相对应的项目值编号，该项目值数组用于按照与表格形式数据的项目值相对应的项目值编号的顺序保存该表格形式数据的项目值；以及

n个处理器，可以访问所述共享内存，其中n≥2，

所述信息处理方法包括：

将所述记录编号数组分割成n1个部分，将所述被分割的记录编号数组的n1个部分分别分配给所述n个处理器中的n1个处理器的步骤，其中，n1≤n；

使用所述n1个处理器中的各处理器，累计与所述被分配的记录编号数组的一部分中所包含的记录编号相关联的项目值编号的出现次数的步骤；

将所述项目值编号的范围分割成n2个范围，将所述被分割的项目值编号的n2个范围分别分配给所述n个处理器中的n2个处理器的步骤，其中，n2≤n；

使用所述n2个处理器中的各处理器，对于被分配至所述n2个处理器上的项目值编号，(i)累计由所述n1个处理器中的各处理器所累计的所述出现次数的和，将累计出的和按照所述项目值编号的范围的顺序在所述n2个处理器之间移动，(ii)按照所述项目值编号的顺序，在所述项目值编号一致的范围内，根据所述记录编号数组的一部分的顺序，将所述出现次数变换至累计数，通过将所述被移动的和加到所述累计数上，按照与被分配至所述n1个处理器中的各处理器上的记录编号数组的一部分中所包含的记录编号相关联的各项目值编号，将所述出现次数变换成累计数的步骤；以及

使用所述n1个处理器中的各处理器，将按照与所述被分配的记录编号数组的一部分中所包含的记录编号相关联的所述各项目值编号得到的所述累计数作为指针使用，将所述被分配的所述记录编号数组的一部分中所包含的记录编号保存至另一记录编号数组中的步骤。

5.一种在共享内存型多处理器系统中根据记录的预定项目的项目值排列记录的顺序的信息处理方法，该共享内存型多处理器系统包括：

共享内存，其用于保存记录编号数组、项目值编号数组以及项目值数组，该记录编号数组用于按照预定的记录顺序保存表格形式数据的记录的记录编号，该项目值编号数组用于与记录编号相关联地保存与表格形式数据的记录的预定项目的项目值相对应的项目值编号，该项目值数组用于按照与表格形式数据的项目值相对应的项目值编号的顺序保存该表格形式数据的项目值；以及

n个处理器，可以访问所述共享内存，其中n≥2，

所述信息处理方法包括：

至少使用一个处理器，通过根据所述项目值编号的范围设定所述项目值编号的基数，将所述项目值编号分为上面的位和下面的位的步骤；

至少使用一个处理器，累计与所述记录编号数组中所包含的记录编号相关联的所述项目值编号的上面的位的值的出现次数，按照所述项目值编号的上面的位的值的顺序将所述出现次数换算成累计数，将所述项目值编号的上面的位的值的累计数做为指针使用，排列所述记录编号数组中的记录编号，生成按照所述项目值编号的上面的位的值的顺序被划分成n1个区间的中间记录编号数组的步骤，其中，n1≤n；

至少使用一个处理器，将所述中间记录编号数组的n1个区间分别分配给所述n个处理器中的n1个处理器的步骤；以及

使用按照所述各区间分配的各处理器，累计与所述中间记录编号数组中的所述被分割的区间内的记录编号相关联的所述项目值编号的下面的位的值的出现次数，按照所述项目值编号的下面的位的值的顺序将所述出现次数变换成累计数，将所述项目值编号的下面位的值的累计数做为指针使用，将所述中间记录编号数组中的所述被分割的区间内的记录编号按照与其相关联的所述项目值编号的下面位的值的顺序排列的步骤。

6.一种共享内存型多处理器系统，包含：

共享内存；以及

可以访问所述共享内存的n个处理器，其中n≥2，

所述共享内存用于保存记录编号数组、项目值编号数组以及项目值数组，该记录编号数组用于按照预定的记录顺序保存表格形式数据的记录的记录编号，该项目值编号数组用于与记录编号相关联地保存与表格形式数据的记录的预定项目的项目值相对应的项目值编号，该项目值数组用于按照与表格形式数据的项目值相对应的项目值编号的顺序保存该表格形式数据的项目值，

各处理器包含：

用于确定被分割成n1个部分的所述记录编号数组内的、由本处理器负责处理的一部分的单元，其中，n1≤n；

用于累计与所述记录编号数组的一部分中所包含的记录编号相关联的项目值编号的出现次数的单元；

用于确定被分割成n2个范围的所述项目值编号的范围内的、由本处理器负责处理的范围的单元，其中，n2≤n；

按照所述项目值编号的顺序，在所述项目值编号一致的范围内，根据所述记录编号数组的一部分的顺序，将由本处理器负责处理的范围内的项目值编号的各自的出现次数变换成累计数的单元；以及

用于将与所述记录编号数组的一部分中所包含的记录编号相关联的所述项目值编号的累计数做为指针使用，将所述记录编号数组的一部分中所包含的记录编号保存至另一记录编号数组的单元。

7.根据权利要求6所述的共享内存型多处理器系统，其中，由用于负责处理所述项目值编号范围内的领先范围的处理器的将所述出现次数变换成累计数的单元所得到的所述累计数，被用于负责处理后续范围的处理器的将所述出现次数变换成累计数的单元所参照。

8.一种共享内存型多处理器系统，包含：

共享内存；以及

可以访问所述共享内存的两个以上的处理器，

所述共享内存用于保存记录编号数组、项目值编号数组以及项目值数组，该记录编号数组用于按照预定的记录顺序保存表格形式数据的记录的记录编号，该项目值编号数组用于与记录编号相关联地保存与表格形式数据的记录的预定项目的项目值相对应的项目值编号，该项目值数组用于按照与表格形式数据的项目值相对应的项目值编号的顺序保存该表格形式数据的项目值，

各处理器包含：

用于根据所述项目值编号的范围设定所述项目值编号的基数的单元；以及

用于按照以所述基数表示的所述项目值编号的最下位至最上位的顺序设定当前位，反复进行第一次将初始的记录编号数组做为当前记录编号数组，第二次以后将另一记录编号数组做为当前记录编号数组的排序处理的单元，

用于反复进行所述排序处理的单元包含：

用于确定所述记录编号数组内的、由本处理器负责处理的一部分的单元；

用于累计与所述记录编号数组的一部分中所包含的记录编号相关联的项目值编号的当前位的值的出现次数的单元；

用于确定所述项目值编号的当前位的值的范围内的、由本处理器负责处理的范围的单元；

按照所述项目值编号的当前位的值的顺序，在所述项目值编号的当前位的值一致的范围内，根据所述记录编号数组的一部分的顺序，将由本处理器负责处理的范围内的项目值编号的当前位的值的各自的出现次数变换成累计数的单元；以及

用于将与所述记录编号数组的一部分中所包含的记录编号相关联的所述项目值编号的当前位的值的累计数做为指针使用，将所述记录编号数组的一部分中所包含的记录编号保存至另一记录编号数组的单元。

9.根据权利要求8所述的共享内存型多处理器系统，其中，

由用于负责处理所述项目值编号的当前位的范围内的领先范围的处理器的将所述出现次数变换成累计数的单元所得到的所述累计数，被用于负责处理后续范围的处理器的将所述出现次数变换成累计数的单元所参照。

10.一种共享内存型多处理器系统，包含：

共享内存；以及

可以访问所述共享内存的两个以上的处理器，

所述共享内存用于保存记录编号数组、项目值编号数组以及项目值数组，该记录编号数组用于按照预定的记录顺序保存表格形式数据的记录的记录编号，该项目值编号数组用于与记录编号相关联地保存与表格形式数据的记录的预定项目的项目值相对应的项目值编号，该项目值数组用于按照与表格形式数据的项目值相对应的项目值编号的顺序保存该表格形式数据的项目值，

各处理器包含：

用于根据所述项目值编号的范围设定所述项目值编号的基数的单元；以及

用于按照以所述基数表示的所述项目值编号的最下位至最上位的顺序设定当前位，反复进行第一次将初始的记录编号数组做为当前记录编号数组，第二次以后将另一记录编号数组做为当前记录编号数组的排序处理的单元，

用于反复进行所述排序处理的单元包含：

用于确定所述记录编号数组内的、由本处理器负责处理的一部分的单元；以及

用于累计与所述记录编号数组的一部分中所包含的记录编号相关联的项目值编号的当前位的值的出现次数的单元，

至少一个处理器的用于反复进行所述排序处理的单元包含：

按照所述项目值编号的当前位的值的顺序，在所述项目值编号的当前位的值一致的范围内，根据所述记录编号数组的一部分的顺序，将所述项目值编号的当前位的值的各自的出现次数变换成累计数的单元，

用于反复进行所述排序处理的单元还包含：

用于将与所述记录编号数组的一部分中所包含的记录编号相关联的所述项目值编号的当前位的值的累计数做为指针使用，将所述记录编号数组的一部分中所包含的记录编号保存至另一记录编号数组中的单元。

Images