JPH02263233A - Data control system - Google Patents

Abstract

PURPOSE:To omit the need to express all storage spaces via a pointer and to save the storage capacity by expressing the data having a structure where the nodes are linked by the pointer over the real and virtual storage spaces. CONSTITUTION:A pointer is shown in an address of a real storage space RM in this space, and a pointer is shown in an address of a virtual storage space IM and an address of the space RM in the space IM. Then the data having a structure where the nodes are linked by a pointer is expressed over both spaces RM and IM by the indirect reference to the nodes of the space IM through the nodes of the space RM. Furthermore the data is transferred between both spaces RM and IM in the list structure units U1 and U2 with use of the link information on those nodes linked by the pointer. Thus it is possible to virtually store the list structure data basic and indispensable to the symbol processing fields of the artificial knowledge, the numerical formula processing, the natural language processing, etc.

Description

[Detailed Description of the Invention] A. Industrial Application Field The present invention relates to a data management method for the main memory of a computer, and in particular, to a basic and essential list in the field of symbol processing such as artificial intelligence, mathematical formula processing, and natural language processing. This effectively realizes the virtualization of structural data.

B. Summary of the Invention The present invention, when managing data by a computer, represents a pointer in a real storage space by an address in the real storage space, and in a virtual storage space, a pointer is represented by an address in the virtual storage space and a pointer to the real storage space. By representing a pointer with an address and indirectly referencing the node in the virtual storage space from the node in the real storage space, data in a structure in which nodes are linked by pointers is transferred to the real storage space and the virtual storage space. By moving the data in the structure where the nodes are linked by pointers between the real storage space and the virtual storage space in a list structure unit using the link information, artificial intelligence, mathematical formula processing, This system efficiently realizes virtual storage of list-structured data, which is fundamental and essential in the field of symbol processing such as natural language processing.

C. Prior Art Generally, in the field of symbol processing such as artificial intelligence, mathematical formula processing, and natural language processing using computers, target symbol processing is performed while list-structured data is managed in memory.

Conventionally, the list-structured data mentioned above has a structure in which nodes are linked by pointers, so-called poi.
inter-1 inked data is widely known. In the above pointer-1 inked data, the pointer often has only one direction, and
A node has a pointer to the node of (lh) and its own data, and the number of pointers is two, so-called
ry tree) structure.

For example, in the LISP language, which is known as a typical language that handles list-structured data, intermediate nodes (Nlo), (Nlt), (N+4), (Nl5), (
Nl? ).

(Nzo) , (Nzg) , (Nl4) , (N1
6) has two pointers and the node (N
++), (N++), (Nli), (Nls).

(N+*), (Nr+), (Nzs), (Nzg
), (Nzt), and (Nt,) have specific data, and the configuration state of the terminal has information.

In addition, when handling list-structured data as described above in memory, for example, as shown in FIG. 14, nodes (Nl.), (N
11), (Nl, (Nls), etc.) are expressed, and a pointer is expressed by the address of the storage space (M), so that the above data is managed by the computer.

By the way, the above-mentioned list-structured data handled in the field of symbol processing has a dynamic structure in which the information given as the data structure changes freely by cutting and connecting, expanding and contracting. 1! behave incorrectly.

In addition, when managing such list-structured data in memory on a computer, the data structure is distributed on memory, and there may be no new nodes in memory, or there may be used and unnecessary nodes. Therefore, garbage collection CGC: Garbage (:oflec
tion) is performed.

Furthermore, when the real storage space is insufficient even after garbage collection is performed, the storage space (M) is expanded by virtualization, and the storage space is expanded in page units, as shown in Figures 15 and 16, for example. Manage real memory space (RM)
) and the virtual memory space (IM), data transfer (swapping) is performed in page units.

D. Problem to be Solved by the Invention By the way, current computer architectures are designed to process local data with static structure, and the above-mentioned list structure, which is handled in the field of symbol processing, is It is not suitable for processing data; for example, it takes a very long time to perform garbage collection when processing objects are dynamically distributed. Furthermore, conventionally, storage space has been virtualized by managing the storage space in page units based on data locality, and while the above page is a fixed area in the storage space, the above list-structured data is dynamic. As the information changes over time, the structure becomes complicated between multiple pages, resulting in frequent page faults and inefficiency. In particular, when garbage collection is executed on a virtualized storage space, execution efficiency is significantly reduced because data is transferred between the real storage space and the virtual storage space in page units.

