JPH0516607B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION Technical Field The present invention relates to a memory control method for storing search data of an information search device and corresponding data of the search data.

Prior Art Conventionally, in an information retrieval device using a magnetic disk or the like in which a large amount of information is stored, when obtaining the information requested by an operator, the control device of the magnetic disk device is asked to identify the characteristics of the desired information (or a heading called a "key"). ), accesses the magnetic disk device, extracts information that matches the provided information, or extracts information that is closest to the provided information, and notifies the operator who made the request. The extracted data is stored in a predetermined buffer memory, and is extracted upon request from the host device. In other words, since the buffer memory and the search data storage memory exist separately, the desired information is stored when processing minimum value and maximum value searches (sorting) in real time with a device using a magnetic disk or the like. When sorting is performed while sequentially reading data from memory, if the information that is the searched data is
The data may be used as search data during the time tx+1, and the searched data and search data must be switched continuously. In general, devices that cannot perform continuous processing use a split sector method to read the sector format on the magnetic disk (the read order is one sector or multiple sectors from the base point, and one If the data is skipped, it takes twice as long, and if it skips n items, it takes n times as long), etc., and the process is performed in time other than reading, and the data is moved, making high-speed processing difficult. .

Purpose The present invention aims to eliminate the above-mentioned drawbacks of the conventional technology, and is aimed at eliminating the occurrence of idle time in an information processing device using a magnetic disk, etc., in which information is stored in a continuous sector format, and using the real time information of the magnetic disk, etc. A memory control method that allows you to extract the desired data using a magnetic disk drive, and also allows data to be registered in a magnetic disk device at any address without having to worry about reading it, and that allows high-speed processing of registration and output to an information retrieval device. I will provide a.

Embodiment An embodiment of the present invention will be described below with reference to the drawings. FIG. 1 is a block diagram of an information retrieval device implementing the present invention.

1 is an external storage device under the control of this information retrieval device. Reference numeral 2 denotes an interface A for controlling, transmitting and receiving data and clocks of the external storage device 1 mentioned above.
3 is an interface B for transmitting and receiving the address of the external storage device 1 and return information from the external storage device 1; 4 is a control unit MCT which controls the above-mentioned 1, 2, 3 and the entire information retrieval device of the present invention.
Reference numeral 5 denotes a three-state gate that switches internal bus lines, which will be described later, and also controls the direction of data according to instructions from the control unit MCT4. 6 is a memory JM that temporarily stores information instructing a search method for search information. Reference numeral 7 denotes a memory Q1 that stores initial values of search information. Memory Q2 (8) and memory Q3 (9) temporarily store searched data extracted from external storage device 1, or temporarily store searched data, according to the contents of memory JM6 and memory Q1 (7). This is a buffer memory/search register that serves as a search data storage memory for searching the second and third extracted data. 10
Comparator CM1 compares data read from external storage device 1 via interface A (2) with data read from memory Q1 (7).
11 and 12 are comparators CM2 or CM3 that compare the read data with the data read from memory Q2 (8) or memory Q3 (9) like the above-mentioned CM1 (10). 13 is memory JM6, memory Q1 (7), A length counter (L/C) that controls the address of memory Q2 (8) and memory Q3 (9) and the length of the searched data. 14 is CM1 (10), CM2 (11),
Controls logic control of each comparator output of CM3 (12)
A search logic circuit control unit IRCT that controls the operation of the LC 13 and sends predetermined control information to a corresponding record address storage memory ADM16 and a corresponding record status storage memory STM17, which will be described later. 15 is
According to the output information of MCT4, the division of searched data is counted, each set of data (record) is held as the corresponding address, and IRCT14
Record address counter RADC sent to ADM16 according to instructions from RADC. 16, as mentioned above,
A memory that temporarily stores the contents of RADC16 and record addresses according to instructions from IRCT14.
ADM. Reference numeral 17 denotes a memory STM that stores the state of searched data (presence or absence of a match, information on the presence or absence of multiple matches indicating that the same data previously existed, etc.). 1
Reference numeral 8 denotes a bus interface BIF for connecting the information retrieval device of the present invention and higher-level devices. 19 is a high-speed bus line MBUS through which raw information from the external storage device 1 mentioned above is exchanged. 20 is an SBUS through which the status of each memory, counter values, and information to the BIF 18 are exchanged under the control of the MLT4. 21 is a communication means LBUS between this information retrieval device and a host device, and an arbitrary communication means can be constructed using the BIF 18.

