JPH0797310B2 - Sort processing device - Google Patents

Description

The present invention relates to a sort processing device for character strings and numerical data, and more particularly to an improvement of a sort processing device having a one-dimensional array structure of a comparison transfer unit. .

[Conventional technology]

The sort process is a process of rearranging a given set of data according to a predetermined rule. The sort process in an electronic computer means that the data given as a numerical value or a character string is represented by a binary code of "0" or "1" inside the computer, so the numerical meaning of the binary code has Based on the ascending order (smallest to largest)
It is to rearrange the data in descending order (from largest to smallest).

In general, the data to be sorted is called a record, and the record can be divided into a key part that compares data with each other to determine a magnitude relation and a part that does not compare.
When this record is limited to a character string or a positive integer (unsigned integer), by comparing the key part of the record represented by the binary code with the superiority in the higher digits,
It is possible to determine the size relationship between the records to be sorted.

Conventionally, the present applicant has proposed, as a dedicated sort processing device for performing such sort processing at high speed, a configuration in which determination of a magnitude relation by comparison of data with each other and data transfer are performed in parallel (Japanese Patent Application Laid-Open No. 2000-242242). (See Sho 60-81640). FIG. 4 is a block diagram of such a sort processing device. The device includes a first memory 10 for holding data to be compared.
1st and 2nd memory 102, comparator 103, flag register for holding the judgment result obtained by the comparator 103
A plurality of comparison transfer units 100 each composed of 104 and a transfer circuit 105 are one-dimensionally connected. In each unit device 100, the first and second memories 100 and 102 and the comparator 1
03, the transfer circuit 105 is configured with an i-bit width, and the first and second
Of the memory capacity of i × j bits, i × k
Records having a length of (k ≦ j) bits can be sorted into N records (N ≦ 2 × number of units). The time required for this sort processing is equal to the record input / output time (2 × kN steps) according to the operation principle described below.

FIG. 5 is an operation principle diagram of the sort processing apparatus of FIG. 4, and as an example, out of the one-digit numerical data from 0 to 9, 6 of 3,6,5,2,4,1 The operation when sorting records in descending order is shown. That is, in this example, one record is i bits, 1 record = i bits, k = 1, N = 6
Is.

When performing the sorting process, the contents of the first memory 101 and the second memory 102 of all units 100 are initialized. In the case of descending sort, 0 which is the minimum value of data is set as an initial value. The sorting process consists of an input operation for inputting sequential records and an output operation for outputting sequential records. In each unit 100, the transfer of data (i-bit) to the right and the comparison between two data are performed in synchronization with one input operation. In this case, the transferred data is the smaller one of the two data held in the first and second memories 101 and 102. At this time, one record is input to the sort processing device in synchronization with the data transfer, and the first memory 101 or the second memory of the leftmost unit is input.
It is held in one of the memories 102, which becomes empty by the transfer (T1 to T7).

When the input of the six records to be sorted is completed, the output operation sequentially transfers the data to the adjacent left unit. At this time, the data to be transferred is the larger of the two data in the unit, and the sorted record string is output from the leftmost unit in descending order. Enter 0, which is the same as the initial value, in the rightmost unit (T7 to T1
2).

When sorting in descending order using this sort processing device,
As an initial setting, the maximum value 9 of the data is set in the first and first memories 101 and the second memory 102 of all units 100, and when the input operation is performed, the comparison is performed in each unit.
Of the two pieces of data, the larger one is transferred to the right, and during the output operation, the smaller one of the two pieces of data compared in each unit is transferred to the left.

Next, in the sorting apparatus of FIG. 4, when the length of one record exceeds i bits that can be compared and transferred at one time (1
FIG. 6 shows an operation example of <k ≦ j). In FIG. 6, assuming that one character of the alphabet is represented by i bits, four records (N = 2) each having a length of two characters (k = 2) are shown.
4) Shows a case where ab, de, ca, bd are sorted in descending order using two units (unit 0, unit 1).
In FIG. 6, m1 and m2 are two memories 101 and 102 of each unit, and f is a flag register 104. Each record is divided into k pieces of data in 1-bit units, and the magnitude comparison is performed. When the comparison up to that time is equal and the magnitude relation is determined for the first time, the value is set in the flag register as the comparison result. In FIG. 6, the value of the memory m1 is compared with the value of the memory m2, and when the value of the memory m2 is small, the comparison result is 1
Is set in the flag register f.

