WO2009082852A1 - Data sorting device for processing communication data - Google Patents

Abstract

A data sorting device is disclosed, including: input process state machine, for processing the n inputted data; m cascade data comparison units, each of which includes comparator for comparing the inputted data with the current largest data or the current smallest data to get a result, selector for outputting the larger one of the inputted communication data and the current largest data, or the smaller one of the inputted communication data and the current smallest data to the first register and the smaller or the larger one to the second register according to the comparison result, the first register for storing the larger one as the new current largest data or the smaller one as the new current smallest data, and outputting them to the comparator, and the second register for storing the smaller one or the larger one to be outputted to the next data compassion unit; output process state machine, for outputting the current largest data or the current smallest data in the m cascade data comparison units in order. The sorting speed is improved.

Description

 BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to the field of communications, and in particular to a data sorting apparatus for processing communication data. BACKGROUND OF THE INVENTION Sorting operations are common operations in various algorithms. The sorting operation is usually programmed in software and then implemented on a general purpose computing device. However, in the process of implementing the present invention, the inventors have found that at least the following problems exist in the prior art: The software implementation is serial processing, and even if the CPU operates at a higher frequency, the sorting operation still takes a lot of time. Assuming that the input data is n, to find the m maximum values sorted by size from the input data, the method is (1) taking the first input data as the current maximum value; (2) taking the next input data. Compared with the current maximum value, if the next input data is greater than the current maximum value, the next input data becomes the current maximum value; (3) repeat step 2 until all input data is processed; (4) the current maximum value is The input data is removed; (5) Steps 1 to 4 are repeated until m maximum values are found. The m maximum values have been sorted in descending order of order, and the maximum value found for the first time is m values. The biggest one. When m=n, the above sorting operation is to sort all input data. Assuming that the execution cycle of the compare instruction and the branch instruction is one clock cycle and the instruction cycle occupied by the current maximum value is not considered, the number of CPU clock cycles occupied by the above sort operation is 2*(nl)*(n- 2)*...*(nm)=2*(nl)!/(nml)!. As can be seen from the above, the number of clock cycles occupied by the software implementation of the sort operation is proportional to the factorial of n. When the value of n is large, the time taken by the sorting operation is particularly significant. Real-time signal processing requires high real-time performance. The sorting operation using the above techniques cannot meet the real-time requirements of real-time signal processing for data processing. SUMMARY OF THE INVENTION The present invention is directed to a data sorting apparatus for processing communication data, which can solve the existing

1 P17456 The problem of slower sorting of technology. In an embodiment of the present invention, there is provided a data sorting apparatus for processing communication data, comprising: an input processing state machine for processing input n communication data; m cascaded data comparison units, m< =n, which includes: a comparator, configured to compare the input communication data with the current maximum value or the current minimum value to obtain a comparison result; and a selector for outputting the input communication data and the current maximum value according to the comparison result The larger one or the smaller of the input communication data and the current minimum value to the first register, the smaller or the larger one to the second register; the first register, which is used to hold the larger one as a new one The current maximum or smaller is used as the new current minimum value, and the output is compared to the comparator for comparison; the second register is used to save the smaller or larger one, and is output to the next-level data comparison unit; the output processing state machine And sequentially outputting the current maximum value or the current minimum value in the m cascaded data comparison units to obtain m sorted communication data in the n communication data. Preferably, the communication data is from a queue, and the input processing state machine includes: a first reader for sequentially reading communication data from the queue; and a counter for counting each time a communication data is retrieved from the queue, When n is counted, a full signal is issued; a first monitor for monitoring the full signal, the first read unit is disabled; and a first outputter for sequentially outputting the communication data to the first level data comparison unit. Preferably, the queue is a first in first out queue. Preferably, the selector comprises: two two-select multiplexers, comprising: a first two-select multiplexer, comprising: two inputs, wherein the first input is used for inputting communication data, and the second The input terminal is used to input the current maximum value or the current minimum value provided by the first register; 1 enable end for inputting the comparison result; and 1 output terminal for the communication end receiving the communication data whose comparison result is input When the current value is greater than the current maximum value or less than the current minimum value, the communication data input from the first input terminal is enabled to the first register; the second two-select multiplexer includes: 2 input terminals, wherein the second input end For inputting communication data, the first input is used to input the current maximum value or the current minimum value provided by the first register; 1 enable end for inputting the comparison result; and 1 output terminal for the enable end receiving When the comparison result is that the input communication data is greater than the current maximum value or less than the current minimum value, enabling the output of the current maximum value or the current minimum value input by the first input terminal to the second register; Of the communication data can be output to the second input terminal of the second register. Preferably, the output processing state machine comprises: a second reader for sequentially reading m cascaded data comparison units; and a counter for counting each data from the m cascaded data comparison units One time, when the count reaches m, a full signal is issued; the second monitor is used to monitor the full letter

