JPH07334366A - Method and apparatus for optimizing graph reduction mechanism - Google Patents

Abstract

PURPOSE:To considerably reduce a memory space and a time length required for calculation to repeat partial recalculation. CONSTITUTION:An entire graph S to be the object of reduction is held in a first storage means 1, and a second storage means 2 is provided with a hash table 2a for storing the hash values of all the partial graphs of the graph S and stores the pairs of partial graphs existent in the past and partial graphs at the reduction destination reached at present. A reduction means 3 reduces the partial graphs held in the first storage means 1 and when any partial graph at the reduction destination is not registered on the second storage means 2, that partial graph at the reduction destination is registered on the second storage means 2 corresponding to its original partial graph.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a method and apparatus for optimizing a graph reduction mechanism, and more particularly, the present invention can reduce the memory space and time required for graph reduction without relying on heuristics. The present invention relates to a method and an apparatus for optimizing a graph reduction mechanism that can be performed.

[0002]

2. Description of the Related Art Various methods have been proposed for garbage collection, which is a technique for reusing a heap area (dynamically allocable address space), which has been generated by research into the realization of a functional language LIPS. The main approaches are copy method, mark scan method and reference count method.

The heap area is usually allocated in units called cells having two pointers on the left and right, and is collected and reused. In the copy method, the above-mentioned heap area is divided into two, and every time a garbage collection is performed, all cells that are not garbage are copied from one to the other. The allocatable area is a contiguous memory area that is not used for copying.

In the mark scan method, each cell is provided with a 1-bit flag called a mark bit, and the heap area is linearly traced as a pre-process of garbage collection to clear the mark bits of all cells. Keep it. Next, set the mark bit by tracing the pointer from the root to all the cells that are currently used, and finally linearly trace the heap area to find all cells that do not have the mark bit set. As a list of reallocable cells called the free list.

In the reference counting method, each cell is provided with a counter called a reference counter for holding the number of times of reference from another cell. Then, in the calculation of each list process, the reference counter is increased / decreased each time the reference from another cell is increased / decreased, but the garbage collection simply traces the heap area linearly and all reference counters are 0. Collect cells and rebuild as a freelist. Or you can just collect it on the freelist when the reference count reaches zero.

The above garbage collection mechanism is as follows.
Currently used in various high-level programming.
A pure functional language without side effects has a lambda calculus system, which is the semantics of the early LIPS, or a term rewriting system as a calculation mechanism based on the equation theory, and the calculation is performed by rewriting terms called reduction. Go ahead.

For example, the Finabotti function fi is as follows:
Given the definition of b, fib (0) = 0 fib (s (0)) = s (0) fib (s (s (X))) = fib (s (X)) + fib (X) 0 + X = X s (X) + Y = s (X + Y) Try to calculate fib (s (s (s (0)))).

Fib (s (s (s (0)))) → fib (s (s (0))) + fib (s (0)) → fib (s (0)) + fib (0) + fib (s (0)) →… → s (s (0)) and the calculation result s (s (0)) is obtained. Where s (X) is X
Represents a natural number larger by 1, and 0,1,2,3, ... is 0, s (0), s
Corresponding to (s (0)), s (s (s (0))), ..., an arbitrary natural number can be represented by the same number of s and one 0.
In the actual calculation, we do not express natural numbers like this,
We use integer as a built-in type from the beginning, but we have shown it here as a typical easy example.

Strictly tracing the above example, first, the subterms of the term to be rewritten and one of the terms on the left side of the function definition match (substitute an appropriate term for the latter variable,
Check whether the former and the latter match). Then, if there is a match, the matched sub-term is replaced by the term obtained by copying the left side of the definition and performing the substitution used to match it (replacing the variable with a copy of the corresponding term). Repeat the process that the entire original subterm is garbage.

For example, fib (s (s (s (0)))) is fib (s (s (X)))
Since it matches with, copy fib (s (s (X))) to X
By replacing s (0) with fib (s (s (0))) + fib (s (0)), where fib (s (s (s (0)))) is garbage. In the usual implementation in a functional language, substitution is replaced by sharing of partial terms by pointers in order to avoid such inefficient copying. Such a calculation is called a graph reduction because the representation of terms becomes a doug (acyclic directed graph) by sharing pointers and reduction is performed on this.

In the above example, two sub-terms fib (s (0)) appear twice in the middle of the calculation, but since this has never been assigned to a variable, it is shared in the framework of sharing by variables. Can not. In order to share this with the pointer as well,
Hash all the subterms of the graph and update the hash table of all subterms including the rewritten subterms every time a reduction is performed so that the same subterm is always shared by pointers. I have to.