FIG. 6A shows the operation at the time of input operation. In the unit 0, if the flag register f = 0, the contents of the memory m1 are
If f = 1, the contents of the memory m2 are output to the unit 1 adjacent to the right. On the other hand, FIG. 6B shows the operation at the time of the output operation. In the unit 1, if the flag register f = 1, the contents of the memory m1 are adjacent to each other in the left direction, and if f = 0, the contents of the memory m2 are adjacent to each other in the left direction. To the unit 0, and similarly, the unit 0 outputs to the outside. The operation when the length of one record exceeds i bits is described in detail in Japanese Patent Laid-Open No. 60-81640.

As shown in FIG. 6, in the sort processing device having two comparison transfer units each having a memory capacity of i × j, j =
In the case of 2, 1 character is i-bit to have a length of 2 characters (k =
2) 4 records (N = 4), 16 steps (= 2
× k × N) can be sorted. In the above procedure,
The comparison operation by the comparator can be performed in synchronization with the transfer of records, and the operation of moving the comparison result to the flag register can be processed in a time sufficiently shorter than the transfer of records and the comparison operation. Then it can be ignored. In FIG. 6, the part in parentheses means this.

[Problems to be Solved by the Invention]

According to the above-described sort processing device of the prior art, sort processing can be performed with the same number of input / output operations and output operations as the number of records. When the length of one record exceeds i bits that can be compared and transferred at one time, each record is divided into k pieces of data in i bit units, and one record is processed by k input / output operations. It can be performed. Therefore, records having a length up to i × k (k ≦ j) bits can be sorted in a time proportional to the number of records.

On the other hand, since the sortable record length is determined by the memory capacity in the comparison transfer unit, in order to lengthen the records to be sorted, a large memory capacity in the comparison transfer unit must be set in advance. I won't. If the memory capacity in the comparison transfer unit is increased, it is difficult to effectively use the memory of the comparison transfer unit regardless of the record length, because the memory usage efficiency at the time of sort processing with a short record length decreases. there were.

An object of the present invention is to realize a sort processing device that can sort records having a long record length at high speed without being limited by the memory capacity in the comparison transfer unit.

[Means and Actions for Solving the Problems]

According to the present invention, in a sorting apparatus having a one-dimensional array structure of comparison transfer units, the records are divided into a plurality of comparison transfer units and stored according to the length of a record to be sorted, and the records are stored. It is characterized in that each comparison and transfer unit that is divided and stored is regarded as one comparison and transfer unit, and the comparison and transfer processing is performed in conjunction with each other.

In the sorting apparatus according to the present invention, since a plurality of comparison transfer units are operated in conjunction with each other, even if the record is too long to be handled by the comparison transfer unit alone, the record is stored in the plurality of comparison transfer units. Sorting can be done by dividing and storing. Further, the width of the data to be compared / transferred at a time can be expanded by linking a plurality of comparison / transfer units in the direction in which the width of the comparator expands, thereby improving the throughput of the sort processing device and sorting. The processing width of data input / output at one time can be adapted according to the usage environment of the processing device.

〔Example〕

 An embodiment of the present invention will be described below with reference to the drawings.

FIG. 1 is a configuration diagram of an embodiment of a sort processing device according to the present invention, (1) is a configuration diagram of the entire sort processing device, and (2) is a configuration diagram of one unit group. In the figure, 11 has the same structure as one comparison transfer unit 100 shown in FIG. 4, and in this embodiment, four comparison transfer units constitute one unit group. The four units in each unit group have identifiers U0 to U3. Further, the entire sort processing apparatus 10 is composed of four unit groups having the identification names G0 to G3. Therefore, the sorting apparatus of this embodiment is G0-U
It consists of 16 comparison and transfer units 11 from 0 to G3-U3. Reference numeral 12 in the unit group is a transfer switching circuit for switching a transfer path of a bus for bidirectional data transfer. Input / output of records to be sorted is done by data input / output terminal PA.
PA and PB are composed of L and H each having an i-bit width equal to the data processing width of one comparison transfer unit 11.

