| 摘要 |
1492260 Data processing; information storage and retrieval INTERNATIONAL COMPUTERS Ltd 22 July 1975 [29 Oct 1974] 46651/74 Headings G4A and G4C A sequence of records, each comprising data items of a plurality of different types, is stored in a memory in a compressed form in which any data item of a given type which is repeated in consecutive records in the sequence is omitted from all but the first of those consecutive records, and the records are supplied in sequence to a processing unit which is arranged to retain the result of processing each record whereby that result may be carried over for use in deriving the result of processing subsequent consecutive records from which repeated data items have been omitted. The invention is described in the context of a system for performing associative search and retrieval operations on a data base stored in the memory. General description of system, Fig. 1.-The memory 1 comprises a set of disc file units S, M provided with single and multiple output channels, a plurality, (up to 12) of which are selected by a switching unit 2 and are time division multiplexed by a multiplexer 3 on to a common highway 4. The multiplexer adds channel numbers and physical addresses to indicate the origins of the data. The multiplexed data and associated control signals are supplied in parallel to a plurality (e.g. 16) of key comparison units 5 and to a retrieval unit 10. The comparison units 5 compare successive data items from each channel with a respective set of stored key values and may be notionally partitioned into groups each of which is allocated to a separate search task on the same data files. The partitioning of the comparison units into groups is determined by the manner in which the comparison results supplied by units 5 at the end of each record are combined in a search evaluation unit 7 which operates under control of stored microprogrammes to identify records which satisfy predetermined search criteria, such records being retrieved from a buffer in the retrieval unit 10 together with the associated physical addresses. The processing unit is under the overall control of a small scale control processor 8 which is in turn controlled by high level instructions from a main computer. The multiplexing of the data channels allows handling of the data by common control hardware which includes various random access memories which are addressed by channel number to retain comparison results and provide control information for the individual channels. Disc format.-Each track has 15 data areas DA each 384 bytes in length for example, and each preceded by a marker pattern CA of 9 bytes identifying the data area within the disc unit, e.g. by cylinder, head and count area. Each CA and DA is preceded by a preamble PA, fixed pattern address mark AM and a sync byte S which denotes CA or DA as appropriate, and is followed by two cyclic check bytes CC which are modulo 2 sums of an all ones byte with the odd and even numbered bytes of the CA or DA. A data file can be of any length ranging from part of a cylinder to a plurality of cylinders and if necessary may extend over several disc units. Record format.-Each record is divided into fields each having a type of field identifier I, e.g. significant part number, price; a length byte L indicating the total record length; and a variable length value portion V, the final field having an I value in the range 240-55 and a length byte L. Fields which are repeated in consecutive records after the first occurrence in the record sequence are omitted. A null field is included where a particular field does not occur in a record, null fields being notionally repeated by omission from subsequent consecutive records. To avoid having to start each scan of a data file from the beginning, pick-up points denoted by a special I byte are located at intervals throughout each file, the record following each pick-up point being recorded in full. Multiplexer, Figs. 4-6 (not shown).-In each channel input, overflow of a 4-bit byte counter is used to select a pair of 16 byte buffers (B1, B2) alternately for write-in and read-out, the byte counter supplying write-in addresses to the input receiving buffer and signalling a request to a channel selector when a buffer is full. Each channel input is controlled by a sequencer shift register (32) which is stepped by the byte counter in synchronism with the reception of the (CA)S, CA, (DA)S, DA and (DA)CC regions of a disc track. A channel number addressed RAM (401) is loaded by the control processor with next required CA value for each channel and the sequencer is reset if a CA does not match the stored CA so that any desired sequence of DA's can be selected independently for each channel. The channel selector includes a priority circuit which selects requesting channels in priority order and provides corresponding encoded channel numbers, and a counter and RAM (39) addressed by channel number provide the number GOB of 16 byte groups of bytes received on each channel, this number being used for detecting the end of the data area DA comprising 24 such groups and, together with the CA value specifying the physical address of the data. The (DA)S value is checked with a wired-in value for validity and the DA and CC bytes are accumulated separately for each channel with storage of intermediate results in a channel number addressed RAM (45), an error being indicated in the final result at the end of a DA is not zero. Comparison units.-Each unit comprises a mask store 229, Fig. 15 for selecting certain bytes from the stream supplied on highway 4 for comparison with key identifier and value bytes held in another store 230. The stores are addressed by a byte counter (119, Fig. 11, not shown) which is preset with a different datum value for each channel from a RAM (120) at the start of each field and is thereafter preset from another RAM (121) with the count at the end of the preceding group of bytes in the same field for that channel. The number of byte comparisons is determined by the L byte. If the I byte is matched, the result of the comparison (greater than, less than, or equal) of the value bytes is loaded into field latches 235, 236, 238, Fig. 16, for storage in a RAM 244 in an area appropriate to the channel being processed. In a normal mode in which non-compressed records are used, the states of the field latches are stored in RAM 244 at the end of each record. In the remember mode using compressed records, memory 244 is updated if one of the field latches is set, or is reset to zero if a null field has been detected. In a substitute search mode two data fields occurring in the same record can be compared with each other, e.g. to check current total expenditure with credit limit. The key stores 230 of two different comparison units are loaded with a respective one of the I bytes of the two fields to be compared. Detection of an I byte which matches the stored key in one of the units A causes the following value byte to be stored in the key store of the other comparison unit B. On detection of the I byte which matches the key I byte stored in unit B, the following value bytes are compared with the value byte previously stored in that unit as keys, the results being loaded into RAM 244 at the end of the record as in the other modes. Search evaluation unit.-This unit comprises 16 microprogrammed processing elements (one for each comparison unit) connected in a series chain or closed loop, a common quorum function unit which weights the outputs of the processing elements and compares the accumulated sum of the weighted outputs with a threshold value, a common select function unit for applying the output of a selected processing element as an input to all the processing elements, and a common control unit. Each processing element, Fig. 21 comprises a logic unit 307 with data inputs from the result memory of the associated comparison unit, the select function unit, the logic unit of the preceding processing element R(N-1), and its own results store S(N) 308. The logic unit, Fig. 22 (not shown), is controlled by sequences of 9 bit micro instructions from a control store 306 of that processing element to provide an output R(N) as follows:- Mode 1: R(N)=X, S(N), S(N).X, or S(N)+X, where X = OR function of the comparison result inputs and the exact nature of which is determined by the micro instruction and may include the SELECT input. Mode 2: R(N) = S(N), R(N-1), S(N).R(N-1), or S(N) + R(N-1) as selected by the micro instruction. R(N) may be loaded into the result store 308 and the S(N) input to the logic unit may be inverted. The combined contents of the result stores 308 indicate satisfaction or otherwise of the search criteria and is used for selection of the required records by the retrieval unit. The control unit includes a RAM addressed by channel number, each location storing a start address of the micro instruction sequence for the corresponding channel and the length of the sequence. The RAM output is loaded into a pair of counters which are respectively incremented and decremented to provide micro instruction addresses and to signal the end of the evaluation procedure to the retrieval unit. The quorum function unit includes a RAM addressed by the micro instruction addresses to first load a threshold value into a register and then to read out successive weight values, e.g. 0 to 1 for application to respective processing element result store values S(0)-S(15). A comparator signals when the accumulated weighted values exceeds the threshold. The selection function unit includes a RAM addressed by the micro instruction addresses and the output of which is decoded to select one of S(0)-S(15) or QUORUM as a broadcast input SELECT to the processing elements. Modifications.-The alternately selected channel input buffers can be replaced by a first in first out store and the comparison units can be arranged to ter |