If the overhead of updating the hash table is of a linear order with respect to the size of the problem, it can be said that it is a realistic method for reducing the cell consumption. Furthermore, considering the calculation of a function that has exponential-order calculation time and space consumption, such as the simple Finabotti function as in the previous example, this sharing not only reduces the linear-order space consumption but also the calculation time. Can be dramatically reduced.

On the other hand, an old method for reducing the calculation time and space consumption is to record a fragment of partial calculation performed in the past and reuse the fragment so that the same calculation is not repeated. There is. For example, ifib computes the Finaboch sequence using the following built-in function type integers
Consider a program.

Ifib (X) = if (eq (X, 0), 0, if (eq (X, 1), 1, + (ifib (-(X, 1)), ifib (-(X, 2)) )))) The above formula shows that if X is 0, ifib (X) is 0,
If X is 1, ifib (X) becomes 1. If X is 2, ifib (X) is + (ifib (-(X, 1)), ifib (-(X, 2))), that is, ifib (2-1) + ifib (2- In 2), it becomes ifib (1) + ifib (0).

Similarly, if X is 3, ifib (2) + ifib
(1), that is, (ifib (1) + ifib (0)) + ifib (1). That is, when ifib (5) is calculated by the normal Call-by-value (depth-first sequential calculation), as shown in FIG.
A tree representing the calculation is obtained. In FIG. 10, the calculation procedure is as shown by an arrow. First, ifib (5) is obtained to obtain ifib (5).
(4) and then ifib (3) to find ifib (4)
Then, similarly, the steps shown in (1) to (14) are performed. Here, the calculation of the region surrounded by the dotted line in the figure (the part shown as the recalculation part in the figure) has already been performed once. For example, the recalculation part ifib of (8) and (9) in the figure
(2) has already been calculated in (4) and (5).

Therefore, ifib (1), ifib
(2), ifib (3) and its calculation result are recorded as a set and recorded in an appropriate place, and if this set is searched before proceeding according to the definition of calculation and the calculation result has already been obtained. , It is possible to reduce the calculation time and space amount by replacing it with that. Generally, ifib (N + 2) is calculated by ifib
Since (N) has already been calculated in the calculation of ifib (N + 1), it does not need to be calculated again. Then, in order to calculate ifib (N + 2) after obtaining the result of ifib (N + 1), the addition is done only once, so the amount of calculation of ifib (N + 2) is in linear order. However, searching for past calculation results is fast enough,
If the amount of calculation is less than or equal to the linear order. (Usually, hashing is used for searching, so the amount of calculation for each search is a constant order. Also, since the total number of ifib (N + 2) calculations is N times, the total calculation amount is in linear order. It becomes.)

[0017]

As described above, in the method of registering past calculation results and reusing them to perform calculation processing without repeating partial recalculation, the past calculation results are If the search is sufficiently fast and the calculation amount is less than or equal to the linear order, the calculation of the Fibonacci sequence, which is naive to the memory space / time amount, can be calculated with the calculation amount of the linear order.

However, the conventional method records past calculation results, that is, a set of partial calculation fragments and their calculation results in a table or the like and reuses them. Could not be registered automatically and dynamically, and the intermediate result of calculation could not be registered and reused. The present invention has been made in consideration of the above-mentioned conventional technique, and a first object of the present invention is to associate a partial calculation fragment with a cell of a root node of a graph of intermediate calculation results, By dynamically updating the associated subgraphs with the intermediate results that have been calculated, the memory space and time required for the calculation that repeats partial recalculations can be significantly increased. An object of the present invention is to provide an optimized method and apparatus for a reduced graph reduction mechanism.

A second object of the invention is to keep registering all the computational fragments until the storage space is exhausted, and in synchronization with garbage collection, to get the maximum share of the current overall graph. By providing a method and apparatus for optimizing a graph reduction mechanism that can efficiently delete registered partial calculation fragments and reclaim storage space by deleting all registrations except is there.

[0020]

FIG. 1 shows the principle of the present invention. In the figure, 1 is a first storage means for holding an entire graph S to be reduced, and 2 is a graph S.
Hash table 2 for the hash values of all subgraphs of
The second storage means 3 stores the set of the subgraph existing in the past and the subgraph of the reduction destination which is currently reached in the second storage means 3 and stores the subgraph held in the first storage means 1. Second storage means 2 by reduction
The reduction means 4 registered in 1. is a garbage collector that collects the garbage in synchronization with the garbage collection.