As shown in FIG. 4, the comparison and transfer unit 11 includes the first,
The second memories 101 and 102, the comparator 103, and the input / output circuit 105 are configured with an i-bit width, and the capacities of the first and second memories 101 and 102 are i × j bits. At this time, each record to be sorted is divided into k data of i-bit width,
By repeating the comparison and transfer processes k times (k ≦ j) per record, one record has a maximum length of i × j bits by the fixed one-dimensional array of the comparison transfer unit shown in FIG. You can sort the multiple records you have by the input / output time of the records (Fig. 6). In the present invention, by connecting and / or combining a plurality of the comparison transfer units 11, the upper limit of the record length that can be sorted is expanded and / or the sorting processing speed, that is, the number of steps required for sorting is reduced. Is realized.

In the embodiment shown in FIG. 1, the comparison transfer unit 11 having the above-mentioned function can be interlocked with a maximum of two units in the direction of expanding the width of the comparator, and can be interlocked with a maximum of four units in the direction of expanding the depth of the memory. Is shown. Hereinafter, interlocking a plurality of units in the direction of expanding the width of the comparator of the comparison transfer unit is referred to as coupling, and interlocking a plurality of units in the direction of expanding the memory capacity of the comparison transfer unit is referred to as coupling.

FIG. 2 shows a data transfer path in the present sorting apparatus shown in FIG.

FIG. 2A shows a data transfer path when the comparison transfer units are connected. At this time, the data path to be formed is the following one type in which 16 comparison transfer units 11 are cascade-connected on the one-dimensional array as shown by the bold solid line in the figure.

PA: L → G0: U0 → G0: U1 ... G3: U3 → PB: L In the case of concatenation, one comparison / transfer process is performed in i-bit units as in the conventional case. However, a long record that cannot be handled by a single comparison transfer unit is obtained by operating each of the plurality of comparison transfer units to be concatenated (maximum 4 units in the embodiment) as if they were linked together. Even in this case, the data can be divided and stored in each unit of a plurality of cascade connections that operate in conjunction (that is, the memory capacity of the comparison transfer unit is expanded), and the record length to be sorted can be expanded.

FIG. 2 (2) shows a data transfer path when two comparison transfer units are combined. In this case, the data transfer paths are the following two types on the robust side shown by the thick solid line and the high byte side shown by the thick broken line in the figure. On the low bite side,
Each data processing width on the high byte side is i bits.

PA: L → G0: U0 → G0: U3 …… G3: U3 → PB: L Low byte side PA: H → G0: U1 → G0: U2 …… G3: U2 → PB: L High byte side Example 2 In the case of combination, two comparison transfer units on the low byte side and two comparison transfer units on the high byte side operate in parallel (that is, the width of the comparator of the comparison transfer unit is expanded), so that one comparison / transfer process is performed twice. × It is a unit of i bits, and the sort processing speed can be reduced by half.

FIG. 3 is a diagram showing an operation mode realized when the 16 comparison transfer units 11 shown in FIG. 1 are combined and connected. () In the figure shows the unit connection state,
[] Indicates the unit connection state. Also( )
Also, HL in [] indicates the high byte side and the low byte side when the record is divided and input into the comparison transfer unit. Concatenation and combination of units changes the connection of the comparison transfer unit, that is, the connection between units is made a variable structure through the transfer switching circuit, and according to the length of records to be sorted and the required sort processing performance. This can be easily realized by changing the connection relationship and forming the data transfer path. Mode 1 corresponds to the prior art of FIG. 4, and since the records are simply stored in each comparison transfer unit, 16 records having a maximum length of i × j bits (j = k) can be sorted. . Mode 2 is a case where two comparison transfer units are connected as one set, and the maximum record length that can be sorted is extended to twice that of mode 1. In the following, up to mode 5, the number of comparison transfer units that are sequentially connected is expanded by a factor of 2. In mode 5, the maximum record length that can be sorted can be increased by 16 times compared to mode 1.