Next, the principle of operation of an information retrieval device according to a preferred embodiment of the present invention will be described in detail with reference to the drawings.

FIG. 2 is an operational flowchart of the present invention.
An external storage device 1 in which instructions and search data to be searched are stored in the information processing apparatus in a predetermined format via the LBUS 21 in FIG.
address or file name for each file is sent from the host device, the sent information is decoded by the control unit (MCT) 4, and controlled to the external storage device 1 via each search register and interface B3. etc., and the search process starts. When predetermined initial values are set in the search registers JM and Q1 (steps 100 and 101), the external storage device 1 enters a data read cycle (step 102). There is a waiting time until the external storage device 1 reaches the address to be searched, and when the search instruction address is reached (Step 103-Y), a search start command is sent from the MCT 4 to the LC 13 and RADC 15 (Step 104), and the external In synchronization with the read speed of the storage device 1, a comparison is performed between Q1 (7) and the read data of the external storage device 1 output on the MBUS 19 via the interface A2 according to the contents of JM6 (step 105). This comparison uses the first and second half of one clock cycle to determine the upper limit value (or lower limit value) and lower limit value (or upper limit value) for the searched data.
The binary information that is the initial value of is compared, and it is determined whether the searched data is included in the initially set values. Next, if it is determined that “applicable in Q1”,
It is selected whether the data has first priority (step 106). If the data is not the first priority, then it is selected whether the data is the second priority (step 107).

The conditions for selection as the first priority are (1) When the first match is found within the specified search range.

(2) From the corresponding data stored in Q2 and Q3,
If it is closer to the limit value.

The conditions to be selected as the second priority are as follows: (1) The second time a match is found within the specified search range, and it is further from the extreme value than the first time, or the first time matching data is found. If equal to .

(2) For the first priority and second priority data stored in Q2 and Q3, if the data is closer to the extreme value than the existing first priority data and closer to the extreme value than the existing second priority data (in this case This data replaces the existing second priority data and becomes second priority data).

If it is determined that the data has the first priority (step 106-Y), a flag indicating whether the data stored in Q2 (8) and Q3 (9) have the same content; determines the FSDB ( Step 108), if FSDB
If ≠1 (if not the same content), it is the first applicable data from the start of the search, or Q2 (8) and Q3
Data with a higher priority than any of the data stored in (9) is input as the searched data, and the new data with the second priority does not have the same data. Therefore, it is determined whether the FDBL flag indicating that there was searched data that is the same as the second priority data in the past has been set (step 113), and if it has been set, it is reset (step 113). 114). After that, in order to make the searched data stored in the work area the first priority data, the value of the record address counter where the searched data was recorded is stored in memory.
In addition to setting ADM (step 111), Q2
(8), the work area where the searched data in Q3(9) is stored is the search data area, and Q2(8),
Data that is farther than the limit value in Q3 (9) is deleted, and the data storage location becomes a new work area (step 112).

Also, if FSDB = 1, the corresponding data stored in Q2 (8) and Q3 (9) are equally searched data, that is, the first priority data, which is closer to the limit value than the already applicable data, so one of the already applicable data is must be deleted, but the FDBL flag is set to indicate that data equal to the existing applicable data existed in the past (step 109), and the FSDB flag is then reset to indicate that the existing applicable data is the same (step 109). Step 110).