2 P 17456 The second read unit is disabled, and the second output is used to sequentially output data to a queue. Preferably, the queue is a first in first out queue. Preferably, the communication data is k bits, and all components in the data sorting device are components capable of processing k bits. Preferably, the first register and the second register are D flip-flops. The above-mentioned data sorting device of the present invention overcomes the problem of slow sorting in the prior art by using a special circuit for sorting, thereby achieving better real-time processing effect of communication data. BRIEF DESCRIPTION OF THE DRAWINGS The accompanying drawings, which are set to illustrate,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,, In the drawings: FIG. 1 is a circuit diagram of a hardware sequencer implementation apparatus according to an embodiment of the present invention; FIG. 2 is a circuit diagram of the data comparison unit of FIG. 1. FIG. 3 shows an implementation of the present invention. A state transition diagram of an input processing state machine of an example; FIG. 4 is a state transition diagram of an output processing state machine in accordance with an embodiment of the present invention. BEST MODE FOR CARRYING OUT THE INVENTION Hereinafter, the present invention will be described in detail with reference to the accompanying drawings in conjunction with the embodiments. The following is an example of sorting by the maximum value, but it is obvious that the present invention can also be applied to the minimum order as long as the maximum value is replaced with the minimum value and the smaller one is sorted. Let the input data be n, and find the m maximum values sorted by size from the input data. 1 shows a hardware sequencer implementation apparatus according to an embodiment of the present invention, which is composed of the following parts: an input processing state machine 10; an output processing state machine 30; m data comparison units 20. Specifically, the input processing state machine is configured to process the input n communication data; the m cascaded data comparison units, m<=n, each of which includes: a comparator, configured to input communication data and current

3 P 17456 Comparing the maximum value or the current minimum value to obtain a comparison result; a selector for outputting the input communication data and the current maximum value according to the comparison result or the smaller one of the input communication data and the current minimum value to The first register outputs the smaller or larger to the second register; the first register is configured to save the larger one as the new current maximum value or the smaller one as the new current minimum value, and output the output to the comparator Comparing; a second register for storing the smaller or larger, outputting to the next level of data comparison unit; an output processing state machine for comparing the current maximum or current of the m cascaded data comparison units The minimum values are sequentially outputted to obtain m sorted communication data among the n communication data. The data sorting device of the above embodiment overcomes the problem of slower sorting in the prior art because it uses a special circuit for sorting, thereby achieving better real-time processing effect of communication data. Preferably, the communication data is from a queue, and the input processing state machine includes: a first reader for sequentially reading communication data from the queue; and a counter for counting each time a communication data is retrieved from the queue, When n is counted, a full signal is issued; a first monitor for monitoring the full signal, the first read unit is disabled; and a first outputter for sequentially outputting the communication data to the first level data comparison unit. Preferably, the queue is a first in first out queue. Preferably, the selector comprises: two two-select multiplexers, comprising: a first two-select multiplexer, comprising: two inputs, wherein the first input is used for inputting communication data, and the second The input terminal is used to input the current maximum value or the current minimum value provided by the first register; 1 enable end for inputting the comparison result; and 1 output terminal for the communication end receiving the communication data whose comparison result is input When the current value is greater than the current maximum value or less than the current minimum value, the communication data input from the first input terminal is enabled to the first register; the second two-select multiplexer includes: 2 input terminals, wherein the second input end For inputting communication data, the first input is used to input the current maximum value or the current minimum value provided by the first register; 1 enable end for inputting the comparison result; and 1 output terminal for the enable end receiving When the comparison result is that the input communication data is greater than the current maximum value or less than the current minimum value, enabling the output of the current maximum value or the current minimum value input by the first input terminal to the second register; otherwise, The communication data input from the second input terminal is enabled to the second register. Preferably, the output processing state machine comprises: a second reader for sequentially reading m cascaded data comparison units; and a counter for counting each data from the m cascaded data comparison units a number of times, when counting to m, a full signal is issued; a second monitor for monitoring the full signal, disabling the second reading unit; and a second output for sequentially outputting data to a queue

