RU2037215C1 - Storage device - Google Patents

Abstract

FIELD: computer engineering. SUBSTANCE: storage device has main storage, control unit, polling code register; newly introduced are additional storage unit, data pattern type register, output switch, group of AND circuits. Main storage has read unit, write unit, input and output registers, integrator incorporating storage locations. EFFECT: improved reliability of device. 2 cl, 5 dwg

Description

 The invention relates to computer technology and can be used to build memory for storing, writing and reading both simple (scalar, vector, vector element, etc.) and complex data structures (tree, network, tuple, etc.) ) in computers of various classes.

 A memory device [1] is known for recording information in a drive and simultaneously reading several words, which in the general case suggests the possibility of its use for storing complex data structures. However, this device has limited functionality, high hardware costs and low speed, when used for recording, storage and simultaneous issuance of several, for example, m words.

 While reading m words (in this case, it is necessary to read information from m memory cells), the device must have m groups of decoders of read addresses, m groups of registers of read addresses, respectively m of registers of read data and a complicated circuit of the address comparison unit, which generally leads to high hardware costs. In addition, the simultaneous presence of m words when reading information requires an increase in the total number of memory cells (compared with the memory where one word is stored) by m times, which accordingly increases the length of the bit buses inside the matrix of memory cells and thereby reduces the speed of the device.

 Moreover, recording m words requires the implementation of m recording cycles, which leads to a low equivalent speed of the device in recording mode.

 A memory device [2] is known for orderly storage, recording and delivery of information on a non-address basis, containing memory cells, each of which for storing one bit contains primary and secondary memory elements, seven AND elements, four OR elements, two delay elements, and eight AND elements, one OR element, which are combined into groups designed to control the reading and recording order of information.

 Information is recorded in such a device in two modes ("Top Down" and "Bottom Up") in the first free cell, and reading in four modes: "Shop", "Bobsleigh", "Inverted Shop", "Inverted Bobsleigh".

 The disadvantage of this device is the great complexity of the drive due to the need to use double memory elements for a single bit, a large number of AND elements, OR elements, delay circuits, which is unacceptable for constructing a memory that stores complex data structures, since the number of bits of such memory is large and amounts to several dozen bits. Moreover, due to the presence of a significant number of these elements for realizing access to the memory elements, the speed of such memory and the useful information capacity of the drive implemented on the LSI cannot be ensured high.

 In addition, both considered devices do not provide hardware support for working with complex data structures (tuple, tree, network, etc.), i.e., the functionality of these devices is very limited.

 A memory device is known for recording, storing and reading packets of information consisting of m fields (words). The specified device is adopted as a prototype. The device contains a reading unit, a writing unit, input and output data registers, a control unit, a drive, each cell of which contains registers from first to fourth, first and second comparison nodes, the first and second elements "OR", the element "AND", the first and the second nodes of the formation and storage of flags.

 These structural elements are interconnected by appropriate bonds. In this case, the information inputs of the respective registers of all the cells of the drive are combined and connected respectively with the outputs of the first, third, fifth and sixth groups of the input data register, the information inputs of which are the inputs of the same name. The synchronization input of the input data register is connected to the first output of the control unit, and the first outputs of the corresponding registers of the cells of the drive are combined and connected respectively to the information inputs of the first, third, fifth and sixth groups of the output data register, the outputs of which are information outputs of the device. The synchronization input of the output data register is connected to the second output of the control unit. The outputs of the recording unit are connected to the first inputs of the job mode corresponding to the registers of the cells of the drive, and the outputs of the read unit are connected to the second inputs of the job mode of the corresponding cell registers of the drive.

 The first inputs of the job mode nodes of the formation and storage of flags are connected to the corresponding outputs of the recording unit. The second inputs of the job mode nodes of the formation and storage of drive cells are connected to the corresponding outputs of the reading unit. The information inputs of the nodes of the formation and storage of flags of the cells of the drive are combined and connected respectively to the outputs of the second and fourth groups of the input data register. The first outputs of the corresponding nodes of the formation and storage of flags of the cells of the drive are combined and connected respectively to the information inputs of the second and fourth groups of the output data register. The second outputs of the first and second registers of the cells of the drive are connected to the first inputs of the corresponding comparison nodes. In this case, the second inputs of the first nodes of comparison of drive cells are combined and are the inputs of the first group of device polling, and the output of the first comparison node of each drive cell is connected to the first input of the first OR element, the second input of which is connected to the second output of the first node of the formation and storage of flags, the third input setting the mode of which is connected to the output of the first OR element and the first input of the AND element of each storage cell. The outputs of the elements And of each cell of the drive are connected to the corresponding inputs of the reading unit. The second inputs of the second nodes comparing the cells of the drive are combined and are the inputs of the second group of the survey device. The output of the second comparison node of each drive cell is connected to the first input of the second OR element, the second input of which is connected to the second output of the second flag generation and storage unit, the third input of the mode setting of which is connected to the output of the second OR element and the second input of the AND element of each drive cell.

 The outputs of the reading unit are connected to the corresponding recording permission inputs of the recording unit, the write request input of which is connected to the third output of the control unit, the fourth output of which is connected to the read request input of the read unit, the read request output of which is connected to the first control input of the control unit, the second control input of which connected to the output of the write request of the recording unit. The inputs and outputs of the control unit are the inputs and outputs of the interface signals of the device.

 The prototype device has high speed and provides when reading an associative search by key (or two keys) of an information package containing several fields, as well as automatic search for free memory cells when writing.

 However, the prototype device has negligible functionality, realizing only the read and write modes of one word with two attribute fields and one data field. Moreover, the prototype device does not provide hardware support for algorithms of access to complex data structures (such as a tuple, tree, network, etc.), which is very important for ensuring high performance computers where this memory is used. In addition, the prototype device does not have the functionality that provides hardware support for the "dense" packaging of information in the drive and the allocation of memory resources.

 The aim of the invention is to expand the scope by expanding the functionality of the device providing hardware support for working with complex data structures.

 A positive effect is achieved by the fact that in the storage device containing a memory unit, a polling code register, a control unit, a register unit, a data structure register and an output switch are connected to each other and the above-mentioned elements with new connections. The outputs of the polling code register are connected to the corresponding polling inputs of the memory block, the first synchronization input is connected to the eighth output of the control unit, the ninth output of which is connected to the second synchronization input of the memory block. The fourth output of the control unit is connected to the input of the write request of the memory unit, the first and second control inputs of which are connected to the fifth and sixth outputs of the control unit, respectively, the seventh output of which is connected to the input of the read request of the memory unit. The tenth output of the control unit is connected to the control input of the polling code register, the information inputs of the first group of which are inputs of the polling code of the device. The information inputs of the memory block are the data inputs of the device. The information inputs of the switch are connected to the information outputs of the memory unit, the control input is with the third output of the control unit, and the information outputs of the first group are information outputs of the device, the information outputs of the second group with information inputs of the second group of the control unit, the information inputs of the first group of which are connected to the outputs of the block group registers, the output of which is connected to the first control input of the control unit, the first and second outputs of which are connected respectively to read-write and register block mode, the information inputs of which are connected to the outputs of the third group of the output switch.

 The second and third control inputs of the control unit are connected to the overflow outputs when recording and the end of the polling of the memory block, the inputs of the data structure type of which are connected to the outputs of the data structure register, the information inputs of which are code type inputs of the device data structure, and the synchronization input is connected to the twelfth output of the block control, the eleventh output of which is connected to the information inputs of the second group of polling code registers. The control inputs and outputs of the control unit are the inputs and outputs of the device.

 In this case, the memory block contains input and output registers, write and read blocks, a group of AND elements, and a drive, the information inputs and outputs of which are connected respectively to the outputs of the input register and information inputs of the output register, the synchronization inputs of which are the first and second synchronization inputs of the block. The inputs and outputs of the output registers are respectively the information inputs and outputs of the block. The outputs of the group of the reading block are connected to the corresponding first inputs of the elements AND groups, the second inputs of which are combined and are the first control input of the block. The outputs of the elements AND groups are connected to the inputs of the group of the recording block, the inputs of which are the inputs of the request to write the block, the output is the overflow output when recording the block. The outputs of the group of the recording block are connected to the corresponding recording inputs of the drive, the read outs of which are connected to the inputs of the group of the reading block, the input and output of which are respectively the input of the read request and the output end of the block polling. The inputs of the type of data structure and polling are respectively the inputs of codes of the type of data structure and polling of the block. The drive control input is the second control input of the unit. The memory unit contains a reading unit, which includes reading nodes, a recording unit, which includes recording nodes, an input register, an output register, a drive containing memory cells.

 In each memory cell containing the first to fourth registers, the comparison schemes from the first to the third, a data structure type identification node, an AND circuit, and a body identification element of the data structure element are introduced. The first inputs of the comparison circuits are connected to the first outputs of the corresponding registers from the first to the third, and the second inputs of the comparison circuits of all the memory cells of the drive are connected in columns and connected to the corresponding polling inputs of the memory block. The first control inputs of the registers from the first to the fourth of each memory cell are interconnected and connected to the corresponding recording outputs of the recording unit. The input of the write request signal and the output of the overflow signal when recording the recording unit are connected to the corresponding inputs and output of the memory unit of the same name. The second control inputs of the registers from the first to the fourth of each memory cell are interconnected and connected to the corresponding read outputs of the read block. The input of the read request signal and the output of the end of the poll signal when reading the reading unit are connected to the corresponding input and output of the memory unit of the same name. The second outputs of the corresponding registers from the first to the third and the outputs of the register of the fourth of all memory cells are combined in columns and connected respectively to the information outputs of the first to fourth groups of the drive block.

 The information inputs of the corresponding registers from the first to the fourth of all cells of the drive are grouped in columns and connected respectively to the inputs of the first to fourth groups of the drive unit. Moreover, the outputs of the first to third comparison circuits are connected to the inputs of the first group of the identification node of the type of data structures. The inputs of the second group with the same name of all identification nodes of the data structure type are combined and connected to the inputs of the data structure type of the memory unit 1. The outputs of the identification node of the data structure type of each memory cell are connected to the corresponding inputs of the AND circuit, the output of which is connected to the first input of the identification node of the body of the data structure, the second input of which is connected to the first control input of the register from the first to the fourth. The third inputs of all the body identification nodes of the drive data structure are combined and connected to the control input (body-element signal) of the drive unit. The outputs of the body identification nodes of the data structure are connected to the corresponding outputs of the drive unit.

 The proposed device does not reduce the positive features of the prototype device (high speed when performing read and write operations). However, compared with it, the proposed storage device has wide functionality, providing hardware support for efficient work with complex data structures. Moreover, the introduced structural elements are quite sufficient so that, if necessary, the set of functions realized by the storage device can be expanded. This is achieved due to the fact that the proposed device provides an effective implementation of the so-called basic operations, and the sequence of actions when writing and reading complex data structures is ensured by the sequence (firmware, program) of basic operations. Moreover, this sequence can be entered into the control unit of the device both knowingly and during its operation.

 In FIG. 1 shows a diagram of a storage device; in FIG. 2 circuit block memory. The device (Fig. 1) contains a memory block 1, a register block 2, an output switch 3, a polling code register 4, a data structure register 5, a control unit 6, input 7 and output 8 data buses, a polling code bus 9, a structure code bus 10 data bus 11 input-output interface control signals. The outputs of the register 4 of the polling code are connected to the corresponding polling inputs of the memory unit 1, the first synchronization input of which is connected to the eighth output of the control unit 6, the ninth output of which is connected to the second synchronization input of the memory unit 1. The fourth output of the control unit 6 is connected to the write request input of the memory unit 1, the first and second control inputs of which are connected to the fifth and sixth outputs of the control unit 6, respectively, the seventh output of which is connected to the read request input of the memory unit 1. The tenth output of the control unit 6 is connected to the control input of the polling code register 4, the information inputs of the first group of which are inputs of the device polling code and are connected to the polling code bus 9. The information inputs of the memory unit 1 are the data inputs of the device and are connected to the input data bus 7. The information inputs of the output switch 3 are connected to the information outputs of the memory unit 1, the control input is from the third output of the control unit 6, and the information outputs of the first group are information outputs of the device and are connected to the bus 8. Information outputs of the second group of switch 3 are connected to the information inputs of the second group of the block 6 control, the information inputs of the first group of which are connected to the outputs of the group of the block 2 registers, the output of which is connected to the first control input of the control unit 6, he first and second outputs which are respectively connected to the inputs of read-write registers and 2 block mode, data inputs of which are connected to the outputs of the third group of output switch 3.

 The second and third control inputs of the control unit 6 are connected to the overflow outputs when recording and the end of the polling of the memory unit 1, the inputs of the data structure type of which are connected to the outputs of the data structure register 5, the information inputs of which are the code type inputs of the device data structure and are connected to the bus 10, and the synchronization input of the register 5 is connected to the twelfth output of the control unit 6, the eleventh output of which is connected to the information inputs of the second group of the register code 4 of the polling code. The control inputs and outputs of the control unit 6 are the inputs and outputs of the device, which are connected to the bus 11. The memory unit 1 (Fig. 2) contains input 16 and output 17 registers, write and read blocks 12, a group of elements 20 AND, and a drive 18, the information inputs and outputs of which are connected respectively with the outputs of the input register 16 and the information inputs of the output register 17, the synchronization inputs of which are the first and second synchronization inputs of the memory unit 1. The inputs of the input 16 and outputs of the output 17 registers are respectively the information inputs and outputs of the block. The outputs of the group of the reading unit 12 are connected to the corresponding first inputs of the elements And 20 of the group, the second inputs of which are combined and are the first control input of the memory unit 1, the outputs of the elements And 20 of the group are connected to the inputs of the group of the recording unit 14, the inputs of which are the inputs of the request to write the block, the output overflow output when writing a block. The outputs of the group of the recording unit 14 are connected to the corresponding recording inputs of the drive 18, the read outs of which are connected to the inputs of the group of the reading unit 12, the input and output of which are respectively the input of the read request and the output end of the block polling, the inputs of the data structure type and the polling are respectively the inputs of codes of the type data structures and block polling. The drive control input is the second control input of the unit.

 Each memory cell 19 contains (Fig. 2) registers 21 from first to fourth, comparison circuits 22 from first to third, the first inputs of which are connected to the first outputs of the corresponding registers 21 from first to third. The second inputs of the comparison circuits 22 of all memory cells 19 of the drive 18 are connected in columns and connected to the corresponding polling inputs of the memory unit 1. The first control inputs of the registers 21 from the first to the fourth of each memory cell 19 are interconnected and connected to the corresponding outputs of the recording unit 14 records. The second control inputs of the registers 21 from the first to the fourth of each memory cell 19 are interconnected and connected to the corresponding read outputs of the reading unit 12. The second outputs of the corresponding registers 21 from the first to the third and the outputs of the register 21 of the fourth of all memory cells 19 are connected in columns and connected respectively to the information outputs from the first to fourth groups of the drive unit 18. At the same time, the information inputs of the corresponding registers 21 from the first to fourth of all cells 19 drive are combined in columns and connected respectively to the inputs of the first to fourth groups of drive unit 18.

 Each memory cell of the drive (Fig. 2) also contains a node 23 identifying the type of data structure, the circuit And 24 and the node 25 identification of the body-element of the data structure. The outputs of the comparison circuits 22 from the first to the third are connected to the inputs of the first group of the node 23 of the identification of the type of data structure. The same inputs of the second group of all nodes 23 identification type data structure are combined and connected to the corresponding inputs of the type of data structure of the memory unit 1. The outputs of the data structure type identification node 23 of each memory cell are connected to the corresponding inputs of the AND circuit 24, the output of which is connected to the first input of the data structure body identification node 25, the second input of which is connected to the first control input of the registers 21 from the first to the fourth. The third inputs of all nodes 25 identification of the body of the data structure of the drive 18 are combined and connected to the signal input of the body-element of the memory unit 1. The outputs of the nodes 25 identification of the body of the data structure are connected to the corresponding reading outputs of the drive unit 18.

 The technical implementation of each component component of the storage device does not cause any difficulties. So block 1 memory (Fig. 2) can be implemented in the form of one or more large integrated circuits (LSI), made by modern technology. Moreover, as in the prototype device, the drive unit 18 (Fig. 2) is regular and contains typical registers 21 constructed according to the classical scheme with the corresponding recording inputs and inputs of the recording permission signal, as well as outputs for issuing information with corresponding inputs permission signal issuance.

 The data structure identification node 23 is a logic circuit, for example, executed on three two-input OR circuits, the first inputs of which receive signals from the outputs of the matching circuits 22, and the second signals of a code of the type of the data structure. Moreover, if one of the code signals of the data structure type is represented by a logical "unit", then the corresponding signal from the output of the matching circuit 22 is ignored. This eliminates the need to compare the contents of the corresponding register with the interrogation code when reading information.

 Similarly, the node 25 (Fig. 2) of identifying the body of the data structure is a logic circuit made using the simplest logic circuits.

 The reading unit 12 and the writing unit 14 are identical to the corresponding reading and writing blocks of the prototype device and respectively comprise reading nodes 13 and recording nodes 15 in the number of memory cells 19 of the drive. Moreover, each of these nodes 13 and 15 contains a trigger circuit and circuits And, connected by appropriate connections, which from the point of view of practical implementation of these blocks is not difficult.

 Block 2 registers is a memory with service disciplines FIFO ("first come first served") or LIFO ("first come last served") and can be implemented according to well-known principles for constructing a buffer memory with these service disciplines (US Pat. No. 4,805,139, cl G 11 C 7/00, 19/00, 19/28, 1989).

 The output switch 3 is actually a demultiplexer for three directions of data structure elements coming from the outputs of the drive 18 of the memory unit 1. In this case, the choice of the direction of transmission of the switched information is determined by the code of the control word coming from the corresponding outputs of the control unit 6. The output switch 3 can be performed on standard logic elements, and its practical implementation is not difficult.

 The register of the polling code 4 and the code register of the data structure 5 (Fig. 1) are classic trigger registers that receive from one (two) direction and output one-way information when there are corresponding control signals coming from the control unit 6. Practical implementation of these registers does not cause difficulties.

 The control unit 6 is a microprogram (or hard) machine designed to analyze, generate and issue control signals that determine the implementation of the above basic operations and based on them algorithms for working with complex data structures. It can be implemented according to well-known classical principles both in the form of a custom-made LSI and on a well-known element base.

 The bus 11 of the input-output interface control signals is designed to communicate on the control signals of the proposed memory with the processing system and contains a transmission line of the signal for accessing the memory, a transmission line of the type of the operation being implemented (read-write), a code transmission line of a variation of the implemented operation of each type (for example, reading with or without destruction, reading an element, a tuple, a tree, a network, etc.), as well as transmission lines for other signals necessary for the coordinated interaction of the memory and processing system (line I have a memory busy signal, signal the end of the line reading cycle, and so on. d.).

 The proposed storage device (memory) operates as follows. The device records, stores and retrieves various data structures of the type: scalar, vector, array, list, tree, network, tuple, matrix, or their components: list element, network element, branch, tree node, tuple element, element (column , row) matrices, etc. The storage device is also focused on recording, storing and issuing the body of the data structure, which is a byte packing (chain) of information with one common name.

