JPH0738168B2 - Data processing device - Google Patents

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a single processor and multiprocessor configuration in which a processing system for executing a program in a programming language such as a logical type or a functional type that requires garbage collection processing for collecting unnecessary data areas is implemented. The present invention relates to a data processing device.

[0002]

2. Description of the Related Art The hardware configuration of a central processing unit of a general computer is such that an arithmetic and logic unit, a group of registers for frequently and temporarily holding data to be processed, and all normal data are recorded. It is composed of a main memory controller for accessing the main memory. These resources are communicated with each other via a data bus and an address bus, and their processing operation is performed by a control unit of wired logic or microprogram.

How the main memory is managed by the processing system is largely determined by whether the programming language is a procedural type, a functional type, a logical type, or the like. In addition, various approaches have been attempted as a main memory management method for increasing the efficiency in the processing system of various programming languages. Recently, in developing a processing system for a programming language, a main memory management method has been designed in consideration of the characteristics of main memory consumption unique to the processing of each programming language.

In the work of programming languages,
If the structure of the data to be handled does not change, such as in numerical calculation, the programmer does not have to do much work for allocating the used area in the main memory, but like symbol processing, the data structure does not change as the calculation progresses. When dealing with objects that change themselves, managing main memory can be a daunting task. Therefore, in a processing system of a functional or logical programming language, a process of collecting a used data area is necessary to continue execution. The processing is a garbage collection function, and that function is an important item to be considered in the design of the main memory management method.

As a method for executing the function of garbage collection, a collective method is generally performed after all available main memory has been consumed. The processing time of this batch type garbage collection is usually on the order of several seconds to several minutes in order to access the main memory over a wide range, and the central processing unit is occupied by the garbage collection processing. It means that the normal calculation process is interrupted for a considerably long time. The interruption of the normal execution process caused by the long processing time of the garbage collection makes real-time processing practically impossible, makes the interactive operation uncomfortable, and influences the overall execution performance. Further, in the case of a data processor having a multiprocessor configuration, one processor keeps silent for a long time in response to a processing request from another processor due to collective garbage collection, which affects the execution performance of the entire multiprocessor. Further, in the worst case, not only another processor waits for a response process to the processing request, but also another processor may perform an extra process that does not need to be performed if the response process is early.

An example has also been announced in which this collective garbage collection process is executed in parallel by a processor different from the main processor. This is to improve the independence of each processing by dividing the main memory space into blocks and performing garbage collection processing for each block. However, there is an overhead for dividing the main memory space into blocks, and due to the characteristics of the programming language, handling of the main memory space in units of blocks is not always appropriate, and the performance of the processing system is not always appropriate. Since the superiority and inferiority of is different, it cannot be said that it is a universal method for processing systems in all programming languages.
([1]: Japanese Patent Laid-Open Publication No. Sho 61-105653, a computer storage device having a parallel garbage collection function independent of a connected user processor).

[0007]

When a batch type garbage collection process is performed by a certain processor, the central processing unit is occupied by the garbage collection process, and a processing request from another processor of a multiprocessor configuration and normal execution of its own processor are performed. No processing will be accepted. In the case of a single processor, this does not cause the central processing unit to execute normal processing for a long time, and in the case of a multiprocessor, the processing requests of the peripheral processors are completely ignored and the execution efficiency of the peripheral processors is adversely affected. give.

The present invention has been made in order to solve the above-mentioned problems, and even when the processor is performing a batch type garbage collection process, it is normally executed without affecting the garbage collection process. The purpose of the present invention is to obtain a data processing device that can perform processing independently in parallel and reduce the overhead to the overall execution performance due to batch type garbage collection.

[0009]

