JPH0155493B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to a memory sorting circuit that rearranges data stored in a memory in a specific order.

In the past, most memory sorting methods involved sequentially comparing a specific address with another address and exchanging them using software. However, when dealing with a huge amount of data, this method requires an extremely long calculation time, and even if individual calculations are performed at high speed, sorting, which involves a large number of calculations, requires a lot of processing time.

Therefore, in memory sorting, the present invention
It is an object of the present invention to provide a memory sorting circuit for performing sorting in a short time without imposing as much load on a processing device as possible. Furthermore, although there are many types of memory sorting, the present invention provides a memory sorting circuit particularly suitable for rearranging data in a certain memory area in order of magnitude.

To achieve this object, the present invention provides a memory read address designation circuit that specifies read addresses of the sorting area in order from the beginning of the sorting area in a memory sorting circuit that rearranges data in a certain area (sorting area) of a memory in order of size. , a memory write addressing circuit that sequentially specifies write addresses of sorted data, a sorting working memory, a sorting counter that sequentially specifies read addresses of the sorting working memory, and a data line of the memory and the sorting working memory. is provided between the address line of the sorting working memory and the output line of the sorting counter, and connects the data line of the memory and the address line of the sorting working memory by a write mode signal;
A read mode signal connects the output line of the sorting counter and the address line of the sorting working memory, and specific data read from the sorting working memory connects the output line of the sorting counter and the data of the memory. and a main control circuit that controls these, and the main control circuit instructs the memory read address designation circuit to set an address in response to an external sorting start command, and a function of instructing a memory to read, sending a write mode signal to the data transmission switching circuit and the sorting working memory, and writing the specific data to the sorting working memory using the data read from the memory as an address; After writing this specific data, the memory write address designation circuit is instructed to set an address, and a read mode signal is sent to the data output switching circuit and the sorting working memory, and the output of the sorting counter is used as the address for the sorting. a function of reading data from the sorting working memory; and when data other than the specific data is read from the sorting working memory while reading data from the sorting working memory, the sorting counter counts up (or counts down). On the other hand, if specific data is read, it instructs writing to the memory, instructs the memory write address designation circuit to set the next address, and instructs the sorting counter to count up (or count down). and a function of sequentially writing into memory the addresses of the sorting working memory from which the specific data has been read.

Embodiments of the present invention will be described in detail below with reference to the drawings.

FIG. 1 is a schematic configuration diagram for explaining the present invention. In FIG. It is connected via a bus (direct memory access bus) 5.

The configuration of the sorting control section 3 is shown in FIG.
6 is a start address register that stores the start address of memory sorting; 7 is a final address register that stores the end address of memory sort; 8 is a memory address counter that specifies the address for reading or writing from memory 2; 9 is a memory address register that stores the start address of memory sorting; This is a coincidence circuit that sends out a match signal _S1 when the contents of the final address register 7 and the contents of the memory address counter 8 match, and these The dense circuit 9 constitutes a memory read address designation circuit that sequentially designates the read address of the sorting area from the beginning of the sorting area, and a memory write address designation circuit that sequentially designates the write address of the sorted data. 10 is a sorting working memory used to replace data in the memory 2; 11 is a sorting counter that sequentially specifies read addresses of the sorting working memory 10;
Reference numeral 12 is provided between the data line 14 of the memory 2, the address line 13 of the sorting working memory 10, and the output line of the sorting counter 11, and connects the data line 14 and the address line 13 by a write mode signal to perform a read operation. Data transmission that connects the output line of the sorting counter 11 and the address line 13 according to the mode signal, and connects the output line of the sorting counter 11 and the data line 14 when the read data of the sorting working memory 10 is specific data. 15 is a main control circuit for controlling the operations of the registers, counters, data transmission switching circuit 12, etc.; 16 is a memory control circuit for the memory 2; and 17 is an address line for the memory 2.

Next, the operation of the sorting control section having the above configuration will be explained.