Then, in the same way as when FSDB=1 mentioned above, the value of the record address counter is set in the memory ADM, and the previous applicable data that is later in time (referring to the existing applicable data that is near the end of the address within the search instruction range) is deleted ( Step 111), Q2 or Q3 mentioned above
The deleted data area is secured as a work area for the next record (step 112).

Next, if it is determined that the data is not the first priority (step 106-N), it is determined whether the above-mentioned second priority conditions are satisfied (step 107), and the data is determined to be second priority. Then, it is determined whether the second priority data is equal to the first priority data (step 115), and if they are equal, Q2 (8) and Q3 (9) are performed.
This means that the data stored in the registers are equal, and the next time the corresponding data interrupts the upper level as first priority data, the flag for setting the FDBL, FSDB (existing Q2 and Q3) is set. ) (indicates that the corresponding data are equal) (step 116), and stores the value of the record address counter in memory.
ADM (step 111), the area where second-priority data was previously stored is set as a new work area, and the area where the searched data was stored is used to search for new second-priority data. data (step 112).

Also, if the second priority data is different from the first priority data, for example, in a descending sort process, if the first priority data < the second priority data, it will be treated as normal applicable data and a special flag will be set. Does not involve setting or resetting. That is, the record address is set in the memory ADM (step 111), and the deleted data area is secured as a new work area (step 112).

If it is determined in step 107 that the data is not the second priority data, it is determined whether the data is equal to the second priority data (step 117), and if they are equal, Q2 (8) and Q3 (9) are performed. The FDBL flag is set to indicate that the same data as the corresponding data stored in the file exists (step 118). Thereafter, it is processed as "not applicable" (step 119).

Next, using FIG. 3, the actual data storage state and comparison state will be explained along the flow of time. Third
The figure shows the data flow when arbitrary numerical information is sorted in descending order from 50 to 125, Q1 (7), Q2 (8),
Indicates the data storage status and record address storage status of Q3 (9). In the figure, the time is T0~
The flow is T1, T2, ...Tn, and the searched data is read output from an external storage device such as a disk device, and record numbers R0, R1, ... are used to distinguish each data.
There is Rn. Q1 (7) stores the limit value, lower limit, and upper limit for sorting, and the comparator 7 in FIG. 1 checks whether the data to be searched is included in the desired values. In other words, it is step 105 of the flowchart, and at T0, 50<123<125, so R0=
123 is determined to be "applicable" and is stored in the work area W of Q2 (8). In T1, 50＜99＜ in Q1
125, and similarly, R1=99 is determined to be "applicable", and 99<123 holds true in Q2 (8), so R1=
99 is the first priority data and R0=123 is the second priority data. Further, each corresponding record address is shown in the storage state of record addresses in FIG. 3, with the upper one representing the first priority and the lower one representing the second priority. In T2, 50 < 105 < 125 in Q1, so "applicable"
However, in Q2 and Q3, 99 < 105 < 123 holds, so R0 = which was the second priority until now.
123 will be deleted. The record address is also R1 and R
Store 2. In T3, the conditions for Q1 are the same as in T2, but in Q2 and Q3, 99=99<105, R2=105, is deleted, and the first and second priority data are equal.
FSDB is set. In T4, the condition of Q1 is satisfied, but in Q2 and Q3, the condition 99=99<102, and the data of R4 has a low priority, so it is determined as "not applicable". In T5, Q1 is “applicable”
Since 91<99=99 holds true for Q2 and Q3, it becomes first priority data and R3=99 is deleted. R3=99
and R1=99 are equal, so as mentioned above, FSDB=1
So, since the first priority data has newly appeared,
FDBL is set, FSDB is reset, and the existence of equivalent data other than the data stored in the register can be known. In T6, the condition of Q1 is satisfied, but in Q2 and Q3, 91<R6≦99 means R6=100
Therefore, it does not hold, so it becomes ``Not applicable.'' In T7, the condition of Q1 is satisfied, and in Q2 and Q3, R7 (85) < 91
Since <99 holds, the first priority data is R7=85, the second priority is R5=91, and R1=99 is deleted. Therefore, (99) disappears in Q2 and Q3, so FDBL is reset.