As shown in FIG. 1, a data processor according to the first aspect of the present invention stores a main memory 3 in which a heap area is divided into an old area and a new area, and a main memory. A first central processing unit and a second central processing unit which are connected so as to be accessed independently at the same time are provided, and the first central processing unit (central processing unit 1 dedicated to normal execution processing) includes response processing to an external processor. Then, the second central processing unit (collective central processing unit 2 for dedicated garbage collection processing) executes the active data structure for each execution-type data structure in the order of execution priority in the main memory. By performing a collective garbage collection process for eliminating unnecessary data areas by copying from the old area 30 of the heap area to the new area 31, during the garbage collection processing, the second central processing is performed. Processing device is given priority to the normal processing of the first central processing unit, without the second central processing unit interferes with the processing of the first central processing unit,
Execution processing including the above copy is performed in the order of execution priority.
In the data processor according to the second aspect of the present invention, as shown in FIG. 5, all the parts of the execution type data structure in which the second central processing unit executes calculation during the batch type garbage collection process are stored in the main memory. Of the execution type data structure for executing the above calculation, the first central processing unit executes the normal processing of the data structure on the new area of the main memory when the data is already copied to the new area. If the part has not been completely copied to the new area, the first central processing unit newly builds a data structure on the new area that can be executed after the batch garbage collection processing. . As shown in FIG. 6, in the data processor according to the third aspect of the present invention, the second central processor has an execution type data structure for executing calculations during a batch type garbage collection process, which is a main memory. Even if the data is distributed in the area and copied in an incomplete state, if the execution type data structure calculation is executed and the data structure is changed due to the calculation execution, the newly allocated data structure is While constructing in the new area, the garbage collection copy operation is performed on the data structure in the old area while paying attention to the data structure.

[0010]

In the data processor according to the first aspect of the present invention, two central processing units that simultaneously access the main memory are prepared in order to perform the batch type garbage collection and the normal execution process. The second central processing unit is dedicated to batch garbage collection, and the first central processing unit is dedicated to normal execution processing. The hardware of the central processing unit is configured by circuits such as dedicated cache memories and register groups so that the respective processes are optimally performed, and it is not necessary to have the same configuration. When the collective garbage collection is activated, the second central processing unit for garbage collection preferentially performs the collective garbage collection processing while accessing the main memory. First
The central processing unit of (1) performs normal execution processing by accessing the active data structure so as not to interfere with the batch type garbage collection processing. The processes that do not interfere with the batch garbage collection process are quite limited.
Since operations such as unification, suspension, and resume that change the data structure can be executed only for the data in the state after the garbage collection, the active data structure in the state before the garbage collection cannot be executed. Generate an executable data structure that performs these processes so that it can be executed after the batch garbage collection. However, the method of changing the data structure of the state during the garbage collection can be designed even though the processing becomes complicated. Further, the batch type garbage collection algorithm by the data processing device according to the first aspect of the present invention employs a copy method that makes it easy to confirm the logical validity of the data structure even during the garbage collection process. The normal execution processing executed in parallel is copied from the old area to the new area in order from the execution-type data structure with the highest execution priority so that the normal execution processing can be performed from the state after the garbage collection. As described above, the normal execution process can be performed in parallel with the garbage collection process with relatively high efficiency. In the data processor according to the second aspect of the present invention, when the second central processing unit copies from the old area to the new area, when all parts of the execution type data structure for executing calculation have been copied, When one central processing unit executes normal processing in the new area with the above data structure and not all parts of the execution type data structure for performing calculation have been copied, the first central processing unit operates as the second central processing unit. The processing can be executed after the batch type garbage collection processing by the processing device. The data processing device according to the third aspect of the present invention calculates the execution-type data structure even if the data is copied incompletely in both the old and new areas by the second central processing unit. Also, when the data structure is changed due to the calculation, the newly allocated data structure is constructed in the new area. Further, the copy operation from the upper Symbol old area of the batch-type garbage collection process by the second central processing unit to said new region
To do.

[0011]

DESCRIPTION OF THE PREFERRED EMBODIMENTS An embodiment of the present invention will be described below with reference to the drawings. FIG. 1 is a schematic configuration diagram showing a data processing device implementing two central processing units dedicated to normal execution processing and batch garbage collection (hereinafter abbreviated as GC) processing according to an embodiment of the first invention, 2 is a schematic configuration diagram of the inside of the central processing unit mounted in the data processing apparatus of FIG.
3 is a conceptual diagram of copy-type garbage collection in the KL1 processing system of the data processing apparatus of FIG. 1, and FIG.
FIG. 6 is a diagram showing the order of copying goal records in a goal stack, which is a marking route, of garbage collection in the KL1 processing system of the data processing apparatus of FIG.

