JPH07104786B2 - Data processing device - Google Patents

Description

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a data processing device intended mainly for use in the field of artificial intelligence.

2. Description of the Related Art In recent years, the field of artificial intelligence has been actively studied as one of computer applications. In this field, it is necessary to process structured data, and therefore LISP, which is a language that can handle structured data, is widely used. Since the LISP language is inefficient to run on a general-purpose computer, various special-purpose machines have been developed (for example, "LISP Machine" Information Processing Vol.23 No.8).
pp752-772).

These dedicated machines have been improved mainly from the linguistic aspect, and as a representation of structural data inside the computer, basically the order relation of elements and the method of connection are represented by pointers (hereinafter referred to as a list). There are the following problems due to the use of. (1) Access to an arbitrary element becomes a list traversal, resulting in poor efficiency. (2) List matching is inefficient because it involves a list decomposition operation.
(3) Garbage collection is difficult. (4) The locality of memory reference is poor, and the cache hit rate is reduced. Moreover, since the shared structure is basically taken, the following problems occur. (5) The direct side-by-side list operations such as RPLACA and RPLACD have an unexpected side effect of implicitly changing other data. (6) It is difficult to lock variables during parallel processing. On the other hand, in order to solve these problems, improvement by changing the representation of the structural data inside the computer has been proposed.

In general, the binary tree list has a form in which it starts from a node at a starting point, sequentially branches to the left and right, and ends at each branch at a node of a leaf. There are two types of leaf nodes, atom nodes and NIL nodes. Nodes that are not leaf nodes are list nodes that indicate that branching is continuing. This list node is for indirectly representing the position of the leaf node.

In the pointer expression, this structural expression is expressed as it is in a cell in which all nodes are connected by addresses.

However, if the position of the leaf node can be represented directly, it is not necessary to have the information of the list node.
Therefore, equivalent list data can be expressed by a table in which the position information of the leaves and the information of the leaves themselves are sequentially arranged. As a method of expressing leaf node positions, a one-dimensional vector representation has been proposed in which sequential numbers are assigned in the CDR direction and sequential items are assigned in the CAR direction (for example, "high-speed matching method for structured data") 33rd National Congress 7D-2). According to this, the list data is represented by a set of data in which a vector indicating position information of the leaf and information of the leaf itself are combined.

FIG. 3 shows an example of representation of list data. This shows the diagrammatic representation (a) and the tabular representation (b) of the list data that is (A (B (C)) D) when represented by the S formula. In the graphic representation, circles represent list nodes, and those surrounded by squares represent leaf nodes. The number string added above each node indicates the node position represented according to the above method. This leaf part is extracted and expressed in the form of a table, which is a tabular form (b), where the node position vector is V in the ADDRESS part.
It consists of a table with leaf elements in the ALUE part.

When the list is expressed in such a tabular form, many drawbacks of the pointer expression can be avoided, but the operation system is naturally different from the conventional pointer expression.

Fig. 4 shows an example of table operation in the basic list operation function of LISP.

As is clear from Fig. 4, the CAR function has a leading 1 in the ADDRESS part.
By extracting the element of the second and the second and lower ADDRESS in the head direction (this is called CAR shift below)
Can be executed. The CDR function is the opposite of the CAR function
The first ADDRE of the remaining elements by removing the element whose ADDRESS is 1
It is executed by subtracting 1 from SS (hereinafter referred to as CDR shift).

The CONS function is a bit more complicated. First, for the first argument of the CONS function, the ADDRESS part is shifted in the direction opposite to the head direction, and the head ADDRESS is set to 1. This is an operation that is the reverse of the CAR shift described above, and will be referred to as an RCAR shift hereinafter. For the second argument, add 1 to the first ADDRESS (hereinafter this is called RCDR shift for the same reason as RCAR). Next, if these two arguments are put together in one table, the CONS function will be executed.

Problems to be Solved by the Invention The following problems have been encountered in a data processing device that uses a tabular representation of structure data, which has been proposed to solve the problems in the pointer representation of structure data inside a computer. Exists. In other words, LISP basic functions such as CAR, CDR, and CONS, which are extremely easy to use with pointer expressions, require a calculation for all elements in the table format.