The record address is stored in the record memory ADM for each record, but if it is determined that there is a match, information on whether or not there is a match is added to the beginning of the record address.
Stored in ADM. The ADM has an n-stage stack structure, and the MCT can check the data in the ADM at any time (any time until the reading of this record is finished), and as described above, multiple records can be sorted in one sort process. (searched data)
You can also extract the record and find out the address of that record. By physically bringing the size of Q2 and Q3 closer to the size of the external storage device, more data can be extracted at one time. In other words, it is possible to rearrange information stored randomly in a disk device or the like (representing random order when numerically representing a magnitude relationship) in ascending order or ascending order by searching the disk once. The structure of this record address is shown in FIG. Further, FIG. 5 shows the relationship between each register and the data to be searched. I1, I2,...
I5 represents an item within each record (RN, RN+1...). Each item is a unit of information that can be used as a key reference at the time of a search, and it is possible to perform a logical product search of each item such as I1, I2, and I3, and a logical sum search starting with I1+I2+I3. In such a search, high-speed search processing can be realized by comparing a plurality of comparison search data for the same search target data in a time-sharing manner depending on the sizes of Q2 and Q3.

Effects As described above, according to the present invention, data to be searched is sequentially read out one by one and stored in a designated position, and this read data and the ranking stored so far are As a result of this comparison,
When there is one or more pieces of data with a lower rank than the read data, the storage position of the data with the lowest rank among them is specified as the storage position of the search target data to be read next, and the rank is set. At this time, the processing of storing and comparing the read data is performed in synchronization with the reading, so that when the processing goes through all the data to be searched, multiple It becomes possible to rank and search data (assuming n data).

Furthermore, by using this to sort all data, we provide a memory control method that reduces the processing time to one-nth compared to the conventional method, which allows searching for only one piece of data each time it goes through all the data. can.

In addition, storage processing is performed in the same way regardless of whether the read data is of a higher rank than the previously stored data.
It is possible to provide a memory control method that realizes high-speed processing that can be used for subsequent comparison processing without moving the storage location even when the data is of a high rank.

Furthermore, since this comparison and storage processing is performed in synchronization with reading, a memory control system that can realize high-speed processing can be provided.

[Brief explanation of the drawing]

FIG. 1 is a block diagram of this embodiment, FIG. 2 is an operation flowchart, FIG. 3 is a diagram showing the flow of data when performing sorting in ascending order, FIG. 4 is a diagram showing the structure of record addresses, and FIG. The figure is a diagram showing the correspondence between searched data and each register. In the figure, 1...external storage device, 2...interface A, 3...interface B, 4...
Control unit, 6...Memory JM, 7...Memory Q1, 8
...Memory Q2, 9...Memory Q3, 10...Comparator CM1, 11...Comparator CM2, 12...Comparator
CM3, 13...Length counter, 14...Search logic circuit control section, 15...Record address counter, 16...Memory ADM, 17...Memory
STM, 18... bus interface.

Claims (1)

[Scope of Claims] 1. Data is sequentially read one by one from a first memory that stores search target data, and the read data is placed into a predetermined number of ranked data in synchronization with the reading of the data. The data is stored in a designated storage location in a second memory having storage locations for the predetermined number of pieces of data, and the read data and the designated storage location of the second memory are stored in a designated storage location. As a result of each comparison, among the data stored in a storage location other than the specified storage location of the second memory, the readout data is compared with the data stored in the storage location of the second memory. If there is data with a lower rank than the data that has been ranked, the storage position of the data with the lowest rank according to the ranking is set as a new designated storage position before reading the next data from the first memory. and changing the ranking.