JPH0437457B2 - - Google Patents

Description

[Detailed description of the invention] [Table of contents] Overview Industrial application fields Prior art Problems to be solved by the invention Means for solving the problems Effects Examples Effects of the invention [Summary] Collection of unnecessary data In a multi-processor system that uses a reference count accumulator, a request is made to the processor holding the data to update the reference count of data existing in other processors by sending a message to change the reference count. In the reference number updating device, each processor includes a local reference number accumulating means for accumulating the number of references from its own processor to data held by other processors, and a cumulative value of the local reference number accumulating means is zero. A message creating means is provided for creating a message indicating that the number of references from the own processor to the corresponding other processor has become zero when the number of references from the own processor to the corresponding other processor has become zero, and when updating the local reference count accumulating means. , when the value of the reference count accumulation means has a non-zero value, no communication is performed to the corresponding other processor, and only when the value of the reference count accumulation means becomes zero, the reference count is changed to the corresponding other processor. To make it possible to greatly reduce the number of reference count update request messages exchanged between processors by configuring to transmit a message for a request.

[Industrial application field]

This invention is in the field of artificial intelligence, sometimes called LISP,
Languages suitable for artificial intelligence such as Prolog and Small talk,
It relates to high-performance processing systems suitable for expert systems, etc., and more specifically, collection of unnecessary data (garbage collection) in multi-processor systems having multiple processors.
Regarding the system.

[Conventional technology]

Current computers, known as von Neumann machines, can perform numerical calculations and string processing at high speed, but are not good at processes that involve human intelligence, such as inference. For this reason, list processing-oriented data flow machines, for example, have been proposed as computers suitable for artificial intelligence, and languages such as LISP and Prolog have been proposed as languages suitable for these machines.

Execution in a data flow machine is based on an execution principle called data-driven.
It has features not found in normal von Neumann computers. For example, the amount of processing is enormous and includes the possibility of parallel processing, and there is no concept of memory addresses in data management, and memory is allocated and released at runtime.

FIG. 4 schematically shows the situation at this time.

The memory space 40 of processing element #0 including a CPU and memory includes a large number of memory cells 41, 42,
43 is allocated to each cell, and the next cell allocated to each cell is indicated by pointers 44 and 45 at the time of actual execution. Each cell 41, 42, 43 is provided with a reference counter 46 for indicating the presence/absence and number of pointers, and represents the use state of the own cell. For example, memory cell 41 is referenced by memory cells 42 and 43, so reference counter 46 of memory cell 41 indicates 2. Data is stored in this memory cell.

The pointer from this cell is the same in the case of so-called parallel processing where many CPUs are installed in parallel.
The presence or absence of pointers from memory cells in other processing elements is also counted. For example, in Figure 4,
For memory cell 41 of processing element #0, broken line 48
If there is a reference from the cell 47 of processing element #1 as shown in , the counter becomes "3".

In such machines, as mentioned above, memory is allocated during execution and released each time, so it is not known in advance how much memory will be needed for one process. Therefore, it is essential to make the released cells, ie, the data that are no longer needed, usable again. For this reason,
An automatic space management system called a garbage collector is provided.

In addition to the bulk garbage collector, which collects all unnecessary data (i.e., cells) after performing a predetermined process, the garbage collector also has a reference counter (reference counter) for each cell as described above. A reference count accumulation unit) is provided to detect when the reference count reaches zero and collect the data as soon as it is no longer needed.
There is a counter method. Since batch garbage collection has the disadvantage that processing is interrupted at that time, a reference count method that does not have this disadvantage is currently attracting attention.

However, in a multiprocessor system equipped with multiple processing elements, when garbage collection is performed using the reference count method, a problem arises in that most of the communication between processors becomes a request message for updating the reference count. You will have points.

In order to solve the above-mentioned problems in multi-processor systems, (1) A network dedicated to reference count update messages is established.

(2) Provide a buffering device for reference count update messages. That is, a method has been proposed in which, when an update request is received, instead of communicating for update immediately, the request is stored in a buffering device for a certain period of time and then communicated all at once.

[Problem that the invention seeks to solve]