In general, the data presentation format contains 4 fields (3 fields for attribute attributes and 1 data field): name fields, two fields of pointers (indices) and one field of this. In accordance with this, the formats of these data structures are as follows:
scalar (SK): And _sk , ⌀, ⌀ D;
vector (B) And _c , J, ⌀, D; (J 1, l)
matrix (M): And _m , J ₁ , J ₂ , D; (J ₁ 1, m; J ₂ 1, n); (array)
list (Cn): And _cn , CC _is , ⌀, T _cn ;
tree (D): And _d , UK1 _is , UK2 _is , T _cn ;
tree (D): And _d , UKI _is , UK2 _is , T _d ;
network (St): And _Art . UKI _in , _{UK2 in} , T _st ;
tuple (K): N _k , U _p , ⌀, T _k ,
where the body (T): U _t , D ₁ , D _i , D _s ;
And the name of the corresponding data structure; UK _IS , UK _IH pointer outgoing and incoming, respectively; N _{to the} number of the tuple;
And _{n is the} name of the position field; ⌀ empty (no information); D data; l the number of components of the vector; m, n the number of elements in the column and in the row of the matrix, respectively; S is the total number of bytes in the body of the data structure.

 In accordance with this, registers 21 are provided for storing the indicated data structures in each cell 19 of the memory block drive (from left to right in Fig. 2 from the first to the fourth). In this case, the first register 21 on the left is for storing the name code, the next two (second and third) for storing the codes of two pointers (indices) and the fourth register 21 is for storing the data code.

 The work of the memory is based on the addressless placement of information in the associative drive 18 (Fig. 2) with the corresponding attribute fields containing polling codes and codes of the data structure type, which determine which field codes are used for associative polling.

 When accessing data structures such as a scalar, vector, array (matrix), complex algorithms are not required. Moreover, according to the results of an associative search, a plurality of data stored in the drive 18 can be detected, which the memory gives out from the drive in a certain sequence. This sequence can generally be arbitrary, but the presence of indices in these structures allows further identification of the read structure elements. Moreover, the output from the device can be carried out with the destruction or preservation of the read information. To do this, use the delete signal (Fig. 1, 2).

 The end of the reading process of the entire sequence of the data set identified by the interrogation code is fixed by the “End of interrogation” signal, which is generated by the reading unit 12 and fed to the third control input of the control unit 6 (Fig. 1).

 The end of the recording process in the drive 18 (there is not a single free memory cell 19) is recorded by the "Overflow when writing" signal, which is generated by the recording unit 14 and fed to the second control input of the control unit 6. The circuits for generating these signals are similar to the generating circuits in the prototype device.