First, the sorting start address information and the sorting end address information of the memory 2 are received from the central processing unit 1, and by the set signal _S2 sent from the main control circuit 15, the start address register 6,
Set in final address register 7. Next, upon receiving a sorting start command from the central processing unit 1, the main control circuit 15 outputs a counter preset signal _S3.
, and presets the contents of the memory address counter 8 to the sorting start address, and also triggers the memory control circuit 16 to enable access to the memory 2.

The data read from the sorting start address of the memory 2 is applied to the data output switching circuit 12 via the data line 14. The data transmission switching circuit 12 is switched to transmit the data from the data line 14 to the address line 13 by the write mode signal _S4 transmitted from the main control circuit 15, and the data read from the memory 2 is transferred to the sorting working memory. 10 as address data. The write mode signal _S4 is also supplied to the sorting working memory 10, and the sorting working memory 10 uses this signal to write "1" using the contents of the read data of the memory 2 as an address.

As an example, if the sorting start address is the M address and the sorting final address is the N address, the memory address counter 8 is first set to M, and the data at the M address is read from the memory 2. If this data is "F5DE", "1" is written to the "F5DE" address of the sorting working memory 10. Next, the main control circuit 15 sends a count-up signal _S5 to the memory address counter 8.
is sent, and the read address of memory 2 is set to (M+
1) At the same time, the memory control circuit 16 is triggered again to read the data at address (M+1). If this read data is "421F", "1" is written to the address "421F" of the sorting working memory 10 in the same way as above.
Thereafter, this operation is repeated until the final sorting address N is read out. Assuming that one word of the memory 2 is 16 bits, the sorting working memory 10 requires 64 kbits of memory.

The contents of memory address counter 8 become N,
When the read address of the memory 2 matches the final sorting address, a match signal _S1 is sent from the coincidence circuit 9 to the main control circuit 15. The main control circuit 15 ends the data retrieval stage and moves on to the next stage since all the data from address M to address N of the memory 2 has been retrieved.

First, a preset signal _S3 is sent from the main control circuit 15, and the memory address counter 8 is preset to M again. Also, the write mode signal _S4 sent from the main control circuit 15 disappears at this stage, the sorting working memory 10 is in the read mode, and the data sending switching circuit 1
2 is switched so that the contents of the sorting counter 11 are sent to the address line 13. Therefore, data at the address indicated by the contents of the sorting counter 11 is read from the sorting working memory 10. This read data signal _S6 is transmitted to the main control circuit 15 and the data transmission switching circuit 12.
It is beginning to be given to Main control circuit 15
sends a count-up signal _S7 to the sorting counter 11, and the sorting working memory 1
The sorting counter 11 is counted up at high speed until "1" is read from 0. If the minimum value of the data from address M to address N in memory 2 is, for example, "00FE," then "1" is read from sorting working memory 10 when the content of sorting counter 11 reaches "00FE." When "1" is read out from the sorting working memory 10, the main control circuit 15 stops sending out the count-up signal _S7 , stops the sorting counter 11 at "00FE", and triggers the memory control circuit 16. . On the other hand, the data output switching circuit 12 is switched to output the contents of the sorting counter 11 to the data line 14 of the memory 2 when the read data of the sorting working memory 10 is "1".

The memory 2 writes the content "00FE" of the sorting counter 11 applied via the data line 14 to the M address applied via the address line 17.
When writing to memory 2 is completed, main control circuit 1
5 sends a count-up signal _S5 to set the memory address counter 8 to (M+1) and also sends a count-up signal _S7 to the sorting counter 11 again.
continue to send out. When "1" is read again from the sorting working memory 10, the contents of the sorting counter 11 at that time are written to address (M+1) of the memory 2. Thereafter, similar operations are repeated, and when the memory address counter 8 reaches N and the coincidence signal _S1 is output from the coincidence circuit 9, the operation ends.