Therefore, in view of the above-mentioned conventional situation, the present invention aims to efficiently realize virtual storage of list-structured data, which is basic and essential in the field of symbol processing such as artificial intelligence, mathematical formula processing, and natural language processing. shall be.

E. Means for Solving the Problems In order to achieve the above-mentioned purpose, the data management system according to the present invention represents a pointer in a real storage space by an address in the real storage space, and represents a pointer in a virtual storage space by an address in the virtual storage space. A pointer is represented by an address in the address and an address to the above real storage space, and a node in the virtual storage space is indirectly referenced from a node in the real storage space, so that nodes are linked by pointers. is expressed across real storage space and virtual storage space, and the data in the structure where the nodes are linked by pointers is moved between the real storage space and virtual storage space in a list structure unit using the link information. It is characterized by causing

F. Effect In the data management system according to the present invention, in a real storage space, a pointer is represented by an address in the real storage space, and in a virtual storage space, a pointer is represented by an address in the virtual storage space and an address to the real storage space. and indirectly reference nodes in the virtual storage space from the nodes in the real storage space, thereby representing data in a structure in which nodes are linked by pointers across the real storage space and the virtual storage space. This eliminates the need to represent the entire storage space with a pointer. In addition, dynamic data can be statically divided by moving data in a structure in which nodes are linked using pointers between the real storage space and virtual storage space in list structure units using the link information. Manage dynamic data structures while reflecting them as they are without having to do so.

G. Example Hereinafter, an example of the present invention will be described in detail with reference to the drawings.

FIG. 2 is a block diagram showing the conceptual configuration of a multiprocessor system that handles list-structured data by applying the data management method according to the present invention. This multiprocessor system consists of multiple processors (la
), (lb) to (In) respectively accessed through memory controllers (2a), (2b) to (2n), and a main storage device (3) forming a real storage space, and a hard disk device, etc. forming a virtual storage space. secondary storage (
4), and storage capacity is expanded through virtualization.

Note that the main storage device (3) has a plurality of memory banks (3).
a), (3b) to (3n) and each of the above memory banks (3a).

It is composed of connection circuits (3A) of (3b) to (3n).

The list-structured data handled by this multiprocessor system is represented by an address in the real storage space as a pointer in the real storage space, and an address in the virtual storage space and an address in the above real storage space in the virtual storage space. represents a pointer, and a node in the virtual storage space is referenced from the node in the real storage space using an indirect pointer, so that the data has a list structure in which nodes are linked by pointers as shown in Figure 1. as the main storage device (3
) with the real storage space (RM) and the above secondary storage device (4)
The list structure unit (01
), (uz), data is transferred (swapped) between the real memory space (RM) and the virtual memory space (IM).

In FIG. 1, a node in the real storage space where an indirect pointer that refers to a node in the virtual storage space is set is indicated by an opening, and other nodes are indicated by an O.

Here, a specific example of expressing the data in the list structure will be explained.

For example, as shown in FIG. 3, nine nodes (N
,. ), (N++), (N+z), (N+ff), (N
z. ), (Nz+), (Nzz).

(Nzs) and (Nx.) are the above real memory space (RM)
The data in the list structure linked by the pointers expressed by the real storage space addresses above are the four nodes (N++), (Lx), (
N□).