4 P 17456 in. Preferably, the queue is a first in first out queue. Preferably, the communication data is k bits, and all components in the data sorting device are components capable of processing k bits. Preferably, the first register and the second register are D flip-flops. Figure 2 shows a circuit diagram of the data comparison unit of Figure 1, the data comparison unit consists of one greater than comparator 22, one selector (including two two-select multiplexers 24, 26) and two bit widths. It is a combination of k-bit registers (28, 29). The input data (V_in) greater than the bit width of the comparator is compared with the current maximum value (value). If the input data v_in is greater than the current maximum value, the output of the comparator (big) is greater than 1, otherwise Take the value 0. The two-choice multiplexer selects one of the two inputs as the output according to the value of the selection signal, and outputs the input from the branch 1 (the first input terminal) if the value of the selection signal is 1, if the value of the selection signal is 0. Then the input from branch 0 (the second input) is output. The register is used to store the result of each data comparison; the initial value of the register after power-on reset is 0; when the register enable signal (enable) is valid, the data on the register data input is saved to the register; when the register clears the signal The register is cleared when (clear) is active. In the apparatus of the present invention, the two registers respectively store the current maximum value (value) and output to the value (v_out) of the next-stage data comparison unit. If the input data v_in is greater than the current maximum value, the value of the value register will be updated to the current input data when the enable signal is valid, and the value of the v_out register will be updated to the original maximum value. If the input data v_in is not greater than the current maximum value, the value of the value register will be unchanged when the enable signal is valid, and the value of the v_out register will be updated to the current input data. The packet format of the input data packet according to an embodiment of the present invention is shown in the following table:

 The packet parameter n is the number of input data; the packet format parameter I is the bit width of the parameter n. The packet parameter m is the number of output results; the packet format parameter J is the bit width of the parameter m. The bit width of the data is k = I + J. The CPU is in the order of the number of the input packet from small to large.

5 P 17456 Each word is written to the input FIFO in turn. The input processing state machine monitors the input FIFO, and generates a FIFO read signal when there is a data packet in the input FIFO; parses the packet parameters n and m from the first word of the data packet according to the determined packet format parameters I and J; The parameter n value obtained from the input data packet determines the number of times the data is read, sequentially reads n data from the input FIFO and synchronously generates a register enable signal of the data comparison unit; reads n data and m clocks The cycle sorting pipeline delays the current round of data processing and generates a sorting completion signal; waits for the output completion signal generated by the output processing state machine to complete the output of the data, and generates a register clearing signal of the data comparison unit after detecting the output completion signal and returns Idle state. 3 shows a state transition diagram of an input processing state machine in accordance with an embodiment of the present invention, as follows:

S—IDLE: Idle state. The input processing state machine is in this state after power-on reset. In this state, the data presence signal ( s_exists ) of the input FIFO is monitored, and when the signal is active (high level), a FIFO read signal (s-read, active high) is generated and goes to the S_DECODE state.

S— DECODE: Decode status. In this state, the first word of the packet on the input FIFO data signal (s_data) is parsed to obtain the packet parameters n and m. If the parameter n or m is 0, no sorting is required, and the input processing state machine returns to the S_IDLE state. If the parameters n and m are both greater than 0, the data of the input FIFO is monitored (s_present). When the signal is valid (high level), a FIFO read signal (s-read, active high) is generated and transferred. S—COMP status.

S_COMP: Comparison status. In this state the input data into the count ^ ^1, if the input data counter data- cnt is smaller than n, the monitoring of the presence signal FIFO input data (s_exists), as a FIFO read signal (s When this signal is active (high level) —read, active high). If the input data counter data_cnt is equal to η, it is transferred to the S_WAIT state.

S—WAIT: Waiting state. In this state, first wait m clock cycles, ensure that the last input data reaches the m-th data comparison unit and complete the data comparison; then generate a sort completion signal (order_ finish), notify the output processing state machine to start outputting the result; The output completion signal (output_finish) generated by the processing state machine is monitored. When the signal is valid (high level), the register clear signal of the data comparison unit is generated and the S_IDLE state is returned. The output processing state machine monitors the sort completion signal, generates a FIFO write signal when the signal is valid and there is an idle position in the output FIFO, and stores the m maximum values stored in the current maximum value register of the m data comparison units from large to small. The order is sequentially written to the output FIFO, the first level of data ratio