The present invention has been made in view of the above problems, and efficiently processes structural data represented by a basic Lisp function by performing parallel processing on all elements of tabular list data. A data processing device capable of performing the above is provided.

Means for Solving Problems In order to solve the above problems, the data processing device of the present invention comprises list data including an ADDRRES portion indicating a node position and a VALUE portion indicating a reference to a value of atom data. List memory device for storing as table format data, a plurality of list register means for storing one element of table format list data, and list for performing arithmetic processing of one element of list data stored in the list register means A plurality of list element processing devices each including an arithmetic means; and elements of the tabular list data stored in the list memory device are sequentially assigned to the plurality of list element processing devices and transferred, and the plurality of list element processing devices are also transferred. The list element for transferring the list data in the tabular format composed of the elements of the list data sequentially transferred from the list element processing device to the list memory device. And a list processing control device for selecting the list register means and the arithmetic processing of the list operation means for the plurality of list element processing devices, and controlling the operation of the list transfer device. A list data processing unit, an atom memory device for storing the value of the atom data, an atom register device for storing the value of atom data extracted from the atom memory device from the reference, and the atom register device. The atom data processing section is composed of an atom arithmetic unit that performs arithmetic processing of the stored atom data value.

Effect The present invention efficiently processes the structure data by expressing the list data in a tabular form and processing all the elements in parallel by the plurality of list element processing devices of the list data processing unit by the above-described configuration. It allows you to do things.

Embodiment A data processing apparatus according to an embodiment of the present invention will be described below with reference to the drawings.

FIG. 1 shows the configuration of a data processing device according to an embodiment of the present invention.

In FIG. 1, 1 is a list memory device, 2 is a list transfer device, 3 is a list element processing device, 4 is a list processing control device, 5 is an atom memory device, 6 is an atom register device,
Reference numeral 7 is an atom arithmetic unit. The list data processing unit 8
The list memory device 1, the list transfer device 2, the plurality of list element processing devices 3, and the list operation device 4 are generic names, and the atom data processing unit 9 is a general term for the atom memory device 5, atom register device 6, and atom operation device 7. Is.

FIG. 2 shows the internal structure of the list element processing device 3 in the above embodiment.

In FIG. 2, 21 is a list register device, 22 is a list operation device, 23 is a list input device, and 24 is a list output device. LIB is a list input bus, LOB is a list output bus, DB is a data bus, RS is a register selection signal, OS
Is an operation selection signal.

The operation of the data processing apparatus configured as described above will be described below with reference to FIGS. 1 and 2.

First, the list data processing is performed by the list data processing unit 8.

When processing the list data stored in the list memory device 1, under the control of the list processing control device 4,
The list transfer device 2 transfers the list element processing device 3 through the list input bus LIB. In this case, each element of the table type list data is transferred to another list element processing device 3. In the list element processing device 3, one element of the list data input from the list input bus LIB is transferred to the list register device 21 through the list input device 23. The list register device 21 is composed of a plurality of storage unit registers.
One of the selected list data is stored in the selected register according to the register selection signal RS output from the selected one.

The various operations of the list described above are executed by the list operation device 22 on the ADRESS portion of one element of the list data in the list register device 21 and returned to the list register device 21 again. At that time, for the ADDRESS part of one element of the list data stored in the register selected by the register selection signal RS output by the list processing control device 4, the operation selection signal OS also output by the list processing control device is targeted. The calculation selected by is executed by the list calculation means 22. In the case of the CAR operation, the list calculation means 22 performs the CAR shift described above on the ADDRESS part of one element of the list data read from the selected list register and returns it to the original list register again. The same applies to CDR operations, and the operation is CDR shift.

As described above, the operation of the list operation means 22 needs to be performed for all the elements of the tabular list data, but under the control of the list processing control device 4, a plurality of list element processing devices 3 operate in parallel. In order to perform this operation, it can be executed in one cycle.

When it is necessary to return the list data from the list element processing device 3 to the list memory device 1, each list element processing device 3 under the control of the list processing device 4 selects the list register selected by the register selection signal RS. The contents are output to the list output bus LOB through the list output device 24. The plurality of elements of the list data output from the plurality of list processing devices to the list output bus LOB are stored in the list transfer device 2
Are compiled in a table format and transferred to the list memory device 1.