In this way, whenever "1" is read from the sorting working memory 10, the contents of the sorting counter 11 at that time are written into the memory 2, and the data from addresses M to N in the memory 2 are replaced in ascending order.

The effects of the sorting control method described above are summarized in a diagram as shown in FIG. 3. Data from addresses M to N in the sorting area of the memory 2 is read out in order, and "1" is written into the sorting working memory 10 using this data as an address. Next, the sorting working memory 10 is sequentially read from address 0 at high speed, and each time a "1" is read, the address of the sorting working memory 10 at that time is written sequentially from address M of the memory 2. 2' indicates a part of the memory 2 after sorting is completed.

When replacing the data in the memory 2 in ascending order, contrary to the above, read the data in the sorting area of the memory 2 in order, write "1" to this data as the address of the sorting working memory 10 as described above, and then start sorting. This can be achieved by setting the sorting counter 11 to "FFFF", counting down in the opposite manner to the above, and sequentially writing into the memory 2 the addresses of the sorting working memory 10 from which "1" is read.
If the same data is duplicated within the sorting area, sorting ends when the sorting counter 11 sends out a carry signal (or borrow signal).

As described in detail above, according to the present invention, the processing device only needs to provide information specifying a sorting area and a sorting command, and while sorting is being performed, other processing can be performed. This has the effect of improving the utilization efficiency of the device, and also has the effect of performing sorting in a short time. In particular, when reading font data of a kanji from a memory device such as a disk or FDD using a kanji code input at random,
This is useful for rearranging input Kanji codes in the order of the storage addresses of the font data so that a large number of font data can be read from the memory device in a short time.

[Brief explanation of drawings]

FIG. 1 is a schematic configuration diagram for explaining the present invention, FIG. 2 is a block diagram showing the configuration of a sorting control section, and FIG. 3 is an explanatory diagram of the operation of the present invention. DESCRIPTION OF SYMBOLS 1...Central processing unit, 2...Memory, 3...Sorting control unit, 4...Program bus, 5...DMA bus, 6...Start address register, 7...Final address register, 8...Memory address counter, 9...
Coincidence circuit, 10... Sorting working memory, 11... Sorting counter, 1
2...Data transmission switching circuit, 13...Address line, 1
4...Data line, 15...Main control circuit, 16...Memory control circuit, 17...Address line.

Claims (1)

[Scope of Claims] 1. A memory sorting circuit that rearranges data in a certain area of memory (sorting area) in order of magnitude, comprising: a memory read address designation circuit that specifies read addresses of the sorting area in order from the beginning of the sorting area; a memory write address designating circuit that sequentially specifies a write address for data stored in the memory, a sorting working memory, a sorting counter that sequentially specifies a read address of the sorting working memory, a data line of the memory, and the sorting working memory. is provided between an address line of the sorting counter and an output line of the sorting counter, and connects the data line of the memory and the address line of the sorting working memory by a write mode signal;
A read mode signal connects the output line of the sorting counter and the address line of the sorting working memory, and specific data read from the sorting working memory connects the output line of the sorting counter and the data of the memory. and a main control circuit that controls these, and the main control circuit instructs the memory read address designation circuit to set an address in response to an external sorting start command, and a function of instructing a memory to read, sending a write mode signal to the data transmission switching circuit and the sorting working memory, and writing the specific data to the sorting working memory using the data read from the memory as an address; After writing this specific data, the memory write address designation circuit is instructed to set an address, and a read mode signal is sent to the data output switching circuit and the sorting working memory, and the output of the sorting counter is used as the address for the sorting. a function of reading data from the sorting working memory; and when data other than the specific data is read from the sorting working memory while reading data from the sorting working memory, the sorting counter counts up (or counts down). On the other hand, if specific data is read, it instructs writing to the memory, instructs the memory write address designation circuit to set the next address, and instructs the sorting counter to count up (or count down). A memory sorting circuit having a function of sequentially writing addresses of the sorting working memory from which the specific data has been read into the memory.