Consider the operation of the memory system when performing the following set of basic operations of writing, reading and scanning (bypassing the elements of the data structure according to a certain law):
writing a data structure element;
body record of data structure;
reading an element of the data structure (or a set of elements) without destruction;
reading an element of the data structure (or a set of elements) with destruction;
reading the body of the data structure without destruction;
reading the body of the data structure with destruction.

Based on these basic operations, algorithms for writing complex data structures to memory unit 1, as well as access algorithms to them, are generated. These algorithms are presented in the form of microprograms (programs), which are located in the control unit 6 of the memory system and provide:
writing, reading tuples, lists, trees, networks and working with them;
refinement (adjustment) of data structures;
growing graphs.

 Record of elements (body) of the data structure.

 Recording mode. The block diagram of the recording mode implementation algorithm (basic operation) is shown in FIG. 3, where control signals generated by the control unit for performing the indicated functions are respectively displayed. We first consider the case when the drive of the memory unit 1 does not contain information, i.e., the state of the device itself, for example, after turning on the power source. The reset signal (in Fig. 1 and 2, the reset circuit is not shown) translates to the initial ("zero") state all the trigger circuits of the memory unit 1 (read unit 12, Fig. 2, write unit 14, input 16 and output 17 registers), block 2 registers, register polling code 4, register data structure 5, as well as trigger circuits of the control unit 6.

 After that, along the corresponding lines of the input-output bus of the interface control signals (Fig. 1), the signal “Access to the memory and the signal“ Record "is applied. At the same time, a word containing the recordable element is supplied via the input data buses 7. The structure of the drive 18 and the operating algorithm of the storage devices in the recording mode is constructed in such a way that recording is carried out simultaneously in all four registers 21 of the selected cell of the drive 18, regardless of what kind of write operation is implemented (recording an element or body of the data structure) for any type of data structure (tuple tree network and t. d.).

 However, if a data structure element is recorded, a signal (for example, a high level) indicating a record of the element is set on the corresponding line of the bus 11. If the body of the data structure is recorded, then a signal (low level) indicating the recording of the body of the data structure is set on the same bus line 11. In this case, the recording sequence of the structural elements that make up the vector, matrix, tree or any other complex structure is assigned to an external (in relation to the memory) system, for example, a processing system.

 If there are control signals and data on buses 11 and 7, the control unit 6 generates the following signals at the respective outputs: "Write request", the "Body-element" signal, as well as the synchronization signal of the input register 16 of the memory unit 1 (Fig. 1), which, entering the control input of the register 16, allows the transmission of the word code from the input data bus 7 through the corresponding inputs of the drive 18, to the input register 16, where this word code is stored. From the outputs of this register 16, the word code signals are fed to the information inputs of all four registers 21 of the memory cells 19 of the drive 18 (Fig. 2).

 At the same time, the write request signal, arriving at the corresponding input of the recording unit 14 of the memory unit 1, initiates the first recording unit 15 from above (Fig. 2), which generates a recording permission signal that passes through the corresponding input of the drive 18 to the first control inputs of all four cell registers 21 memory 19, thereby realizing a record in registers 21 of the word codes located on the information inputs of these registers.

 At the same time, the write enable signal is supplied to the second input of the data structure body identifier node 25 (Fig. 2), thereby preparing the node 25 for receiving the body-element signal. Moreover, if the “body” of the data structure is recorded, the “body-element” signal (high level) generated by the control unit 6, arriving at the corresponding input of this node 25, is stored in it for the duration of storage of the entire recorded word in the registers 21 ( Fig. 2). If the data structure element is recorded, the body-element signal is not generated by the control unit 6, and is not stored in the node 25. It should be noted: that the body structure identification node 25 of the data structure is present in each cell 19 of the drive 18, and information is recorded in it at the same time as writing the code of the whole word in the registers 21 of the memory cell 19 of the drive 18.

 The recording unit 15, as well as in the prototype device, is constructed in such a way that when the drive 18 is full, the first word is always recorded automatically in the first (top) memory location 19, the second word in the second, etc. This is done due to that the 1st recording node 15 (after completing the first recording cycle) blocks its output signal generation circuit and switches the recording request signal to initialize the subsequent (second from the top) recording node. A similar process occurs when writing the word code into the second, third from above and subsequent memory cells 19.

 In the same way, the word code is recorded in an arbitrary free memory cell 19 located anywhere (with respect to other cells) of the drive 18. In this case, the recording nodes 15 corresponding to the occupied memory cells switch the write request signal to the subsequent recording nodes (from top to bottom) until the first free memory cell 19 appears, and then the corresponding recording unit 15 is initialized with this signal. Then, when recording the next word, the write request signal likewise initializes the recording unit 15, which belongs to the next available free memory cell, and so on, until all free memory cells are occupied. Then, when the next write request signal is fed to the input of the recording unit 14, this signal “skips” all the blocked recording units 15 and, as an overflow signal, is recorded through the corresponding output of the unit 14 to the input of the control unit 6 of the same name, thereby preventing the possibility of information loss during records.

 Reading mode. Reading an element (body) of data structures.

 The block diagram of the algorithm for implementing the reading mode is shown in FIG. 4, where the control signals generated by the control unit 6 for performing these functions are respectively displayed.

 To perform a read operation, the signal “Access” to the memory system, the “Read” signal, as well as the corresponding control word code indicating one of the six types of read operations indicated above, for example, reading a structure element, are sent to the corresponding inputs of the control unit 6 via bus 11 data (or a set of elements) without destruction.

 At the same time, a data structure type code is supplied to the inputs of register 5 via bus 10, which determines, depending on the type of data structure, the use of the first three fields of the word code (recorded in registers 21) when associatively searching for the requested information by the values of the polling key codes that are fed to the inputs of register 4 on bus 9.