In order to solve the above-mentioned problems, the invention of claim 1 of the present invention shares a graph S with a hash table 2a, obtains a hash value for a certain subgraph g3, and based on the obtained hash value, the hash table is obtained. 2a
With the pointer registered in the hash table 2a, the subgraph g having the same structure as the above subgraph g3.
1 is calculated as the reduction target subgraph g2, and the pointer of the subgraph g3 is replaced with the pointer of the reduction target subgraph g2, whereby the past calculation fragments are reused and calculation is performed without repeating partial recalculation. Is to do.

According to a second aspect of the present invention, in the first aspect of the invention, all subgraphs are continuously registered until the storage space is used up, and the current whole graph is shared at maximum in synchronization with garbage collection. All the registrations except the part that can be deleted are deleted and the storage space is collected. According to a third aspect of the present invention, there is provided a graph reduction mechanism optimizing device comprising: a first storage unit 1 for holding an entire graph S to be reduced;
The hash values of all the subgraphs of the graph S stored in the storage means 1 are stored in the hash table 2a, and a set of a subgraph existing in the past and a subgraph of the reduction destination currently reached is stored. The second storage unit 2 and the subgraph held in the first storage unit 1 are redacted, and the subgraph of the reduction destination is the second subgraph.
When it is not registered in the storage means 2, the reduction destination subgraph is associated with the original subgraph and registered in the second storage means 2.

According to a fourth aspect of the present invention, in the third aspect of the invention, all the registrations except the part necessary for maximally sharing the current entire graph are deleted in synchronization with the garbage collection. The garbage collector 4 is provided.

[0024]

As described above, not only the sharable part is found by hashing and replaced by the sharing of the pointer, but also this hash table is expanded so that the subgraph existing in the past and which subgraph it is currently reduced to are reduced. It is possible to significantly reduce the calculation time and space consumption by associating whether or not it has come and not repeating all the reductions performed in the past. Note that, until now, if none of the subgraphs have been reduced, the correspondence will be the same as before expansion.

It should be noted that, unlike the old reuse of the calculation result as described above, not only the partial calculation fragment and the set of the calculation results are stored,
The partial calculation fragment is associated with the cell of the root node of the graph of the intermediate calculation result. Moreover, since this associated subgraph forms a part of the graph to be calculated, the intermediate result dynamically calculated by direct or joint reduction of the graph, or Complete calculation results will be obtained.

However, since the subgraph is rewritten by the reduction but the cell of the root node is invariable, the latest intermediate result can always be obtained by associating the intermediate result with the cell address. However, such reuse of the calculation results results in registering a huge number of calculation fragments as the entire calculation result progresses, and consumes storage space (note that the intermediate result of each calculation is the entire calculation result). Since it is shared as a subgraph in the graph, its registration requires only one pointer storage space).

Since not all the fragments registered as described above are reused, it is necessary to delete the ones that are unlikely to be reused by some method to promote the reuse of the storage space. . However, it is very difficult to predict whether it may be reused in the future. So, instead of relying on heuristics, keep registering all the pieces of computation until you run out of storage space, and then synchronize with garbage collection to remove all but the part needed to maximize sharing of the current graph. To recover the storage space. That is, it is expected that the overhead, which is reused many times, will be recomputed even if it is deleted once, and that it will be reused again, so that the overhead is considerably reduced.

Further, since a small calculation can be performed without causing garbage collection even once, a better result can be obtained than relying on heuristics. The present invention is intended to optimize the graph reduction mechanism based on the above concept. Next, the hash technique and the registration, search, update, and deletion of calculation fragments in the present invention will be described. (1) Hash technique The graph hashing mechanism consists of a graph hash function and a registration / deletion mechanism.

Now, let g be Doug, f be the function symbol of the root node of g, and g1, g2, ..., Gn be child Dougs representing the arguments of g. Considering the hash function hash: G → N (G is a set of Doug, N is a natural number), since the graph is structured data, it is usually given in the following recursive form. hash (g) = α (h (f), hash (g1), hash (g2), ... hash (gn)), where α: N ⁺ → N and h: F → N (where N ⁺ is A finite sequence of natural numbers, where F is a set of function symbols). That is, the hash value hash (g) is the value h (f) determined by the function symbol f of the root node and the hash value hash (g
1), hash (g2), ... Given in a recursive form determined by hash (gn).