6 P 17456 The current maximum value stored in the unit is written first; waiting when the output FIFO is full; the output completion signal is generated after the output of the m maximum values is completed and returns to the idle state. 4 shows a state transition diagram of an output processing state machine in accordance with an embodiment of the present invention, as follows: MJDLE: Idle state, the output processing state machine is in this state after power-on reset. In this state, the sort completion signal (order_finish) generated by the input processing state machine is monitored, and when the signal is active (high level), it is transferred to the M_WRITE state.

M— WRITE: Output status, in which the m maximum values stored in the current maximum value register of m data comparison units are sequentially written to the output FIFO in descending order. If the FIFO full signal of the output FIFO (m_ftill, active high) is invalid, that is, there is an idle position in the output FIFO, the current maximum value stored in each stage of the data comparison unit is output to the data input signal (m_data) of the output FIFO one by one. The FIFO write signal (m_write, active high) of the output FIFO is synchronously generated, and the maximum value stored in the first-stage data comparison unit is output first. After the output is completed, an output completion signal ( output_fmish ) is generated and the M_IDLE state is returned. The entire hardware sequencer implementation is shown in Figure 1. The input data packets stored in the input FIFO are sequentially read under the control of the input processing state machine, and the packet parameters n and m are parsed from the first word of the data packet according to the determined packet format parameters I and J; Then, each data is sequentially read and input to the first-stage data comparison unit; each time one data is read from the input FIFO, the enable signal of each data comparison unit is valid once; the output of the first-stage data comparison unit is input to the second level. The data comparison unit inputs the output of the second-stage data comparison unit to the third-stage data comparison unit, and so on, and the output of the m-1th-level data comparison unit is input to the m-th level data comparison unit; After the unit has also completed the comparison of all the data, the m maximum values stored in the data comparison units of each stage are written to the output FIFO under the control of the output processing state machine. The input processing state machine returns to the idle state, and the output processing state machine returns to the idle state. Take the common peak search operation in wireless communication processing as an example. The number of input data is at most

256, the data bit width is 16 bits; it is required to find up to 8 maximum peaks from the input data. The device for implementing the hardware sequencing coprocessor according to the embodiment of the present invention is composed of the following components: 8 data comparison units, 1 input processing state machine, and 1 output processing state machine. According to the description of Fig. 2, the data comparison unit is composed of one register larger than the comparator, two two-selection multiplexers, and two registers having a bit width of k = 16 bits.

7 P 17456 Preferably, the hardware sequencing coprocessor implemented by the embodiment of the present invention implements input through

The FIFO and output FIFO are connected to the CPU. The CPU writes the input data packet to the input FIFO according to the data packet format of Figure 2. The values of the packet format parameters I and J of the data packet are 1=10 ( 2 ^Λ 10>=256 ), J=6 ( 2 ^Λ 6 >=8 ). The implementation device completed according to the above design requirements can handle all cases where the number of input data is less than or equal to 256 and the number of output results is less than or equal to 8. The actual number of input data is 199, and it is required to output 7 maximum peaks. The actual values of the parameters n and m in the data packet are n=199 and m=7 o respectively. 199 input data take the actual value. According to Figures 3 and 4, the working process of the entire hardware sequencing coprocessor implementation device can be derived. The input processing state machine is idle after a power-on reset and monitors the input FIFO. When there is a data packet in the input FIFO, the input data packets stored in the input FIFO are sequentially read under the control of the input processing state machine, and the first format of the packet is from the packet format parameters of 1=10 and J=6. The data packet parameters n=199 and m=7 are parsed in the word; then each data is sequentially read and input into the first level data comparison unit; each time a data is read from the input FIFO, the enable signal of each data comparison unit is valid. Once; the output of the first-stage data comparison unit is input to the second-stage data comparison unit, the output of the second-stage data comparison unit is input to the third-stage data comparison unit, and so on, and the output of the sixth-stage data comparison unit is input to Level 7 data comparison unit; after the 7th stage data comparison unit also completes the comparison of all 199 data, the 7 maximum values stored in the 1st to 7th stage data comparison units are under the control of the output processing state machine Is written to the output FIFO. The input processing state machine returns to the idle state, and the output processing state returns to the idle state. The above embodiments of the present invention are characterized by: 1. The sorting operation is implemented by hardware. Second, multiple data comparison units are sequentially connected to form a pipeline, each data comparison unit compares the input data of the unit, and the data comparison units of the pipelines operate simultaneously; all the input data can be sorted once by the pipeline once. operating. 3. The implementation device according to the determined n and m values can process all cases where the number of input data is less than or equal to n and the number of output results is less than or equal to m. With the apparatus of the present invention, the sorting operation is improved from software implementation to hardware implementation as compared with the prior art. Assuming that there are a total of n input data and m-level data comparison units, after n + m clock cycles, the m-level data comparison units from 1 to m store m maximum values arranged in descending order. Therefore, the number of clock cycles occupied by the sort operation implemented by the hardware sequencer is proportional to n. Therefore, the device of the present invention can overcome the shortcoming that the number of clock cycles occupied by the software implementation of the sorting operation in the prior art is proportional to the factorial of n, and solves the problem that the sorting operation implemented by software in the prior art cannot meet the real-time signal processing pair. The problem of real-time requirements for data processing.