Modes 6 to 9 are examples in which two comparison and transfer units are combined and then the units are connected. Mode 6 is a case where two units are simply combined as one set, and the width of the data transfer process is doubled,
The throughput of sort processing can be doubled. At this time, the maximum record length that can be sorted is twice that in the case of mode 1 because one record is divided into two and input into two units in parallel. Mode 7 to Mode 9 are 2
This is a case in which units are further connected based on mode 6 in which individual units are combined, and the maximum record length doubles based on mode 6 with the same sort processing throughput as mode 6 (twice that of mode 1). Can be extended.

In the embodiment described above, in the sort processing apparatus including 16 comparison transfer units, maximum 2 units are combined in the direction of expanding the data transfer width and maximum 16 units in the direction of expanding the amount of memory for storing data. Although the case where the units are connected has been shown, even when the total number of units is other than 16, by changing the connection structure between the units as in the present embodiment, the data transfer processing width and the sorting are performed. You can extend the maximum record length that you can. Furthermore, by setting the number of units to be connected / connected to a value other than that in this embodiment, the data transfer processing width and the maximum sortable record length can be expanded to desired values. On the other hand, in the present embodiment, the data processing width of the comparison transfer unit, which is the basis of merging / concatenating, is shown as i bits = 1 byte, but if the value is other than this, the unit combining is performed in the same manner as in the present embodiment. -Can be connected.

Next, as an example, a specific operation example in the case of mode 2 (two coupling) and mode 6 (two coupling) of FIG. 3 will be shown. However, for simplification of description, it is assumed that two comparison transfer units (unit 0, unit 1) constitute one unit group, and two unit groups are constituted (unit group G0, unit group G1). To do.

FIG. 7 is an operation example in the case of expanding the record length in which the comparison transfer units are connected, (A) is an operation during an input operation, and (b) is an operation during an output operation. In the example of FIG. 6 described above, a case where k = 2, that is, a record consisting of two alphabetic characters is sorted is shown. In FIG. 7, two comparison transfer units are connected to each other, and two sets of unit groups are connected. Due to
The case where four (N = 4) records (abcd, defg, acdf, abef) consisting of four alphabetic characters (k = 4) are sorted is shown. Note that one character has i bits, and the capacity of each memory of each comparison transfer unit is i × 2 (j = 2). The setting of the comparison result in the flag register is the same as in the example of FIG. 6, but two units (unit 0 and unit 1) forming the unit group are operated in conjunction. That is, the memory m1 of the unit 0 is connected to the memory m1 of the unit 1, and similarly, the memory m2 of the unit 0 is connected to the memory m2 of the unit 0.
A flag register F is prepared for a group of interlocked units (in FIG. 7, the flag register of the unit 1 is used) in order to operate the connection of m2, and the transfer of records is controlled by the value of F. During input operation, F = 0
If so, the contents of the memory m1 side, if F = 1, the memory m2
The contents on the side are output to the adjacent comparison transfer unit in the right direction. On the other hand, at the time of output operation, if F = 1, the memory
If the content on the m1 side is F = 0, the content on the memory m2 side is output to the comparison transfer unit adjacent in the left direction.

As shown in FIG. 7, by connecting a plurality of comparison transfer units in the direction of increasing the memory capacity, it is possible to sort records of a length that cannot be sorted by a single comparison transfer unit. The number of steps required for sorting at this time is the same as the sorting in a single unit in Fig. 6 (i bits) because the data width that can be transferred at a time is the same. In the example of FIG. 7, 32 steps (= 2 × k × N) are required.

FIG. 8 shows an example of a descending sort using the same four records as FIG. 7, showing the operation when a plurality of comparison transfer units are combined and the sort processing speed, that is, the number of steps required for sorting is reduced. It is shown. The difference from the concatenation of the comparison transfer units in FIG. 7 is that the concatenation connects the comparison transfer units in the direction of increasing the memory capacity, whereas the connection increases the width of data that can be compared and transferred at one time. That is, the width of data transfer, which is i bits in a single unit, is expanded to (2 × i) bits by combining with two units as shown in FIG. Therefore, it is possible to input a record consisting of four characters, two characters by two transfer operations. In Figure 8, (A)
Is an input operation operation, and (B) is an output operation operation.