The control unit 6 upon receipt of signals via the bus 11 generates at its outputs the following set of control signals in a certain sequence:
"Read request", arriving at the same input of the memory unit 1 (Fig. 1, 2);
"Deletion" (low level) supplied to the first control input of the memory unit 1 and preventing the destruction of the contents of the selected memory cell 19 of the drive 18 (Fig. 2);
a control signal for entering the polling code coming from the tenth output of the control unit 6 to the control input of the polling code register 4 (Fig. 1);
a control signal for entering the read word code from the drive 18 (Fig. 2) to the output register 17 of this drive coming from the ninth output of the control unit 6 to the second synchronization input of the memory unit 1 (Fig. 1);
control signals of the output switch 3 coming from the third output of the control unit 6 to the control inputs of the output switch 3.

In the presence of these control signals generated by the control unit 6, a code such as a data structure on bus 10 is entered into register 5, and a polling code on bus 9 is stored in register 4 (Fig. 1). The signals from the outputs of these registers are supplied to the corresponding inputs of the same name block 1 memory. In this case, the interrogation codes of the first three fields of the data structure arrive in parallel along the column to the second inputs of the comparison circuits 22 of all memory cells 19 of the drive 18. The first inputs of the same comparison circuits 22 receive codes that are respectively in the first registers 21 (for the first field of the word code ), in the second registers 21 (for the second field of the word code) and in the third registers 21 (for the third field of the word code) of all memory cells 19 of the drive 18. In that memory cell 19, where the code on the first inputs of the comparison circuit 22 coincides with the polling code at her second entrances, and the output of the comparison circuit 22 produces a signal which is fed to a first group of input node 23 identifying data structures. In this case, there may be cases where the coincidence of the codes on the first and second inputs of the comparison circuits 22 can occur both for one, and for two or three comparison circuits 22 inside the memory cell 19, which means that in the general case on the first group of inputs of the node 23 one, two or three match signals may be present. Such a situation may occur for one or many memory cells 19 of drive 18. However, the node 23 will only respond to those matching signals at its inputs of the first group that will not be blocked by the corresponding codes such as data structures arriving at the inputs of the second group of the node 23 of each cell memory 19 of drive 18 (Fig. 2). Codes of data structures are determined by the principles of construction and the logic of functioning of the circuit of node 25 and, for example, for the following data structures can be of the form:
Name Formal Type Code
structures (ele-
cops data structure
data data tours
Scalar I _ck , ⌀, ⌀, Д 0 1 1
Vector (element
vectors) U _in , I, ⌀, Д 0 0 1
Matrix (ele
matrix matrix) U _m , I ₁ , I ₂ , D 0 0 0
Matrix column "0 1 0
Matrix row "0 0 1
Tree, network, etc. U _D , UK ₁ , UK ₂ , T _c 0 0 0 (with additional sign)
According to the accepted principle of constructing a node 25 for the indicated codes of the type of data structures, the code bit position number corresponds to the data structure field number from left to right, and the code bit value equal to "1" means that the signal for the field code (under this number) coinciding with the polling code is blocked and is not taken into account in associative searches.

 Thus, when reading the scalar, the contents of only the first registers 21 of all memory cells 19 are compared with the polling code received at the second inputs of the comparison circuits 22 of only the first (left) column of all the circuits (Fig. 2) of the drive.

 When they coincide, the output of the circuit 22 of a particular memory cell 19 gives a signal that goes to the first group of inputs of the node 23. In accordance with the specified value of codes such as a data structure at the inputs of the second group of the node 23 (scalar), the signals at all other inputs of the first group of this node are blocked, and the node 23 gives out at its outputs signals that match in value at the inputs of the circuit And 24. The received signal matches the outputs of the circuit And 24 goes to the first input of the node 25 identifying the body of the data structure. Since in the selected memory cell 19 there is an element (scalar), and not the body of the data structure, when writing the whole word, the attribute of the body of the data structure in node 25 of the selected memory cell was not recorded. Therefore, the signal from the output of the And 24 circuit without logical transformations passes through the node 25 and, from its output, as a read permission signal, goes to the reading input of the same name of the corresponding node 13 of the reading block 12, preparing it for generating the read signal.

 The signal "Read request", coming from the corresponding output of the control unit 6 to the same input of the memory unit 1 (Fig. 1) and, respectively, of the drive 18 (Fig. 2), starts the corresponding read node 13 of the read unit 12 prepared by the read permission signal. generates a read signal at its output, which is fed to the first input of AND circuit 20, which belongs to the selected memory cell 19, as well as to the second control inputs from the first to the fourth registers 21, providing information from these registers to the corresponding groups in output register odov Jan. 17 of the storage unit (FIG. 2). If there is a synchronization signal at the control input of register 17 coming from the second synchronization input of block 1, all the read information from the registers 21 of the selected memory cell 19 is stored on this register. From the outputs of the register 17, all word codes are fed to the information inputs of the output switch 3.

 At the same time, since a simple element of the data structure is read (such as a scalar, vector), the signal at the control input of the output switch 3 configures this switch to transmit the entire read word code from the memory unit 1 through the information outputs of the first group to the output data bus 8.

 Moreover, if the data structure element is read without being destroyed, then, as was mentioned above, the control unit 6 generates a “Delete” signal with a low level (Fig. 1), which, arriving at the first control input of memory unit 1 and at the first inputs of all circuits AND 20 (Fig. 2), blocks the passage of the read signal through the corresponding circuit And 20, at the input of the write permission of the recording unit 14 and the corresponding recording unit 15 belonging to the selected memory cell. Thus, this recording node 15 is not prepared for initialization by the write request signal, and the write request signal in the write cycle “skips” through this node 15 to the input of the next node of the recording unit 14. Thus, the recording of new information in the memory cell from which it was read, does not occur, that is, the old information is stored.

 If the information is read with destruction, then the control unit 6, by the signal of the control word code coming on the bus 11 and indicating the type of reading mode, generates a "Delete" signal (high level) at the corresponding output. This signal, passing through the first control input of the memory unit 1 to the first inputs of the AND circuits 20 of the drive 18, allows the read signals to pass from the output of the node 13 of the read unit 12 (Fig. 2) of the selected memory cell to the input of the corresponding recording unit of the write unit 14, thereby preparing this node itself 15 for its triggering by a write request signal and, therefore, for recording new information in this memory cell. The read information is not stored, and the registers 21 of the selected memory cell are reset.

 It should be emphasized that the storage or destruction of information during reading can be implemented in the proposed storage device, regardless of whether the element or body of the data structure is read, a simple data structure (scalar, vector, etc.) or a complex data structure (tree, network , tuple, etc.). To do this, it is only necessary that the control unit 6, depending on the type of reading mode, produce a “Delete” signal at a corresponding output low or high.

 Reading the body of the data structure (with or without destruction) from the memory unit 1 is carried out similarly to reading a simple data structure, for example, a scalar. The only difference is that the code 0 1 1 is supplied to the second group of inputs of the data structure type identification node 23, which, together with an additional feature (which is a body sign entered in the recording unit 25), provides the first memory node 25 of the selected memory cell read permission signal.

 Based on the basic operations discussed above, reading or writing complex data structures (tree, network, tuple, etc.) in the form of an algorithmic sequence of basic operations can be implemented. Moreover, the implementation of calls is carried out according to the appropriate programs (microprograms), which can be placed either from a special memory located in the control unit 6, or implemented in this unit 6 in the form of a hard machine.

 This is because the information body of complex data structures, as a rule, cannot be placed in the fourth field (fourth register 21) allocated for this word format (for example, when recording a character string of arbitrary length or a constant with double precision, etc. ) In this case, a special type of placement of a complex data structure in drive 18 is used: the global name of the complex data structure is placed in the first field (in the first register on the left in Fig. 2, register 21), and the information body in all other fields (in the second, third and fourth registers 21) with byte packing. Using the identification node 23, it is possible to block coincidence signals from the second and third fields of drive cells during associative comparison with polling keys, while the code space of the body name does not intersect with the code space of the first fields of data structure elements due to the use of an additional feature of the data structure body recorded in node 25 (Fig. 2).

We will consider reading complex data structures using the example of reading a tuple, the structure of which has the form N _k , U _k , ⌀, T _k .

 The block diagram of the implementation of reading complex data structures is shown in FIG. 5.

 The sequence of calls to the storage device for reading a tuple is determined (as was indicated above) by a program external to the memory, implemented, for example, by a processor.

First, by the global number N _{to the} tuple, the "head" of the tuple is found in the memory unit 1. To do this, they implement the basic operation of reading a scalar-type data structure element by associative polling by key, which is a tuple number code N _k . According to this code, in the drive 18 (Fig. 2), a plurality of memory cells 19, constituting a tuple, each cell with its own position number U _to “respond”. The contents of these memory cells are sequentially read in exactly the same way as the basic scalar reading operation is implemented, except that the read information (position numbers U _к ) is transmitted through the third and second groups of outputs of the output switch to the information inputs of the block 2 registers and to the information inputs of the second group of the block control 6. In this case, control unit 6, if there are corresponding control signals on the bus 11 ("Access", "Read", etc.), generates control signal of switch 3 at the third output, and to other outputs the necessary set of control signals that ensure the implementation of the above basic operations of reading information by key from the memory unit 1, as well as a recording signal and a mode selection signal received at the corresponding inputs of the same block 2 registers (figure 1) to write numbers into it ( names) of the positions U _{to the} tuple coming from the third group of outputs of the switch 3.

Then, by the names of the positions U _k located in the block 2 of the registers, a plurality of cells 19 of the drive 18 are searched for, in which the recording bodies T _k are placed in the form of byte packing of character strings.

For this, in its own program (microprogram), the control unit 6 generates on the corresponding first and second outputs a sequence of control signals "Read" and "Mode Selection", which, when fed to the corresponding inputs of the block 2 registers, implement sequential reading of numbers U _to , which through the information inputs of the first group enter the control unit 6 to generate codes for the search keys of the "bodies" of the data structures of the tuple. The key codes of the tuple bodies generated by the control unit 6 in a certain sequence defined by the block 2 of the registers are fed to the information inputs of the second group of the register code 4 of the polling code, where, in the presence of a control signal from the tenth control output of the block 6, they are stored. Next, the control unit 6 in its own program (microprogram) generates a sequence of control signals for the implementation of the basic operations of reading the body of the data structure from the drive 18 (Fig.2) by the method of associative polling by key codes sequentially received on the register 4. In this case, the read information through the output the switch 3 is fed to the output data bus 8.

 When implementing memory access for working with data structures of the list, tree, network type, in addition to the name of a specific structure, its pointers are used. At the same time, the pointers are used to implement various crawl modes by the elements of the selected data structure (we will conditionally distinguish two crawl modes: "deep" and "breadth"). The breadth-first crawl strategy involves scanning a complex data structure, represented, for example, in the form of a graph, horizontally: first, all elements of one tier of the graph are selected and processed, then the transition to the next tier is performed.

The "deep" traversal strategy involves scanning a complex data structure at each step from one tier to another, while enumerating related routes from the initial vertex to the final one. The bypass algorithm is implemented by a sequence of simple basic operations described above. So, if a tree walk "deep" is carried out, then the search for the tree element in the current step is performed by the name code located in the first attribute field of the data structure (U _d , UK ₁ , UK ₂ , T _d ). To do this, perform the basic operation of reading an element of the data structure with an associative search by the contents of the first left register 21 memory cells 19 (Fig.1,2). After reading the information from the found memory cell, the output switch 3, under the action of a control signal from the third output of the control unit 6, transmits the read field codes of the pointers of this structure element from the outputs of the second and third groups of the switch (Fig. 1) to the corresponding inputs of the control unit 6 and block of 2 registers, where they are stored in the memory of the stack type with the LIFO service discipline. Simultaneously with the outputs of the first group of the switch 3, the read information enters through the output bus 8 into an external system for analysis and formation of search functions.

 Based on the contents of the information field (fourth field) of the read data structure element, the control unit 6 generates a polling code, which from the eleventh outputs of the unit 6 goes to the information inputs of the second group of register 4, where it is stored. Next, the control unit 6 generates at its outputs the necessary sequence of control signals to implement the basic operation of reading the body of an element from the memory unit 1 in accordance with the polling code in register 4. After reading the body of the element, issuing it through the output switch 3 to the output data bus 8, the control unit 6 generates control signals "Read" and "Mode Selection" corresponding to the LIFO type access mode. These signals are supplied to the inputs of the same block of 2 registers, realizing the reading of the codes of pointers recorded earlier and transferring them to the corresponding inputs of the control unit 6. Next, the external system checks the conditions for achieving the search target and, if the target is reached, stops further search operations. Otherwise, the external system again initializes the control unit 6. The control unit 6 generates a polling code from the indicator code, which from its outputs goes to the second inputs of register 4, where it is stored. Then, using this interrogation code, the next element of the tree is searched and read and the process described above is repeated until block 2 of the registers is “empty”.

 The implementation of the bypass mode "in depth" is carried out similarly except for the signal "Mode Selection", which is generated by the control unit 6 at a different level (compared to the "breadth" mode), which provides access to the register block 2 of the FIFO type.

Thus, the proposed device in comparison with the prototype has significantly greater functionality, which allows to provide:
hardware support for complex algorithms of access to drive cells for writing and reading data structures of various types, including tuple, network, tree, etc.

 dynamic allocation of memory resources and tight packing of information due to the fact that the code space of data and attribute attributes is fixedly separated, and the physical memory space is filled dynamically, and the same memory registers are used in some cases to store signs, in other cases to store elements (records) of the body of the data structure.

 When using the microprogramming principle of generating control signals in control unit 6, it becomes possible to flexibly reconfigure and replenish access algorithms and the formation of complex data structures.

Claims (2)

 1. A MEMORY DEVICE containing a memory unit, a polling code register whose outputs are connected to the corresponding polling inputs of the memory unit, the first synchronization input is connected to the eighth output of the control unit, the ninth output of which is connected to the second synchronization input of the memory unit, the fourth output of the control unit is connected to an input of a write request for a memory unit, the first and second control inputs of which are connected to the fifth and sixth outputs of the control unit, respectively, the seventh output of which is connected to the read request input of the memory unit, the tenth output of the control unit is connected to the control input of the polling code register, the information inputs of the first group of which are inputs of the device polling code, the information inputs of the memory block are data inputs of the device, characterized in that, in order to expand the scope by providing hardware support work with complex data structures, a register block, a data structure register and an output switch are inserted into it, the information inputs of which are connected to the information outputs and a memory unit, the control input with the third output of the control unit, and the information outputs of the first group are the information outputs of the device, the information outputs of the second group with the information inputs of the second group of the control unit, the information inputs of the first group of which are connected to the outputs of the group of the register block, the output of which is connected to the first control input of the control unit, the first and second outputs of which are connected respectively to the read-write and register block mode inputs, information inputs They are connected to the outputs of the third group of the output switch, the second and third control inputs of the control unit are connected to the overflow outputs when recording and the end of the polling of the memory block, the inputs of the data structure type of which are connected to the outputs of the data structure register, the information inputs of which are the inputs of the code of the device data structure type and the synchronization input is connected to the twelfth output of the control unit, the eleventh output of which is connected to the information inputs of the second group of the poll code register, The inputs and outputs of the control unit are the inputs and outputs of the device.  2. The device according to claim 1, characterized in that the memory block contains input and output registers, write and read blocks, a group of AND elements and a drive, the information inputs and outputs of which are connected to the outputs of the input register and information inputs of the output register, the synchronization inputs of which are the first and second inputs of the block synchronization, the inputs of the input and outputs of the output registers are respectively the information inputs and outputs of the block, the outputs of the group of the reading block are connected to the corresponding first inputs copys And groups, the second inputs of which are combined and are the first control input of the block, the outputs of the elements and groups are connected to the inputs of the group of the recording block, which are inputs of the write request of the block, and the output is the overflow output when recording the block, the outputs of the group of the recording block are connected to the corresponding recording inputs drive, the read outs of which are connected to the inputs of the group of the read block, the input and output of which are respectively the input "Read request" and the output "End poll" of the block, inputs of the type of data structure and polling Ithel are respectively input data structure type codes and the interrogation unit, the control input is a second control storage unit entrance.