(When the list structure unit (Uo) based on N2 is transferred to the virtual storage space (I?l) of the secondary storage device (4), it is expressed as shown in FIG. 4.

In FIG. 4, four nodes (
n, 1), (nlz), (nt+), (nxx)
is each node (nt,) on the virtual memory space (IM)
, (n-) virtual memory space address and each node (N++), (N+z), (
Each of the above nodes (ntt) and (nt
t), (Net), (Net), (NIs), (Ibs
) will be linked. In addition, the above real storage space (12M
), each node (Net), (Net) on the virtual memory space (IM) represents the virtual memory space address of each node (n,), (nl-) of the list structure unit (U,) on the virtual memory space (IM). Each of the above nodes (n,), (n
It will be linked with the following.

In this system that handles list-structured data as described above, during the dynamic change process of the list data, there is no necessary node in the real memory space (RM), and a list fault occurs, and that node is transferred to the virtual Memory space (
IM), the data of a series of list structure units including that node is transferred (Swap-in) from the virtual memory space (LM) to the real memory space (RM) to perform the procedure described later. List in according to the following.

In addition, this system monitors the number of free nodes on the real memory space (RM), and monitors the number of free nodes on the real memory space (RM).
M) When there are no more free nodes on the list, garbage collection is performed to collect unnecessary nodes as free nodes, and if the number of free nodes becomes more than a predetermined threshold (tI S h), the original data processing is resumed. If the number of free nodes does not exceed the predetermined darkness value sh due to the above garbage collection,
At that point, extract the pointer to unnecessary list data on the real memory space (RM), and transfer the list structure unit data from the real memory space (RM) to the virtual memory space (IM) according to the procedure described later. A restore operation for transfer (swap-out) is performed on the real memory space (RM).

If the number of data in list structure units restored on the above real storage space (1?M) is small and does not reach a predetermined threshold (!!SS), unnecessary list data will be stored on the above real storage space (RM). The bonder is further extracted and the restore operation of new list data is repeated on the real memory space (RM), and the number of data in the list structure unit restored on the real memory space (RM) is the dark value. S
s, the list structure unit data restored in the real memory space (RM) is transferred to the real memory space (R'
Data transfer (
Swap-out) Ends the restore operation and returns to the original data processing.

From the above real memory space (RM) to the above virtual memory space (IM)
The operation of restoring to is performed as follows by sweeping the list structure and using an indirect pointer while referring to the number of links of each node using a reference counter.

For example, as shown in FIG.
nodes (Ne.), (Ne +), (Ne z)
, (NIs), (Nx.).

To explain the case where a list structure unit (υ, .), in which (To+) and (Nzz) are linked by a pointer, is read-out from the real memory space (RM) to the virtual memory space (IM), first, the real memory On the space (RM), the above list structure unit (U
,. ) is restored using the procedure shown in FIGS. 6A to 6F.

That is, first, focusing on the node (N16), for example, at the start position of the list structure unit (El t @) on the real memory space (RM), as shown in FIG. 6A, the node ( A dereference pointer that represents a link to the node (Ne
. A node (nl.) having a dereference pointer that indicates a link to a node (N,) linked by a pointer in the virtual storage space (I
An indirect pointer expressing a link to the node (neo) to be moved to the virtual memory space (IM) is set in the work area (A^) on the real memory space (RM) as a node to be moved to the virtual memory space (IM). Set to the node (Ne.) on the space (RM).

Next, the node (Nl) on the real storage space (RM).

), focusing on the above node (Nl+) that was linked to
As shown in FIG. 6B, each node (Net), (Nz+) linked by the dereference pointer expressing the link to the node (Ni+) as a real storage space address and the pointer of the node (Net) A node (n,) having each dereference pointer representing each link with a real storage space address is provided in the work area (W^). Then, the indirect pointer representing the link of the work area (A) to the node (n11) is set to the node (N1).
．． + ), and the link to the node (N12) on the real storage space (12M) by the pointer of the node (nl.) in the work area (-^) is set to the node (N + t). Move the link to the node (n, t) in the corresponding work area (HA), and change the dereference pointer to the node (Lx) to the link to the node (nl,) using the virtual memory space address. Change the pointer to the expressed content.

Next, the node (N
Focusing on the above node (N, □) that was linked to 11), the node (N
i3), each node (N, □), (N'3) in the real storage space is transferred to the work area (HA).
As shown in FIG. 6C, the above node (n, 1
) and a node (nl3) linked by the pointer of this node (nIz) are provided in the work area (-8).

Next, the real storage space (R
By focusing on the node (Nz+) on M) and linking the pointer of this node (NZ+) to the node (No), each node (N2 +) on the real memory space (RM) is created. , (N22) in the above work area (IA
A), as shown in the sixth diagram, the above node (n
,) Node linked by pointer (nz+)
Then, a node (n,) linked by the pointer of this node (nz+) is provided in the work area (WA). Further, the link to the node (Ni1) on the real storage space (RM) by the dereference pointer of the node (nz□) in the work area (11A) is changed to the work area (Ni1) corresponding to the node (Nl+). ridge) to the above node (n,).

Further, an unswept node (N
! . ), as shown in Figure 6, the above node linked by the dereference pointer expressing the link to the above node (Nzo) as a real storage space address and the pointer of the above node (Nz.). A node (ntJ) having a dereference pointer indicating a link to (N,) with a real storage space address is provided in the above work area (-A), and an indirect pointer expressing a link to this node (nz.) is set as above. Node (Nt) on real memory space (RM)
O).

And the above node (nz.) in the above work area (-^)
The link to the node (N++) on the real storage space (RM) by the dereference pointer of the node (n, ,) in the work area (HA) corresponding to the node (N++)
As shown in FIG. 6F, instead of attaching a link to By moving the work area (
The restore of the list structure unit (U, .) to HA) is completed.

Finally, the data in the list structure unit (υ, .) is transferred from the work area (reference) on the real memory space (RM) of the main memory (3) to the virtual memory space (2) of the secondary memory (4). By transferring data (Si1ap-out) to IM), the list structure unit (U+O) is restored to the virtual storage space (IM) as shown in FIG.

In this way, by using an indirect pointer, a circular list structure such as the list structure unit (υ, .)' can be successfully restored, and moreover, the main memory bag W(
Data transfer (Swap-out) of list structure unit data restored on the real memory space (RM) by 3) from the real memory space (RM) to the virtual memory space (IM) by the secondary storage device (4) ), it is possible to efficiently and quickly restore to the virtual memory space (IM).