In the case of the example of combining two units shown in FIG. 8, two units behave logically as one unit in parallel operation, and the sorting process that requires 32 steps in the unit connection of FIG. It can be seen that it can be realized in 16 steps with half the time.

As described above, as a specific example, the width of one data transfer is i bits,
By using two comparison transfer units each having a capacity of i × 2 (j = 2) bits of the memories m1 and m2 and performing a concatenation operation, records of i × 4 bit length can be sorted, and further, by combining them, , Showed that the sort processing time can be reduced by half. The interlocking of units by these connection and coupling is basically to form a logical unit by using a plurality of units, and the direction of unit connection when forming a logical unit is to increase the memory, or The difference is whether the data transfer path is to be expanded. Therefore, by making the connection between the comparison transfer units variable by the transfer switching circuit,
It is possible to form a logical unit including a plurality of comparison transfer units according to the record length and the sort processing speed. In particular, in a dedicated hardware sort processing device, it is important that the provided hardware effectively functions and achieves sufficiently high performance regardless of whether the record length is short or long. With concatenation, short records can be sorted by a single unit, and long records can be sorted by concatenating multiple units, which not only eases the hardware limitation on the record length but also enables hardware. It also works extremely effectively in terms of utilization. That is, it is possible to realize a sort processing device capable of sorting a large number of short records and a small number of longer records at a time.

〔The invention's effect〕

As described above, in the sort processing device of the present invention, the connection structure of the comparison transfer unit arranged on the one-dimensional array can be changed based on the sort processing conditions such as the data transfer width and the maximum record length during the sort processing. With the configuration, it is possible to easily realize the sort processing device according to the usage environment, particularly the data transfer processing width and the required sort processing performance. Further, when the sort processing device according to the present invention is implemented as an LSI, the external transfer condition can be absorbed by the connection configuration of the comparison transfer unit, so that the comparison transfer unit serving as a repeating unit can be designed without depending on the external use condition. , And the advantage that the range of application of the sort processing device made into an LSI is expanded.

[Brief description of drawings]

FIG. 1 is a block diagram of a sort processing apparatus according to an embodiment of the present invention,
FIG. 2 is a diagram showing the configuration of the data transfer path of the embodiment of FIG. 1, FIG. 3 is a diagram showing the operation mode of the embodiment of FIG. 1, and FIG. 4 is a configuration diagram of a conventional sort processor. FIG. 5 is a diagram showing an operation principle of the sort processing apparatus shown in FIG. 4, FIG. 6 is a diagram showing a concrete operation example of the conventional art, and FIG. 7 is a concrete operation example of connection of the present invention. FIG. 8 is a diagram showing a concrete operation example of the combination of the present invention. 10 …… Sort processor, 11 …… Comparison transfer unit, 12…
… Bus switching circuit, 13 …… Unit group.

Claims (3)

[Claims] 1. A first and a second memory for storing two pieces of data, a comparator for judging a magnitude relation between the data held in the first and the second memory, and the two pieces of data. In a sort processing device having a plurality of one-dimensional arrays, each of which has at least a transfer circuit for transferring one of the plurality of comparison transfer units. A means for grouping into arbitrary groups having one set is provided, and the sort target record is divided and given to each comparison transfer unit constituting the one set, and each comparison transfer unit is operated in conjunction. Characterizing sort processing device. 2. A sort processing apparatus according to claim 1, wherein each comparison transfer unit constituting one set is connected in parallel, and each comparison transfer unit is operated in parallel. Sort processing device. 3. The sort processing device according to claim 1, wherein each comparison transfer unit constituting one set is connected in cascade, and the entire first and second memories of each comparison transfer unit are respectively connected to each other. As the first and second memories,
A sorting apparatus characterized in that each of the comparison and transfer units is operated in conjunction with each other.