Since the hash function is for obtaining a hint for speeding up the search, it may be any arbitrary, but the calculation of the hash function itself is sufficiently fast and does not cause the overhead of the original calculation. In addition, it is desirable that the hash function be close to injective in order for the search to be performed at the highest speed. The above hash function is recursive, but in the actual calculation, the child graph is already shared by the hash, and it is enough to simplify the calculation by regarding the address of the root cell as its hash value. It is a valid hash function.

That is, the form of the function is as follows. hash (g) = α (h (f), # (g1), # (g2), ... # (gn)), where # (g) is the address of the root cell of Doug g. Also, since there are practically infinite numbers of built-in types,
It is not practical to register these values in the hash table. Therefore, the graph matching algorithm is improved so that even if two built-in type values are not on the same cell, they are considered to share the same cell when they have the same value.

Also, in the hash function, when the child graph has a built-in type value, if the value itself is used instead of the address of the cell, the built-in type data may actually have the same value. For example, they can always be regarded as sharing the same cell. Furthermore, if the hash table is divided for each function symbol, it is not necessary to calculate h (f), and the hash value is as follows.

Hash (g) = α (# (g1), # (g2), ... # (gn)), However, when gi is a built-in value, # (gi) is the value itself, that is, gi Let it be. Also, if the hash table is allocated at the beginning at once, the hash table of the function symbol that is rarely used and the hash table of the function symbol that is often used use the same memory space, which is not efficient. Therefore, the hash table is two-dimensional, and the one-dimensional partial hash table and an array of pointers to the hash table are configured, and the partial hash table is dynamically allocated when the table is needed according to the value of the hash function. To do so. (2) Registration, Retrieval, Update, and Deletion of Computation Fragment (Subgraph) FIG. 2 is a diagram for explaining the hash mechanism of the present invention. Referring to FIG. 2, registration of a computation fragment (subgraph) of the present invention. , Search, and update will be described. Note that the calculation fragments such as ifib (1), ifib (2), ifib (3) described in FIG. 10 are called subgraphs.

In FIG. 2, a large hatched area S indicates the whole graph, and it is assumed that the whole graph has already been registered and hashed.
Consider three hatched polygonal portions (graphs) A, B, and C in FIG. Further, the graph A is a graph to be reduced, the graph B is a graph of a reduction destination, and the graph C is a graph having the same hash value as the graph A.

In the figure, each graph is composed of cells as a unit, and each cell 11a, 11b, 11c has a structure shown in FIG.
, The function symbol (or the value of the built-in type, the function f is shown in the figure) normally assigned to the cell, and some pointers to the root cell of the subgraph representing the argument. P1, P2, P3, ..., A pointer Pli to the attribute list 12 assigned to the function symbol, and further, in this framework, since the graph structure is hashed, a pointer Pm for maintenance of the hash table is attached. There is.

Returning to FIG. 2, 12 is an attribute list,
Since the hash table is divided for each function, the attribute list 12 provided for each function contains a pointer Pha for tracing the entire hash table of that function. The hash table has a two-dimensional structure as described above, and the one-dimensional partial hash table 1
4a-14b and its partial hash tables 14a-1
The partial hash tables 14a to 14b are composed of an array 13 in which pointers to 4b are stored, and the pointers of the partial hash tables 14a to 14b point to a hash list 15a corresponding to a plurality of graphs.

The memory space of the hash table is
All are not pre-allocated, so if space is not allocated at the registration location, it is allocated each time. Moreover, since the same hash value may be assigned to different graphs, generally, a plurality of graphs are registered. For example, as shown in FIG. 2, the graph C is registered as a graph having a different hash structure and the same hash value as the graph A.

For registration, as shown in the figure, at the end of the hash list 15a, a hash list 15b consisting of three new elements is created and connected, and the first element 151 and the second element 151 are connected.
The pointers Pg1 and Pg2 (pointing to the same cell at the beginning) to the graph to be hashed are put in the element 152, and the empty list is put in the last element 153. And
When the graph is redacted, hash list 15
As indicated by a, the pointer Pg2 points to the reduction-destination graph (for example, graph B in the same figure). Also, when newly registering, the last element 1 above
A pointer Pg3 to a new hash list is put in 53.

In FIG. 2, when trying to hash a certain subgraph (hereinafter referred to as graph X), first,
A hash value is obtained from the subgraph X by a hash function. Next, the attribute list 12 is obtained from the root cell of the subgraph X, and the hash tables 13 and 14 of the functions of the subgraph X are obtained. Then, the pointer to the root cell of the graph X is registered at the position in the hash table corresponding to the already calculated hash value.

Here, as described above, since the memory space of the hash table is not allotted in advance, it is assigned when it is not assigned to the space to be registered. Then, when nothing is registered at the position to be registered, the subgraph X is registered, and when a hash list of another graph is registered, it is determined whether or not there is a graph having the same structure, If not, the graph X to be hashed is registered in the hash list.

That is, a graph in which the addresses of the root cells are the same or the addresses of the root cells of the graph of all the arguments are the same as those of the corresponding arguments of the graph to be registered (this is called a graph of the same structure) If it is not registered, the graph X to be hashed is registered in the hash list. For example, in the figure, when a graph C is newly registered, as described above, a new 3 is added at the end of the hash list 15a.
A hash list 15b composed of elements is created and connected, and a pointer to the root of the graph C to be registered is registered in the first elements 151 and 152 of the hash list 15b.

If a graph having the same structure is registered, the graph X to be hashed is replaced with the graph of the second element of the hash list having a pointer to this graph. In the example of FIG. 2, when trying to hash a certain graph X, if a graph A having the same structure as the graph is already registered, the second element 152 of the hash list 15a having a pointer to the graph A is present.
Replace graph X, which is to be hashed, with graph B pointed to by. The second element 152 of the hash list 15a
As will be described later, since a pointer Pg2 pointing to the graph B of the reduction destination of the graph A is registered, the graph X to be hashed is replaced by the graph B of the reduction destination by the above replacement.

The above replacement is replacement of all pointers to the root cell of the graph X (which cell does not know which cell is pointed to), which is called the indirection method (detour method). Using the method
Postpone replacement. That is, as shown in FIG. 4, pointers to the arguments (pointers P1, P in FIG.
2) is cleared, a pointer to the cell to be replaced is inserted instead, and an attribute indicating that it is used for indirection is added to the cell of the graph (cells with such an attribute are added. Is called an indirection cell).

In the above-described manner, the pointer to this cell is replaced with the pointer ahead of this cell each time this indirection cell is found while tracing the entire graph. By doing this, it is actually the same as replacing the links to all the root cells during hashing without induction.

Here, the reason why the graph of the second element of the hash list is replaced as described above is that the graph after reduction of the graph of the first element is included in this graph. When the graph is first registered, the first element and the second element of the hash list point to the same graph (for example, as shown in FIG. 3, the first element 151 and the second element of the hash list 15). Element 152 points to the same graph).

When redacting an arbitrary graph, it finds its own hash list using the maintenance pointer Pm from the root cell of the graph (the own hash list cannot be known from the root cell of the graph). ), Put a pointer to the redacted destination graph in its second element. For example, in FIG. 2, when the graph A is redacted, the hash list 15a is not known from its root cell 11a, so the hash pointer 15a is found using the maintenance pointer Pm, and the reduction destination is set to the second element 152 of the hash list 15a. The pointer to the root cell 11b of the graph B is inserted.