However, among the above methods, in the method (1) that provides a dedicated network, messages other than the reference count update message can be communicated relatively efficiently due to the provision of the network, but the reference count update message No essential changes were made to the text,
The network dedicated to the reference count update message still has the problem of being punctured.

In addition, in the method (2) of providing a buffering device, the update message sent from the own processor is not immediately sent, but is stored in a dedicated buffer, so the opposite message (request for increase versus request for decrease) is stored in a dedicated buffer. )
When a request comes, the two messages are canceled out and lost, or the n increase request messages are combined into one n increase request message.
However, on the other hand, there is a problem in that the characteristic of immediate collection, which is a major feature of the reference count method, is lost. become.

The present invention has been made in order to solve the above-mentioned problems, and it can be used in a multi-processor system using a garbage collection collector based on the number-of-reference method without impairing the immediate collection performance of the number-of-reference method. It is an object of the present invention to provide a reference count update device capable of reducing the amount of reference count update messages that run on a network between processors.

[Means for solving problems]

In order to solve the above-mentioned problems, the present invention provides a multi-processor system consisting of a plurality of processors, in which each processor has a local reference count accumulator ( (indicates only the number of references from within the own processor).

FIG. 1 is a drawing showing the principle of the invention.
In the figure, #0, #1, #2, and #3 are processor units each including an execution unit (CPU) not shown, and in particular, their memory spaces are schematically shown. Each processor unit has memory cells 1, 2, and 2 that hold data.
3, 4, 5, 6, and 7 are provided, and each memory cell is provided with a reference counter (reference number accumulator) in the conventional manner. Additionally, a local reference count accumulator is provided in each processor. In Figure 1, processor unit #0
Reference count accumulator 1 provided in memory cell 1 of
-1, indicating that local reference count accumulators 8 and 9 are provided in processor unit #1 and processor unit #2. Then, the number of references to cell 1 in processor unit #1 is registered in this local reference number accumulator 8,
This is collectively referred to as a pointer to cell 1. The same applies to the number of references to processor #2. For one cell, the number of references from other processor units is treated as "the number of other processors making references" and is registered in the reference number accumulator 1-1. In the example of FIG. 1, the number of references is "4" including references within the own processor. Changes in the number of references to other processors are limited to updating only the local accumulator, and only when this local accumulator reaches 0, the number of references to the processor that holds the data is updated. Request a reduction.

[Effect]

As described above, in the present invention, the number of references to data held in a memory cell in another processor can be changed by changing the number of references to data held in a memory cell in another processor, unless the number of references from that processor becomes zero. This is done in the updating process of the target reference count accumulator.
Therefore, unless the number of references reaches zero, a message requesting an update of the number of references is not sent between the processors, so that the amount of communication between the processors can be greatly reduced. Moreover, the speed of collecting unnecessary data is maintained by the reference count method.

〔Example〕

An embodiment of the present invention will be described below with reference to FIGS. 2 and 3.

First, the principle of the reference count update method according to the present invention will be explained.

In this invention, in order to reduce the number of reference update messages, the number of references (content held by the reference number accumulation section) is changed as follows.

Number of references = number of references from within its own processor + number of other processors that are making references, and each processor has a local reference number accumulator (self) for data held by other processors within its own processor. (indicates only the number of references from within the processor). (See 9 and 8 in Figure 1).

The method for updating the number of references based on this new number of references is as follows.

(1) If the data to be updated is in its own processor, the contents of its reference count accumulation section are directly updated.

(1-1) When the number of references reaches zero, the data is no longer needed and should be collected.

(2) If the data to be updated is in another processor, the contents of the local reference count accumulation section in that processor are updated.

(2-1) When the contents of the local accumulation section become 0, there are no more references from that processor, so send a message to the processor that holds the data to request a reduction in the number of references. send.

(3) When sending data to another processor, first increment by 1 the reference count accumulator attached to the data itself in its own processor.

(3-1) On the processor side that receives the data,
If the data is new data (there is no reference to the data in the processor), a local reference count accumulator is prepared and the count is set to 1.

(3-2) If it is not the first data, there is already a local reference count accumulator for that data, so increment its contents by 1.

The reference count updating hardware for implementing this method is shown in FIGS. 2 and 3. Figure 2 shows a system with four processor units #0, #1, #2, and #3, and each processor unit has an execution engine (CPU).
21, a local memory 26, a message transmitting/receiving device 24, and a reference count updating device 23 for data in its own processor are provided, and further, according to the present invention, a device 23 for updating and storing the reference count for data in other processors is provided. A reference number update device 22 is provided that includes a local reference number accumulating unit. Each processor
Units #0 to #3 are connected by a network 25, and communication for updating the number of references is performed in addition to exchanging data. Reference count update device 22
The details are shown in FIG. Although a system with four processors is shown in FIG. 2, it is sufficient to have n processors, and the network 25 is not limited to the bus type shown in the figure, but may be of any type such as mesh, torus, or cube. This allows Prolog,
It will perform processing such as LISP.

FIG. 3 shows an embodiment of a device for updating the number of references to data in other processors. In the figure, numeral 34 is a reference number table, which functions as a local reference number accumulator that corresponds to data in other processors. 35 is an increase/decrease circuit (executes +1 or -1), which increases/decreases the local reference count accumulation section in the reference count table according to increase/decrease in the reference count. 3
2 is a zero detection circuit, and the number of references is zero, that is,
It is detected that the cumulative part in the reference count table 34 has become zero, and a signal is sent to a message creation circuit 33 and a control circuit 31, which will be described later. Message creation circuit 33
When it receives a signal from the zero detection circuit, it creates a reference count update message to send to the processor holding the data. The control circuit 31 performs overall control such as addition/deletion of entries in the reference count table.

In FIG. 3, upon receiving a request from the execution engine to update the number of references to data in another processor, the reference number table 34 is searched. If it is unregistered data, it is added to the table. This creates a local reference count accumulator for the other processors. If it is existing data, there is already a local reference count accumulation section, so the contents of the table are updated using the increase/decrease circuit 35. If it becomes zero, the control circuit 31 detected by the zero detection circuit 32 deletes the corresponding entry in the reference count table. At the same time, the message creation circuit 33 generates a reference count update request message to be sent to other processors.

〔Effect of the invention〕

According to this invention, unless the number of references becomes zero, the number of references to data in other processors ends with only a local update process of the reference number accumulator, and communication between processors does not occur. Therefore, the number of reference count update request communications is greatly reduced. Moreover, according to this method, the immediacy achieved by the reference count method is maintained.

[Brief explanation of drawings]

FIG. 1 is a diagram showing the principle of this invention, and FIG.
FIG. 3 is a diagram showing an embodiment of the present invention,
FIG. 4 is a diagram showing a conventional example. #0, #1, #2, #3...Processor unit, 1-7...Memory cell, 8, 9...Local reference number accumulator, 21...Execution engine (CPU), 22, 23 ...Reference count update device, 2
4...Message transmitting/receiving device, 25...Network, 26...Local memory, 31...Control circuit, 32
...Zero detection circuit, 33 ...Message creation circuit, 3
4... Reference count table, 35... Increase/decrease circuit.

Claims (1)

[Scope of Claims] 1. A multi-processor system that collects unnecessary data using reference count accumulation means, comprising:
In a reference count update device that requests a processor holding the data to update the reference count of data existing in another processor using a reference count change message, each processor receives a request from its own processor to the other processor. Local reference number accumulating means 34, 35 that accumulate the number of references to the retained data, and when the cumulative value of the local reference number accumulating means 34, 35 reaches zero, the information is sent to the corresponding other processor. Message creation means 32, 3 for creating a message indicating that the reference from its own processor has become zero.
3, and when updating the local reference number accumulating means 34, 35, the reference number accumulating means 34, 3
When the value of 5 is not zero, no communication is made to the corresponding other processor, and only when the value of the reference count accumulation means 34, 35 becomes zero, a request to change the reference count is sent to the corresponding other processor. 1. A reference count updating device, characterized in that it is configured to transmit a message for the purpose of updating the number of references.