The programming language of the processing system implemented by the data processing device realized below is a parallel logic language KL1.
Is. KL1 (Nuclear Language 1st Edition) is a parallel logic type language GHC (Guarded Ho) as a programming language executed by a parallel inference computer developed in the 5th generation computer project planned and promoted by the Ministry of International Trade and Industry.
rn Clauses). The execution model of the KL1 processing system is such that one unit of the execution type of processing is
Reasonably valid data structure (ie active data
( 1 ) as a goal, the set of goals connected by AND relations obtained in the execution process of the program is stored in the execution waiting pool, and the central processing unit takes out the goals from the execution waiting pool one by one, The execution or reduction of is tried. Goal execution is to perform calculation and unification processing on the argument data. Along with the execution of this goal, a new goal is generated and stored in the execution waiting pool, or it is held in the execution suspension pool because the argument data required for goal execution is undefined. The execution standby pool constitutes a stack of goals, and the execution suspension pool is realized by a mechanism in which goals are bound to the variable that caused the suspension.
([2]: New Generation Computer Technology Development Organization, Computer Basic Technology Development Results Report, Inference Subsystem, March 1989 ) In addition, the above "Active data structure
As an example of the data structure that means "structure", one number
List structure and vector as well as value data and character data
It includes various forms such as structure.

Realization of the goal pool on the processor is carried out by management by a table called a goal stack entry table. Goals are stored in the main memory as an execution type data structure called a goal record, and this goal stack entry table is a table having an entry corresponding to the execution priority of this goal record, as shown in FIG. That is, the goal stack entry table 11 is arranged in order from the entry 40 having a high priority to the entries 41, 42, and 43 having a low priority, and goal records are arranged in a chain in each entry. There is. Entry 40 contains goal records 12, 12
, Entry 41 has goal records 12-12,
Entry 42 has goal record 12 and entry 43
Goal records 12 and 12 are lined up.

The central processing unit of the processor takes out one top goal record from the goal stack having the highest execution priority, reads this goal record information into the environment register group, and executes arithmetic logic operation and unification. I do. Execution of this goal may create a new goal record and may also push the goal record to the same goal stack, or it may be consumed and a new goal record may be retrieved from the goal stack.

A data processing device according to an embodiment of the first invention is a multiprocessor type data processing device in which two central processing devices share access to a main memory and a schematic diagram of the configuration thereof is shown. 1 is shown. That is, in FIG. 1, 1 is a central processing unit dedicated to normal execution processing as a first central processing unit (hereinafter referred to as normal processing unit), 2 is a central processing dedicated to batch type garbage collection processing as a second central processing unit Device (hereinafter referred to as GC (garbage collection) processing device) 3, main memory, 4
Is a cache memory, 5 is a main memory data bus, 30 is an old area of the heap area, and 31 is a new area of the heap area.

The above two central processing units are each constructed as shown in FIG. In FIG. 2, 6 is A
A main processing unit including an LU (arithmetic logic circuit), a micro controller, and a tag processing unit, 7 is a register group including an environment information register, an argument register, and a general-purpose register, 8 is a main including a cache memory, and a TLB (translation index buffer). The storage control unit 9 is a cache data bus. The central processing unit having the above-mentioned configuration is capable of executing the processing system of the parallel programming language KL1. The central processing unit is provided with a tag for discriminating the type of the data, and the data type can be speeded up by the tag. It incorporates hardware that can perform other processing.

When the batch type garbage collection is activated, the GC processing unit 2 preferentially performs the copy type garbage collection processing. The algorithm of the copy method of garbage collection is widely known, and FIG. 3 shows a conceptual diagram of the copy status of the data structure in the old and new areas in this KL1 processing system. In FIG. 3, the old area 30 to the new area 31
8 shows a situation in which the goal records 12A to 12D are copied according to the priority order of the goal stack entry table 11. Here, the heap area to be subjected to the collective garbage collection process is divided into two areas, new and old, and the goal stack entry table 11 is allocated on the main memory as a part of the system area other than the heap area. The marking route of the copying method according to the first aspect of the invention, that is, the order of data to be copied follows the order of execution priority of goal records as shown in FIG.

At the same time that the GC processing device 2 performs the copy type garbage collection process, the normal processing device 1 executes the goals in descending order of execution priority. Since the contents of the logical data structure of each goal record can be grasped by the copy method before or after the copying, the GC processor 2 is performing the garbage collection. Also, the normal processing device 1 can execute an arbitrary goal record. Even in the case of the multiprocessor configuration, the request processing from the external processor can be executed independently of the garbage collection processing.

During the batch type garbage collection process of this copy method, even if the complete copying of the data structure is not completed, the logical contents are logically accessed regardless of the marking route of either the old or new area. Can read the exact same data structure that is correct. Whether or not each data cell has been copied in the process of copying partial data cells one by one from the old area to the new area with the active data structure by the batch type garbage collection processing of this copy method Can be found by examining the data cell.

FIG. 5 shows a state in the middle of performing the garbage collection copy processing in the data processing apparatus according to the embodiment of the second invention. In FIG. 5, there are active goal records 12A, 12B, 12C, the goal records 12A, 12B are copied from the old area 30 to the new area 31, and the data cell 2 referred to by the goal record 12B.
The copy of 0 indicates that the copy has not been performed yet. Second
In the case of the data processing device according to the invention, the processing to be executed differs depending on the three states of the goal records 12A, 12B and 12C. In the goal record 12A, since the goal record itself is first copied to the new area, it is checked whether the contents of each goal information are already copied, and since it is already copied, the goal is executed. In the goal record 12B, since the copy of the goal information to be referred to is not done yet, the goal execution processing is limited. In other words, the process that causes a change in the data structure creates an execution-type goal record to be executed after garbage collection, and makes the execution process wait. In the goal record 12C, the goal record itself is not copied, but the goal information to be referenced is copied, so that the goal execution can be performed without limitation as in the goal record 12A.

However, in the case of the data processing apparatus according to the second aspect of the present invention, if all the data structures belonging to the goal record to be executed have not been copied to the new area, the execution process involving a change in the data structure will be a garbage collection process. Not done for simplicity. Here, the execution process involving the data structure change is a process such as unification, suspend, and resume, and a goal record for directly performing unification is newly generated in a new area,
Execute after garbage collection processing.

On the other hand, if the GC processing device 2 starts copying a little before the normal processing device 1 starts executing, the normal processing device 1 can execute the goal record after copying. This is because goal records are copied in order of execution priority, and after copying, the situation is close to pipeline processing in which execution is performed. In general, it is not possible to execute all the goal records during the processing time of the batch type garbage collection, so as the copying of the goal records progresses, the goal execution only accesses the post-copy. Therefore, it is expected that the goal record before the copy is rarely accessed.

FIG. 6 shows a situation in which the data processor according to the third embodiment of the present invention separately accesses the new area.
In FIG. 6, 20 is a pointer (NH
P: New Heap Pointer). In order for the normal processing device 1 and the GC processing device 2 to independently write to the new area, if the new processing area is to be accessed as a single new area by both processing devices,
It is necessary to update the pointer pointing to the top NHP of the new area independently, and it is locked so as not to allow access to other processing devices until the top position of the new area is read and updated. It is necessary to keep However, if the new area of the heap is divided into two and the allocation of the new data structure of the normal processing device 1 is distinguished from the area of the copy destination, it is not necessary to use the common top pointer.

As described above, in the first to third data processing devices, the normal execution process can be simultaneously performed during the batch garbage collection process, and the normal execution can be performed for a long time. The processing is not delayed, and the execution performance is not deteriorated by delaying the request processing of the external processor.

[0025]

As described above, according to the first aspect of the present invention,
Since the second central processing unit dedicated to the batch garbage collection processing is provided, the parallel execution method of the batch garbage collection processing and the normal execution processing that is realized does not deteriorate the execution performance of the batch garbage collection at all. Normal execution processing can be executed efficiently in parallel.In addition, the batch type garbage collection of the copy method is adopted, and since the execution type data structure that you want to execute in normal execution processing is sequentially copied to the new area, There is an effect that the execution process can be performed without waiting for a long time. According to the second aspect of the present invention, since the execution-type data structure is made to correspond to the processing state of the copy operation by the batch-type garbage collection process, the same data structure can be obtained by copying the active data structure once. Is rarely accessed. In other words, most of the data structures that perform normal execution processing are basically already copied to the new area, and even when the execution-type data structure after the garbage collection processing is generated in the new area, the new area to be copied by the garbage collection Since there is a difference, the contention for access to the main memory is considerably reduced, and there is an effect that an efficient multiprocessing method can be obtained. According to the third aspect of the present invention, even if the copies are incomplete in both the old and new areas,
Further, since the structure is adapted even when the data structure is changed, there is an effect of improving the execution performance.

[Brief description of drawings]

FIG. 1 is a schematic configuration diagram showing a data processing device mounting two central processing units dedicated to normal execution processing and batch garbage collection processing according to an embodiment of the first invention.

FIG. 2 is a schematic configuration diagram of the inside of a central processing unit mounted in the data processing device of FIG.

FIG. 3 is a conceptual diagram of a copy type garbage collection in the KL1 processing system of the data processing apparatus of FIG.

4 is a diagram showing the order of copying goal records in a goal stack, which is a marking route for garbage collection in the KL1 processing system of the data processing apparatus of FIG.

FIG. 5 is a diagram showing a process in which the data structure of the KL1 processing system in the embodiment of the second invention is being copied by the garbage collection of the copy method.

FIG. 6 is a diagram showing an operation of updating a top pointer of a new area when a normal processing device and a GC processing device according to an embodiment of the third invention allocate a data structure to the new area.

[Explanation of symbols]

 1 Central processing unit dedicated to normal execution processing 2 Central processing unit dedicated to batch type garbage collection processing 3 Main memory 4 Cache memory 5 Main memory data bus 6 Main processing unit 7 Register group 8 Main memory control unit 9 Cache data bus 11 Goal stack entry table 12 gold record 20 register

Claims (3)

[Claims] 1. A main memory in which a heap area is divided into an old area and a new area, and an external processor connected to the main memory.
First central processing unit that performs normal processing including response processing to
And a first central processing unit connected to the main memory
At the same time, the main memory can be independently accessed.
Run one valid data structure for each run-type data structure
According to the order of priority, the old heap area on the main memory is
Unnecessary data area by copying from area to new area
Second batch type garbage collection process to solve the problem
And a second central processing unit,
During the batch type garbage collection process, the first
A data processing device, characterized in that it executes an execution process including the copy in the order of the execution priority in preference to the normal process of the central processing unit. 2. The first central processing unit, wherein the second central processing unit during the collective garbage collection process,
If all portions of the data structure at run type to perform calculations is copied to the new area of the main memory, it executes the normal processing of the upper Symbol data structures in the main memory of the new region on, perform the above calculations If all parts of the execution type of data structure that has not yet been copied to a completely new area, the data structure can be executed after the processing of the upper Symbol batch-type garbage collection to the new above-mentioned new area on the The data processing device according to claim 1, wherein the data processing device is constructed. 3. In the second central processing unit, an execution type data structure for executing a calculation during a batch type garbage collection process is distributed to both the old and new areas of the main memory and copied in an incomplete state. Also, when the execution type data structure is calculated and the data structure is changed according to the above calculation, the newly allocated data structure is constructed in the above new area and the copy operation of the batch type garbage collection process is performed as described above. The data structure of the old area is executed while paying attention to the data structure.
The data processing device according to the item.