Further, when the subgraph of the reduced graph is reduced, the tip of the second element is
After being reduced twice, the cycle is repeated many times. As a result, the second element is indirectly and dynamically changed to the pointer to the most redacted destination. That is, the set of all the subgraphs that have been reduced in the past and the current latest latest subgraph that has been reduced is dynamically updated.

However, when updating the second element of the hash list, it is necessary to rewrite a part of the graph preceding the first element (that is, the graph to be reduced). This is because the indirection method is used, and as described above, the root cell of the graph to be redacted is used to create the graph of the redacted destination.

Therefore, before the reduction is finished, the first
It is necessary to copy the root cell of the graph preceding the element, including the pointer to the subgraph of the argument, and replace the pointer of the first element from the redacted graph to this copy. Note that there are no cells that reference this copied cell.
That is, the copied cells are garbage for the garbage collector, and are collected as garbage when the heap area is used up.

FIG. 5 is a diagram for explaining the sharing of the above-mentioned graph, which shows sharing of the graph in the above-mentioned ifib program. In the figure, if
Since ib (3) is ifib (2) + ifib (1), if the graph of ifib (3) shown in (a) of the figure is reduced, as shown in (b) of the figure, ifib (3 ) Graph is copied and becomes garbage, and its cell becomes an indirection node. Then, the indirection node contains the reduction target subgraph (in this case, ifib (2) + ifib
A pointer to the cell in (1)) is inserted. Also, as mentioned above, the first element of the hash list is the above ifib (3).
, And the second element now points to the above indirection node.