Here, a link to a node on the above real memory space (RM) is expressed as a real memory space address, and a link to a node on the above virtual memory space (IM) is expressed as a virtual memory space address in each memory space. A normal pointer that directly represents a link within each storage space, and a node on the real memory space (RM) that represents the virtual memory space address of the node on the virtual memory space (IM). Indirect pointers such as (N++) and (Nit), and nodes (nl.) and (nl) on the virtual memory space (IM), which represent links to nodes on the real memory space (RM) as real memory space addresses, are expressed as real memory space addresses. A dereference pointer such as ) is identified by the contents of the tag, for example, by adding a tag indicating the type IF of the node pointed to by the pointer to the pointer.

Next, from the virtual storage space (group) of the secondary storage device (4) to the real storage space (RM) of the main storage device (3)
List-in to is performed as follows when the node to be accessed is not on the above real storage space (R?) but on the virtual storage space (IM) indicated by indirect blank ink. .

For example, as shown in FIG.
The nodes (Nl.) and (Nll) on the above virtual storage space (IM) linked by the indirect pointers of the above nodes (Nl.) and (Nll)
nl−), (n++)+ (r++zL (nIs)
, (nt->, (n-,), (ngz) into the list structure unit (U! , the data of the list structure unit (Uio), the work area (-8) on the real storage space (R1'l)
Data transfer (Swap-in) L/, on the real storage space (RM), the list structure unit (Ox.) is transferred from the work area (HA) to the list structure unit (Ox.) using the steps shown in FIGS. 9A to 9. Performs list-in operation.

That is, regarding the list structure unit (Uz.) of the work area (HA) as shown in FIG. 9A, which has undergone data transfer (Swap-in) from the virtual memory space (IM) to the real memory space (RM). , First, the above list structure unit (
Uo. ), and as shown in FIG. 9B, each node (n++) constituting the list structure unit (Lh.) is
+(r++□).

(nl-), (nz+)+ Set a dereference pointer to (nzz) and set the above nodes (n,), (nIs)+
(nlff)+ (n-5), each node corresponding to (n-) (Nll), (Nlz), (N+3), (Nz
+) and (Tow) are provided on the real storage space (RM).

Next, the list structure unit (UZ.) is scanned again, and as shown in FIG. 9C, each of the above nodes ( n,
-), (r+++), (nIs)+ (n+3),
The pointer expressed by the virtual memory space addresses (n, o), (nz+), (nzz) is transferred to the above real memory space (
Each of the above nodes (Nll) on IiM).

The dereference pointers are replaced by real storage space addresses linked to (Nlz), (N+3), (lJz+), and (Nzz).

Then, by scanning the list structure unit (UZ.) three times, as shown in the seventh diagram, each of the above nodes ( n+oL(n++)+(nIs)+(nIs)+(n
The contents of zoL(nz+)+(n=-) are transferred to each node (NIP) on the real memory space (RM), (Nll)l(N
(Nl3), (Nx.), (N□), (Nz
By moving to □), the above list structural unit (U2゜)
from the work area (-8) to the real memory space (RM), and from the virtual memory space (IM) in the secondary storage device (4) to the real memory space (RM) in the main storage device (3). ) ends the list-in of the list structure unit (Uz.).

Note that from the virtual memory space (IM) to the real memory space (
The list-in to the RM) can also be performed in the same manner as the above-mentioned restore from the real memory space (RM) to the virtual memory space (IM).

Here, the real storage space (RM
) is stored in the virtual storage space (IM
), the above virtual storage space (
References often occur from nodes in the restored list structure unit on the IM) to nodes on the real memory space (RM), for example, as shown in FIG. The above real storage space (RM
) on the list structure unit (UC) on the virtual memory space (IM) without being referenced by other nodes on the real memory space (RM).
It may be an indirect pointer to.

In such a case, by rewriting the reference from the virtual memory space (IM) to the node (Nl) on the real memory space (RM), the indirect pointer can be deleted as shown in Figure 11. Thus, it is possible to increase the number of free nodes on the real memory space (RM).

In principle, the series of operations for deleting indirect pointers as described above is to create a dereference table for each indirect pointer, and when restoring, to delete the corresponding indirect pointer in the restored list structure unit. This can be achieved by rewriting the reference to . Since this operation includes the operation of manipulating the list structure in the virtual storage space, the number of accesses to the virtual storage space, which requires a long access time, increases.

Therefore, in this system, as shown in Figure 12A,
A structure reference table (SR) collectively manages each list structure unit listed in the virtual storage space (1?I).
T) and an external reference table (XRT) that manages references to external nodes in list structure units restored in the virtual storage space (Il+) on the real storage space (RM), and As shown in FIG. References between each list structure unit listed in the space are handled collectively, and the above virtual storage space (1
? I).

The structure reference table (SRT) includes information srt, id that specifies each list structure unit listed in the virtual storage space (R), the number of references from outside to the node of the list structure unit ref, c, and the above information. External reference table (XR
A pointer xrt to T) is stored, and is used for managing, searching, etc. of the external reference table (XRT).

In addition, the external reference table (XRT) is assigned to each restored list structure unit, and contains information ptr, id that specifies the node referencing the outside in the corresponding list structure unit, and information about the node A pointer dat that specifies the referenced external node is stored. moreover,
The above dereference table (DRT) is stored in the above real memory space (IIM).
Data ptr, 1 that identifies nodes on the virtual storage space (IM) that refer to the above nodes in list structure units;
ist, and data dst and id that specify the node on the real storage space (RM) are stored.

The above reference tables (SRT), (XI?T), (D
For example, the entry for the above structure reference table (
SRT) is the structure number of the list structure unit, the external reference table (XRT) is the address within the structure of the list structure unit, and the above dereference table (DRT) is hashed with the real storage space address. Reference table (S
RT).

(XRT), (DRT) searches, etc. can be sped up. Note that if the referenced node does not exist in the real storage space, it cannot be hashed to the dereference table (DRT), but the dereference pointer from the node of the list structure unit in the virtual storage space can be hashed to the dereference table (DRT). (DRT).

Here, although binary tree list structure data was managed in the above embodiment, list structure data that can be handled in the data management method according to the present invention is limited to binary tree list structure data. It is possible to expand the list structure data to an n-ary tree structure without any problems. Furthermore, the data management method according to the present invention is not only applicable to multiprocessor systems such as those in the above-described embodiments, but can of course be applied to processor systems such as boat fishing.

H Effects of the Invention In the data management system according to the present invention, in a real storage space, a pointer is represented by an address in the real storage space, and in a virtual storage space, a pointer is represented by an address in the virtual storage space and an address to the real storage space. represents a pointer, and the nodes in the virtual storage space are indirectly referenced from the nodes in the real storage space, so that data in a structure in which nodes are linked by pointers is transferred between the real storage space and the virtual storage space. By representing it, there is no need to represent the entire storage space with a pointer, so the storage capacity can be saved and the storage capacity can be substantially increased.

Further, in the data management method according to the present invention, data in a structure in which the nodes are linked by pointers is moved between the real storage space and the virtual storage space in a list structure unit using the link information. Since dynamic data is managed without statically partitioning it while reflecting the dynamic data structure as it is, it is possible to reduce the number of accesses to the virtual storage space and significantly improve memory access efficiency. In particular, it is extremely effective because it can significantly improve the execution efficiency of garbage collection.

Therefore, by applying the data management method according to the present invention, it is possible to efficiently realize the virtualization of list-structured data, which is basic and essential in the field of symbol processing such as artificial intelligence, mathematical formula processing, and natural language processing. become.

[Brief explanation of drawings]

Figure 1 is a schematic diagram showing an example of list-structured data handled in a processor system to which the present invention is applied, expressed across real and virtual memory spaces, and Figure 2 is a diagram of a multiprocessor system to which the present invention is applied. A block diagram showing the configuration, Figure 3 is a schematic diagram showing a specific example of list-structured data expressed in real storage space, and Figure 4 shows how the list-structured data shown in Figure 3 above is expressed in real storage space and virtual memory. FIG. 5 is a schematic diagram showing a specific example of representation across space; FIG. 5 is a schematic diagram showing a configuration example of a list structure unit restored from real storage space to virtual storage space; FIGS. Figure C2
Figure 6, Figure 6 E, and Figure 6 F explain the procedure for restoring the list structure unit shown in Figure 5 above from the real storage space to the virtual storage space in the real storage space. Fig. 7 is a schematic diagram showing the list structure unit shown in Fig. 5 above restored from the real storage space to the virtual storage space, and Fig. 8 is a schematic diagram showing the list structure unit shown in Fig. 5 above restored from the real storage space to the real storage space. Schematic diagrams showing configuration examples of list structure units to be listed in, Figures 9A, 9B, 9
Figures C and 9 are schematic diagrams for explaining the list-in operation procedure on the real storage space for list-in the list structure unit shown in Figure 8 from the virtual storage space to the real storage space. 10 is a schematic diagram showing a list structure with indirect pointers remaining in the real storage space due to restore, and FIG. 11 is a schematic diagram showing a list structure in which indirect pointers shown in FIG. 10 have been deleted. FIGS. 12A and 12B are schematic diagrams showing the configurations of various reference tables provided for collectively managing each list structure unit restored on the virtual storage space. Figure 13 is a schematic diagram showing an example of general list-structured data, Figure 14 is a schematic diagram representing list-structured data in a storage space, and Figures 15 and 16 are conventional general virtualization diagrams. FIG. 3 is a schematic diagram showing an example of the structure of a storage space expanded in FIG. (la), (lb) ~ (In) = processor (2a)
, (2b) to (2n)... Memory controller (3)... Main storage device (3aL(3b) to (3n)-・・−=(4)・
・・・・・・・・・・・・・・・・・・(RM) ・・
・・・・・・・・・・・・・・・(IM) ・・・・
・・・・・・・・・・・・Bank memory Secondary storage device Real storage space Virtual storage space

Claims (1)

[Claims] In a real storage space, a pointer is represented by an address in the real storage space, and in a virtual storage space, a pointer is represented by an address in the virtual storage space and an address to the real storage space, and the pointer is represented by an address in the virtual storage space and an address to the real storage space. By indirectly referencing a node in the virtual storage space from a node in the space, data in a structure in which nodes are linked by pointers is expressed across the real storage space and virtual storage space, and the nodes are linked by pointers. A data management method characterized in that data in a structure linked by is moved between a real storage space and a virtual storage space in a list structure unit using the link information.