Next, atom data processing is performed in the atom data processing unit 9.

A reference to atom data is stored in the VALUE part of each element of the list in the above table format, but in the list processing, it is necessary to perform an operation on numerical values or characters that are their actual values. The calculation is not performed by the list element processing device 3, but is performed by the atom calculation device 7. First, the reference value of the list element is output from the list element processing device 3 to the data bus DB, and the atom memory device 5 storing the actual value.
Is accessed and the value is stored in the atom register device 6. After that, the atom arithmetic means 7 performs arithmetic processing on the value of the atom data stored in the atom register device 6, and the result is stored again in the atom memory device 5.

As described above, according to the present embodiment, each element of the tabular list data stored in the list memory device is transferred to the list register device in each separate list element processing device by the list transfer device, and each list is transferred. By processing in parallel by the list processing unit of the element processing unit, Lisp
The structure data represented by the basic list operation function can be efficiently processed.

As described above, the present invention is a list memory device for storing list data as tabular data composed of an ADDRRES part indicating a node position and a VALUE part indicating a reference to a value of atom data, and a list memory device. A plurality of list element processing devices each including a plurality of list register means for storing one element of the list data in the form, and a list operation means for performing an operation processing of one element of the list data stored in the list register means. , The elements of the tabular list data stored in the list memory device are sequentially allocated and transferred to the plurality of list element processing devices, and the list data of the list data sequentially transferred from the plurality of list element processing devices are transferred. A list transfer device for transferring tabular list data including elements to the list memory device and a list transfer device for the plurality of list element processing devices. To select the list register means and the operation processing of the list operation means, and a list data control unit configured to control the operation of the list transfer device, and the atom data. Atom memory device for storing the value of the atom data, an atom register device for storing the value of atom data fetched from the atom memory device from the reference, and an atom for performing arithmetic processing of the value of atom data stored in the atom register device. It has an atom data processing unit composed of an arithmetic unit and processes all the elements of the tabular list data in parallel, thereby efficiently processing the structure data. It is a thing.

[Brief description of drawings]

FIG. 1 is a block diagram of a data processing device according to an embodiment of the present invention, FIG. 2 is an internal block diagram of the list element processing device of FIG. 1, and FIG. 3 is a diagram showing an example of a tabular representation of list data. FIG. 4 is a diagram showing an example of table operation in the basic list operation function of LISP. 1 ... list memory device, 2 ... list transfer device, 3 ...
... list element processing device, 4 ... list processing control device, 5
... atom memory device, 6 ... atom register device, 7
...... Atom arithmetic unit, 8 …… List data processing unit, 9 ・ ・ ・
… Atom data processing unit, 21 …… List register device, 22
...... List computing device.

 ─────────────────────────────────────────────────── ─── Continuation of the front page (72) Inventor Masato Honma 1006 Kadoma, Kadoma City, Osaka Prefecture Matsushita Electric Industrial Co., Ltd. (72) Toshio Shimizu, 1006 Kadoma, Kadoma City, Osaka Matsushita Electric Industrial Co., Ltd. 56) References JP-A-63-65523 (JP, A) JP-A-63-61335 (JP, A)

Claims (1)

[Claims] 1. ADDRRE showing list data indicating the position of a node
A list memory device for storing as table format data composed of an S section and a VALUE section indicating a reference to the value of atom data, a plurality of list register means for storing one element of the table format list data, and A plurality of list element processing devices each comprising a list calculation means for calculating one element of the list data stored in the list register means, and a plurality of the elements of the tabular list data stored in the list memory device. A list transfer device for sequentially allocating and transferring the list element processing devices from the list element processing device, and transferring tabular list data composed of elements of list data sequentially transferred from the plurality of list element processing devices to the list memory device. , Selection of the list register means and selection of operation processing of the list operation means for the plurality of list element processing devices And a list data processing unit configured from a list processing control device that controls the operation of the list transfer device, an atom memory device that stores the value of the atom data, and an atom memory device from the reference. An atom data processing unit including an atom register device that stores the value of the atom data that has been taken out and an atom data processing unit that performs an arithmetic process on the value of the atom data stored in the atom register device. And data processing device.