From the state shown in FIG.
When the graph of (2) is reduced, the graph of ifib (2) becomes garbage, and the indirection node has a subgraph of the reduction destination (in this case, ifib (1) + ifib (0)) cell pointer is inserted. Here, the part A surrounded by the dotted line in the figure
And B are the same graph and can be shared. Therefore,
As described above, the pointer to the graph of the part B is replaced.

FIGS. 6 and 7 are diagrams for explaining the sharing of the graph in consideration of the calculation history.
The sharing of graphs considering the calculation history in the ib program is explained. In FIG. 6A, the pointer of the root cell points to the subgraphs of ifib (2) and ifib (3), respectively, and the first and second elements of the hash lists 15a and 15b are both ifib (2). And ifib (3) point to a subgraph cell.

When the subgraph of ifib (2) is reduced from the state shown in FIG. 9A, as shown in FIG.
The cell of ifib (2) is copied to become garbage, and the pointer to the cell of the reduction target subgraph (in this case, ifib (1) + ifib (0)) is put in the indirection node. Further, as described above, the first element of the hash list 15a becomes the above garbage ifib (2).
, And the second element now points to the above indirection node. Further, the pointer to the cell of ifib (1) is put in the first element and the second element of the hash list 15c.

Further, if the subgraph of ifib (3) is reduced from the state of FIG. 7B, the cell of ifib (3) is copied and becomes garbage, as shown in FIG. The first element is garbage ifib
The cell of (3) will be pointed to, and the second element will point to the indirection node. Where ifib
(3) is reduced to the subgraphs of ifib (2) and ifib (1), but the subgraph of ifib (2) has already been registered by the reduction from Fig. 6 (a) to Fig. 6 (b). Cage,
These can be shared. Similarly, ifib (1) subgraphs are already registered, ifib (1) subgraphs can be shared. Therefore, the ifib (2) subgraph generated by the ifib (3) reduction is replaced with the already registered ifib (2) subgraph.

That is, in the cell pointed to by the indirection node generated by the reduction of ifib (3), the tip of the pointer pointing to the subgraph of ifib (2) is already registered as shown in FIG. It is replaced by the subgraph in (2). Similarly, the ifib (1) subgraph generated by the ifib (3) reduction is replaced by the already registered ifib (1) subgraph. (3) Deletion of calculation fragment (subgraph) As described above, before the reduction ends, the root cell of the graph preceding the first element is copied including the pointer to the subgraph of the argument, and the The pointer is changed from the redacted graph to this copy, and the copied cell is collected as garbage when the heap area is exhausted.

For example, in FIG. 5C, the ifib (2) and ifib (3) cells that have become garbage are collected. As a result, the part necessary for maximally sharing the current graph, that is, the pointers of the first element 151 and the second element 152 of the hash list 15 shown in FIG. 3 both point to the same cell. All registrations are deleted except for.

However, as it is, a pointer to the collected cells (for example, ifib
(2) and ifib (3) cell pointers) will remain, and inconsistency will occur in later reduction. Therefore, at the time of garbage collection, it is necessary to delete the enlit of the hash table that has the pointer to the cell to be collected as garbage.

Hash maintenance pointer Pm for each cell
The reason is that this deletion is performed at high speed. That is, when a garbage collector finds a garbage cell, it will follow the hash's maintenance pointer and get a pointer to the hash list pointing to that cell. Then replace the pointer to the next list in the hash list with the pointer to the next next list.

For example, in FIG. 2, assuming that the cell 11a is a garbage table, the hash table 14b that points to the hash list 15a by tracing the maintenance pointer Pm.
Of the hash list 15a is replaced with a pointer pointing to the hash list 15b next to the hash list 15a. As a result, the enlit of the hash table having the pointer to the cell collected as the garbage is deleted.

Also, each time a link to an indirection cell is found, the link destination is replaced with the cell ahead of the cell, so that it becomes the same as when there is no indirection cell. As I explained, in detail, when changing this link, the address of the link destination changes. That is, in the present invention, as described above, since the hash function based on the address of the root cell of the subgraph is used, the hash values of all subgraphs including this subgraph are recalculated, and the location to register is calculated. If you don't move, unnecessary hash will be accumulated in the hash and the efficiency of the calculation will decrease.