8 P17456 The above is only the preferred embodiment of the present invention, and is not intended to limit the present invention, and various modifications and changes can be made to the present invention. Any modifications, equivalent substitutions, improvements, etc. made within the spirit and scope of the present invention are intended to be included within the scope of the present invention.

9 P 17456

Claims

 Claims A data sorting apparatus for processing communication data, comprising:  An input processing state machine for processing the input n communication data;  m cascaded data comparison units, m<=n, which all include:  a comparator, configured to compare the input communication data with a current maximum value or a current minimum value to obtain a comparison result;  a selector, configured to output, according to the comparison result, the larger of the input communication data and the current maximum value or the input communication data and the current minimum value to a first register , the smaller or larger output to the second register;  The first register is configured to save the larger one as a new current maximum value or a smaller one as a new current minimum value, and output the result to the comparator for comparison;  The second register is configured to save the smaller one or the larger one, and output the data comparison unit to the next stage;  And an output processing state machine, configured to sequentially output the current maximum value or the current minimum value in the m cascaded data comparison units to obtain m pieces of the communication data in the n communication data. 2. The data sorting apparatus according to claim 1, wherein the communication data is from a queue, and the input processing state machine comprises:  a first reader, configured to sequentially read the communication data from the queue; a counter, configured to count a number of times when the communication data is taken from the queue, and when the count reaches n, issue the full Signal  a first monitor, configured to disable the first reading unit when the full signal is monitored;  And a first outputter for sequentially outputting the communication data to the first level data comparison unit. 10 P17456 The data sorting apparatus according to claim 2, wherein the queue is an advanced first-out queue. The data sorting apparatus according to claim 1, wherein the selector comprises: two two-selection multiplexers, including:  The first two-select multiplexer includes:  Two inputs, wherein a first input is used to input the communication data, and a second input is used to input the current maximum value or a current minimum value provided by the first register;  1 enable terminal for inputting the comparison result;  1 output terminal, configured to enable the output of the first input terminal when the communication terminal receives the comparison result that the input communication data is greater than the current maximum value or less than a current minimum value Transmitting communication data to the first register; a second two-select multiplexer, comprising: Two inputs, wherein the second input is used to input the communication data, and the first input is used to input the current maximum value or the current minimum value provided by the first register;  1 enable terminal for inputting the comparison result;  1 output terminal, configured to enable the output of the first input terminal when the communication terminal receives the comparison result that the input communication data is greater than the current maximum value or less than a current minimum value Describe the current maximum value or the current minimum value to the second register; otherwise, enable the output of the communication data input by the second input terminal to the second register. The data sorting apparatus according to claim 1, wherein the output processing state machine comprises:  a second reader, configured to sequentially read the m cascaded data comparison units; and a counter for counting each time data is taken from the m cascaded data comparison units, when counting When m is reached, a full signal is issued;  a second monitor, configured to disable the second reading unit when the full signal is monitored; 11 P17456 a second outputter for sequentially outputting the data to a queue. 6. The data sorting apparatus according to claim 5, wherein the queue is a first in first out queue. The data sorting apparatus according to any one of claims 1 to 6, wherein the communication data is k bits, and all components in the data sorting means are components capable of processing k bits. The data sorting apparatus according to any one of claims 1 to 6, wherein the first register and the second register are D flip-flops. 12 P 17456