However, since the cost of this recalculation is enormous, the subgraph is rehashed so that unacceptably unnecessary entries do not remain. Therefore, only the subgraph rooted at the cell having the link to the indirection cell is rehashed. If replacement of this subgraph does not occur in this hash, that is, if the address of the root does not change, the hash value of the subgraph including it remains unchanged even if it is recalculated, and recalculation is not necessary.

On the other hand, when replacement of a subgraph occurs, the entire graph cannot always be kept at the maximum shared structure Doug unless the subgraph including it is rehashed. This means that when you have a subgraph that is not registered in the hashtable, and later you have another subgraph with the same structure, it will not be shared with the previous subgraph, and this previous subgraph will If you don't rehash it, you'll never be shared.

However, even in this case, the hash of the outer graph including this subgraph is valid. That is,
This is because the addresses of the cells involved in the hash of these crafts have not changed. The present invention is based on the above principle and solves the above problems. In the invention of claim 1 of the present invention, a graph S is shared by a hash table 2a, and a hash value is obtained for a certain subgraph g3. Based on the obtained hash value, a pointer registered in the hash table 2a with reference to the hash table 2a is used to obtain the reduction target subgraph g2 of the subgraph g1 having the same structure as the subgraph g3.
Since the pointer of the subgraph g3 is replaced with the pointer g2 of the reduction target subgraph, it is possible to reuse the past calculation fragment and perform the calculation without repeating the partial recalculation. It is possible to significantly reduce the memory space and the amount of time required for the calculation that repeats the recalculation.

In the invention of claim 2 of the present invention, in the invention of claim 1, all subgraphs are continuously registered until the storage space is used up, and the current entire graph is maximized in synchronization with garbage collection. The storage space is collected by deleting all the registrations except the sharable part, so that the overhead can be reduced and the storage space can be collected efficiently without resorting to heuristics.

In the invention of claim 3 of the present invention, the optimization device of the graph reduction mechanism is provided with the first storage means 1 for holding the entire graph S to be reduced.
And the hash values of all subgraphs of the graph S stored in the first storage unit 1 are stored in the hash table 2a, and the subgraphs that existed in the past and the subgraphs of the reduction destination that are currently reached are stored. The second storage unit 2 for storing the set and the subgraph held in the first storage unit 1 are reduced, and when the reduction-target subgraph is not registered in the second storage unit 2, the reduction destination Since it is composed of the reduction means 3 which registers the subgraph in the second storage means 2 in association with the original subgraph, all the subgraphs reduced in the past and the latest reduction destination subgraph. The set can be updated dynamically, and the memory space and the amount of time when reusing past calculation fragments to perform calculations can be significantly reduced. That.

In the invention of claim 4 of the present invention, in the invention of claim 3, all the registrations except the part necessary for maximally sharing the current entire graph are synchronized with the garbage collection. Since the garbage collector 4 for deleting is provided, the overhead can be reduced and the storage space can be efficiently collected without depending on the heuristic.

[0067]

FIG. 8 is a diagram showing an embodiment of the present invention, in which reference numeral 21 is a first storage device for holding an entire graph (cell unit) to be rewritten, 22.
Is a second storage device that holds a rewrite rule (or a rule that has undergone some kind of conversion for speeding up search), and 23 is a third storage device according to the present invention, and the storage device 23 Exchanges data while communicating between a reduction device 25 and a garbage collector 26, which will be described later, stores all subgraphs of the graph stored in the first storage device 21 in a hash table, and exists in the past. It remembers the set of subgraphs and the previous subgraphs it is currently being rewritten to.

24 is an attribute (function symbol,
A fourth storage device for storing type information and various hash tables), a reduction device 25 for rewriting a graph while matching a rewriting rule with a subgraph, 2
A garbage collector 6 collects the garbage at the time of garbage collection. Although the storage device is divided into the first to fourth storage devices in the figure, the storage device does not necessarily have to be provided with four devices, and is physically one device, and You may use it separately.

Next, the operation of the embodiment of the present invention shown in FIG. 8 will be described. The apparatus of this embodiment is a reduction apparatus 2
5, peripheral storage devices 21, 22, 23, 24
Work while communicating with. Also, the garbage collector 26
Operates independently of the reduction device 25, detects that a cell in the storage device 21 has been exhausted by the reduction device 25, and automatically refers to no other cell in this cell, that is, Garbage is collected and made available again.

FIG. 9 is a flow chart showing the operation of the reduction device 25 in this embodiment, and the operation of the reduction device 25 will be described with reference to the figure. Note that FIG.
Although not shown in the figure, the reduction device 26 is provided with an input / output device through which the storage devices 21, 22, 22 are connected.
Data is exchanged with 23 and 24.

The reduction device 26 first initializes all cells of the first storage device 21 to an available state and loads the rewrite rule into the second storage device 22, as shown in step S1 of FIG. Then, the initial graph (graph to be rewritten) is loaded. Also, accompanying this, various attributes are loaded into the fourth storage device 24. In step S2, all subgraphs of the initial graph of the first storage device 21 are registered in the hash table of the third storage device.

In step S3, the reduction device 26 finds a redactable subgraph from the storage device 21, and in step S4, the second storage means 22.
Refer to the rule of and reduce the subgraph by the rule that matches it. In step S5, it is checked whether or not the reduced partial graph is already registered in the hash table of the storage device 23, and if it is not registered, it is registered.

Then, as a result of the hash, the destination of the further reduction of the subgraph, which is paired with the subgraph, is returned to the storage device 23. Here, as described above, after the rewritten graph is registered, it is necessary to recalculate the rehash of the graph including the graph. When the above process is repeated and there is no more part that can be reduced, in step S7, all the graphs that have been rewritten are output and the calculation ends. As described above, when the reduction is performed and it is detected that there are no available cells, the garbage collector 26
Collects garbage, communicates with the second storage device 23, and deletes the garbage from the hash table in which it is registered.

[0074]

As described above, according to the present invention, the memory space and time required for repeating partial recalculation can be significantly reduced without relying on heuristics. For example, to calculate a naive Fibonacci sequence with O (2 ^N ) memory space and time amount, the problem size N is small, the hash table can be searched almost in a certain time, and the garbage collection can be performed during the calculation. If it does not occur, it is possible to perform the calculation on the order of O (N) dynamically, that is, without conversion by the program.

[Brief description of drawings]

FIG. 1 is a principle diagram of the present invention.

FIG. 2 is a diagram illustrating a hash mechanism of the present invention.

FIG. 3 is a diagram showing a structure of cells of a graph.

FIG. 4 is a diagram illustrating replacement by the indirection method.

FIG. 5 is a diagram illustrating sharing of graphs in the present invention.

FIG. 6 is a diagram illustrating sharing of a graph using a calculation history.

FIG. 7 is a diagram (continuation) illustrating sharing of a graph using a calculation history.

FIG. 8 is a diagram showing a configuration of an exemplary embodiment of the present invention.

FIG. 9 is a flowchart showing the operation of the embodiment of the present invention.

FIG. 10 is a diagram showing an example of a calculation tree for recalculation.

[Explanation of symbols]

 1 1st memory | storage means 2 2nd memory | storage means 2a Hash table 3 Reduction means 4 Garbage collector 12 Attribute list 11a, 11b, 11c Cell 21 1st memory | storage device 22 2nd memory | storage device 23 3rd memory | storage device 24 4th 4 storage device 25 reduction device 26 garbage collector g1, g2, g3 partial graph S graph

Claims (4)

[Claims] 1. A graph (S) using a hash table (2a)
Is shared, a hash value is calculated for a certain subgraph (g3), and based on the calculated hash value, the hash table (2a) is referred to and the pointer registered in the hash table (2a) is used. ), Find the reduction target subgraph (g2) of the subgraph (g1), and replace the pointer of the above subgraph (g3) with the pointer of the reduction target subgraph (g2) A method for optimizing a graph reduction mechanism, which is characterized by reusing and recalculating without repeating partial recalculation. 2. A storage space in which all subgraphs are continuously registered until the storage space is used up, and all registrations are deleted in synchronization with garbage collection except for a portion where the current whole graph can be shared to the maximum extent. The method for optimizing a graph reduction mechanism according to claim 1, wherein 3. An overall graph subject to reduction
A first storage means (1) holding (S) and hash values of all subgraphs of the graph (S) stored in the first storage means (1) are stored in a hash table (2a). , A second storage means (2) for storing a set of a subgraph existing in the past and a subgraph of the reduction destination that has arrived now, and the subgraph held in the first storage means (1) If the reduction-destination subgraph is not registered in the second storage means (2), the reduction-destination subgraph is associated with the original subgraph and the second storage means
An optimization device for a graph reduction mechanism, comprising: a reduction means (3) registered in (2). 4. A garbage collector (4) for synchronizing all garbage collections and deleting all registrations except those necessary for maximally sharing the current whole graph. An optimization device of the graph reduction mechanism according to item 3.