JP6417727B2 - Information aggregation system, program, and method - Google Patents

Description

  The present invention relates to an information aggregation system, program, and method for aggregating information from a plurality of nodes in a distributed system.

  In order to control parallel jobs executed using multiple nodes in a large-scale distributed system, or to manage nodes or node components as "resources" in the entire system, control the job or the entire system. It is often necessary to collect state information of management targets in real time for nodes.

  In information intensive communication for performing such aggregation, there is a problem in the amount of communication or transmission time associated with transmission / reception on the network. In recent computer systems, the communication speed of the network that connects the nodes is much slower than the processing speed of the computers that make up each node. This is the main factor that determines the overall load.

  In order to reduce the load as described above, the following network management system is conventionally known (for example, Patent Document 1). The terminal device outputs the state inside the device as management information. An intelligent agent (intermediate management apparatus) connected to these in a LAN (local area network) acquires these MIBs (Management Information Base), aggregates them, and creates an aggregate MIB. The management apparatus connected to these by the backbone LAN manages the terminal apparatus by managing the aggregate MIB. With this conventional technology, the network management device is not burdened, the traffic between the network management device and each terminal device is low, the management information can be easily analyzed, and the administrator can identify the differences in management information unique to each vendor. Realize a network management system that can be managed without awareness.

JP-A-9-298543

  The above-described conventional network management system is a related art relating to information aggregation of hierarchical nodes, in which the aggregation intermediate device and the management device symbolize terminal information and aggregate and manage the devices under the terminal.

  However, in information-intensive communication in a distributed system that does not have a hierarchical structure, the amount of communication on the network that connects nodes cannot be efficiently reduced in the process of sending messages from the sending node to the receiving node. Had a point.

  Accordingly, an object of one aspect of the present invention is to reduce the amount of communication between nodes during information aggregation in information-intensive communication in a distributed system.

  In one example, an identifier aggregation mechanism that is provided in a transmission side node and generates a collective identifier by aggregating notifications by individual identifiers unique to information notification sources and individual identifiers from information notification sources; The information aggregating system includes a process for receiving a collective identifier and restoring an individual identifier, and an identifier analysis mechanism for executing a process for specifying a notification source of information from the individual identifier.

  In information intensive communication in a distributed system, it is possible to reduce the amount of communication between nodes during information aggregation.

It is comparative explanatory drawing of the technique considered normally and embodiment. It is explanatory drawing of the necessity of the interrupt aggregation process in a large-scale system. It is a figure which shows the example of a sparse (almost all bits are 0) bit strings. It is a block diagram of embodiment of the computer which comprises an information aggregation system. It is a flowchart which shows the example of a process of the identifier aggregation mechanism 401 in the transmission side node in 1st Embodiment. It is a flowchart which shows the example of a process of the identifier analysis mechanism 402 in the receiving side node in 1st Embodiment. It is a figure which shows the structural example of the information aggregation system according to 1st Embodiment. It is explanatory drawing of the management object managed by the transmission side node. It is explanatory drawing of operation | movement which encodes a management object into an individual identifier with the encoding system of an identifier, and calculates a group identifier by reduction from the individual identifier and a state. It is explanatory drawing of the effect of the memory usage reduction by the information integration by reduction in case resolution is perfect. It is explanatory drawing of the concept of the resolution of a group identifier. It is explanatory drawing of the effect of the communication amount and memory usage reduction by the information integration by reduction in the case where the resolution is perfect and when it is restricted. It is explanatory drawing of the correspondence of a management object number and the bit position of the group identifier storage area in the memory area of a receiving side node. It is a figure which shows the structural example of the computer which matches a management object number and a bit position. It is a figure which shows the example of the separate identifier table | surface which the receiving side node has in the case of calculation being multiplication. It is a figure which shows the example of the identifier table | surface which a receiving side node has in the case of calculation being addition. It is a flowchart which shows the example of the process by the identifier aggregation mechanism 401 in the transmission side node in 2nd Embodiment. It is a flowchart which shows the example of the reception process over the whole group identifier by the identifier analysis mechanism 402 in the receiving side node in 2nd Embodiment. It is a flowchart which shows the example of the reception process of each bit field which comprises the group identifier by the identifier analysis mechanism 402 in the receiving side node in 2nd Embodiment. It is a figure which shows the 1st structural example of the information aggregation system according to 2nd Embodiment. It is a figure which shows the 2nd structural example of the information aggregation system according to 2nd Embodiment. It is a figure which shows the 3rd structural example of the information aggregation system according to 2nd Embodiment. It is explanatory drawing of the hierarchy of management object (node) grouping. It is explanatory drawing of the correspondence of the "grouped hierarchy of management object" and "assigned identifier" with respect to each subgroup. FIG. 25 is a diagram illustrating a specific example of FIG. 24 and illustrating an operation for limiting a search range of non-zero bits of a sparse bit string by hierarchical grouping. It is a figure which shows the example of the transmission message and receiving area at the time of limiting the search range of the bit which is not 0 of a sparse bit sequence by hierarchical grouping. It is a flowchart which shows the example of the transmission process of the group identifier grouped hierarchically by the identifier aggregation mechanism 401 in the transmission side node in 4th Embodiment. It is a flowchart which shows the example of the reception process accompanied by the depth priority search by the identifier analysis mechanism 402 in the receiving side node in 4th Embodiment. It is a flowchart which shows the example of the process of a lower layer identifier area | region search at the time of the reception process by the identifier analysis mechanism 402 in the receiving side node in 4th Embodiment. It is a flowchart which shows the example of a process of the identifier aggregation mechanism 401 in the transmission side node in 5th Embodiment. It is a flowchart which shows the example of a process of the identifier analysis mechanism 402 in the receiving side node in 5th Embodiment. It is a chart explaining a 5th embodiment. It is a flowchart (the 1) which shows the extraction process of the individual identifier component of the prime number from a group identifier in case reduction calculation is a multiplication. FIG. 10 is a flowchart (part 2) illustrating a process for extracting an individual identifier component of a prime number from a group identifier when the reduction operation is multiplication. FIG. 10 is a flowchart (No. 3) illustrating a process for extracting an individual identifier component of a prime number from a group identifier when the reduction operation is multiplication. FIG. 10 is a flowchart (part 4) illustrating a process of extracting an individual identifier component of a prime number from a group identifier when the reduction operation is multiplication. It is a flowchart which shows the example of a process of the identifier aggregation mechanism 401 in the transmission side node in 6th Embodiment. It is a flowchart which shows the example of a process of the identifier analysis mechanism 402 in the receiving side node in 6th Embodiment. It is a flowchart (the 1) which shows the example of a process of 7th Embodiment. It is a flowchart (the 2) which shows the example of a process of 7th Embodiment. It is a flowchart (the 3) which shows the example of a process of 7th Embodiment. It is a flowchart which shows the example of a process of the identifier aggregation mechanism 401 in the transmission side node in 8th Embodiment. It is a flowchart which shows the example of a process of the identifier analysis mechanism 402 in the receiving side node in 8th Embodiment. 12 is a flowchart (part 1) illustrating an example of an exceptional value list creation process in the case of using multiplication by logarithmic addition. 12 is a flowchart (part 2) illustrating an example of an exceptional value list creation process in the case of using multiplication by logarithmic addition. 12 is a flowchart (part 3) illustrating an example of an exceptional value list creation process in the case of using multiplication by logarithmic addition; It is a flowchart which shows the example of a process of the identifier aggregation mechanism 401 in the transmission side node in 9th Embodiment. It is a flowchart which shows the example of a process of the identifier analysis mechanism 402 in the receiving side node in 9th Embodiment. FIG. 10 is a flowchart (part 1) illustrating an example of a process of creating a correspondence list of individual identifier components used at a reception side node when a group identifier component is obtained by additive reduction. FIG. 11 is a flowchart (part 2) illustrating an example of a process of creating a correspondence list of individual identifier components used at a receiving node when a component of a collective identifier is obtained by additive reduction. FIG. 12 is a flowchart (part 3) illustrating an example of a process of creating a correspondence list of individual identifier components used at a receiving node when a component of a collective identifier is obtained by additive reduction. FIG. 25 is a flowchart illustrating an example of transmission processing of identifiers hierarchically grouped by bitwise or calculation in the tenth embodiment. In the tenth embodiment, it is a flowchart illustrating an example of reception processing of identifiers hierarchically grouped by bitwise or calculation. In the tenth embodiment, it is a flowchart showing an example of transmission processing of identifiers hierarchically grouped by multiplication operation. In 10th Embodiment, it is a flowchart which shows the example of the reception process of the identifier hierarchically grouped by the multiplication operation. It is a flowchart (the 1) which shows the example of the general process of the search process of the separate identifier list | wrist in 11th Embodiment. It is a flowchart (the 2) which shows the example of the specific process of the search process of the separate identifier list | wrist in 11th Embodiment. It is a flowchart (the 3) which shows the example of the search process of the separate identifier list | wrist in 11th Embodiment. It is a flowchart (the 4) which shows the example of the search process of the separate identifier list | wrist in 11th Embodiment. It is a flowchart (the 1) which shows the example of the speed-up process of matching with the individual identifier and management object number in 12th Embodiment. It is a flowchart (the 2) which shows the example of the speed-up process of matching with the individual identifier and management object number in 12th Embodiment. It is a flowchart (the 3) which shows the example of the speed-up process of matching with the individual identifier and management object number in 12th Embodiment. It is a flowchart (the 4) which shows the example of the speed-up process of matching with the individual identifier and management object number in 12th Embodiment. It is a flowchart (the 5) which shows the example of the speed-up process of matching with the individual identifier and management object number in 12th Embodiment. It is a flowchart (the 6) which shows the example of the speed-up process of matching with the individual identifier and management object number in 12th Embodiment. It is a flowchart which shows the example of the process which calculates | requires at least one prime factor of a given integer with algorithms other than brute force method. It is explanatory drawing of the difference of 13th and 14th embodiment.

Hereinafter, embodiments for carrying out the present invention will be described in detail with reference to the drawings.
First, before describing some embodiments, as a premise, a technique that can be generally considered by the present applicant and problems in the technique will be described.

  As an example of information aggregation in a distributed system, for example, in the following cases, the state of each system resource at a time sufficiently close to the time of allocation needs to be aggregated in a node that performs allocation control. For example, when a node is assigned to a job, optimization is performed according to the expected execution time of the job or the hardware resource to be accessed. Alternatively, for example, the checkpoint interval and the migration destination are determined after execution is started. Further, for example, the allocation is performed in consideration of the state of the components of each node itself, the load distribution of the file server, and the expected load of the communication path accessing the server.

  Also, in order to continuously monitor the state and load of each hardware resource and change them appropriately as needed, it is desirable to collect information at short intervals.

  In addition to state information aggregation, in a parallel computer environment, the results of partial computations in parallel at multiple nodes may be aggregated into one specific node at a certain point in time, or the mutual computation results are shared between multiple nodes The need often arises. Such information-intensive communication tends to be a bottleneck or a critical path for the entire parallel computation.

  In information-intensive communication, the amount of communication or transmission time associated with transmission / reception on the network becomes a problem. In recent computer systems, the communication speed of the network between nodes is much slower than the processing speed of the computers that make up each node. This is the main factor that determines the size of the load. Therefore, not only the portion proportional to the data amount, but also the amount of time required for one transmission / reception operation cannot be ignored regardless of the data amount.

  In the information-intensive communication, not only the transmission time associated with transmission / reception on the network but also the processing load on the node that collects information becomes a problem. In recent computer systems, the memory access speed is slow, in the order of several orders of magnitude, compared to the CPU processing speed, so the amount of memory to be accessed is the main factor that determines the amount of load on the node.

  Problems inherent in information-intensive communication become clear when compared with “broadcast communication”, which is typical of information diffusion communication.

  In the case of broadcast communication to a large number of nodes, the load on the transmission side node is improved to the same order as that for transmission to one node by using hardware having a broadcast communication mechanism. However, notification of status information and application to parallel computing require realization of reliable multicast including strict measures against data bit corruption and packet loss unlike broadcast communication such as video distribution, There are many cases that cannot be realized simply by using a hardware broadcast communication mechanism. However, there are a number of methods for realizing reliable multicast using the broadcast function that can be used in each system environment. With these technologies, the load on the transmitting side node becomes O (1) with the number of nodes as a parameter, and the requirements concerning the actual communication time are relatively easy to satisfy.

  Where O () is a "Landau symbol", and generally an amount increases or decreases in the same order as the amount specified in () (the amount mentioned in the symbol and the amount specified in () The limit of the ratio is a constant). O (1) means “even if the reference amount (or parameter) changes, it remains constant”.

  Communication for aggregating information from a plurality of nodes to a specific one node is defined as an API called MPI_gather in the Message Passing Interface (MPI) standard, for example. On the other hand, the communication API in MPI when all participating nodes share communication target data is called MPI_Allgather. In the following explanation, even if the API specified by MPI is not used, if the communication pattern is common, it is called gather or allgather.

  For reducing the time required for gather, for example, a technique based on the following operation (including a communication hardware function for realizing this operation) is known.

  Write RDMA (Write Remote Direct Memory Access) is a technology that uses a communication function characterized by "communication is started only by a command on the transmitting side and a predetermined area of the receiving side memory is updated". With this technique, the overhead of issuing a communication command on the receiving side is reduced.

  Technology that suppresses interrupt operations for each individual communication. In this technology, when receiving data from a plurality of nodes, a reception interrupt is not generated for each data, and the data transmission completion of all the transmission side nodes is separated by barrier synchronization between all the transmission side nodes and the reception side node. Know by means of In particular, if an interrupt proportional to the number of transmitting nodes occurs in a large-scale system, the overhead due to context switching becomes very large. Therefore, the reduction in the number of interrupts by this technique is effective for improving the performance.

  There is a limitation due to the following factors (1) and (2) in reducing overhead of the receiving node by the combination of the above-mentioned conventional techniques regarding gather.

  (1) The amount of data received from each node is at least “minimum packet length”.

  For write RDMA (and more generally for RDMA including read), apart from the minimum packet length, the minimum data length supported as a memory access unit (hereinafter written as L (unit is usually bytes)) Exists.

  (2) The amount of data to be received increases with O (N) as the number of communicating nodes N increases.

  When data of a predetermined format is received from each node by the write RDMA described above, an area of N * L bytes or more is required. However, the time required for reception is O (log (N)) when the data from each node is relatively small (that is, when the contribution of the communication delay time (latency) term to the communication time is large). On the other hand, if the data is relatively large and the communication time can be evaluated by “data size / bandwidth”, O (N). In general, in the case of reception from several tens of nodes or more, a time proportional to “(number of relay stages) × (number of communication partner nodes for each receiving side node including relay)” is set by setting several stages of relay nodes. I need it.

If the number of communicating nodes a for each receiving node is constant at each relay stage, the number of relay stages is proportional to the logarithm with a as the base. When the number of source nodes is N, the required communication time is approximately “a × log (N) / log (a)”. When relay processing is performed on a node, it is advantageous to set a to a relatively small value of about 2 to 3 for large-scale systems. This is a study with support based on theoretical models, simulations, and actual measurements. Is widely known. Here, log (N) / log (a) is an expression expressing “logarithm of N with a as the base” by logarithm with “standard fixed value” as the base. The “standard fixed value” that forms the base of the logarithm varies depending on the context, but in all cases the form of the formula is the same. The following values are used for “standard fixed values”.
-10 for "Logarithm"
-In the case of “natural logarithm” e (Napier's constant)
-2 for many literatures in computer science
In the following, the notation log_a (x) is also used when expressing “the logarithm of x with a as the base”. For example, log_a (x) = log_10 (x) / log_10 (a) = log_e (x) / log_e (a) = log_2 (x) / log_2 (a).

  When relaying, if the entire area including the received data is transferred to the upper level once after waiting for all the transfer by Write RDMA from the previous node to be completed, the processing time of the CPU required for relaying is not necessarily It can be made independent of the number of nodes. However, it is inevitable that the entire real time for communication increases with the number of nodes.

  Here, a technique assumed as a comparison target in some embodiments described later is information collection by gather described above. FIG. 1A is a diagram showing a method of a technique normally considered by the applicant of the present invention, which is assumed as a comparison target in some embodiments described later (FIG. 1B will be described later). As shown in FIG. 1A, the assumed normal technique is that a method 104 for aggregating information from one or more managed objects 101 in one or more nodes 102 to a receiving node 103 is based on gather. It is information accumulation. The information accumulation method 104 by gather is a method in which information is represented by, for example, an identifier of the management target 101 and 1-bit information about the management target 101 (: 1 in a predetermined state, 0 otherwise).

  The technology that is normally considered that some embodiments to be described later assume as a comparison target is: “Communication with interrupt processing is performed from a node that senses that a predetermined state has occurred in the management target, and no other node notifies anything. This is not the method (X). The reason for this is as follows.

  Method (X) may seem to be a natural monitoring method at first glance because the load on the receiving side should be sufficiently small if the rate at which a predetermined state occurs in the management target is a small number of nodes as expected. However, the method (X) has the following problems (A) and (B) from the viewpoint of stable operation in a large-scale system.

  (A) There is no distinction between “a message cannot be sent from the node in charge of management because the management target is not in a predetermined state” and “a message cannot be sent because a serious abnormality has occurred in the node”.

  If the latter state is monitored separately, the state of the node may eventually be detected appropriately. However, it is not always easy to avoid the occurrence of misidentification and record the status of the management target and to recover from the influence of the misidentification.

  (B) If a predetermined state occurs simultaneously in many nodes, the receiving node may be overloaded. FIG. 2A is an explanatory diagram of the necessity of interrupt aggregation processing in a large-scale system. As shown in FIG. 2A, consider a case where a NIC (Network Information Controller) 203 in the receiving node 202 generates an IO interrupt every time it receives a message from each transmitting node 201. In this case, based on the IO interrupt from the NIC 203, the CPU 204 switches the context 205 on the receiving side, starts an interrupt handler, and starts a process. In this case, the worst value of the number of interruptions is proportional to the number of nodes of the transmission side node 201. Further, the traffic on the network connected to the NIC 203 also increases in accordance with the number of transmission side nodes 201, and the amount of communication on the network increases.

  As shown in FIG. 2A, the communication accompanied by the interruption always causes an overhead of context switching processing to cope with the interruption. For this reason, if it is attempted to process reception interrupts from a large number of nodes by an order of magnitude in a large-scale system, it is difficult to avoid an overload in the receiving node 202.

  Stopping interrupts as a function of the receiving hardware when k messages have been received can be considered as a countermeasure for overloading the receiving node. It is not easy to decide. Furthermore, when the interrupt stop specifiable range in the hardware specification on the receiving side is for each network interface or port, stopping the interrupt prevents communication using the same network interface or upper port. In this case, from the viewpoint of necessity for communication for other uses by the network device, stopping the interrupt causes a problem in system operation. Therefore, it may be inconvenient to stop the interrupt.

  The problem here is that “how many nodes are in a particular state at a certain point in time” is not “information determined before transmission”, so depending on the packet attribute corresponding to the type of notification information It is impossible to use the “determining whether or not an interrupt has occurred by specifying (on the sending side)” method.

  Based on the above considerations, the following measures are required when using communication with interrupts at the time of reception, assuming that notifications from a large number of nodes are received simultaneously. As shown by 206 in FIG. 2 (b), traffic on the network is reduced by layering according to the number of transmission side nodes 201 (managed objects) in the system, and the load on each node. It is necessary to distribute and to prepare system resources assuming the maximum load.

  Furthermore, it is known that the occurrence of irregular interrupts degrades the “collective communication” performance during parallel computation. In other words, a node that receives such monitoring information is separate from a node that performs parallel calculation, or at least does not have a system resource that handles the interrupt at each node separately from a system resource for parallel calculation. The parallel computing performance of the system is significantly degraded.

  However, such a method of preparing independent system resources for each purpose with an extra margin for normal processing leads to a significant increase in system cost.

  From the above considerations, it can be seen that a monitoring method in which there is no great difference in the load on the receiving side node between the case where the state distribution of the management target is as expected and the case where it is not so is extremely desirable in a large scale system. The method (X) of “performing communication with an interrupt only when a predetermined state occurs” does not satisfy this condition.

  To summarize the problems to be solved by some embodiments described later, the following three technical problems are obtained.

Technical issue 1:
In information-intensive communication, the receiving node must refer to the area of the minimum message size for each message from each node, increasing the amount of communication on the network and reducing the memory access load at each node. To exceed.

Technical issue 2:
With information-intensive communication, the receiving node must access all information from nodes that do not need to take action, increasing the amount of communication on the network and reducing the memory access load at each node. To exceed.

Technical issue 3:
In information-intensive communication, if the number of management targets that exceed a preset threshold value is "monitoring status", all management targets must be recognized under the condition that only "threshold value exceeded" needs to be recognized. The amount of communication on the network and the memory access load at each node must be reduced compared with the case where it is necessary to identify the state of the network.

  The common premise of all these technical issues is the normal idea in the situation that a certain node receives information about the same number or a larger number of managed objects from multiple nodes, one bit for each. The low communication efficiency and memory use efficiency of the information aggregation technology that is used limit the communication performance of the entire system.

  Also, the premise common to technical problem 2 and technical problem 3 is that the information aggregation technology that is usually considered in the situation where “the majority of the bits to be received are 0 (the number of bits that are 1 is a small number)” under the above common assumptions The low communication efficiency and memory access efficiency limit the communication performance of the entire system. FIG. 3 is a diagram illustrating an example of a sparse bit string (almost all bits are 0). As can be seen from this, even for an information sequence in which the majority is 0, communication must be performed for each bit, and a memory area must be allocated in each node, resulting in poor communication efficiency and memory access efficiency. I understand that.

  In the following, the above three problems will be described in more detail, including the relationship with the technology that the applicant normally considers.

  At the time of simultaneous reception in a large-scale system, there are problems common to general information reception and problems specific to information reception when an “exceptional state” occurs.

First, common problems in receiving information from a large number of nodes in a large-scale system will be described.
In order to relay information, there is the following trade-off between the number of communication counterpart nodes and the number of relay stages of the management node or each intermediate node in each stage, so it is difficult to greatly reduce the communication delay.
Decreasing the number of communicating nodes at each stage increases the number of relay stages.
Increasing the number of correspondent nodes at each stage increases the memory area for reception.
The memory area required for reception processing increases, and the overhead associated with reception (or relay) processing increases in proportion to the number of communication partner nodes at each stage.

  In communication involving relay operation at a node, the communication delay time (latency) increases in proportion to “logarithm of the number of nodes” as the number of relay stages increases. The reduction of the communication delay time must be achieved by reducing the time required for the “relay operation” at each stage. Therefore, it is necessary to reduce the amount of communication data and the processing time at each stage of the relay.

  As a factor governing the processing performance of information accumulation from a large number of nodes, the processing time at the receiving side node, particularly the proportion of the time required for memory access at the receiving side node is also large.

Since the time required for memory access is an increasing function of the amount of memory to be accessed, the reduction in the amount of memory to be accessed is the key to improving the performance, but the lower limit of the reduction is defined by the following factors. This problem is “Technical Problem 1” described above.
Even when receiving 1 bit, a memory area of at least the minimum packet size is required.
In order to reduce the CPU overhead due to interrupt processing at the time of reception, when trying to receive packets of all nodes while interrupts are suppressed, memory of the number of nodes × minimum packet size is required for storing messages. This is because the memory cannot be released until all messages are received.

  Next, a problem peculiar to information reception when “an exceptional state occurs in the management target” will be described.

  Here, the “exceptional state” is often rephrased as an “abnormal state”, but may be “normal state, simply rare”. For example, when the product of a large sparse matrix is calculated in parallel, if it is known that “most components are 0”, a non-zero component is It is thought. A sparse matrix is often expressed as “a pair of“ position of non-zero component ”and“ value of that position ”” rather than assigning one region to all components, and the input data or (final ) As output data, each component is rarely directly managed. However, when processing operations in parallel, the share of the majority of nodes may be zero. However, from the viewpoint of easy understanding, a case of state monitoring in the case where an “abnormal state” occurs will be described below as an example.

  In general, the failure rate of individual hardware components that make up a large-scale parallel system is very low, so there are multiple nodes or parts in the system unless there is a common cause for multiple nodes or multiple components. The probability of failure at the same time is many orders of magnitude smaller than the probability of one failure. This is because if the abnormality of each node or component is an “independent event”, the probability that a plurality of management targets will be in an abnormal state simultaneously is the product of the probability that one will be in an abnormal state.

  For this reason, when checking the status of each management target after receiving the status of all the management targets, the status of most of the management targets is “skip”. In other words, although there is no need for the receiving side to take action for almost all management targets, a load for referring to the communication and memory for the status of many management targets is generated. This problem is the technical problem 2 described above.

  Note that in such cases, it may not be necessary to identify all the nodes that have anomalies.

For example, in a system that monitors the abnormality of all the nodes assigned to one parallel job, if the number of nodes with an abnormality is less than or equal to a predetermined threshold and the threshold is exceeded, To do.
If it is less than or equal to the threshold, the alternative node assignment job is immediately continued.
If the threshold is exceeded, the job is terminated.

  In such a system, in the former case, it is necessary to identify the node in which the abnormality has occurred. In the latter case, if it is known that “the number of abnormal nodes has exceeded the threshold value”, the current processing itself is Since it is considered possible, it is not necessary to identify the node where the abnormality occurred.

  More generally, if an abnormality that exceeds the number of redundant resources prepared for ensuring reliability occurs, assuming that the basis for determining the number of redundant resources is reasonable, if the abnormality occurs at the same time, those abnormalities are independent. Is unlikely. Therefore, it is uncertain whether recovery is possible even if the number of redundant resources is increased. If there is an unexpected “single point of failre”, the process cannot be continued by redundant resource allocation, and the process must be aborted. In this situation, it is considered that the identification of individual abnormal locations may be performed as necessary after the processing is terminated.

  Here, consider the case of using a technique that collects information at a receiving node by Write RDMA from a plurality of nodes, which is a normally considered technique. In this case, as long as the reception is confirmed after all the data has been transmitted in order to reduce the reception overhead, “a predetermined (usually abnormal) state has been received from a number of nodes exceeding the threshold” It will be determined by the search process for all data.

  In such a case, the worst case is access to the entire memory of “number of nodes × minimum packet size”. On average, access to at least about half of the memory is required. The reason is that if there is an equal probability that the area corresponding to each node in the abnormal state is in front of or behind the half point counted from the top in the access order, it corresponds to one abnormal state. This is because the average amount of memory accessed until a node is detected is 1/2 of the total amount of memory. If the threshold is k and the search is continued until a number exceeding the threshold k is found, the average amount of memory to be searched is an increasing function of k.

  As described above, in the normally considered technology, for example, when k = 1 and it is sufficient to see the state of one managed object at normal time, the communication amount and memory access proportional to the total number of managed objects are required, and for each managed object A communication amount and a memory area with a minimum packet size are required. For this reason, the increase in communication volume and processing load are not small.

  However, even when the distribution state of the predetermined state is different from the assumption, it is always possible to switch the processing when it is detected that more management targets than the assumption are in the predetermined state, so there is no great difference in processing time. In other words, the method of performing communication with interruption for each management target in a predetermined state (method (X) described above) increases the processing time in an unexpected situation, but stable even in unexpected cases There is an advantage that the operation is easy to realize.

  Therefore, under the situation that “the management target in the normal state is assumed to be below the threshold k”, “the processing time in the unexpected state is not much different from the processing time in the normal state”. The problem is to reduce the amount of communication on the network and the amount of memory that needs to be accessed during processing at each node, while maintaining the above advantages. This is the above-described technical problem 3 that should be solved by some embodiments described later.

  In the following description, the following monitoring method is defined as “the resolution is k”. It does not necessarily identify individual management targets for a specific state (usually an abnormal state) common to a number of management targets that exceed a specific threshold k, but the number of management targets in a specific state is less than or equal to the threshold k. In this case, the monitoring method identifies the management target.

  There are two ways of thinking about the behavior of the monitoring system when the monitoring condition is satisfied for more than k management targets during monitoring with resolution k. Which idea is appropriate depends on the situation.

(1) It is better that more than k objects can be identified in many cases.
For example, since the calculated collective identifier fits in an area of a predetermined size, even if it is impossible in all cases, it is preferable that more than k individual identifiers can be decomposed in many cases. In other words, if there are more than k management targets in a given state and it is not necessary to know the individual identifiers, the calculation for obtaining the individual identifiers from the group identifiers is often executed (this is the case). May not be desirable).

(2) The process of identifying more than k objects is unnecessary or light in many cases.
For example, there are cases where it is preferable that there are more cases where it is possible to determine that more than k individual identifiers are included based on the size of the collective identifier (including cases where determination is possible due to an overflow of computation during reduction). In other words, there are few cases where more than k individual identifiers are known (this may not be desirable).

For example, if a certain set S to be managed is fixed and the following processing is performed, encoding whose resolution is limited by the upper limit k can be used.
If a problem occurs in more than k management targets in S, the use of S is temporarily canceled.
If there are no more than k nodes where an event has occurred in S, take some measures for each node and continue using S.

  The same method can be used not only for the state of an entire node but also for the state of "components of a node" and "a series of devices managed by a node". Use simple expressions. In the embodiment described below, the expression “node management” may be used. That is, the notification is performed for each management target by the node in charge of management.

<Technical elements common to all embodiments>
FIG. 1B is a diagram illustrating a method 105 for aggregating information from one or more managed objects 101 in one or more nodes 102 to a receiving node 103 in some embodiments described later. As shown in FIG. 1B, when the management target 101 is in a predetermined state, coded data (individual identifier described later) is notified, and a reduction operation is executed for this notification. Thus, the data (the collective identifier described later) whose data amount has been reduced is notified to the receiving side node 103. When the management target 101 is not in a predetermined state, the unit of the reduction calculation to be used is notified, and the reduction calculation is executed for this notification. That is, when the unit element is notified, the reduction calculation result with the unit element as an input does not change.

  Some embodiments to be described later relate to an information aggregation method in a distributed environment that does not share a memory. As illustrated in FIG. 1B, an information management target 101 and an information notification source node 102 are identical. This is a typical example. That is, when the node 102 itself notifies the “state” of the entire node 102 (from a certain point of view), the management target 101 is considered as the node 102 itself. However, the management target 101 and the notification source node 102 are conceptually distinguished in consideration of a more general situation, such as a case where the present invention is applied to the case of information aggregation regarding a plurality of specific types of components constituting the node 102.

  However, when the management target 101 is the node 102 itself and the group identifier notification process is hierarchized between the nodes 102, the information aggregation for the plurality of management targets 101 on the node 102 is equivalent to the information aggregation technique. Therefore, when emphasis is placed on easy understanding, it is often safe to assume that the management target 101 is the information notification source node 102 itself.

<First Embodiment>
FIG. 4 is a block diagram of a first embodiment of a computer constituting the information aggregation system. The first embodiment has the following technical contents (1) to (6).

  (1) For the notification target events defined for multiple management targets in the distributed system, the status of the entire system is managed by aggregating the coded identifiers of the targets where the events occurred as information It is a mechanism to do. The coded identifier corresponding to each management object is hereinafter referred to as “individual identifier”.

  (2) “Mechanism for aggregating target coded identifiers (individual identifiers) as information” is hereinafter referred to as “identifier aggregation mechanism 401”. The individual identifier becomes an input to the identifier aggregation mechanism 401.

  (3) The identifier aggregation mechanism 401 aggregates identifiers by “reduction 404” which is a form of collective communication. This reduction 404 reduces the amount of communication on the network, and the amount of memory required for reception and the CPU time required for reception on the node (103 in FIG. 1B) that receives the aggregated information. The object is to reduce (including memory access time).

  It can be said that the identifier aggregation mechanism 401 in the present embodiment embodies a combination of “identifier coding system 403” and “reduction 404” on the computer system, which is a function for coding management targets into individual identifiers. .

  Here, the reduction 404 is a kind of collective communication on a distributed parallel system, and “inputs data distributed in a plurality of nodes (102 in FIG. 1 (b)) and inputs an operation result to those nodes. In other words, the reduction 404 is a combination of a series of communications and operations between nodes, and in this embodiment, the mechanism as a “mechanism” of the reduction 404 is known from the past. Use the method that is used. The unique addition in the present embodiment regarding the reduction 404 is in the policy regarding what data is to be subjected to “reduction”.

  For example, the details of the packet format in the reduction communication do not matter in the present embodiment.

  The result calculated by the reduction 404 from the individual identifier determined by the “identifier coding system 403” is hereinafter referred to as “collective identifier”. Recognizing that the reduction 404 is typical of collective communication, the calculation result of the reduction 404 is called a “collective identifier” with the intention of calling it a collective identifier in English.

  The individual identifier used in the calculation of the group identifier is hereinafter referred to as “generation factor” (of the group identifier) or simply “factor”. If the operation is multiplicative, it corresponds to “factor” as an ordinary mathematical term. However, in the present application, the term “generation factor” or “factor” is used even when operations other than multiplication such as bitwise or (bitwise OR operation) or addition are used for the reduction 404.

(4) “Identifier coding system and calculation method for coded identifier” for achieving the above object (3) are technical elements of this embodiment. The technical element has the following two aspects.
Technology in terms of identifiers (code system) and algorithms for each code.
A technique related to a method of using an “inter-node computing device” (a special network used for realizing the reduction 404 or a special device connected to the network) unique to the system.

  (5) When the group identifier corresponding to a plurality of management objects is calculated from the individual identifier by the identifier aggregation mechanism 401 by the reduction 404, the node in charge of information notification (corresponding to 101 in FIG. 1B) Called “side node”. A node in charge of information aggregation (corresponding to 103 in FIG. 1B) is called a “receiving node”.

  FIG. 5 is a flowchart illustrating an example of processing of the identifier aggregation mechanism 401 (FIG. 4) in the transmission side node in the first embodiment. The processing of the flowchart of FIG. 5 is executed by the CPU 701-1 of the transmission origin node 701 of FIG. 7 described later or the CPU 702-1 of the reception / relay node 702 functioning as a relay node. The work area such as the input parameter 1 or 2 is stored in the memory 701-2 of the transmission origin node 701 or the memory 702-2 of the reception / relay node 702.

First, it is determined whether or not the own node is a communication origin node (step S501).
If the determination in step S501 is NO (“n” in the figure), the received value (group identifier) is stored in the input parameter 1 that stores the received value (step S502).

  If the determination in step S501 is YES ("y" in the figure), there is no received value, so a default value is stored in the input parameter 1 (step S503). Here, the default value is preferably the unit of operation used for the reduction 404. For example, if the operation is an additive operation or a bitwise or operation, the default value is preferably 0. If the operation is a multiplicative operation, the default value is preferably 1. If the own node is the communication origin node and there is no received value, the unit element is stored in the input parameter 1 so that the input parameter 1 does not affect the calculation of the reduction 404.

  Next, it is determined whether or not a condition to be notified is established in the management target managed by the own node (step S504).

  If the determination in step S504 is YES, the individual identifier corresponding to the management target in the own node (or the own node itself) is stored in the input parameter 2 that stores the state of the own node (step S505).

  If the determination in step S504 is no, a default value is stored in the input parameter 2 (step S506). The unit value of the calculation used for the reduction 404 is also preferable for the default value here, as in step S503. If the condition to be notified is not satisfied in the management target managed by the own node, the unit element is stored in the input parameter 2 so that the input parameter 2 does not affect the calculation of the reduction 404.

  Thereafter, the binary operation used for the reduction 404 is executed on the input parameter 1 and the input parameter 2 (step S507). Details of the binary operation will be described later in some embodiments.

  Finally, the calculation result in step S507 is output as a collective identifier that is the transmission content to the next transfer destination (step S508). Thereafter, the processing of the identifier aggregation mechanism 401 in the transmission side node exemplified in the flowchart of FIG.

  The effect of the identifier aggregating mechanism 401 in the first embodiment is necessary when the communication amount and the memory amount necessary for the calculated collective identifier are individually notified from the notification node to the node where the information is aggregated. The part derived from the fact that each of the total amount of communication and the amount of memory is smaller is large.

  In addition, every node is in charge of information notification and may collect information. In other words, the transmitting side node and the receiving side node do not necessarily refer to specific physical nodes, but are merely called for roles in the system.

  In collective communication terminology, when any node is in charge of both information notification and information aggregation, it is called “Allgather” for simply collecting information as it is, and “Allreduce” for reduction 404. There are two main ways to implement Allreduce. The first implementation method is a method of combining reduction to a specific node and broadcasting to a plurality of nodes (broadcast: one-to-many communication of data having the same contents). Note that one-to-many communication of data with the same content is called “multicast” in general depending on the context. The term “broadcast” is a special case of “simultaneous communication to all nodes in one physical network segment”. In some cases, it is only used. The second realization method is a method in which information is shared between nodes participating in aggregation after communication processing is completed by exchanging information between nodes in the process of aggregation. For example, this is a case where the information aggregation process is realized by “exchanging information held by two nodes at each stage”. Since these realization methods are distinctions on the communication mechanism, either one may be used in the present embodiment.

  (6) A mechanism for identifying a management target in a monitored state from the received group identifier is referred to as “identifier analysis mechanism 402”. The identifier analysis mechanism 402 includes the following two parts (see FIG. 4). The first part is a process of identifying and restoring an individual identifier that is a “generation factor” from the received collective identifier (based on the identifier coding system 403 in FIG. 4). The second part is a process for identifying the management target (101 in FIG. 1B) from the individual identifier.

  FIG. 6 is a flowchart illustrating an example of processing of the identifier analysis mechanism 402 (FIG. 4) in the receiving side node in the first embodiment. The processing of the flowchart of FIG. 6 is executed by the CPU 702-1 of the reception / relay node 702 of FIG. The work area W and the like are stored in the memory 702-2 of the reception / relay node 702.

  First, the collective identifier in the reduction 404 between nodes is received (step S601).

Next, the group identifier is stored in the work area W (step S602).
Next, it is determined whether or not the value indicated by the work area W is a unit element in the calculation of the reduction 404 (step S603).

If the determination in step S603 is NO, one individual identifier is specified from the group identifier (step S604). As this specific concrete method, for example, the following means is used depending on the identifier coding system 403 of FIG.
Bit manipulation operation Prime factorization Search for “collection identifier and individual identifier comparison table” Search function “hash function” that speeds up the search by limiting the search range of the comparison table
"Complete hash function" for finding at least one individual identifier (which is its generation factor) from a group identifier
Details of these means will be described later in some embodiments.

Thereafter, the management target corresponding to the individual identifier specified in step S604 is processed (specified) (step S605). As this specific concrete method, for example, the following means is used depending on the identifier coding system 403 of FIG.
Bit operation calculation “Search table for individual identifiers and control numbers” “Hash function” that speeds up search by limiting the range of search for the comparison table
"Complete hash function" to obtain the management target number from the individual identifier

  Next, the individual identifier specified from the work area W in step S604 is removed by the inverse operation of the operation used for the reduction 404 (step S606). Thereafter, the processing returns to step S603, and the processing from step S603 to step S606 described above is repeatedly executed.

  If the determination in step S603 is YES, the processing of the identifier analysis mechanism 402 in the receiving side node illustrated in the flowchart of FIG.

  In the present embodiment, the mechanism based on the above (1) to (6) is realized on, for example, an information aggregation system having the configuration of FIG. The minimum requirement of the information aggregation system that realizes the present embodiment is “a configuration in which individual computers (nodes) having a CPU, a memory, and a network interface are interconnected by a network”. That is, as shown in FIGS. 7 to 10, the transmission origin node 701 and the reception / relay node 702 are interconnected by a network including a relay device 703 that is a switch or a router and a communication line 704. FIG. 7 is an illustration of a computer system according to the first embodiment, and the number of nodes 701 and 702 or relay devices 703 included in this system may be arbitrary. The transmission origin node 701 includes a CPU 701-1, a memory 701-2, and a NIC 701-3 that is a network interface. The reception / relay node 702 includes a CPU 702-1, a memory 702-2, and a NIC 702-3. The reception / relay node 702 is classified into type 1 (collection identifier reception area) or type 2 (collection identifier reception area and identifier table storage area), depending on how the storage area of the memory 702-2 is used. The

  In FIG. 7, the transmission origin node 701 corresponds to the node 102 of FIG. 1 and includes the management target 101 of FIG. Alternatively, the transmission origin node 701 itself may be the management target 101.

  FIG. 8 is an explanatory diagram of management targets managed by such nodes. The management target managed by the node may be the state of the node as shown in FIG. 8A, or the state of each component of the node as shown in FIG. . Further, the management target managed by the node may be a management target other than the component parts of the node as shown in FIG. 2C, and the memory of the node as shown in FIG. It may be specific data. As shown in FIGS. 2B to 2D, the management target whose state is managed can be conceptually distinguished from the information communication source node. However, if the status information of a plurality of management targets managed by the information communication source node is aggregated in the information communication source node by the same information aggregation processing as the processing of reduction 404 (FIG. 4) described later, This can be explained in the same manner as when both are conceptually matched as shown in FIG. Therefore, in order to clarify the explanation, the management target managed by the node will be described below as a state of the node as shown in FIG. 2A for convenience.

  In the transmission origin node 701, the CPU 701-1 executes the process of the identifier aggregation mechanism 401 illustrated in the flowchart of FIG. 5 while executing the control program incorporated therein, while using the memory 701-2 as a work area. Run. As a result, the transmission origin node 701 transfers the calculation result of the reduction 404 (FIG. 4) for the individual identifier (or the above-mentioned unit element) generated in its own node to the next receiving / relay node 702 as a collective identifier. As described above in the description of step S506, the unit element is stored in the input parameter 2 and the calculation of the reduction 404 is executed if the condition to be notified is not satisfied in the management target managed by the own node. As a result, in this case, the output of the operation of the reduction 404 is not changed from the input, and the collective identifier is not changed and is transferred to the next receiving / relay node 702.

  In FIG. 7, the reception / relay node 702 can also be a transmission origin node 701 when operating as a relay node. In this case, the reception / relay node 702 receives the collective identifier from the transmission origin node 701 or another reception / relay node 702 functioning as a relay node. Then, in the reception / relay node 702, the CPU 702-1 executes the program contained therein, thereby using the memory 702-2 as a work area, and the processing of the identifier aggregation mechanism 401 illustrated in the flowchart of FIG. Execute. As a result, the reception / relay node 702 transfers the operation result of the reduction 404 (FIG. 4) for the received collective identifier and the individual identifier generated in the own node to the next receive / relay node 702 as a new collective identifier.

  When the reception / relay node 702 operates as a reception node, the reception / relay node 702 corresponds to the node 103 in FIG. 1 and receives a collective identifier from another transmission origin node 701 or the reception / relay node 702. Then, in the reception / relay node 702, the CPU 702-1 executes the program included in the reception / relay node 702, thereby using the memory 702-2 as a work area and the identifier analysis mechanism 402 illustrated in the flowchart of FIG. Execute the process. As a result, the reception / relay node 702 identifies the individual identifier and the management target corresponding to the individual identifier from the received group identifier.

The most basic points of the first embodiment are the following two points.
The individual identifier to be managed in the present embodiment is not a serial number or the like but data encoded by a specific method.
The data transmitted to the receiving side is not an individual identifier itself but a group identifier calculated by reduction using an individual identifier corresponding to a management target for which the condition is satisfied.

  These are realized by the processing of the identifier aggregation mechanism 401 shown in FIG. 4 illustrated in the flowchart of FIG. FIG. 9 is an explanatory diagram of an operation for coding a management target into individual identifiers by the identifier coding system 403 in FIG. 4 and calculating a collective identifier from the individual identifier and state by the reduction 404 in FIG. In FIG. 9, 0b before the constant means that it is in binary notation.

  As shown in FIG. 9 (a), the identifier coding system 403 in FIG. 4 indicates that each individual identifier corresponding to each management target is represented by data in which the bit of the position corresponding to the management target is turned on. Code it. That is, for a management target that satisfies a predetermined condition, an individual identifier corresponding to the management target is given as an input of reduction, and for a management target that is not so, a unit in which 0 is input to all bit fields The original is given as an individual identifier.

  Further, as shown in FIG. 9A, the “reduction 404” in FIG. 4 calculates a collective identifier by bitwise or with an encoded individual identifier as an input. However, the calculation function used for this calculation only needs to satisfy the condition that “input data from each node is at least 1 bit on and the others are off”. Therefore, multiplication (FIG. 9B), bitwise exclusive or (bitwise exclusive OR operation), integer addition, or floating point addition (however, it is used as integer addition within the range of the number of digits of the mantissa part) ) May be used to calculate the population identifier. In addition, the collective identifier may be calculated using bitwise and if each node performs bit inversion (bitwise not) on all input data. In this case, the data may be interpreted by reversing the final result in the receiving node or by reversing the on / off meaning of the bit.

  In this way, in the first embodiment, the “technical problem 1” described above is solved by “folding information from a plurality of nodes into one packet / message”. That is, the state information from each node is reduced using the group identifier. As a result, the amount of traffic on the network (communication line 704 in FIG. 7) is compared with the case where the status information from each transmitting side node (such as the transmission origin node 701 in FIG. 7) is simply aggregated and received. It can be greatly reduced. Similarly, the amount of memory and the communication processing time required for reception in the reception side node (reception / relay node 702 in FIG. 7) that collects information are the states from each transmission side node (transmission origin node 701 in FIG. 7). Compared to the case where information is simply collected and received, it can be greatly reduced. FIG. 10 is an explanatory diagram of the effect of reducing the amount of memory used in information accumulation by reduction. FIG. 10A is an explanatory diagram in the case where the receiving node simply collects and receives the state information from each transmitting node, which is normally considered by the present applicant. On the other hand, FIG.10 (b) is explanatory drawing when a receiving side node collects and receives the status information reduced using the group identifier from each transmitting side node. When the receiving side node simply collects and receives the state information from each node (FIG. 10A), the amount of memory required for the receiving side node to receive the state information of each managed object is the minimum write Size (2 bits) x Management target (4). On the other hand, when the reception side node collects and receives the state information reduced using the collective identifier from each transmission side node (FIG. 10 (b)), it is as follows. The amount of memory required for the receiving node to receive status information for each management target is the minimum write size (4 bits) x number of management targets (4) / number of bits in the area (4 bits) .

  In the present embodiment, the content of information included in the message is further devised according to circumstances, that is, the identifier coding system 403 in FIG. Usage efficiency can be increased. The basic concept of the encoding method is described below.

  By improving the coding suitable for the nature of the event to be notified, the amount of communication required for communication on the network, the amount of memory required for reception at the information aggregation node, and the degree of improvement in communication processing time can be increased. it can. “Resolution” in the meaning defined below is particularly important as “property of notification target event” to be considered in coding.

  For a positive integer k, “When the number of management targets that occurred at the same time as the notification target event is less than or equal to k, the notification target event occurs from the group identifier received by the identifier analysis mechanism 402 of FIG. It is assumed that the specified node can be specified. When this assumption holds, it is defined that “resolution” of the identifier analysis mechanism 402 (as “system” including the identifier aggregation mechanism 401, individual identifiers, and group identifiers) is k. If the number of management targets that can generate notification target events is N, then N ≥ k.

In the description below,
When N = k, the identifier analysis mechanism 402 has a “resolution” of “complete”.
(Or no limit).
When N> k, the “resolution” of the identifier analysis mechanism 402 is limited (with an upper limit k).
I will also use the expression. When the resolution is limited, it is not necessary to include all “the distinction between establishment and non-establishment of the state to be monitored for all the management targets” in the information to be transmitted in the message having a predetermined length. For this reason, if other information, specifically, information about a part of the identifier of the target whose state to be monitored is included in the message area of the same length, information that can be discriminated can be sent. . When a plurality of pieces of information are contained (2 bits or more are standing in one column), it is possible to cope with a case where it is only necessary to know which one of the management targets in the monitoring state has an abnormality. FIG. 11 is an explanatory diagram of the concept of resolution of the group identifier. When the resolution of the group identifier is perfect, as shown in FIG. 11A, the management target in the monitoring state and the target that is not in the combination of all the states are specified. When the resolution of the group identifier is limited, as shown in FIG. 11B, the target is specified when the number of targets in the monitoring state does not exceed the upper limit. On the other hand, if the number of objects in the monitoring state exceeds the upper limit, no object is identified.

  FIG. 12 is an explanatory diagram of the effect of reducing the amount of communication and the amount of memory used for information accumulation by reduction when the resolution is perfect and limited. For example, as shown in FIG. 12A, for N (three in the figure) management targets, 1-bit information is received indicating whether the monitoring state is established or not established for each management target without limiting the resolution. Requires at least N bits (3 bits in the figure). However, for example, as shown in FIG. 12 (b), when the resolution k is limited (k <N), information on monitoring states from more than N management targets in an area smaller than N bits. Is possible in principle. FIG. 12B shows a case where the upper limit of 1 is set for the resolution and five management target states are received in the 3 bits area. In the present embodiment, this is actually realized mainly by the idea of the identifier coding system 403 in FIG.

  In this embodiment, when the resolution is limited, “characteristics as a numerical value of a set of identifiers that can be stored in a certain area” is used for information compression.

  In the present embodiment, when the resolution is limited, the above-described technical problem 2 is solved by devising the identifier encoding system 403 in FIG. 4 according to fifth to ninth embodiments described later. Further, in the case where complete resolution is required, as described later in the fourth or tenth embodiment, a group of management targets (in multiple hierarchies if necessary) is regarded as a new management target. This solves the technical problem 2 described above.

  As described above, according to the first embodiment, it is possible to reduce the time required for information-intensive communication. In particular, the amount of communication on the network required for reception or relay, the amount of memory area access at each node, and the overhead associated with memory access are greatly reduced.

  In addition, according to the first embodiment, when the reference memory area at the relay node and the receiving node is reduced, the memory bus bandwidth and the cache usage viewed as the entire system are reduced. The load related to the sharing process is reduced. This also has the effect of improving the throughput of the entire system.

  According to the first embodiment, by using the collective identifier, the amount of communication on the network, the amount of memory necessary for reception at the information aggregation node, and the communication processing time are simply aggregated state information from each node. Compared with the case of receiving, it is greatly reduced.

  According to the first embodiment, when the necessary “resolution” has an upper limit, it is possible to reduce the amount of communication and the amount of memory used according to the concept described in FIG.

  Furthermore, the amount of memory required for reception can be reduced by reducing contention between memory access and memory access during reception (independent of reception) performed in parallel with reception. Derivative effects are also significant by improving overall performance in systems that are wrapped and executed.

  Details of the identifier encoding system 403 in FIG. 4 will be described in detail in some embodiments described later.

<Second Embodiment>
Next, a second embodiment will be described.

  The basic functional configuration of the second embodiment is the same as the configuration according to the first embodiment described with reference to FIG. The overall system configuration of the second embodiment is also the same as the configuration according to the first embodiment described with reference to FIG. Further, the basic functions of the identifier encoding system 403 and the reduction 404 (both see FIG. 4) in the second embodiment are the same as the functions according to the first embodiment described in FIG.

  As described with reference to FIG. 8A in the first embodiment, the identifier coding system 403 in FIG. 4 uses each individual identifier corresponding to each management target as a bit at a position corresponding to the management target. Code with data turned on. In this case, the bit position corresponding to each management target is determined, for example, as in (1) to (5) below.

  (1) N bits concatenated memory area or piecewise concatenated area when sharing information in bits in an information aggregation system with N management targets (nodes, subsystems, jobs ...) Prepare. When a concatenated area is prepared, the concatenated area is divided according to the size s bits (in many cases, the integer size supported by the CPU) that is applied to one bit manipulation instruction. The x-th area is specified as the s × x bits (s × x / 9 bytes) th from the beginning. In the case of a piecewise linked area, if the linked area is handled separately for each size s bits to which a single bit manipulation instruction is applied, the first address of the xth area is set to (pointer Is specified).

  (2) The above N bits memory area is divided for each update unit m bits by reduction or atomic operation. Let n be the number of bit areas after division. For example, if the atomic operation can be performed only in units of 128 bits for 1024 bits corresponding to 1024 nodes, 8 128-bit areas are prepared. Note that if the alignment constraint for the atomic operation is 16 bytes (= 128 bits), a region on a 16 byte boundary is used. If N is not an integer multiple of m, a dummy bit is added at the end of the area to make it an integer multiple of m.

  (3) The i-th individual identifier (i is an integer from 1 to N) is i, and the number j of n bit areas after division for each m bits and the bit number in each m bits area are k. , I and (j, k) are in a one-to-one correspondence. For example, in the case of a connected region, j = ((i−1) / m) +1, k = i−j * m. In this case, the inverse mapping is obtained as i = (j−1) * m + k. The individual identifier and the management target number in the information aggregation system are associated with algebraic conversion such as “take a lower digit” or create a correspondence table between the management target number and the individual identifier. .

  Processing in (1) to (3) will be further described with reference to FIG. FIG. 13 is an explanatory diagram of the correspondence between the management target number and the bit position of the collective identifier storage area in the memory area of the receiving node. As shown in FIG. 13, a node to be managed in the information aggregation system is divided into a set of nodes equal to or less than the number of bits in the integer area s, and the set of nodes is associated with the integer area. The N bits memory area is divided into m bits bit fields, and a management target number (node number) in a set of nodes is associated with a bit number in an integer area. Since the management target number and the individual identifier are associated with each other, the individual identifier is associated with 1 bit at a predetermined position in the memory area.

  The above-described processes (1) to (3) are executed in advance by the computer before the operation of the information aggregation system is started. FIG. 14 is a diagram illustrating a configuration example of a computer that associates a management target with a bit position. As shown in FIG. 14, the computer includes a CPU 1401, a memory 1402, an input device 1403, a display device 1404, an external storage device 1405, a recording medium writing device 1406 that can write data to the recording medium 1409, and a communication interface 1407. These are connected to each other by a bus 1408. The association between the management target and the bit position is executed by the CPU 1401, and the execution result is displayed on the display device 1404 and recorded on the recording medium 1409 via the recording medium writing device 1406. Data indicating the above-described correspondence relationship recorded in the recording medium 1409 is stored in the memories 701-2 and 702-2 of the transmission origin node 701 and the reception / relay node 702 that require identification of the management target in the system configuration of FIG. In particular, it can be recorded via a recording medium reading device (not shown).

  FIG. 15 is a diagram showing an example of an individual identifier table possessed by the receiving node when the operation is multiplication. (A) to (d) are used prime numbers or prime numbers 冪, and (e) and (f) are correspondence tables. (G) is the correspondence between the management target number and the real part and imaginary part of the "prime number" (prime element) in Gaussian integer, and (h) is the "prime number" (prime) in the management target number and Eisenstein integer. It is a table | surface which shows the correspondence with the coefficient of 1 of the former, and the coefficient of (omega).

  FIG. 16 is a diagram illustrating an example of an identifier table possessed by the reception-side node when the operation is additive. FIG. 16 shows an example in which the operation used in the function of the reduction 404 in FIG. 4 is additive, the upper limit of the resolution is 2, and the field length of the identifier is 7 bits. (A) is a comparison table of individual identifiers and management target numbers. (B) is a comparison table between a collective identifier and a bitmap of individual identifiers that are generation factors thereof. In this bitmap, the value is 1 when the monitoring condition is satisfied, and the value is 0 when the monitoring condition is not satisfied. (C) is a comparison table of a group identifier and “maximum individual identifier included as a generation factor”. (D) is a comparison table of a group identifier and “minimum individual identifier included as a generation factor”.

  15 and 16, each identifier table implements the identifier coding system 403 of FIG. 4, and data representing each identifier table is a receiving / relay node that functions as a receiving side node in FIG. It is expanded on the memory 702-2 of 702.

  When the identifier analysis mechanism 402 of FIG. 4 uses the comparison table of FIG. 16 with addition as an operation, in order to obtain “an individual identifier that is a generation factor of a received group identifier”, a group identifier and an individual identifier that is a generation factor A comparison table as shown in FIG. 16 (c) or (d) is required to be associated with at least one of these or a plurality of individual identifiers (represented by bitmaps, arrays, linked lists, etc.).

  When the resolution is 2 or more, the number of entries in the comparison table becomes larger than the number of individual identifiers, so that the storage capacity of the memory 702-2 (FIG. 7) necessary to hold the entire comparison table increases. Therefore, a secondary storage medium such as a hard disk storage device may be required. However, the amount of memory reference per search of identifiers in this embodiment (processing for obtaining individual identifiers of generation factors from group identifiers and processing for obtaining management target numbers from individual identifiers) is described in, for example, embodiments described later. It can be suppressed by the “hash function” technique.

  (4) The function of the identifier coding system 403 in FIG. 4 realized by the CPUs 701-1 and 702-1 of the transmission origin node 701 and the reception / relay node 702 in FIG. 7 performs the following processing. The identifier encoding system 403 sets data for turning on the k-th bit for the j-th region divided by m bits as needed (for example, when a status flag of a certain management target is on) It is given as an argument to Reduction or Atomic Operation. For example, for the 1024 bits corresponding to 1024 management targets, if the atomic operation can only process data in units of 128 bits, the node with node number 130 performs bitwise or operation on the second 128 bits area. Perform with data with 2nd bit turned on. As a result, the identifier encoding system 403 notifies that the condition for the management target at the node is satisfied. Here, the bit number in the area divided into m bits may be counted from either. In particular, as the word length of the computer used by m bits, it is not necessary for the Endian numbering method and the bit numbering method of the computer architecture to be the same. For example, the receiving node may select the one that is convenient for the process of specifying the individual identifier from the collective identifier (acceleration).

  FIG. 17 is a flowchart illustrating an example of processing by the identifier aggregation mechanism 401 (FIG. 4) in the transmission side node in the second embodiment.

here,
Group identifier = {value of all reduction operation result stored bit fields}
Individual identifier = (bit field number, bit position in bit field)
Suppose that

  When the processing of the identifier aggregation mechanism 401 is started, the CPU 701-1 of the transmission origin node 701 or the reception / relay node 702 in FIG. 7 inputs the bit field number of the management target managed by the node into the bit field number ( Step S1701).

  When the node is the transmission origin node 1701 (transmission side node) in FIG. 7 (Yes in Step S1702), the CPU 701-1 in FIG. 7 inputs 0 (zero) as the initial value of the bit field (Step S1702). S1703). On the other hand, when the node is not the communication origin node, that is, the reception / relay node 702 of FIG. 7 functioning as a relay node (NO in step S1702), the following processing is executed. The CPU 702-1 inputs the value received from the preceding node as the initial value of the bit field (step S1704).

  When the condition to be notified is established in the management target managed by the own node (Yes in step S1005), the CPU 701-1 or 702-1 sets the bit field value input in step S1703 or step S1704 and the management target. The corresponding bit is ORed (step S1706). On the other hand, when the condition to be notified is not satisfied in the management target managed by the node (NO in step S1705), the CPU 701-1 or 702-1 proceeds to the process in step S1707. The CPU 701-1 or 702-1 transmits the calculation result as a collective identifier as transmission contents to the next transfer destination node via the NIC 701-3 or 702-3 (step S1707), and a series of identifier aggregation mechanisms 401 Terminate the process.

  (5) The relay node or the reception node obtains the entire information of the management target (system, subsystem, job, device, etc.) by referring to the received N bits (n m bits area). In order to confirm that all nodes that collect information have updated a predetermined area, for example, barrier synchronization is executed after each node has updated information, or a reduction operation including a synchronization function is performed. That's fine.

  By the processes (1) to (5) described above, each node can notify the receiving side node by including 1-bit state information for each management target in the group identifier. Arbitrary length data can be reported after being decomposed into bit strings. However, if the number of bits in the data area to be reduced is m, data larger than m bits is processed in units of m bits.

  FIG. 18 is a flowchart illustrating an example of reception processing over the entire group identifier of the identifier analysis mechanism 402 (FIG. 4) in the reception side node in the second embodiment. When the processing of the identifier analysis mechanism 402 is started, the CPU 702-1 of the reception / relay node 702 in FIG. 7 inputs 1 as the initial value of the bit field number (step S1801). When the current bit field number is equal to or less than the number of bit fields (YES in step S1802), the CPU 702-1 executes processing for the bit field of the bit field number in the collective identifier received by the own node. (Step S1803).

  When the process in step S1803 ends, the CPU 702-1 adds 1 to the bit field number (step S1804), and returns to the process in step S1802.

  When the bit field number exceeds the number of bit fields (NO in step S1802), the CPU 702-1 ends the series of identifier analysis mechanism 402 processes.

  FIG. 19 is a flowchart illustrating an example of reception processing of individual bit fields constituting a collective identifier by the identifier analysis mechanism 402 in the reception-side node according to the second embodiment, which is detailed processing in step S1803 of FIG.

  When the processing for the bit field having the predetermined bit field number is started, the CPU 702-1 extracts the value of the bit field having the predetermined bit field number and uses the extracted bit field value as the work area W in the memory 702-2. (Step S1901).

  When the value stored in the work area W is not 0 (zero) (NO in step S1902), the CPU 702-1 reads the bit B in which 1 in the individual identifier appears from the work area W as a Reading Zero Count (LZC) or The next bit position of Trailing Zero Count (TZC) is identified (step S1903), where LZC is an operation for obtaining Number of Leading Zero (NLZ), and NLZ is Most Significant Bit (MSB). ) Indicates the number of 0 counted from the first occurrence until 1. Also, TZC is an operation to calculate Number of Trailing Zero (NTZ), which is the first 1 from the least significant bit (LSB). Points to the number 0 until it appears.

  The CPU 702-1 identifies the management target number corresponding to the identified individual identifier, and executes a predetermined process for the management target of the identified management target number (step S1904). The CPU 702-1 turns off the value of the bit B specified in step S1903 to 0 (zero) (step S1905), and returns to the process in step S1902.

  When the value stored in the work area W becomes 0 (zero in step S1902), the CPU 702-1 ends a series of processes for a bit field having a predetermined bit field number, and the process shown in FIG. The process in step S1803 ends. As for the group identifier, individual identifiers are sequentially added from the state of unit element = 0 (see step S1704 in FIG. 17) by bitwise or operation (step S1706 in FIG. 17). Accordingly, in the flowchart of FIG. 19, individual identifiers are sequentially specified by the inverse operation of the bit unit or operation (step S1903) and the bits are turned off (step S1905), and finally the unit element = 0 is returned. Therefore, when the determination in step S1902 is YES, the process of the flowchart in FIG. 19 ends.

  When a bit string representing data of each node is regarded as a vector of a finite field GF (2) and a matrix is formed from a set of vectors representing data of a plurality of nodes, the data transmission of the transmitting node according to the second embodiment is as follows. This is a communication method based on the following virtual transpose matrix.

In the data aggregation communication normally considered by the present applicant, data corresponding to each transmitting side node is received in the form of “one for each node” as it is, as described below.
node01 | b11 b12 ... b1m ("row vector" corresponding to node01)
node02 | b21 b22 ... b2m ("row vector" corresponding to node02)
... ... ...
node0N | bN1 bN2 ... bNm ("row vector" corresponding to node0N)

On the other hand, the receiving-side node according to the second embodiment receives “data in which bits at the same position of the same type of data are arranged in node order” of data transmitted from all transmitting-side nodes. When the receiving node reads a set of bit data from individual nodes, by looking at each row when it is again considered as a matrix like the following, the matrix of the matrix before transposition (from the transposed matrix) Each column can be reproduced.
1st bit | b11 b21 ... bN1 ("column vector" corresponding to 1st bit)
2nd bit | b12 b22 ... bN2 ("column vector" corresponding to 2nd bit)
...
Mbit | b1m b2m ... bNm ("column vector" corresponding to mbit)

  According to the information aggregation system according to the second embodiment, as in the case of the first embodiment, it is possible to reduce the traffic and time required for information-intensive communication. Furthermore, the access amount of the memory area at each node required for reception or relay and the overhead associated with the memory access are greatly reduced. When the reference memory area in the relay node and the receiving node is reduced, the memory bus bandwidth and the cache usage seen as the whole system are reduced, and the load related to the state monitoring and state sharing processing is reduced. The effect of improving the overall throughput can also be obtained.

  Furthermore, when the receiving side node accumulates 1-bit status information from each transmitting side node and performs specific processing only on the management target in which a predetermined state has occurred, the following technical effect is obtained. It is done. When a specific process is executed only for a management target in which a predetermined state has occurred, the bit position is assigned to the node by reduction by bit operation in the integer area, rather than using the data collected from each node directly by gather. Processing with reference to the corresponding data is faster. This is because, when gathering state information to be managed is gathered in the receiving node, each piece of information to be managed is in an area separated by about the minimum packet length or the minimum length of write RDMA. For this reason, the receiving node needs to issue a load command for each management target when determining that each management target is in a predetermined state. On the other hand, according to the integration method with reduction according to the embodiment, assuming that an area representing an integer is m bits, m management target states are integrated into one integer in advance. For this reason, the number of load instructions issued is 1 / m, the rate of occurrence of cache misses per unit time is greatly suppressed, and the processing speed is increased.

  Further, the technical effect including the case where information of a plurality of bits is accumulated will be described in detail with a focus on the size of the memory area to be used. As in the second embodiment, if all the bits of the area that can be reduced are used effectively, “write RDMA is used by putting all the information of the source node in the packet from each node”. Compared to the case, the memory area for reception can be reduced.

  First, information to be notified from each node is 1 bit, the minimum unit that can be written by write RDMA is W bits, and the number of nodes on the transmitting side is N. In the method in which each node writes information by write RDMA, a NW bits memory area is required at the receiving side node. On the other hand, the required area in the present embodiment, when written as N = qm + r (0 ≤ r <W), is (qm) bits or more and less than ((q + 1) m) bits, that is, Nbits or more (N + m) Less than bits. N, W, and m are positive integers, and W and m are about the same size. If N> 1, always N + W <NW. Therefore, the memory efficiency in the second embodiment with 1-bit notification (whether or not an event has occurred) is NW / (N + W) times as compared with the case where notification is performed by write RDMA from each node. If N >> W, it will be about W times. Since W can range from several tens of bits to one hundred and several tens of bits, it can be considered that N >> W in an information aggregation system having a scale larger than 1,000 nodes.

  When the information to be notified from each node is X bits, YN bits become redundant if there is Y bits where each node writes information by write RDMA and is not effectively used in W bits. Therefore, in general, the order of the number of redundant bits is about N, and is written as O (N) with the Landau symbol. In particular, when X = 1, Y = W-1 and (W-1) N bits are redundant. On the other hand, when the information to be notified from each node in the second embodiment is X bits, X sets of areas necessary for 1-bit notification are prepared. The number of redundant bits is maximized when the remainder r obtained by dividing N by m is 1 for each bit transfer (m-1) bits. (m-1) bits. That is, in the second embodiment, even if the number of nodes N increases, there is an effect of keeping the redundant bit area below a certain size. If N >> X, each node writes information by write RDMA. Compared with the method, the required memory area can be significantly reduced. Even if N and X are about the same number, according to the second embodiment, the number of redundant bits can be reduced and the memory efficiency can be improved. This is because when N is divisible by m, the number of redundant bits when transferring 1 bit is 0, and therefore the redundant bit when transferring X bits for any X> 1 is also 0. When the remainder r obtained by dividing N by m is close to m, the number of redundant bits when transferring 1 bit is mr, and the number of redundant bits in the method in which each node writes information by write RDMA and the second embodiment The ratio to the number of redundant bits is ((W-1) / N) / X (mr). Therefore, if (mr) <(X (W-1) / N), then ((W-1) / N) / (X (mr)))> 1 and the second embodiment is required. The memory area becomes smaller. For example, when N = X, m-r <W-1 is sufficient.

<Third Embodiment>
Next, a third embodiment will be described.

  The basic functional configuration of the third embodiment is the same as the configuration according to the first embodiment described in FIG.

  Similar to the information aggregation system according to the second embodiment, the information aggregation system according to the third embodiment uses the individual identifier corresponding to each management target as a bit corresponding to the serial number of the management target. However, the information aggregation system according to the third embodiment has a configuration different from that of FIG. 7 according to the first or second embodiment. In the third embodiment, as shown in FIGS. 20, 21, and 22, the bit operation in the reduction 404 in FIG. 4 is performed not by the CPUs 701-1 and 702-1 in the node, but by atomic operations and network reduction. This is realized by using an inter-node arithmetic device such as function.

  FIG. 20 is a diagram illustrating a first configuration example of the information aggregation system according to the third embodiment. FIG. 21 is a diagram illustrating a second configuration example of the information aggregation system according to the third embodiment. FIG. 22 is a diagram illustrating a third configuration example of the information aggregation system according to the third embodiment.

  In the configuration example of the information aggregation system in FIG. 20, FIG. 21, or FIG. 22, parts having the same functions as those in FIG.

  As shown in FIG. 20, FIG. 21, or FIG. 22, in the information aggregation system according to the third embodiment, unlike the information aggregation system according to the first or second embodiment, a transmission origin node 701 is provided. The CPU 701-1 and the CPU 702-1 of the reception / relay node 702 do not include the identifier aggregation mechanism 401 and the identifier analysis mechanism 402 of FIG. On the other hand, in the information aggregating system according to the third embodiment, the independent case type inter-node computing device 2001 that executes the identifier aggregating mechanism 401 that collects the individual identifiers into the collective identifiers as shown in FIG. It can be connected to the relay device 703. Further, as shown in FIG. 21, the inter-node computing device 2101 or 2102 can be implemented in each node separately from each component in the transmission origin node 701 or the reception / relay node 702. Furthermore, as shown in FIG. 22, the inter-node calculation function can be integrated and implemented with the NIC 2201 or 2202 in the transmission origin node 701 or the reception / relay node 702.

  The function of the reduction 404 in FIG. 4 indicates, for example, a process defined by an API named MPI_reduce in the Message Passing Interface (MPI) standard, and is the same type as before the calculation by repeating binary operations specifying individual data. Refers to reduction to one data. For example, if the specified binary operation is additive, the corresponding reduction result is the sum of the data of all nodes. The MPI standard defines macros that specify multiplication, bitwise or, “maximum value and place pair”, etc., in addition to addition, as operations that can be specified by reduction using MPI_reduce.

  The performance of the above-described reduction 404 in the environment of the distributed memory system is determined by the communication time between nodes, and the time required for the calculation is a negligible ratio. However, as the system scale increases, the reduction 404 can be a process involving a multi-step relay operation between all nodes having input information.

  A considerable part of the communication time between nodes is the access overhead of the network device to the main storage device, that is, the time for data to pass through the IO bus and the CPU time for controlling the IO processing and performing the calculation. In order to perform the calculation on the CPU, it is necessary to first fetch the calculation target data stored in the memory into the CPU and store the calculation result in the memory again. Further, when the calculation of the reduction 404 is performed on the CPU while performing relay processing of a plurality of stages on the network, data passes through the IO bus and the memory bus twice for each stage of relay. On the other hand, if the calculation is performed inside the network device having the inter-node calculation function, the overhead due to the data passing through the IO bus and the memory bus is reduced, and the reduction performance is greatly improved.

  In the information aggregating system according to the third embodiment, the procedure of the identifier aggregating process is the same as that of the first embodiment except that the bit operation is performed by the inter-node arithmetic device. However, since the types of operations that can be used in the inter-node arithmetic device are limited compared to the case where arithmetic is executed by software on the CPU, arithmetic processing is performed using the functions that are available in the inter-node arithmetic device. Ingenuity is required to realize.

Documents [1] to [5] shown below are techniques related to a device having the functions described above.
[1] A. Gara et al, "Overview of the Blue Gene / L system architecture", IBM Journal of Research and Development VOL. 49 NO. 2/3 March / May 2005, p.7-8.
This document [1] discloses the function of the collective network of Blue Gene / L, which is an example of “an apparatus that performs operations on data on a plurality of nodes independently of a CPU”. The inter-node calculation function is built in the “Network Interface for Collective Network” of each node.

[2] Hiroaki Ishihata, “Development of high-performance, high-performance system interconnect technology” p.3 [Search April 1, 2014], Internet
(URL: http://ngarch.isit.or.jp/psi/images/event/hiroaki_ishihata_20061220.pdf)
[3] Toshiyuki Shimizu, “Development of high-function switches that support collective communication” p.2, p10 [Search April 1, 2014], Internet
(URL: http://ngarch.isit.or.jp/psi/images/event/toshiyuki_shimizu_20080218.pdf)

  In the above documents [2] and [3], “high function switch” is an example of “independent enclosure type inter-node arithmetic device” in “communication device that performs operation on data on multiple nodes independently of CPU”. ”And the internal structure are disclosed.

[4] Y. Ajima, S. Sumimoto, T. Shimizu, "Tofu: A 6d mesh / torus interconnect for exascale computers", IEEE Computer, Vol. 42, No. 11, pp. 36-40 (2009)
[5] Y. Ajima, T. Inoue, S. Hiramoto, T. Shimizu, Y. Takagi, "The Tofu Interconnect", IEEE Micro, Vol. 32, Issue 1, p.21-31 (2012)

  In [4] and [5] above, TBI (Torus Barrier) of ICC (InterConnect Controller: Network Interface and Router) of Torus fusion (tofu), the original network of the super computer “K” (The K computer) Interface) function is disclosed. TBI is an example of the NIC 2201 or 2202 that incorporates the inter-node calculation function of FIG. 22 in the present application. Reference [4] states that the implementation is different from the “high-function switch” in References [2] and [3], but is functionally equivalent.

  In the third embodiment, the hardware mechanism as disclosed in the above documents [1] to [5] is used as an inter-node computing device 2001 (FIG. 20), 2101 or 2102 (FIG. 21), NIC 2201 or 2202 ( 22).

  Network devices that support the reduction function (inter-node arithmetic devices) have relatively diverse types of arithmetic functions such as integer addition, multiplication, bitwise {and, or, exclusive or}, max, min, and floating-point addition. Often have. However, the types of operations that are supported, the data types that are supported, and the size and number of data that can be manipulated at one time depend on the type of network device. If atomic operation and reduction cannot be realized within the range of supported data size and number of data, it may be necessary to expand the application range by hierarchization, use of multiple areas, repeated use, etc. Therefore, any of the available operations described in the second embodiment uses an operation supported by the network device.

  In addition, because the reduction function in the MPI standard, which is an API standard for reduction in parallel processing, implies a synchronization function, the reduction function provided by the network device in the parallel processing environment includes a synchronization function at completion. There are many. In this case, the receiving side node can know from the completion of synchronization that the data from all the transmitting side nodes is ready.

  On the other hand, when the inter-node operation function that does not notify the completion of the operation performed by other nodes, such as Fetch and Add of InfiniBand, is used, the timing when the data of all the nodes on the transmission side are gathered is another method. Need to know at. Therefore, the following synchronization procedure (a) or (b) is performed between the transmission side node and the reception side node.

  (a) Barrier synchronization is executed between all transmitting nodes and receiving nodes as follows. That is, the transmission side node starts barrier synchronization after the transmission of the individual identifier code from the own node is completed. The receiving node starts barrier synchronization from the beginning.

  (b) The receiving node monitors a specific area updated by the transmitting node. In other words, after the transmission of the individual identifier code from the own node, the transmitting side node performs Fetch and And on the area on the receiving node (initial value is 0), and the management target node is in charge of information notification. Add a number. The receiving side node monitors the area that the transmitting side node updates with Fetch and Add, and determines that the process is finished when the data in the area matches the number of management targets.

  Note that it is not always a good idea in terms of performance (even if the counter does not overflow) because all nodes on the sending side directly execute Fetch and Add on the area of the receiving side node. In some cases, it may be advantageous to divide into multiple hierarchies. This layering is performed by software, but the hardware on the network side aggregates data without overhead associated with notification to the CPU by interrupts, and on the CPU without using these mechanisms. Compared to the case where the software performs reduction, it is also possible to increase the number of nodes that can be aggregated in one layer, which is a performance advantage in the third embodiment. This is because when the inter-node operation mechanism and Fetch and Add are not used, the upper node side for information aggregation needs to repeat the communication process as many times as the number of nodes per layer. This is because in order to prevent the delay at each stage from becoming too large, the number of aggregation nodes in one layer must be reduced to a small number such as 2 or 3, and the number of relay stages tends to increase.

  According to the information aggregation system according to the third embodiment, the above-described technical effect similar to that of the information aggregation system according to the first or second embodiment can be obtained. In addition, according to the information aggregation system according to the third embodiment, the real time until the communication is completed is shortened, and the load on the receiving side node (including intermediate nodes in the case of hierarchical processing) can be reduced.

<Fourth Embodiment>
Next, a fourth embodiment will be described.

  This embodiment is an embodiment relating to speeding up of processing after a receiving node receives a group identifier on the premise of the first, second, and third embodiments.

  Each managed data is represented by 1 bit. If the corresponding management target is in a predetermined state, the bit at the position corresponding to the management target is on (1), otherwise it is off (0).

  It is assumed that the collective identifier storage area for reception is composed of a plurality of m bits areas each of which can be processed as an “integer”.

  When performing a specific process for a management target in a predetermined state, the process of “viewing all the bits in each mbits area in order, performing 1 if it is 0, and proceeding if it is 0” is often performed. Is called.

  However, in this method, as shown in FIG. 3 described in the first embodiment, when a relatively small number of nodes are in a predetermined state as shown by a sparse bit string in which almost all bits are 0. Therefore, many condition judgments and bit references are performed for the bit corresponding to the node that does not perform processing.

  That is, in this type of processing, when there are a relatively small number of management targets in a predetermined state, in order to refer to many areas corresponding to the management targets that are not processed in the end, a memory reference following a cache miss is performed. Frequently occurs, and the processing time of the receiving node increases.

  If there are a relatively small number of management targets in a given state, the number of bit operations can be reduced by taking the logical or multiple areas corresponding to the management target group in advance and skipping the group that results in 0. There is a possibility that the speed will be reduced. However, with this method, there is no change in that a load command is issued to the area corresponding to all management targets, so a significant speedup cannot be expected.

  For this reason, for example, it is considered that “grouping” is performed by a representative node for each group. For example, in the embodiment using the reduction using Fetch and Add such as InfiniBand as in the third embodiment described above, when the “combined” node originally exists, it is added when using this method. This method is also conceivable because it requires less system resources.

  In the present embodiment, a group of management targets (with a plurality of hierarchies if necessary) is regarded as a new management target. FIG. 23 is an explanatory diagram of a hierarchy of grouping of management targets (nodes). FIG. 24 is an explanatory diagram of the correspondence relationship between the grouping hierarchy to be managed and the “assigned identifiers” for each subgroup. FIG. 25 is a specific example of FIG. In the present embodiment, logical or is executed in advance on the management target in the group at the transmission side node. That is, as shown in FIG. 23, management targets are hierarchically divided into groups. Next, as shown in the specific examples of FIGS. 24 and 25, when “there is at least one management target in a predetermined state”, the node that manages the group has a bit position corresponding to the group. Creates data with on turned off and other bit positions (bit positions corresponding to other groups) turned off. Then, using such data as input, reduction is performed separately from the status notification of the original management target.

  The above processing is nothing other than setting “managed group” to “(virtual) higher-level managed target”, and the processing procedure at the sending node is subject to management at some nodes. Other than the increase, the same processing as in the first, second, or third embodiment without grouping is executed. That is, in the fourth embodiment, it is only necessary to designate a group area as a storage area in which a group identifier is to be stored.

  The receiving node determines the necessity of area reference for the (lower) management target in the group based on on / off of the bit in the area corresponding to each group (higher management target). Process by skipping the area. That is, as shown in the specific example of FIG. 25, it is treated as a tree structure with the bit on position as a branch in the management area of each hierarchy.

  In particular, when grouping is performed only for the purpose of speeding up the search of the lowest identifier region, as described later, a depth-first search is performed on this tree structure, so that the memory to be held during the search The size of the area can be saved.

FIG. 26 is a diagram illustrating an example of a transmission message and a reception area when limiting a search range of non-zero bits in a sparse bit string by hierarchical grouping. In FIG. 26, 0x before the constant means that it is in hexadecimal notation. As shown in FIG. 26, for each hierarchy,
It is sufficient to generate a collective identifier transmission packet in the identifier transmission message format of bits in the nth layer region address | bit. The “nth layer” indicates the first layer, the second layer, the third layer,. The “nth layer region address” indicates an address corresponding to the nth layer of the storage region of the collective identifier in the memory at the receiving side node (for example, the memory 702-1 of the reception / relay node 702 in FIG. 7). The “bit in the area” is the “n-th layer area address” is a bit string of the collective identifier corresponding to the n-th layer. After that, as described in the first, second, or third embodiment, the bit information of the individual identifier related to the management target of the own node may be set for each layer.

  FIG. 27 is a flowchart illustrating an example of a transmission process of group identifiers grouped hierarchically by the identifier aggregation mechanism 401 (FIG. 4) in the transmission side node in the fourth embodiment. The functional block and system configuration will be described with reference to FIG. 4 and FIG. 7 in the first embodiment. Of course, the system configuration of FIG. 20, FIG. 21, FIG. 22, etc. may be adopted. When the processing of the identifier aggregation mechanism 401 in FIG. 4 is started, the CPU 701-1 or 702-1 of the reception / relay node 702 functioning as the transmission origin node 701 or relay node in FIG. 1 is input (step S2701). If the current group hierarchy number is less than or equal to the predetermined number of group hierarchies (YES in step S2702), the CPU 701-1 or 702-1 is the current group hierarchy indicated by the “group hierarchy number” received by the own node. A collective identifier is obtained from the individual identifier by reduction 404 in FIG. 4 (step S2703).

  When the process in step S2703 ends, the CPU 701-1 or 702-1 increments the group hierarchy number by 1 (step S2704) and returns to the process in step S2702.

  If the group hierarchy number exceeds the predetermined number of group hierarchies (YES in step S2702), the CPU 701-1 or 702-1 ends the series of identifier aggregation mechanisms 401, and displays the group hierarchy group identifier. Transmit (step S2705).

  FIG. 28 is a flowchart illustrating an example of a reception process involving a depth-first search performed by the identifier analysis mechanism 402 (FIG. 4) in the reception-side node according to the fourth embodiment. “Depth-first search” means that in the hierarchical structure of the tree structure, the search is not performed in the horizontal direction for each hierarchy, but the processing of the lowest management target is performed when the lowest hierarchy is reached, and then the first hierarchy is again entered. This is a process for searching for the next lowest layer. The functional block and system configuration will be described with reference to FIG. 4 and FIG. 7 in the first embodiment. Of course, the system configuration of FIG. 20, FIG. 21, FIG. 22, etc. may be adopted. When the processing of the identifier analysis mechanism 402 in FIG. 4 is started, the CPU 702-1 of the reception / relay node 702 in FIG. 7 inputs 1 as the initial value of the group hierarchy number (step S2801). If the current group hierarchy number is less than or equal to the predetermined number of group hierarchies (YES in step S2802), the CPU 702-1 sets zero to the next hierarchy of the current group hierarchy indicated by the “group hierarchy number” received by the own node. It is determined whether there is a non-region (step S2803).

  If the determination in step S2803 is YES, the CPU 702-1 obtains a non-zero area in the hierarchy immediately below the current group hierarchy by the process of “search for lower layer identifier area” described later in FIG. 29 (step S2804).

  Thereafter, the group hierarchy number is incremented by 1 (step S2805), and the process returns to step S2802.

  When the group hierarchy number reaches the number of group hierarchies and becomes the lowest layer, and the determination in step S2802 is NO, the CPU 702-1 executes a process of extracting a management target from the individual identifier extracted from the lowest layer in step S2804. (Step S2806). Thereafter, the CPU 702-1 returns to the process of step S2801 and continues searching for another group hierarchy.

  FIG. 29 is a flowchart illustrating an example of detailed processing of the lower layer identifier area search processing in step S2804 of FIG.

  First, the CPU 702-1 takes out the value of the bit field of the designated area number corresponding to the group hierarchy designated by the group hierarchy number in FIG. 28 (this is referred to as “g”), and operates the memory 702-2. Store in the area W (g) (step S2901).

  Next, the CPU 702-1 determines whether or not the content of the work area W (g) is 0 (zero) (step S2902). If determination of step S2902 is YES, CPU702-1 will transfer to the process of S2906 mentioned later.

  If the determination in step S2902 is NO, CPU 702-1 sets bit B in which 1 in the individual identifier appears to the bit position next to LZC or TZC (see description of step S1903 in FIG. 19) from work area W (g). Is identified (step S2903).

  Next, the CPU 702-1 obtains the identifier area number r of the next hierarchy from the group hierarchy number, the identifier area number in the hierarchy, and B (step S2904).

  After that, the CPU 702-1 turns off the value of bit B specified in step S2903 to 0 (zero) (step S2905).

  After the process of step S2905 or when the determination in step S2902 is NO, the CPU 702-1 notifies the caller program (FIG. 28) of the identifier area number r of the next layer and the contents of the work area W (g). (Step S2906). Thereafter, the CPU 702-1 ends the process of the flowchart of FIG. 29 and ends the process of step S2804 of FIG.

In the fourth embodiment, in addition to the above operation, the speed is increased when “1 is relatively small” when referring to a bit in an area of m bits (handled as an integer) corresponding to the management target of each layer. The target process will be described. Details of this processing are disclosed in the following document [6].
[6] Henry S. Warren, "Hacker's Delight (2nd Edition)", 2012/9/14

  This document describes how to count bits in a specified integer area (Population Count), count bits that are 0 at the beginning or end of an integer area, LZC, TZC, and division by specific constants such as 3, 5, 7, etc. Discloses a currently known fast algorithm. This algorithm can be realized by a general computer.

Means for executing the following bit operations at high speed in the integer data area are known.
(a) Check the number of 1 (bit on) in the integer area.
(b) Find the bit position where 1 appears first, counting from the end of the integer area (LSB: Least Significant Bit).
(c) Find the bit position where 1 appears first, counting from the beginning of the integer area (MSB: Most Significat Bit).

Note that finding the bit position where 1 appears first is equivalent to finding the number of 0s until 1 appears first. Define related terms and abbreviations.
Population Count: Checking the number of 1s in the region
NTZ: Number of Trailing Zero: Number of 0s counted from the LSB until the first 1 appears
TZC: Trailing Zero Count: Operation to find NTZ
NLZ: Number of Leading Zero: Number of 0s counted from the MSB until the first 1 appears
LZC: Trailing Zero Count: Operation to find NLZ

In some cases, the high-speed calculation of the above-described means (a) is used to realize the high-speed calculation of the means (b). For example, the number of 1's in the 32 bits integer area is known to perform the following five repetitions of assignment without judgment or loop. Where bits is an integer field of 32 bits, = is assignment, & is bitwise and, “a >> b” indicates a shift of b bits of a (bit shift processing), and 0x before the constant is expressed in hexadecimal notation Means something.
bits = (bits & 0x55555555) + (bits >> 1 &0x55555555);
bits = (bits & 0x33333333) + (bits >> 2 &0x33333333);
bits = (bits & 0x0f0f0f0f) + (bits >> 4 &0x0f0f0f0f);
bits = (bits & 0x00ff00ff) + (bits >> 8 &0x00ff00ff);
bits = (bits & 0x0000ffff) + (bits >> 16 &0x0000ffff);

  In addition, if the CPU has an “instruction for finding the number of 1s in a given integer area” (for example, the POPCNT instruction, which is one of the SSE instructions for Intel CPUs), the instruction can be used to The number of 1 is required at high speed.

  The above-mentioned means (b) is based on “two's complement” in the expression format of the negative number in the current general CPU. For example, population count for “((x & (−x)) − 1)” You can ask for NTZ.

  Compared with the means (b), the above means (c) is difficult to execute at high speed with general instructions provided in many CPUs. For example, there is a method of using an LZC instruction provided in a CPU such as SPARC64 IXfx developed by Sun Microsystems and currently registered trademark of SPARC International Inc.

  In addition, on CPUs that can directly convert between integers and floating-point numbers specified in IEEE754 between registers, use that the exponent part in the conversion to floating-point format is the "integer part of the logarithm with base 2" A relatively fast calculation method is known.

  As described in the procedure (4) of the second embodiment, “select the one that is convenient for the identification processing (acceleration) of the individual identifier” means that, for example, if the receiving side node has an LZC command, the LSB If not, it refers to the correspondence between the management target number and bit from the MSB.

  If the number of bits that are 1 is relatively small, the method of “using LZC or TZC to determine the management target by sequentially finding the bits that are 1” shifts the reference position by 1 bit and whether the bit is 1 In any case, it is faster than the method based on the “determination loop”.

  Selecting whether to use LZC or TZC based on which can be executed at the high speed at the receiving node is meaningful as part of system optimization.

  According to the fourth embodiment described above, it is assumed that the ratio of “target management objects in a predetermined state” is small, and there are many areas in which no one bit is 1 when viewed in units of an integer area of m bits. In this case, it is possible to speed up the processing by grouping the management targets hierarchically and making the determination on the “higher management target” first.

<Fifth Embodiment>
Next, a fifth embodiment will be described. In this embodiment, an individual identifier encoding method will be described. The functional block and system configuration will be described with reference to FIG. 4 and FIG. 7 in the first embodiment. Of course, the system configuration of FIG. 20, FIG. 21, FIG. 22, etc. may be adopted.

  As described with reference to FIG. 9B in the first embodiment, the operation used in “reduction 404” in FIG. 4 is not only a prime number but also a “number of prime 冪, An individual identifier is assigned using a number whose index itself is a prime number again. In particular, the case where “the heel index itself is 2” is the most efficient from the viewpoint of increasing the number of “individual identifiers having a predetermined size or less”.

  In this embodiment, the resolution described in the first embodiment does not need to be complete (if more management targets than the fixed upper limit k are in a predetermined state, it is necessary to identify those management targets. Not).

  Whether or not the individual identifier is included as a factor of multiplication can be determined from the group identifier calculated from the individual identifier encoded by “reduction” by multiplication, for example, by division with each individual identifier. For example, the individual identifier can be extracted as a multiplicative factor from the group identifier by selecting “a relatively prime integer” or “all different prime numbers” as the individual identifier.

  The assignment of individual identifiers is the same as that described in the first embodiment with reference to FIGS. 9B, 12B, and 8A, 8B, 8C, and 8D. It is the same.

First, as an easy-to-understand example, consider the case where an integer that satisfies the following condition is assigned as an individual identifier (a more general assignment method will be described later).
“Integers corresponding to different management targets do not have a common prime factor.”
This condition can be rephrased as follows.
“Integers corresponding to different management targets are relatively prime.”
For example, if different prime numbers are assigned to different management targets, the above condition is satisfied.

  Here, an individual identifier is made to correspond to a management object in a predetermined state, and 1 is made to correspond to a management object that is not, and the collective identifier is given by multiplicative reduction 404. The storage area is set to a size that does not overflow for any product of k or less individual identifiers. For example, k individual identifiers are taken in descending order, and the product is made large enough to be stored.

  The condition that “individual identifiers do not have a common prime factor” is that when a product that has become a group identifier has not overflowed, the fact that a “predetermined event of a certain managed object has been notified” Guarantees that it can be determined by dividing the group identifier.

  In this way, when the resolution is limited by the upper limit k, it is possible to overflow the calculation for more than k identifiers, and the identifiers that were input can be restored from the operation results of k or less. Uses arithmetic, for example, reduction by integer multiplication or addition of integers or floating point numbers. Note that “overflow” often indicates an error in the calculation procedure when it occurs in normal calculation. In this embodiment, “overflow” is one of “information notification paths for collectively receiving a plurality of management target states”. , "Overflow" is actively used.

  In the present embodiment, by utilizing the fact that there is a constraint on resolution (it is not necessary to be complete), in the same size area, compared with the case of the first to fourth embodiments, more management targets are available. (Or correspond to the same number of management targets with a smaller area).

  For example, if k = 2 and the number of management targets is 54, and the prime numbers correspond to the management targets in ascending order, the 53rd prime number is 241, the 54th prime number is 251 and 241 * 251 <(256 * 256) Note that -1 = 2 ^ 16-1 ("^" indicates power), and 16 bits are enough for the storage area. If k = 1, the number of prime numbers smaller than 2 ^ 16-1 in the 16-bit area = 6542 management targets can be handled.

  In the first to third embodiments, 16 management targets can be handled with 16 bits. The reason why 16 <54 <6542 is that it is necessary to transmit only “a smaller part of the information about a plurality of objects” as k decreases. For example, if it is not necessary to distinguish between “two or more management targets are in a predetermined state” and “only one is in a predetermined state”, the condition is relaxed rather than “resolution is k = 1” It will be possible to deal with more management targets. For example, any integer other than 0 that can be stored in a 16-bit area is used as an individual identifier. A management target in a predetermined state is associated with an individual identifier, and other management targets are associated with 0 (zero). By executing, 2 ^ 16-1 = 65535 management targets can be handled in the 16bit area.

  FIG. 30 is a flowchart illustrating an example of processing of the identifier aggregation mechanism 401 (FIG. 4) in the transmission side node according to the fifth embodiment. FIG. 30 is obtained by replacing the calculation of the reduction 404 from addition to multiplication in the flowchart of FIG. 5 according to the first embodiment. The functional block and system configuration will be described with reference to FIG. 4 and FIG. 7 in the first embodiment. Of course, the system configuration of FIG. 20, FIG. 21, FIG. 22, etc. may be adopted. 4 is started, the CPU 701-1 of the transmission origin node 701 or the CPU 702-1 of the reception / relay node 702 functioning as a relay node in FIG. 7 executes. The work area such as the input parameter 1 or 2 is stored in the memory 701-2 of the transmission origin node 701 or the memory 702-2 of the reception / relay node 702.

  First, it is determined whether or not the own node is a communication origin node (step S3001).

  If the determination in step S3001 is NO, the received value (group identifier) is stored in the input parameter 1 that stores the received value (step S3002).

  If the determination in step S3001 is YES, since there is no received value, the value 1 of the unit element of the multiplication operation is stored in the input parameter 1 (step S3003). If the own node is a communication origin node (transmission origin node 701 in FIG. 7) and there is no received value, the unit element is stored in the input parameter 1, so that the input parameter 1 is used for the calculation of the reduction 404. It is made not to influence.

  Next, it is determined whether or not a condition to be notified is established in the management target managed by the node (step S3004).

  If the determination in step S3004 is YES, the individual identifier corresponding to the management target in the own node (or the own node itself) is stored in the input parameter 2 that stores the state of the own node (step S3005).

  If the determination in step S3004 is NO, the unit element value 1 is stored in the input parameter 2 (step S3006). If the condition to be notified is not satisfied in the management target managed by the own node, the unit element is stored in the input parameter 2 so that the input parameter 2 does not affect the calculation of the reduction 404.

  Thereafter, the multiplicative operation used for the reduction 404 is executed for the input parameter 1 and the input parameter 2 (step S3007).

  Finally, the calculation result in step S3007 is output as a collective identifier that is the content of transmission to the next transfer destination (step S3708). Thereafter, the processing of the identifier aggregation mechanism 401 in the transmission side node illustrated in the flowchart of FIG. 30 ends.

  FIG. 31 is a flowchart illustrating an example of processing of the identifier analysis mechanism 402 (FIG. 4) in the receiving side node according to the fifth embodiment. FIG. 31 is obtained by replacing the calculation of the reduction 404 from addition to multiplication in the flowchart of FIG. 6 according to the first embodiment. The functional block and system configuration will be described with reference to FIG. 4 and FIG. 7 in the first embodiment. Of course, the system configuration of FIG. 20, FIG. 21, FIG. 22, etc. may be adopted. When the processing of the identifier analysis mechanism 402 in FIG. 4 is started, the CPU 702-1 of the reception / relay node 702 in FIG. 7 that functions as a reception side node executes. The work area W, X, and the like are stored in the memory 702-2 of the reception / relay node 702.

  First, the collective identifier in the reduction 404 between nodes is received (step S3101).

  Next, it is determined whether or not an overflow (“overflow” in the figure) has occurred in the group identifier (step S3102). If the determination in step S3102 is YES, substantially no reception process is performed, and the process of the identifier analysis mechanism 402 in the reception side node illustrated in FIG. 31 ends.

  Next, if the determination in step S3102 is NO, the group identifier is stored in the work area W (step S3103).

  Next, it is determined whether or not the value indicated by the work area W has become the unit element value 1 in the multiplication operation of the reduction 404 (step S3104).

  If the determination in step S3104 is NO, one individual identifier is specified from the group identifier, and the result is stored in the work area X (step S3105). Specifically, it is determined whether the group identifier is divisible by each individual identifier. If the group identifier is divisible, it is determined that a predetermined event has occurred in the target represented by the individual identifier, and the individual identifier is specified.

  Thereafter, the management target corresponding to the individual identifier stored in the work area X in step S3105 is processed (specified) (step S3106). This specific specific method is the same as that in step S605 of FIG. 6 according to the first embodiment.

  Next, the individual identifier stored in the work area X identified from the work area W in step S3105 is removed by the inverse operation of the multiplication operation used for the reduction 404, that is, the division operation (step S3107). That is, a division operation called W / X is executed, and the result is stored in the work area W again. Thereafter, the processing returns to step S3104, and the processing from step S3104 to step S3107 described above is repeatedly executed.

  As a result of the value indicated by the work area W being the unit element value 1 in the multiplicative operation of the reduction 404, if the determination in step S3104 is YES, the process of the identifier analysis mechanism 402 in the receiving side node illustrated in the flowchart of FIG. Ends. In the group identifier, individual identifiers are sequentially added from the state of unit element = 1 (see step S3003 in FIG. 30) by multiplicative calculation (step S3007 in FIG. 30). Therefore, in the flowchart of FIG. 31, the individual identifiers are sequentially removed by the division operation (step S3107) which is the inverse operation of multiplication, and finally the unit element = 1 is returned. Therefore, when the determination in step S3104 is YES, the process of the flowchart in FIG. 31 ends.

  In the operation of the fifth embodiment described above, due to the condition that “the identifiers of the nodes are relatively prime” and the fact that “uniqueness of prime factorization”, which is well known in mathematics in the field of “number theory”, is correct. Guarantee is guaranteed.

  Up to this point, the individual identifiers are relatively prime or all prime numbers. However, it is explained that the individual identifiers can be assigned under more general conditions ("relatively prime" or "prime number" is a simple explanation. To do that).

  That is, it is only necessary that “a divides b” and “a was used in the process of multiplication to calculate b” for any individual identifier a and group identifier b. Since it is clear that the latter is a sufficient condition of the former, the latter may be a necessary condition of the former.

  Even if multiple individual identifiers a1 and a2 share a prime factor p, a1 contains only one p, a2 contains two p (ie, divisible by p ^ 2 and not divisible by p ^ 3), etc. Suppose that there is no individual identifier with prime factor p. Whether or not a1 and a2 are used in the process of calculating b depending on how many times the prime factor p is included in b is determined as shown in the table of FIG. 32, the latter is a necessary condition for the former.

  Similarly, for a prime factor shared by a plurality of individual identifiers, the number of each individual identifier including a prime factor is “a number that can determine an individual identifier from a group identifier including a product of combinations of products of arbitrary individual identifiers”. If so, the individual identifiers do not have to be “disjoint”.

  For example, for a prime factor p, there is a set Q = {q ^ a | a = 0,1,2, ...} consisting of 冪 of integer q, and `` each individual identifier sharing a prime factor p is assigned p If the "number of times included" is an element of Q different from each other, any one of the non-zero digits when "the number of times the group identifier contains p" is expressed in q notation as a, and "the prime factor p is q It can be determined that the “unique identifier including ^ a times” is a group identifier generation factor.

  FIGS. 33 to 36 are flowcharts showing detailed processing examples based on the above-described theory of the processing for specifying the individual identifier in step S3105 of FIG.

  First, the processing of the flowchart of FIG. 33 will be described. This flowchart implements the function (A) for extracting the individual identifier component of the prime number from the group identifier.

The component of the received group identifier is stored in the work area W (step S3301).
Next, a component list of individual identifiers is stored in the work area L 1 (step S3302).

Next, the start position of the work area L is stored in the work area X (step S3303).
Next, until it is determined in step S3305 that the value of the work area X has reached the end position of the work area L, the next position in the work area L is sequentially stored in the work area X in step S3307. The process of S3307 is repeatedly executed.

  That is, the component of the individual identifier at the position indicated by the work area X in the work area L is stored in the work area Q in step S3306.

  In step S3307, it is determined whether the value of the work area Q is less than the value of the work area W.

If the determination in step S3307 is YES, the process ends.
If the determination in step S3307 is NO, the position in the work area L indicated by the work area X is updated in step S3308, and the process returns to step S3305.

  As a result of the above repeated operation, when the value of the work area X becomes the end position of the work area L and the determination in step S3305 is YES, the process is terminated.

  In the process of the flowchart, the search result of the list of work areas L can be distinguished by the value of the work area Q. That the value of the work area Q is not 0 (zero) indicates that the individual identifier is found in the list of the work areas L.

  Next, the process of the flowchart of FIG. 34 will be described. This flowchart implements the function (B) for extracting the individual identifier component of the prime number from the group identifier.

The component of the received group identifier is stored in the work area W (step S3401).
Next, one of the prime factors of the work area W is stored in the work area p (step S3402).

Next, the value of the work area p is stored (step S3403).
Next, the value 1 is stored in the work area f (step S3404).

  Next, the result of dividing the value of the work area W by the value of the work area p is stored in the work area V (step S3405).

  Next, the processing of steps S3407 to S3409 is repeatedly executed until it is determined in step S3406 that the value of the work area p is no longer divisible by the value of the work area V.

  That is, if the result of dividing the work area p by the value of the work area V is YES in step S3406, the result of dividing the value of the work area V by the value of the work area p is obtained in step S3407. Stored in

  In step S3408, the result of multiplying the value of the work area p by the value of the work area q is stored in the work area q. The value of the work area q is the maximum power factor for the prime number of the work area p included in the work area W. That is, W / q does not include a factor of a prime number p, and q = p ^ f where f is an exponent.

In step S3409, the value of the work area f is incremented by one.
As a result of the above iterative process, when the value of the work area p is not divisible by the value of the work area V, the process ends when the determination in step S3407 is NO.

  Next, the processing of the flowchart of FIG. 35 will be described. This flowchart is executed subsequent to the flowchart of FIG. 34, and realizes the function (C) of extracting the individual identifier component of the prime number from the group identifier.

  First, the value of the work area f in FIG. 34 is stored in the work area g (step S3501).

  Next, the value of the prime power factor that becomes the individual identifier is stored in the work area X (step S3502).

Next, it is determined whether or not the value is the work area g (step S3503).
If the determination in step S3503 is YES, the process returns to step S3502, and the value of the next prime power factor that becomes the individual identifier is stored in the work area X.

If the determination in step S3503 is NO, the process ends.
Instead of the process shown in the flowchart of FIG. 35 above, even if a procedure is executed in which LZC (g) (leading zero count to g) is d and the (d + 1) -th bit counted from the MSB is 0 Good.

  Next, the process of the flowchart of FIG. 36 will be described. This flowchart implements the function (D) of extracting the individual identifier component of the prime number from the group identifier.

  First, the value of TZC (g) is stored in the work area c (step S3601). Here, TZC (g) is a trailing zero count (counted from LSB (Least Siginificant Bit) within g) continuously to the value of the work area g). The work area g is set in the flowchart of FIG. Instead of TZC (g), LZC (g) (leading zero cunt) may be used.

  Next, p ^ (c + 1) (a value obtained by raising the prime factor p to a value obtained by adding +1 to the value of the work area c) is stored in the work area X (step S3602).

  In the work area g, the value of the (c + 1) -th bit counted from the LSB is changed to 0 (zero) (step S3603).

  In the generalized individual identifier method described here, when the resolution k is increased with the size of the region fixed, {when all the prime numbers or prime numbers are If the number is a power of 2 with a power of 2}, the symbol {p ^ (2 ^ a) | p is a prime number and a = 0,1,2, ...} is used for the set of components of the individual identifier Is advantageous. FIG. 9B and FIG. 15C and FIG. 15D described in the first embodiment illustrate this case.

  On the other hand, if the resolution k is fixed, and more than k management targets are in a given state, the overflow will occur as soon as possible. It is advantageous to include the necessary number in the set of individual identifiers in ascending order including the number other than the prime number.

  As described above, according to the fifth embodiment, when the required resolution k is relatively small, it is possible to reduce the memory area compared to the first to fourth embodiments.

<Sixth Embodiment>
Next, a sixth embodiment will be described.

  This embodiment is a development of the fifth embodiment. The assignment of individual identifiers in the present embodiment follows (e) and (f) of FIG. 15 shown in the description of the first embodiment.

  In this embodiment, an ordered set of a plurality of integers is associated with each node in the same system configuration as in the fifth embodiment. Let i, j be the node number, and associate m number pairs with each node.

That is, a vector having m integers as elements as shown below is set as an individual identifier to be managed.
Z (i) = (zi1, zi2, ..., zim)
Z (j) = (zj1, zj2, ..., zjm)

If i ≠ j, the number of at least one place in the m sets is different. In other words, “∨” represents or as a logical expression.
i ≠ j _⇔ (zi1 ≠ zj1 ∨ zi1 ≠ zj1 ∨ ... ∨ zim ≠ zjm)
It is.

Here, the set of integers used may be the same or different for each component of the vector, but the different elements for each set are disjoint. That is,
S1 = {a set of integers for the first component of the vector}
...
Sm = {set of integers for the mth component of the vector}
, S1, ..., Sm is a set of integers such that two different elements are all prime.
Except for the case where all components are 1, 1 may appear in the components.

  In the following description, the number of prime factors that generally appear in a set of x disjoint integers is greater than or equal to x, and the number of prime factors is x only if all the x numbers are prime. .

  In the fifth and sixth embodiments, the factorization for node identification is nothing but a process of sequentially trying to determine whether the reduction result is broken by a predetermined number of sets of elements.

  Compared with the fifth embodiment in which a single number is used to identify a management target, this embodiment increases the number of fields to be used, but is a relatively small number and a small size for a system with the same number of management targets. Nodes can be identified by a set of Therefore, factorization of each element can be performed at high speed, and the specific processing time of the node is shortened as compared with the fifth embodiment.

  The number of elements of the set S used in the fifth embodiment needs to be greater than or equal to the number N of nodes, but the number of elements in the set S1... Sm used in this embodiment is the smallest exceeding N / m. A natural number is sufficient. In both embodiments, the maximum and average number of divisions required are equal. This is because, in this embodiment, factorization of each component is repeated m times, but the number of divisions required for each component is 1 / m.

  Although the integers of the individual identifiers so far are relatively prime, as in the fifth embodiment, a more general allocation in which the prime factor includes the number of “prime number よ う な whose index itself is a prime number 冪” A method is possible (the term “disjoint” so far is for the sake of simplicity).

Here, reference will be made to the basic principle common to other embodiments described later.
Both the fifth and sixth embodiments are based on the common principle of “uniqueness of prime factorization for natural numbers”. The only difference is “whether the identifier assigned to each node is a single number or a set of a plurality of numbers”.

  Even for whole integers (in the usual sense) including zero and negative numbers, 0 is excluded from decomposition and “+ 1, -1 is not considered a prime factor (in other words, it is a product of negative numbers). Note that the difference in how the sign of each is attached to each factor is not considered to be a different decomposition).

  If “unique” “prime factorization” in the same meaning as in the case of integers is possible with “multiplication” defined in a general set, the conditions for “prime numbers” in that set are the fifth and In the same manner as in the sixth embodiment, the identifier can be encoded. (In general, "numbers whose reciprocals are integers" such as 1 and -1 are not included in "prime factors").

  An example of a set capable of “unique” “prime factorization” in the same meaning as in the case of an integer is a set made up of polynomials having coefficients of arbitrary “field” elements. In the set of polynomials, “irreducible polynomial” corresponds to “prime number”.

  Here, the “field” is a number in which four arithmetic operations are defined, both addition and multiplication satisfy the exchange law and the coupling law, include 0 and 1, and all elements other than 0 are “multiplied to be 1”. It refers to the set where “inverse element” exists.

  “Field” includes “whole rational number”, “whole real number”, or “whole complex number”, and finite field GF (q) (where q is the number of elements as a set). In order to emphasize that the set of “whole rational numbers”, “whole real numbers”, or “whole complex numbers” is “field”, it is called “rational number field”, “real number field”, or “complex number field”.

  There are other sets with multiplicatives that hold “uniqueness of prime factorization” besides polynomials with integers and “field” coefficients. An embodiment using “algebraic integer” which is a kind of such a set will be described later in the description of the seventh embodiment.

  FIG. 37 is a flowchart showing an example of processing of the identifier aggregation mechanism 401 (FIG. 4) in the transmission side node in the sixth embodiment based on the above theory. The basic concept of the processing in this flowchart is the same as that of FIG. 5 (first embodiment), FIG. 17 (second embodiment), FIG. 30 (fifth embodiment), and the like. FIG. 37 is obtained by replacing the operation of reduction 404 from addition to multiplication in the flowchart of FIG. 5 according to the first embodiment, and vectorizing individual identifiers and group identifiers based on the above-described theory. The functional block and system configuration will be described with reference to FIG. 4 and FIG. 7 in the first embodiment. Of course, the system configuration of FIG. 20, FIG. 21, FIG. 22, etc. may be adopted. 4 is started, the CPU 701-1 of the transmission origin node 701 or the CPU 702-1 of the reception / relay node 702 functioning as a relay node in FIG. 7 executes. The work area such as the input vector 1 or 2 is stored in the memory 701-2 of the transmission origin node 701 or the memory 702-2 of the reception / relay node 702.

  The identifier in this example is an ordered set of integers. Here, an “ordered set” is called a “vector”, and an integer that is an element of the “ordered set” is called a component. When emphasizing that the identifier is a vector, the “individual identifier vector”, the “collective identifier vector”, and the combination thereof are called “identifier vector”. The calculation between identifier vectors is determined by the calculation between components at corresponding positions.

  In FIG. 37, first, it is determined whether or not the own node is a communication origin node (step S3701).

  If the determination in step S3701 is NO, the received group identifier vector is stored in the input vector 1 that stores the received value (step S3702).

  If the determination in step S3701 is YES, since no value has been received, the value 1 of the unit element of the multiplication operation is stored in all components of the input vector 1 (step S3703).

  Next, it is determined whether or not a condition to be notified is established in the management target managed by the own node (step S3704).

  If the determination in step S3704 is YES, the individual identifier vector corresponding to the management target in the own node (or the own node itself) is stored in the input vector 2 that stores the state of the own node (step S3705).

  If the determination in step S3704 is NO, unit element value 1 is stored in all components of input vector 2 (step S3706).

  Thereafter, a multiplicative operation used for the reduction 404 is executed between all components of the input vectors 1 and 2 (step S3707).

  Finally, the calculation result in step S3707 is output as a collective identifier vector that is the content of transmission to the next transfer destination (step S3708). Thereafter, the processing of the identifier aggregation mechanism 401 in the transmission side node exemplified in the flowchart of FIG. 37 ends.

  FIG. 38 is a flowchart showing an example of processing of the identifier analysis mechanism 402 (FIG. 4) in the receiving side node in the sixth embodiment based on the above theory. The basic concept of the processing in this flowchart is the same as that in FIG. 6 (first embodiment), FIG. 18 (second embodiment), FIG. 31 (fifth embodiment), and the like. FIG. 38 is obtained by replacing the operation of reduction 404 from addition to multiplication in the flowchart of FIG. 5 according to the first embodiment, and vectorizing individual identifiers and group identifiers based on the above-described theory. The functional block and system configuration will be described with reference to FIG. 4 and FIG. 7 in the first embodiment. Of course, the system configuration of FIG. 20, FIG. 21, FIG. 22, etc. may be adopted. When the processing of the identifier analysis mechanism 402 in FIG. 4 is started, the CPU 702-1 of the reception / relay node 702 in FIG. 7 that functions as a reception side node executes. The work area vector W, X, and the like are stored in the memory 702-2 of the reception / relay node 702.

  First, the collective identifier vector in the reduction 404 between nodes is received (step S3801).

  Next, it is determined whether or not an overflow (“overflow” in the figure) has occurred in the collective identifier vector (step S3802). If the determination in step S3802 is YES, the reception process is not substantially performed, and the process of the identifier analysis mechanism 402 in the reception side node illustrated in FIG. 38 ends.

  Next, if the determination in step S3802 is NO, the group identifier vector is stored in the work area vector W (step S3803).

  Next, it is determined whether or not all the component values of the work area vector W have become the unit element value 1 in the multiplication operation of the reduction 404 (step S3804).

  If the determination in step S3804 is NO, one individual identifier vector is specified from the group identifier vector, and the result is stored in the work area vector X (step S3805).

  Thereafter, the management target corresponding to the individual identifier vector stored in the work area vector X in step S3805 is processed (specified) (step S3806).

  Next, the inverse operation of the multiplication operation used for the reduction 404, that is, the division operation is applied to each component of the work area vector W and the work area vector X, and is identified from the work area vector W and stored in the work area vector X in step S3805. The individual identifier is removed (step S3807). Thereafter, the processing returns to step S3804, and the above-described processing from step S3804 to step S3807 is repeatedly executed.

  If the determination in step S3804 is YES, the processing of the identifier analysis mechanism 402 in the reception side node exemplified in the flowchart of FIG.

  In general, in order to perform division, it is necessary to fetch the dividend and the divisor from the memory. In the fifth embodiment, if all the component sets are the same, the number of divisors to be fetched from the memory is 1 / m. In a large-scale system where N >> m (N is sufficiently larger than m), the benefit of increasing the number of times the divisor hits the cache increases the number of cache misses by changing the dividend from 1 to m. Exceeds increasing losses. Therefore, if N >> m, the present embodiment is more advantageous than the fifth embodiment in terms of calculation processing time.

  Further, when N is sufficiently large, the present embodiment is not disadvantageous with respect to the amount of memory used. This is because if we write π (x) as a function representing the number of prime numbers less than or equal to x, the ratio of π (x) to (x / log (x)) This is because it is known to converge to 1 when x → ∞.

  In other words, the “prime number density” (π (x) / x) is approximately the reciprocal 1 / log (x) of the logarithmic function (the logarithm here is a natural logarithm). In other words, when adding a prime number that can be used as a prime factor of a component due to an increase in the number of nodes, it is necessary to increase the average exponentially. For this reason, the number of bits of the memory area necessary for storing without overflowing is a single prime number in the present embodiment when a set of individual identifiers by a plurality of combinations of relatively small prime numbers or prime numbers is used. In addition, the number of cases becomes smaller as compared with the fifth embodiment using a prime number.

<Seventh Embodiment>
Next, a seventh embodiment will be described.

  In addition to integer multiplication, if an operation in a set has the same nature as integer multiplication in the sense that "the original element can be restored from the result of the operation of multiple elements", that operation can be used to implement the functions shown in Fig. 4. Can be used. In particular, each operation of the function of FIG. 4 can be performed in substantially the same manner as when using a normal integer multiplication by using a set having multiplication that establishes “unique factorization uniqueness”.

  The assignment of the individual identifier in the seventh embodiment follows (g) and (h) in FIG. 15 shown in the description of the first embodiment.

  For any "body", the "vector space" with the "body" as the "coefficient field" is an addition that satisfies the exchange law and the coupling law between the elements "vector", and the specified body element is a scalar. Defined as a set having the operation of “scalar multiplication”.

  A field K including a rational number field and having a finite dimension as a vector space is called a “(finite dimension) algebraic number field” (hereinafter, “finite dimension” is omitted). Write the whole "algebraic integer" in K as O_K. (Here, “algebraic integer” refers to a complex number that is the root of the equation f (x) = 0, where f (x) is an irreducible polynomial with an integer coefficient of highest order 1).

  Since O_K is known to be a closed set for addition, subtraction, and multiplication, the number that plays the role of "prime number" in O_K is p | ab → p | a ∨ p | b (here "X | y" is defined by x being divisible by y, "→" is "if", and "∨" is "or".

  By this definition, the conditions and examples that satisfy “uniqueness of prime factorization” in O_K are well known in a field of mathematics called “algebraic number theory”. Therefore, each operation of the function of FIG. 4 can be performed by using a method similar to the fifth or sixth embodiment using any O_K that satisfies “unique factorization”.

  The point at that time is that the algebraic field K has a finite dimension on the rational field. Therefore, with n as its dimension, n elements k1, k2, ..., kn are appropriately selected from K, and any element of K is a linear combination of rational coefficients {c1 * k1 + c2 * k2 +. ..cn * kn | ci can be expressed as a rational number, ki∈K (i = 1,2, ... n)}, so that the storage area can be a fixed length. Further, k1,..., Kn, in which the element coefficients of O_K are all integers, are selected, and a set of n integers and O_K elements are made to correspond one-to-one. It is known that the algebraic field K is obtained by adding one algebraic integer α (and its power) to the rational number field. Therefore, for k1, ..., kn, take one "irreducible polynomial f (x) with integer coefficient of highest order 1" and use α to satisfy f (α) = 0. K1 = 1, k2 = α,..., Kn = α ^ (n-1).

  Where k1, ..., kn (as a vector space over a rational field) are the basis of K. Note that the necessary and sufficient condition that n elements of K are bases is “linearly independent” as an element of the vector space on the rational number field, so the choice of {k1, ..., kn} is 1 Not street. Unless otherwise noted, {1, α, ..., α ^ (n-1)} is set by an algebraic integer α included in K 1.

In the following, two examples where n = 2 are shown. The principle is the same for general n.
First, the imaginary unit i is an algebraic integer because it is the root of x ^ 2 + 1 = 0. A field Q [i] obtained by adding an imaginary unit i to a rational number field is a two-dimensional vector space on the rational number field.

  The set Z [i] = {complex number whose real part and imaginary part coefficients are both integers} is called "Gaussian integer". A Gaussian integer is an example of O_K described above for K = Q [i]. It is known that “uniqueness of prime factorization” holds for Gaussian integers.

  For example, in “Gaussian integer”, 2 is expressed as the product of two Gaussian integers, such as 2 = (1 + i) × (1-i), so 2 is not a “prime number as a Gaussian integer” . However, 1 + i, 1-i is “a“ prime number in a Gaussian integer ”” (as is clear from the absolute values of the real and imaginary parts). The method of decomposing 2 into “prime numbers in Gaussian integers” is limited to the decomposition of these two Gaussian integers into products.

  A Gaussian integer is divided into a real part and an imaginary part and stored in two ordinary integer areas. The individual identifiers of each management object are the fifth and the second under the condition of “prime number in Gaussian integer” The conditions for prime numbers in the sixth embodiment are replaced and set. Then, a group identifier can be obtained by reduction using “product as Gaussian integer (product as complex number)” as a binary operation. This is because, for two Gaussian integers A and B, a certain Gaussian integer C can be taken to be A = B × C. The reciprocal D as a complex number of B is taken and the coefficient of D × A is the real part. This is because it can be determined whether or not both imaginary parts are integers. Due to the uniqueness of prime factorization within the above-mentioned Gaussian integer, the determination of which individual identifier product is generated can be performed as in the fifth and sixth embodiments.

  In addition, a division method that generates a quotient and a remainder is defined between Gaussian integers, and whether or not the group identifier (component) is divisible by the individual identifier (component) depending on whether the remainder in this division is zero or not. It is known that it is possible to make a judgment with

  Next, if ω = (-1 + i√3) / 2 (i is an imaginary unit), ω is an algebraic integer because it is the root of x ^ 2 + x + 1 = 0. A field Q (ω) obtained by adding ω to a rational number field becomes a two-dimensional vector space on the rational number field. Because it is clear that Q [ω] = {A + Bω | A, B is a rational number} for addition and multiplication, so if the division is also closed, Q (ω) = Q [ω] This is because it is understood that it is two-dimensional on the rational number field. In particular, the reciprocal may be closed. For any two rational numbers a and b where a + bω ≠ 0, 1 / (a + bω) = (a + bω ^ 2) / (a ^ 2-ab + b ^ 2) = ((ab) -ω) / (a ^ 2-ab + b ^ 2) ∈ Q [ω]

The set Z [ω] = {a + bω | a, b is a normal integer} is called “Eisenstein integer”.
(a + bω) * (c + dω) = ac + (bc + ad) ω + bdω ^ 2
Substituting ω ^ 2 = -1-ω for, it can be calculated as follows.
(a + bω) * (c + dω) = (ac-bd) + (bc + ad-bd) ω

  Therefore, since the product of “Eisenstein integers” can be expressed as an operation between “two integer pairs”, one “Eisenstein integer” is held by two ordinary integer regions, and “Eisenstein integers” are stored. "Stein integer" can be an individual identifier.

For two Eisenstein integers A and B, whether a certain Eisenstein integer C exists and A = B × C is determined by whether D × A is an Eisenstein integer with respect to the inverse D of the complex number of B Is done. From the following equation, for any reciprocal number D of Eisenstein integer B, D = (E / Z) can be expressed by a combination of a certain Eisenstein integer E and a normal integer Z. Can be determined by whether the E × A coefficient is divisible by Z or not.
(a + bω) * (a + bω ^ 2) = a ^ 2 -ab + b ^ 2
∴1 / (a + bω) = (a + bω ^ 2) / (a ^ 2 -ab + b ^ 2)
“Uniqueness of prime factorization” holds among “Eisenstein integers”.

  Also, it is known that a division method for generating a quotient and a remainder is defined in “Eisenstein integer”, and it is possible to determine whether or not it is divisible even if the remainder in this division is 0 or not.

  From the above, the calculation function of FIG. 4 can be realized by using “Eisenstein integer” (or a set thereof) as an individual identifier and obtaining a group identifier by reduction by product.

  Even in a general nth-order algebraic field, the root of f (x) = 0 is α for the nth-order irreducible polynomial f (x) with the highest-order coefficient of 1, and the elements of O_K are {1, α, α ^ 2, ..., α ^ (n-1)} is expressed as a linear combination of integer coefficients. As a result, the product of the elements of O_K can be calculated as an operation between “n sets of integers” by replacing α ^ n with a linear combination of で smaller than the n-th order of α by f (α) = 0. I understand that I can express it.

  For any nth-order algebraic field K and a set of algebraic integers O_K, there exists a function N (γ) that satisfies the following (a) and (b) (called “(norm) norm”) Things are known.

(a) For any element of K, (1) and (2) hold.
(1) For any element γ of K, N (γ) is a rational number.
(2) For any two elements γ1 and γ2 of K, N (γ1 × γ2) = N (γ1) × N (γ2)

(b) In addition to (a), the following (1) and (2) also hold for any element β of O_K.
(1) N (β) is an integer.
(2) The reciprocal δ of β is expressed as δ = (ε / N (β)) by an element ε of O_K.
For example, N (a + bi) = a ^ 2 + b ^ 2 for Gaussian integer a + bi, N (a + bω) = a ^ 2-ab + for Eisenstein integer a + bω b ^ 2.

  Therefore, even for a general nth-order algebraic field K, if the uniqueness of prime factorization is established for the entire algebraic integer O_K, it is possible to reduce the number of elements of O_K (or a set of them) as an individual identifier. By obtaining the group identifier, the calculation function of FIG. 4 can be realized. Here, it is determined that the “individual identifier divides the collective identifier” by the property (b)-(2) of the norm. If the nature of the prime factor included in the individual identifier is selected in the same way as in the fifth and sixth embodiments due to the uniqueness of the prime factorization, it will be “divisible” and “the individual identifier will be used in the process of calculating the group identifier. It is guaranteed.

  However, the uniqueness of prime factorization does not always hold for an algebraic integer O_K in a general nth-order algebraic field K. Also, in O_K, a division that generates a quotient and a remainder is defined, and it is not always possible to determine whether or not it is divisible by the remainder of the division being zero.

  However, the necessary and sufficient conditions for the uniqueness of prime factorization to hold for the algebraic integer O_K are well known. A set of individual identifiers can be determined from any O_K for which “uniqueness of prime factorization” is established, according to the same conditions for “prime numbers” as in the fifth and sixth embodiments.

39 to 41 are flowcharts illustrating an example of processing according to the seventh embodiment.
In the fifth or sixth embodiment, the reduction calculation for realizing the reduction 404 of the identifier aggregating mechanism 401 in FIG. 4 is executed in step S3007 in FIG. 30 or step S3707 in FIG. In these reduction operations, the individual identifier is “a prime number or a prime power as an ordinary integer”. On the other hand, the individual identifier in the present embodiment is one algebraic field that is not a rational number field, and is a “prime element” (a prime number as an algebraic integer) in the algebraic field. Specifically, a prime number as a Gaussian integer is used. From these relationships, “ordinary integer product and quotient” in the fifth embodiment becomes “algebraic integer product and quotient” in the present embodiment. Based on these, FIG. 9 in the present embodiment replaces, for example, the processing in step S3007 in FIG. 30 in the fifth embodiment or step S3707 in FIG. 37 in the sixth embodiment.

  Further, in the fifth or sixth embodiment, the “processing for restoring individual identifiers of generation factors from population identifiers” of the identifier analysis mechanism 402 in FIG. 4 is executed in step S3107 in FIG. 31 or step S3807 in FIG. Yes. FIG. 40 in the present embodiment replaces these processes.

  Furthermore, FIG. 41 in the present embodiment is a flowchart in which the process of FIG. 40 is generalized in another form.

First, as a premise of the processing of the flowchart of FIG. 39, the basis of the algebraic field K is given as {1, α, α ^ 2, ..., α ^ (n-1)} by an algebraic integer α satisfying the following properties. It has been.
f (x) = x ^ n + a_ (n-1) × x ^ (n-1) + .... a_k * x × k + ... + a_0
f (α) = 0

Then, the algebraic integers β and γ are expressed by the polynomial of α as follows.
g (x) = b_m ^ x ^ m + b_ (m-1) * x ^ (m-1) + .... b_1 * x + b_0
β = g (α)
h (x) = c_l ^ x ^ l + b_ (l-1) * x ^ (l-1) + .... c_1 * x + c_0
γ = h (α)

  The flowchart of FIG. 39 operates using the algebraic integers β and γ defined as described above.

  First, the coefficient vector of the algebraic integer β is stored in the work area B (step S3901).

  Next, the coefficient vector of the algebraic integer γ is stored in the work area C (step S3902).

  Further, a coefficient vector of the product of the algebraic integers 1 and 2 is calculated, and the coefficient vector is stored in the work area D (step S3903).

  The above-described flowchart of FIG. 39 replaces, for example, the process of step S3007 of FIG. 30 in the fifth embodiment or step S3707 of FIG. 37 in the sixth embodiment.

Next, the process of the flowchart of FIG. 40 will be described.
First, the coefficient vector of the dividend is stored in the work area b (step S4001). Next, the coefficient vector of the divisor is stored in the work area c (step S4002).

  Further, the reciprocal of d is expressed in the form of e / N (c) (e is an algebraic integer of K, N (c) is the norm of c) (step S4003).

Next, the e × b coefficient vector is stored in the work area f (step S4004).
Then, it is determined whether or not the vector component of the work area f is divisible by each component of N (c) (step S4005).

  For example, the process in step S3107 in FIG. 31 or step S3807 in FIG. 38 in the fifth embodiment is replaced by the flowchart in FIG.

  Next, the processing of the flowchart of FIG. 41 will be described. In this flowchart, after the value of i is reset to 0 (zero) in step S4101, it is incremented by +1 in step S4110, and changes from 0 to m until it is determined in step S4103 that m has been reached. Be made. Further, for each value of i, after the value of j is reset to 0 in step S4102, it is incremented by +1 in step S4109, and from 0 until it is determined that it has reached l in step S4104. Can be changed to l.

  If it is determined in step S4105 that the value of i + j is greater than or equal to n using i and j that change in this way, in step S4106, the value of i + j is set to the algebraic integer α. The coefficient of the calculation result α ^ (i + j) to be raised is stored in the work area d.

  In step S4107, α ^ n in α ^ (i + j) is replaced with a term of 冪 that is less than or equal to the n−1 order of α in the relational expression f (α) = 0.

Thereafter, in step S4108, the coefficient from the term α ^ (i + j) is added to each term in the multiplication result coefficient storage area D.
The above processing is repeatedly executed while i and j are incremented.

  In order to efficiently perform operations on coded identifiers, identifiers must be stored in a specific fixed-length area or a set of those areas that are supported by the CPU or inter-node arithmetic device. . There are more “prime numbers” (prime elements) in algebraic integers such as “Gaussian integers” and “Eisenstein integers” than ordinary prime numbers when the coefficients are compared within a certain range. Therefore, according to the present embodiment, when an algebraic integer is used, it is relatively easy to assign an individual identifier so as to increase the resolution k using the same size region.

  Furthermore, when compared with the method of “representing an integer whose number of digits in binary number is doubled by using two integer regions”, the two-dimensional upper bound on a rational field such as “Gaussian integer” or “Eisenstein integer” ( For a set of algebraic integers in an algebraic field, both regions can be used effectively within a range of numbers with relatively small absolute values. When two integer areas represent integers with twice the number of digits, the area used to represent the upper digits is not used for storing individual identifiers unless an integer of a size that cannot be represented by only one area is used. For this reason, using “Gaussian integers” and “Eisenstein integers” as individual identifiers compares memory efficiency on the assumption of the same amount of computation. It is more advantageous to do.

  The same thing can be expressed by the method of representing an algebraic integer in an algebraic field of n dimensions over a rational number using n integer areas, and “the number of digits in binary number is n using n integer areas. This is also true when compared to the “representing a double integer” method.

<Eighth Embodiment>
Next, an eighth embodiment will be described.

  If the identifier coding system 403 shown in FIG. 4 is used for the reduction using multiplication, it is possible to use an inter-node operation device that supports addition by converting the multiplication to addition using the logarithm of each identifier. Realization and speeding up by it. However, when selecting the number to be used as an individual identifier, the following cautions and ingenuity are required. The details will be described below.

  “When selecting the nearest integer and factoring it, it is verified in advance that there is no misjudgment due to error accumulation in floating point arithmetic, or it is guaranteed by accuracy-compensated arithmetic. Since it will be in floating point format, in subsequent calculations it will be necessary to replace the “equal” determination in integer calculations with “the error is less than a predetermined value (eg a value called“ machine epsilon ”)” is there. Convert the data as it is or convert it to a fixed-point format (integer format), take the sum, and return the result to the floating-point format as the input to the exponential function. Errors accumulate in each process of a series of processing to restore the previous product.

  In order to reduce the influence of the precision error in the calculation in the floating point format, it is effective to set the original number (before taking the logarithm) to “the same size”. In this case, the policy of “determining the maximum value and determining the range in descending order” is advantageous.

  Similarly to the fifth to seventh embodiments, the present embodiment is also applied when the resolution is limited to a positive integer k.

  Although the logarithm of the individual identifier is used in the present embodiment, the description in the case of using the logarithm function of the complex number is complicated in spite of having many common points in principle. And

  The functions realized by the multiplication of integers in the fifth and sixth embodiments are realized by addition in this embodiment. However, both floating point addition and integer (fixed point) addition are used.

  The fifth embodiment can be regarded as a case where the number of components is 1 in the sixth embodiment. On the other hand, the sixth embodiment can be regarded as having implemented the fifth embodiment on a plurality of components of a vector. In the present embodiment, in order to simplify the description, one component will be described below.

  As in the fifth and sixth embodiments, an individual identifier is assigned to each management target (for example, each node), and the group identifier is “reduction by integer multiplication” as in the fifth and sixth embodiments. Defined as “result”. However, in the present embodiment, the “reduction result by multiplication by integers” is obtained by using a reduction operation by addition via logarithm (based on “logarithm of product” is “sum of logarithms”).

  However, since the logarithm other than the number that is the base of the logarithm is not an integer, an error occurs when the floating-point format is used, and an error also occurs when calculating the addition of the logarithmic floating-point number. Considering the above, it is necessary to devise when assigning identifiers.

  The calculation procedure itself for obtaining the individual identifier from the group identifier is the same as in the fifth and sixth embodiments, except that the “logarithm of product” is “sum of logarithms”. The logarithm of the individual identifier is calculated at the time of assigning the individual identifier, and the logarithmic value is stored in the notifying node so that the logarithm calculation is not required at the time of information notification. A value after conversion into a logarithm of the value of the individual identifier, or after conversion into a logarithm and further multiplied by a constant to form an integer form is called a “modified individual identifier” to be distinguished from the original individual identifier. Similarly, the result of reduction (summation) for the “modified individual identifier” is called a “modified group identifier” to distinguish it from the original group identifier.

(a) When using floating-point addition
(1) The logarithm of the individual identifier to be managed is taken at each node that notifies the information, or the logarithm of the individual identifier stored in advance is prepared as an input to the reduction. In the latter method, there is no need to calculate the logarithm at the transmitting node. The reduction operation is performed so that the node that collects the information receives the reduction result obtained by adding the logarithm of the individual identifier to be managed.
(2) The node that aggregates information restores the product of individual identifiers from the sum of logarithms. Since the original data is an integer, the group identifier is obtained by taking the integer closest to the result restored from the logarithm by an exponential function.
(3) Find individual identifiers that divide group identifiers.

(b) When using integer addition
(1) The logarithm of the individual identifier to be managed is taken at each node that notifies the information, or the logarithm of the individual identifier stored in advance is prepared as an input to the reduction. Here, “preparation” means that the logarithm of the individual expression identifier in the floating-point format is multiplied by a constant and converted into an integer, or data input that has been converted into an integer by multiplying by a constant in advance. The latter method does not require the sending node to perform floating point operations.
(2) The node that collects the information performs a reduction operation so as to receive a reduction result obtained by adding “the number obtained by multiplying the logarithm of the individual identifier to be managed by a constant and converting it into an integer”. Here, after converting to a fixed-point format up to a certain digit, multiplying the number of digits m after the decimal point by 2 ^ m, "expressing the approximate value of the logarithm in integer format" means "converting to an integer" It is called.
(3) The node that aggregates the information returns the reduction result of (2) to the floating-point format, and divides by the size adjustment constant 2 ^ m used in the conversion to the integer format in (2). Return to.
(4) The node that collects the information restores the collective identifier that is the product of the original individual identifiers from the “total sum of logarithms of individual identifiers” returned to the floating-point format. Since the original data is an integer, the group identifier is obtained by taking the integer closest to the result restored by the exponential function.
(5) Find individual identifiers that divide group identifiers.

  The point of the present embodiment is to eliminate an erroneous determination due to an error associated with the operation of taking the logarithm itself and expressing the result with a finite number of digits. In other words, reducing the magnitude of the error to an extent that does not affect the determination result is the key to achieving high speed. (By using “multiple-length calculation”, the error can be reduced as much as possible, but since the memory access amount including the required amount of memory area and the node on the notification side increases, it can be realized by calculation in a fixed-length area. Is advantageous in terms of performance).

  Although there is a method to limit the error range by “calculation with accuracy guarantee”, a simpler method is in a predetermined state according to the procedure of (a) and (b) above for a set of predetermined individual identifiers. It is to actually calculate and confirm that the individual identifier can be restored. This calculation may be performed when a set of individual identifiers is determined. For example, if a set of individual identifiers having a sufficiently large number of elements is prepared in advance, the above accuracy check calculation does not adversely affect the performance when the system operates.

  Even in a system that needs to dynamically increase the number of management targets, it is possible to avoid calculating accuracy check during operation by using it by extracting it from the pool of available individual identifiers.

  For example, in the case of resolution k, the confirmation calculation is performed for (a) all combinations of individual identifiers that give a product that does not exceed U (k), where U (k) is the product of k largest individual identifiers. , (b) It should be confirmed that there is no misjudgment due to errors in the procedure.

  Here, if a case of erroneous determination is detected in the accuracy check calculation described above, the set of individual identifiers is replaced, or the value of the group identifier in the combination is combined with the set of correct individual identifiers as “exception value list” This is handled by first performing the process of checking the exceptional value list when calculating the individual identifier from the group identifier.

  In the case of adding floating-point numbers with extremely different sizes, in consideration of the fact that significant digits are likely to be lost due to digit loss, in this embodiment when using floating-point number addition, the size of the individual identifier is used. It is desirable to arrange them as much as possible within the possible range.

  In addition, in order to increase the number of cases where it is possible to determine with a numerical value that does not require a relatively large division, it is advantageous to take all individual identifiers as large as possible within a range that satisfies the conditions. For example, it is effective to “select individual identifiers in descending order from numbers that can become individual identifiers”.

  For example, if the maximum integer that can be stored in the prepared area is z, the kth root of z is z ^ (1 / k) = y, and the number of individual identifiers (or individual identifiers in descending order from y) Take out the number of pooled candidates.

  On the other hand, when it is desired to “discretely distinguish more than individual identifiers than resolution k”, it is advantageous to make individual identifiers as small as possible. It is effective to "release only".

  However, if the selection is made in ascending order of the integer candidates before taking the logarithm, it is difficult to satisfy the condition from the viewpoint of “equalizing the size in order to reduce the error”. For example, the number of significant digits when the difference between the number of digits (minimum and maximum) that is the end point of the interval determined from the number of required individual identifiers is converted to an integer (fixed point) by multiplying it by a floating point or a constant multiple Choose to be smaller than the range.

  It is possible to reduce the number of registrations in the exception value list by not using a number including a combination with a large error as an individual identifier. Furthermore, from the viewpoint of speeding up the search process of the individual identifier at the time of reception, it is advantageous that the size (number of elements) of the exception value list is as small as possible (the size of the exception value list is 0 as a result). (That is logically possible if the exception value list is no longer needed).

  FIG. 42 is a flowchart showing an example of processing of the identifier aggregation mechanism 401 (FIG. 4) in the transmission side node in the eighth embodiment based on the above theory. The basic concept of the processing in this flowchart is as shown in FIG. 5 (first embodiment), FIG. 17 (second embodiment), FIG. 30 (fifth embodiment), and FIG. 37 (sixth embodiment). Form) and the like. FIG. 37 is a flowchart of FIG. 30 or FIG. 37 according to the fifth and sixth embodiments, in which the operation of the reduction 404 is replaced from multiplication to logarithmic addition, and individually as in the case of the sixth embodiment. An identifier and a group identifier are vectorized. The functional block and system configuration will be described with reference to FIG. 4 and FIG. 7 in the first embodiment. Of course, the system configuration of FIG. 20, FIG. 21, FIG. 22, etc. may be adopted. 4 is started, the CPU 701-1 of the transmission origin node 701 or the CPU 702-1 of the reception / relay node 702 functioning as a relay node in FIG. 7 executes. The work area such as the input vector 1 or 2 is stored in the memory 701-2 of the transmission origin node 701 or the memory 702-2 of the reception / relay node 702.

  The identifier in this embodiment is an ordered set of integers. However, the transmitting node does not necessarily hold the original individual identifier itself, but a modified individual identifier obtained by conversion to a logarithm or a logarithm and an integer after a constant multiple, and the receiving node receives the received modified group identifier. The original group identifier is restored from and the individual identifier is extracted. Here, an “ordered set” is called a “vector”, and an integer that is an element of the “ordered set” is called a component. The generic name of the original individual identifier and the original group identifier is “identifier”, and the generic name of the modified individual identifier and the modified group identifier is “modified identifier”. The calculation between the identifier vector or the modified identifier is determined by the calculation between the components at the corresponding positions.

  In FIG. 42, first, it is determined whether or not the own node is a communication origin node (step S4201).

  If the determination in step S4201 is NO, the received modified population identifier vector is stored in the input vector 1 that stores the received value (step S4202).

  If the determination in step S4201 is YES, since no value has been received, the value 0 of the unit element of the logarithmic addition operation is stored in all components of the input vector 1 (step S4203).

  Next, it is determined whether or not a condition to be notified is established in the management target managed by the own node (step S4204).

  If the determination in step S4204 is YES, the modified individual identifier vector corresponding to the management target in the own node (or the own node itself) is stored in the input vector 2 that stores the state of the own node (step S4205).

  If the determination in step S4204 is NO, unit element value 0 is stored in all components of input vector 2 (step S4206).

  Thereafter, a logarithmic addition operation used for the reduction 404 is executed between all components of the input vectors 1 and 2 (step S4207).

  Finally, the calculation result in step S4207 is output as a modified group identifier vector that is the content of transmission to the next transfer destination (step S4208). Thereafter, the processing of the identifier aggregation mechanism 401 in the transmission side node illustrated in the flowchart of FIG. 42 ends.

  FIG. 43 is a flowchart showing an example of processing of the identifier analysis mechanism 402 (FIG. 4) in the receiving side node in the eighth embodiment based on the above theory. The basic concept of the processing in this flowchart is the above-described FIG. 6 (first embodiment), FIG. 18 (second embodiment), FIG. 31 (fifth embodiment), and FIG. 38 (sixth embodiment). Form) and the like. FIG. 43 is a flowchart of FIG. 31 or FIG. 38 according to the fifth and sixth embodiments, in which the operation of the reduction 404 is replaced from multiplication to logarithmic addition, and the individual identifier is the same as in the sixth embodiment. And the group identifier is vectorized. The functional block and system configuration will be described with reference to FIG. 4 and FIG. 7 in the first embodiment. Of course, the system configuration of FIG. 20, FIG. 21, FIG. 22, etc. may be adopted. When the processing of the identifier analysis mechanism 402 in FIG. 4 is started, the CPU 702-1 of the reception / relay node 702 in FIG. 7 that functions as a reception side node executes. The work area vector W, X, and the like are stored in the memory 702-2 of the reception / relay node 702.

  First, it is determined whether or not an overflow (“overflow” in the figure) has occurred in the received modified group identifier vector (step S4301). If the determination in step S4301 is YES, the reception process is not substantially performed, and the process of the identifier analysis mechanism 402 in the reception side node illustrated in FIG. 43 ends.

  Next, if the determination in step S4301 is NO, the modified group identifier vector is stored in the work area vector V (step S4302).

  Next, it is determined whether or not each element of the work area vector V is included in the exceptional value (step S4303).

  If the determination in step S4303 is NO, an exponential operation is performed for each element value of the work area vector V (this is expressed as “exp (V)”), and the integer closest to the operation result is the work area. It is stored in the corresponding element of the vector W (step S4304).

  If the determination in step S4303 is YES for any element of work area vector V, a value obtained by correcting the error in the exceptional value for that element is stored in the corresponding element of work area vector W (step S4305). The process for creating the exception value list necessary in this step will be described later with reference to the flowcharts of FIGS.

  Next, it is determined whether or not all the component values of the work area vector W have become the unit element value 1 in the state where the logarithmic addition operation area of the reduction 404 is returned to the multiplicative operation area (see step S4304). (Step S4306).

  If the determination in step S4306 is NO, one individual identifier vector is specified from the group identifier vector, and the result is stored in the work area vector X (step S4307).

  Thereafter, the management target corresponding to the individual identifier vector stored in the work area vector X in step S4307 is processed (specified) (step S4308).

  Next, the inverse operation of the multiplication operation before logarithmic transformation used for the reduction 404, that is, the division operation is applied to each component of the work area vector W and the work area vector X, and is specified from the work area vector W in step S4307. The individual identifier stored in X is removed (step S4309). Thereafter, the processing returns to step S4306, and the processing from step S4306 to step S4309 described above is repeatedly executed.

  If the determination in step S4306 is YES, the processing of the identifier analysis mechanism 402 in the receiving side node exemplified in the flowchart of FIG. 43 ends.

  FIG. 44 and FIG. 45 are flowcharts showing an example of exception value list creation processing necessary for the correction processing in step S4305 of FIG.

  First, the sorted individual identifier component list is stored in the work area L (step S4401).

  Next, the upper limit value of the number of components of the individual identifier that needs an error check is calculated and stored in the work area K (step S4402). Details of this processing will be described later with reference to the flowchart of FIG.

  Next, a list of combinations for extracting K elements from the work area L is created and stored in the work area U (step S4403).

Next, the start position of the work area U is stored in the work area X (step S4404).
Next, until the work area X is determined as the end position of the work area U in step S4405, the next position of the work area U is sequentially stored in the work area X in step S4413 of FIG. To S4412 in FIG. 45 are executed.

  First, when the determination in step S4405 is NO, a set of individual identifiers at the current position indicated by the work area X in the work area U is stored in the work area T (step S4406).

  Next, a set of modified individual identifiers (elements are logarithm) corresponding to the work area T is stored in the work area S (step S4407).

  Next, the group identifier corresponding to the work area T is stored in the work area t (step S4408).

  Next, by converting the value min (Σ (S)) that takes the minimum value among the sums in which the order of the work areas S is changed, the logarithmic effect is canceled by performing the conversion with an exponential function, and the calculation is performed. The result is stored in the work area s (step S4409 in FIG. 45).

  It is determined whether or not the calculation result of step S4409 has overflowed (step S4410).

If the determination in step S4410 is YES, the process proceeds to S4413.
If the determination in step S4410 is NO, it is determined whether the integer closest to the value of work area s is the value of work area t (step S4411).

If the determination in step S4411 is YES, the process proceeds to S4413.
If the determination in step S4411 is NO, the pair of the value of the work area s and the value of the work area T is registered in the exception value list (step S4412).

  Thereafter, the next position in the work area U is stored in the work area X (step S4413), and the process returns to step S4405.

  As a result of the repetition processing from step S4405 to step S4413 as described above, if the determination in step S4405 is YES, the exception value list creation processing ends.

  FIG. 46 is a flowchart illustrating a detailed example of the process of calculating the upper limit value of the number of components of the individual identifier that requires error checking and storing it in the work area K in step S4402 of FIG.

  First, the sorted individual identifier component list is stored in the work area L (step S4601). Here, the work area L is aligned so that the smallest element is at the top.

Next, the upper limit value of the resolution is stored in the work area k (step S4602).
Next, the start position of the work area L is stored in the work area Y (step S4603).

Next, the value 1 is stored in the work area f (step S4604).
Next, the value of the work area k is stored in the work area K as an initial value (step S4605).

  Next, it is determined whether or not the position of the work area Y has reached the end position of the work area L (step S4606).

  If the determination in step S4606 is NO, the element at the current position indicated by the work area Y in the work area L is stored in the work area g (step S4607).

  Next, the result of multiplying the value of the work area f by the value of the work area g is stored in the work area f (step S4608).

  It is determined whether or not the calculation result of step S4608 has overflowed (step S4609).

If the determination in step S4609 is YES, the process ends.
If the determination in step S4609 is NO, the value of work area K is incremented by +1 (step S4610).

  The next position in the work area L is stored in the work area Y (step S4611), and the process returns to step S4606.

  As a result of the repetitive processing from step S4606 to step S4611, if the determination in step S4606 becomes YES, the processing of the flowchart in FIG. 46 ends, and the upper limit value of the number of components of the individual identifier that requires error check in the work area K Is stored, and the process of step S4402 of FIG. 44 ends.

  The eighth embodiment described above is particularly effective when only addition can be used as an inter-node operation mechanism (Reduction or Atomic Operation function). Compared with the case where each node performs computation on the CPU without using the inter-node arithmetic mechanism, as described in the third embodiment, it is more advantageous in terms of performance to use the inter-node arithmetic mechanism. It is.

  Since the logarithm of the individual identifier of each node can be calculated in advance and distributed to each node, the calculation of the exponential function and logarithmic function, and the operation of pulling the exception value list table are performed on the receiving side. The transmission side node does not need an arithmetic unit or a memory for storing the table.

<Ninth Embodiment>
Next, a ninth embodiment will be described.

  In the above-described eighth embodiment, the reduction for obtaining the group identifier is performed by addition, and the division method is used when the individual identifier is extracted (after conversion by an exponential function that is an inverse function of the logarithmic function). Then, an individual identifier is extracted by drawing a table based on the addition result.

In other words, the calculation method of this embodiment corresponds to the case where all group identifiers are registered in the “exception value list” in the eighth embodiment. However, the individual identifier in this embodiment does not have to be obtained from the “individual identifier in the fifth and sixth embodiments”, and for example, satisfies the following conditions (P) and (Q): Any element of the “set with defined addition” may be used.
(P) The sums of combinations of individual identifiers that do not overflow in calculations in a predetermined size area are all different.
(Q) The sum of more than k individual identifiers is all greater than a specific number, and the sum of k or less individual identifiers is all different.

For example, a set having the above property for integer addition can be selected as follows, with the upper limit of the number that can be stored in the identifier storage area as a.
When k = 1: A set of all integers between a / 2 and a can be used as a set of individual identifiers.
If k ≥ 2: Add elements of the set S from the largest in the range below a / k as follows. Any subset of S thus obtained can be used as a set of individual identifiers.

  (1) A set S is a set of one element {[a / k] +1}. The symbol [x] here is a “Gaussian symbol” and means the largest integer that does not exceed x. If a is the m bits region, a = 2 ^ m-1. It is easy to see that even if k integers are selected in descending order from [a / k] +1, the sum does not overflow (ie, the sum is less than or equal to a).

  (2) Let b be the minimum value of set S, and test whether S∪ {c} maintains the above conditions (P) and (Q) with a positive integer c less than b, starting from b-1 in descending order. To go. If an integer c that keeps the condition is found, replace S∪ {c} with S and repeat (2). It is not always necessary to try all positive integers less than or equal to b-1, and the processing may be terminated when a predetermined size or a predetermined number of individual identifier candidates are found. For example, censoring at a size that “overflows with the sum of k + 1” or censoring when a required number of individual identifiers (which is sufficiently larger than the number of systems to be managed) is obtained.

  In the case of k ≧ 2, when a is `` an integer that can be stored in the m bit area '' and the resolution is perfect, it can be used for more management targets than the upper limit of the number of management targets. It is also necessary to confirm that the number of elements in S is greater than m.

  For example, with the upper limit of resolution k = 2, the set of {64, 63, 62, 60, 57, 52, 44, 35} in the 7bits region has 8 elements and satisfies the condition. (A = 127 in steps (1) and (2) above)

  First, referring to FIG. 16B shown in the description of the first embodiment, it is confirmed that “sum of two elements” is all different. It is clear from the fact that the sum of all three elements or more overflows in the 7 bits area, that is 35 + 44 + 52 = 131> 127, that is, the sum of the three elements from the smaller one overflows in the 7 bits area.

  The reason for checking in descending order in the above example is that, in the range where the sum of more than k numbers overflows, it is only necessary to calculate the sum of combinations of k or less. Intended to reduce. However, since the set of individual identifiers is prepared not at the time of system operation but at the time of system design, the calculation time for determining the set of individual identifiers will affect the performance during system operation. Absent.

  In the table or hash function for examining the individual identifier used when generating the group identifier, if at least one of the individual identifiers for generating a certain group identifier is given, the table is redrawn or the hash function is applied. The remaining individual identifiers can be obtained sequentially. For example, if a table or hash function that provides the maximum number of individual identifiers for generating a certain group identifier is prepared in advance, all the individual identifiers that have generated the received group identifier can be obtained.

  FIG. 47 is a flowchart showing an example of processing of the identifier aggregating mechanism 401 (FIG. 4) in the transmission side node in the ninth embodiment based on the above theory. 47, as in the case of the flowchart of FIG. 5 according to the first embodiment, addition is used as the calculation of the reduction 404, and the individual identifier and the collective identifier are vectorized. However, the additive operation in the present embodiment satisfies the conditions (p) and (q) described above. The functional block and system configuration will be described with reference to FIG. 4 and FIG. 7 in the first embodiment. Of course, the system configuration of FIG. 20, FIG. 21, FIG. 22, etc. may be adopted. 4 is started, the CPU 701-1 of the transmission origin node 701 or the CPU 702-1 of the reception / relay node 702 functioning as a relay node in FIG. 7 executes. The work area such as the input vector 1 or 2 is stored in the memory 701-2 of the transmission origin node 701 or the memory 702-2 of the reception / relay node 702.

  The identifier in this example is an ordered set of integers. Here, an “ordered set” is called a “vector”, and an integer that is an element of the “ordered set” is called a component. The calculation between identifier vectors is determined by the calculation between components at corresponding positions.

  In FIG. 47, first, it is determined whether or not the own node is a communication origin node (step S4701).

  If the determination in step S3401 is NO, the received group identifier vector is stored in the input vector 1 that stores the received value (step S4702).

  If the determination in step S4701 is YES, since no value has been received, the value 0 of the unit element of the addition operation is stored in all components of the input vector 1 (step S4703).

  Next, it is determined whether a condition to be notified is established in the management target managed by the own node (step S4704).

  If the determination in step S4704 is YES, the individual identifier vector corresponding to the management target in the own node (or the own node itself) is stored in the input vector 2 that stores the state of the own node (step S4705).

  If the determination in step S4704 is NO, unit element value 0 is stored in all components of input vector 2 (step S4706).

  Thereafter, an addition operation used for the reduction 404 is executed between all components of the input vectors 1 and 2 (step S4707).

  Finally, the calculation result in step S4707 is output as a collective identifier vector that is the content of transmission to the next transfer destination (step S4708). Thereafter, the processing of the identifier aggregation mechanism 401 in the transmission side node illustrated in the flowchart of FIG. 47 ends.

  FIG. 48 is a flowchart showing an example of processing of the identifier analysis mechanism 402 (FIG. 4) in the receiving side node in the ninth embodiment based on the above theory. The basic concept of the processing in this flowchart is that the receiving side node extracts an individual identifier (component) by drawing an individual identifier (component) configuration table using a group identifier as a key. The individual identifier and the group identifier are vectorized as described above. The functional block and system configuration will be described with reference to FIG. 4 and FIG. 7 in the first embodiment. Of course, the system configuration of FIG. 20, FIG. 21, FIG. 22, etc. may be adopted. When the processing of the identifier analysis mechanism 402 in FIG. 4 is started, the CPU 702-1 of the reception / relay node 702 in FIG. 7 that functions as a reception side node executes. The work area vector W, X, and the like are stored in the memory 702-2 of the reception / relay node 702.

  First, the collective identifier vector in the reduction 404 between nodes is received (step S4801).

  Next, it is determined whether or not an overflow (“overflow” in the figure) has occurred in the collective identifier vector (step S4802). If the determination in step S4802 is YES, the reception process is not substantially performed, and the process of the identifier analysis mechanism 402 in the reception side node illustrated in FIG. 48 ends.

  Next, if the determination in step S4802 is NO, the group identifier vector is stored in the work area vector W (step S4803).

  Then, for each component of the work area vector W, an individual identifier is specified by drawing a comparison table between a group identifier and a bitmap of individual identifiers that are generation factors as illustrated in FIG. Step S4804). This comparison table is held in the memory 702-2 of the reception / relay node 702, for example.

  Thereafter, the processing of the identifier analysis mechanism 402 in the receiving side node illustrated in the flowchart of FIG. 48 is finished.

  FIG. 49 and FIG. 50 are flowcharts showing an example of a process for creating a correspondence list of individual identifier components used in the receiving node when the component of the collective identifier is obtained by additive reduction in the ninth embodiment. . This process may be executed by a computer other than the reception / relay node 702 of FIG.

  First, the sorted individual identifier component list is stored in the work area L (step S4901).

  Next, the upper limit value of the number of components of the individual identifier that needs to be checked for errors in each component is calculated and stored in the work area K (step S4902). Details of this processing will be described later with reference to the flowchart of FIG.

  Next, a list of pairs of combinations for extracting K elements from the work area L and the sum of the K elements is stored in the work area U (step S4903).

  Next, the work areas U are aligned so that the top of the sum of the elements is minimized (step S4904).

Next, the start position of the work area U is stored in the work area X.
Moving to the flowchart in FIG. 50, it is determined whether or not the position indicated by the work area X is the end position of the work area U (step S4906).

If the determination in step S4906 is NO, the value of work area X is stored in work area Z.
Next, the next position in the work area U is stored in the work area X (step S4908).

  Next, the sum of the elements at the position indicated by the value of the work area X is calculated and stored in the work area S (X) (step S4909).

  Next, the sum of the elements at the position indicated by the value of the work area Z is calculated and stored in the work area S (Z) (step S4910).

  It is determined whether or not the values of the work area S (X) and the work area S (Z) are equal (step S4911).

  If the determination in step S4911 is YES, two sets of the work area U value U (X) indicated by the work area X value and the work area U value U (Z) indicated by the work area Z value cannot be distinguished from each other. When it is determined that it is possible, a predetermined process is executed (step S4912). For example, registration of a reference value in the comparison table is prohibited.

  If the determination in step S4911 is NO, the process in step S4912 is skipped.

  Thereafter, the process returns to step S4906, and the process for the next position indicated by the value of the work area X is continued.

  If the determination in step S4906 is YES as a result of the position indicated by the work area X reaching the end position of the work area U, the processing of the flowcharts of FIGS. 49 and 50 is terminated, and the creation of the comparison table is terminated.

  FIG. 51 is a flowchart showing a detailed example of the process of calculating the upper limit value of the number of components of the individual identifier that needs to be checked for errors in each component and storing it in the work area K in step S4902 of FIG. This flowchart is almost the same as the process of the flowchart of FIG. 46 described above in the exception value list creation process in the case of using multiplication by logarithmic addition in the eighth embodiment. That is, the process starting from step S46... Is the same process as in FIG. 51 differs from FIG. 46 in step S5101 in FIG. 51 corresponding to step S4608 in FIG. 46, by adding the value of the work area f and the value of the work area g instead of multiplication, thereby creating a new work area. This is the point where the value of f is calculated. This is because the operation of the reduction 404 in the ninth embodiment is addition rather than multiplication. Other algorithms for calculating the upper limit value are the same as those in FIG.

  A specific procedure for creating the above-described comparison table of FIG. 16B will be described below based on the flowcharts of FIGS. 49 to 51 described above.

<Processing flow>
The initial set
S = {64}
And
64 + 63 = 127
So it will not overflow. therefore,
S = {64,63}
It is good.
Here, the minimum value 63 of S is taken.
64 + 63,64 + 62,63 + 62 are all different, so
(P) The sums of combinations of individual identifiers that do not overflow in calculations in a predetermined size area are all different.
(Q) The sum of more than k individual identifiers is all greater than a specific number, and the sum of k or less individual identifiers is all different.
The condition is satisfied. For this reason, 62 can be added. therefore,
S = {64,63,62}
It is good. However,
S = {64,63,62,61} is not possible. because,
64 + 61 = 63 + 62
Because. Therefore, 61 is skipped.
S = {64,63,62,60}
It is possible to confirm as follows.

If both are in the subset formed by the previous three elements, it is confirmed. The minimum sum is the two sums from the bottom,
63 + 62 = 125
It is. If at least one protrudes, one element is 60. Since the sum with the largest element 64 is 124, any one of the previous three is chosen and the sum is smaller than the sum of the previous three, so it does not match. Also, the sum with the previous one is completely different.

Generally, the difference from the previous element is 1 or more,
S = {64,63,62,60,59}
What can not be
63 + 59 = 62 + 60
It is clear from Therefore, 59 is skipped.
S = {64,63,62,60,58}
What can not be
64 + 58 = 62 + 60
It is clear from Therefore, 58 is also skipped.
S = {64,63,62,60,57}
What can be done is confirmed if both are in the subset of the previous four elements. If at least one protrudes, one element is 57. Since the sum with the largest element 64 is 121, any sum selected from the previous three is smaller than the sum of the previous three, so it does not match. Also, the sum with the previous one is completely different.

Thereafter, by performing the same processing, the comparison table of FIG. 16B is completed.
The ninth embodiment described above is particularly effective when only addition can be used as an inter-node operation mechanism (Reduction or Atomic Operation function). Compared to the case where each node performs an operation on the CPU without using the inter-node operation mechanism, as described in the third embodiment, it is more advantageous in terms of performance to use the inter-node operation mechanism. Because.

<Tenth Embodiment>
Next, a tenth embodiment will be described.

  In the fifth to eighth embodiments, the data sent from the transmission side node to the reception side node has a larger number of areas in a smaller area than in the second to fourth embodiments on the condition that the resolution has an upper limit k. Can receive managed information. In the methods of the second to fourth embodiments in which the resolution is complete, the same number of bits as the management target is required.

  However, in the fifth to eighth embodiments, it is necessary to refer to a table of identifiers separately when obtaining individual identifiers from collective identifiers. Therefore, if the range of individual identifiers that can be taken by any method is not limited, identification should be performed. Access to the memory area of the identifier table, including the area of individual identifiers that do not correspond to the management target, increases.

  In this embodiment, the set of identifiers is divided into a plurality of groups, and each node notifies the group to which the identifier of the management target belongs, separately from the identifier of the management target itself by another reduction. The basic idea so far is the same as that of the fourth embodiment, and the individual identifier of each group (for management) is set separately with the group as the upper (virtual) management target. In the present embodiment, the following processing is further executed.

  When a group is identified, assigning an “individual identifier with the bit in the same position in the same area turned on” to a management target belonging to the same group, “at least one of the management targets in the group is monitored by bitwise or computation. You can be notified by reduction. That is, it is possible to notify a logical or status of a plurality of management target states.

  When using bitwise and (bitwise AND operation) or multiplication, De Morgan's law of “not (A and B) ← → (not A) or (not B)” may be used. In other words, 0 is input to the management target for which the condition is satisfied, and if not, 1 is input and bitwise and multiplication results are reversed.

  In the case of using addition, it is only necessary to have another “storage area for group identifiers for groups”. (If the individual identifiers are all positive, it is possible to know whether or not a value has been entered (changed) just by adding, and if the result is a non-zero value or overflows as an initial value of 0, it can be seen that at least one input is not zero. Therefore, it is not necessary to define the “individual identifier for the group” separately from the identifier of each management target.The “individual identifier for the group” is for viewing the “storage area of the group identifier for the group”, and In this case, the “group collective identifier storage area” can be calculated without giving the “group individual identifier”.

  Since the number of management targets is reduced in the calculation of group identifiers of groups, the average reference range can be reduced rather than sequentially trying all identifiers of management targets.

  As a group identifier of a group, the method using the second and third embodiments (same as the fourth embodiment) may be used, and the fifth to ninth embodiments may be applied. Note that the methods of the fifth to eighth embodiments can also be applied to the group identifiers for the second and third embodiments.

  FIG. 52 is a flowchart showing an example of transmission processing of identifiers hierarchically grouped by bitwise or computation in the present embodiment.

  First, the group identifier of the group is obtained from the individual identifier of each group hierarchy by reduction by bitwise or calculation (step S5201).

  Next, a multiplicative reduction collective identifier is obtained for the individual identifier (original management target) in the lowest layer (step S5202).

Then, both group identifiers are transmitted to the next transfer destination (step S5203).
FIG. 53 is a flowchart showing an example of reception processing of identifiers hierarchically grouped by bitwise or calculation in this embodiment.

  First, a list of individual identifier components that use the lowest-order multiplication as an operation is specified from the group identifier of each group hierarchy by depth-first search (step S5301). A specific algorithm example of the reception processing with depth priority search has been described above with reference to the flowchart of FIG. 28 in the fourth embodiment.

  Then, based on the specified list of individual identifier components, the individual identifier (component) is specified from the multiplicative reduction collective identifier (step S5302).

  FIG. 54 is a flowchart illustrating an example of transmission processing of identifiers hierarchically grouped by multiplicative computation in the present embodiment.

  First, a group identifier of a group is obtained from the individual identifier of each group hierarchy (step S5401).

Then, the group identifier of each layer is transmitted to the next transfer destination (step S5402).
FIG. 55 is a flowchart illustrating an example of reception processing of identifiers hierarchically grouped by multiplicative computation in the present embodiment.

First, the value 1 is stored in the work area g indicating the hierarchy currently processed (step S5501).
Next, the group identifier (component) of the hierarchy indicated by the work area g is stored in the work area W (g) (step S5502).

  Next, it is determined whether or not the value of the hierarchy indicated by the work area g is greater than the number of group hierarchies (step S5503).

  If the determination in step S5503 is NO, it is determined whether or not the work area W (g) is not 1 (unit element of multiplicative calculation) (step S5504).

  If the determination in step S5504 is YES (W (g) is not 1), one of the individual identifier components in work area W (g) is stored in work area q (step S5505).

  Next, it is determined whether the value of the hierarchy indicated by the work area g is equal to the number of group hierarchies, that is, whether it is the lowest layer (step S5506).

  If the determination in step S5506 is YES, processing unique to the lowest layer identifier, that is, processing for extracting a management target from the individual identifier extracted from the lowest layer is executed (step S5507).

If the determination in step S5506 is NO, the process in step S5507 is skipped.
Thereafter, the result of dividing the work area W (g) by the work area q is newly stored in the work area W (g) (step S5508).

  Finally, the value of the work area g is incremented by +1 (step S5509). Thereafter, the processing returns to step S5502, and the reception processing for the next layer is executed.

  If the determination in step S5503 is YES as a result of the value of the hierarchy indicated by the work area g being greater than the number of group hierarchies, the reception process ends.

  According to the tenth embodiment described above, it is possible to reduce the processing time associated with memory access by limiting the search range of the individual identifier for an arbitrary resolution k 1.

<Eleventh embodiment>
Next, an eleventh embodiment will be described.

  When retrieving a table in the process of identifying an individual identifier from a group identifier, or when retrieving a table by a process of identifying a management target from an individual identifier, speeding up the retrieval process becomes an issue.

  In particular, the basic idea for multiplicative operations when “the resolution is limited by the upper limit k” is to use the “unique factorization” to determine the group identifier calculated by multiplicative reduction. The individual identifier is taken out. Therefore, the time required for “prime factorization” is an important factor in speeding up the processing performance of the system.

  By using “algebraic integers” instead of ordinary integers as a set where “unique factorization uniqueness” is established, the number of coefficients that can be used as individual identifiers within the same size range is increased. Reduce the amount of memory required to achieve the same resolution k. Here, “prime numbers” (elements corresponding to “algebraic integers”) other than ordinary integers are called “prime elements” in related mathematics literature. Is often called “prime factorization”, but in this application, the term “prime number in a set” is mainly used. This is because the emphasis was on ease of understanding rather than academic rigor.

  In this embodiment, when using the brute force method (a factorization method by sequentially dividing by a number that can be a factor), a method for separately reporting the range of prime factors that appear or a remainder calculation by an integer division is performed. By using this, the set of “numbers that can be factors” is reduced, and the processing time associated with memory access for drawing a table including elements of the set is reduced. In the brute force method, the number of management targets can also be obtained in the process of drawing a table of numbers that can be factors. The management target number itself is used as the “primary key” of the table, or the management target number is included in each entry of the table. Further, by dividing the table of “number that can be a factor” for each hash value by using the remainder from the division as a hash value, the size of the table to be subtracted can be reduced. By limiting the “remaining combination of individual identifiers” based on the “remainder of division of group identifiers” within the range of “the upper limit of the number of prime factors in a group identifier” defined from the set of individual identifiers. The table to be drawn for obtaining the individual identifier can be limited. Further, by subdividing the table of “number that can be a factor” by a combination of remainders by division by a plurality of numbers, the size of the table to be subtracted can be further reduced. The condition based on the remainder of the division becomes an “independent condition” by making the divisors prime to each other, and can therefore be subdivided by creating a table for each “combination of remainders by a plurality of relatively prime divisors”.

  In the present embodiment described below, in the operation for obtaining the number to be managed from the identifier, the remainder from the division is used as a hash value, and the table of “number that can be a factor” is divided for each hash value, so that the table to be subtracted Reduce the size. That is, in the present embodiment, the amount of memory area that needs to be referred to in the search process is limited by using a “hash function”. When multiplicative is used for the reduction operation and the generation factor of the collective identifier is obtained by "prime factorization", the set of all the individual identifiers to be used is "candidate of prime factors known in advance". And N is O (N) or less. Even if N is in the range of tens of thousands to hundreds of thousands, depending on the system, it can be “within an acceptable range”. A hash function that uses the remainder of division, even if O (N) remains unchanged, it can be made “within tolerance” by reducing the “constant coefficient”.

  When subtracting the "prime number table used for individual identifiers" when obtaining the numbers to be managed from individual identifiers, arrange the tables in order of size (binary search instead of linear search). The search time for table size N can be reduced to log_2 (N).

  Furthermore, the search range can be narrowed by a table or calculation formula (hash function) that can be reversed, or a combination thereof. Hereinafter, examples of hash functions that can be used in this embodiment will be described.

  For example, the value of lower 4 bits to lower 8 bits of the individual identifier area can be used as a hash function, and the prime number used for the individual identifier can be stored in a separate table for each lower 4 bits or 8 bits.

  If you select a set of prime numbers to be used for individual identifiers so that the size of the table for each hash value (lower 4 bits to 8 bits) is averaged, the size of the table to be searched is reduced to 1/15. Or it can be as small as 1/255.

  In the fifth and sixth embodiments, when k = 2 and a 32-bit region is used, the individual identifier is a prime number smaller than 2 ^ 16-1 and larger than 2 ^ (32/3) (for example, 1627 or more If the prime number) is an individual identifier, the product of three or more individual identifiers overflows, so the number of group identifiers may be two or less.

  Also, since 1627 ^ 2> 2 ^ 16-1, it is possible to distinguish between the case where two individual identifiers are included and the case where only one individual identifier is included depending on the size of the group identifier.

  If it is determined that only one individual identifier is included, the search range can be reduced by the same method as in the case of k = 1.

  When two individual identifiers are included, the square root r of the group identifier is calculated. Since one of the individual identifiers is larger than r and the other is smaller than r, it is sufficient to search in one of the ranges.

  Furthermore, if the sizes of the individual identifiers are aligned as much as possible, the included individual identifiers are close to the square root of the collective identifier, so the prime number to try to divide first is `` prime number as close to the square root '' ascending order by size, Or the method of trying in descending order becomes effective.

  For an arbitrary combination of resolution k and m bits, use a prime number in the range lower than 2 ^ (m / k) as the individual identifier, and make sure that at least one individual identifier is larger or smaller than the k-th root of the group identifier. The search range can be limited. The effect of arranging the sizes of the individual identifiers is the same as in the case of k = 2.

  Also, only the odd prime numbers are used as individual identifiers, and the table search range for individual identifiers is created by creating separate tables for the prime number with a remainder of 1 and 3 prime numbers divided by 4 with reference to the lower 2 bits. It is possible to limit as follows.

  If the remainder of dividing the group identifier by 4 is 3, the remainder of dividing one prime number by 4 is 3, and the remainder of dividing the other 4 by 1 is 1, so the prime number table is based on "Remainder by dividing by 4". If the two are divided, each table always includes an individual identifier, so that the search range is reduced to about half by searching the range of one table first. If the remainder of dividing the group identifier by 4 is 1, the method of searching first within the range of one table increases the search time when the individual identifier is not included in that table. The search time is averaged when searching the table including the candidate identifiers.

  Note that if the individual identifier is divided by 4 and each node notifies the logical or reduction in parallel, the remainder when the two individual identifiers are divided by 4 is the same. Therefore, the search range is about half. This is an example of the method described in the fourth embodiment).

  Individual identifiers can be separated by the remainder other than 2 For example, the remainder is divided by a remainder obtained by dividing by 3, a remainder obtained by dividing by 5, a remainder obtained by dividing by 7, and the like. For the distribution of prime numbers that are the prime factors of individual identifiers, for example, conditions such as equalizing each remainder, or conversely, only prime numbers that become specific remainders are prime factors of individual identifiers are added in accordance with the search procedure for individual identifiers. You can keep it.

  For example, if the remainder of division by 3 is 1 or 2, and the remainder of the product of two numbers is 1, you can see that the original two remainders are equal, but in the case of 2, at least one of the remainders is 1 and the other If you search for either one, you will always find a prime factor. Therefore, the search range is about half.

  The probability that the hash value obtained by dividing the two numbers by 4 and the hash value obtained by dividing the number by 3 will be the same (if the proportion of individual identifiers having each remainder is equal) is about 1/4. If used in combination with a hash function with the remainder divided by 3, the search time is about half at a rate of about 3/4. If hash values with other numbers are also used together, the search time can be reduced by a larger percentage.

  In general, the cost per instruction (in terms of time) of calculation by an arithmetic unit is several orders of magnitude smaller than the memory reference cost, so processing that requires calculation by an arithmetic unit is added to reduce the memory reference cost, thereby increasing the speed. It often happens. Division is relatively expensive in processing using an arithmetic unit. For example, division by 3, 5, 7 is disclosed in the document [6] cited in the fourth embodiment. There are known relatively fast algorithms. For this reason, it can be expected that the time for the division (or the remainder) processing is sufficiently small compared to the effect of reducing the search range.

  In the case of the remainder in other numbers of divisions, the search range may be narrowed in the same manner from the condition for the remainder in the attempted division. That is, the set of individual identifiers is Q = {q_1, q_2, ..., q_i} and each element of Q- {q_1} = {q_2, ..., q_i} is classified by the remainder obtained by dividing q_1, and Q_1 , Q_2, ..., Q_j, it is possible to identify Q_1, Q_2, ..., Q_j that do not contain a group identifier generation factor from the condition for the remainder of group identifier division in q_1 There is a case.

  Furthermore, the set of individual identifiers can be adjusted in advance so that the effect of reducing the search range by the hash function is increased. If the individual identifier candidates that need to be searched due to a value of a hash function and that need to be searched are excluded from the individual identifier table that is actually used, the individual identifier candidates are ordered in descending order. The average search range decreases due to the decrease in “collision”.

  FIG. 56 is a flowchart showing an example of the individual identifier list search processing in the present embodiment, and shows an example of general processing for searching by limiting the individual identifier table with the hash value.

First, the hash value of the individual identifier is stored in the work area h (step S5601).
Next, a table of individual identifiers corresponding to the hash value indicated by the work area h is stored in the work area L (step S5602).

  Then, the individual identifier is searched in the work area L, and the management target number is obtained (step S5603).

  FIG. 57 is a flowchart showing an example of the search process of the individual identifier list in this embodiment, and an example of the process of limiting the table of individual identifiers by limiting the range of the hash value of the individual identifier with the hash value of the collective identifier Show.

First, the hash value of the collective identifier is stored in the work area H (step S5701).
Next, an individual identifier table candidate list determined by the work area H is stored in the work area G (step S5702).

  Next, the head individual identifier table is extracted from the work area G and stored in the work area X (step S5703).

  Next, the individual identifier included in the collective identifier is searched for in the work area X (step S5704).

It is determined whether an individual identifier has been found (step S5705).
If the determination in step S5705 is NO, the search process ends.

  If the determination in step S5705 is YES, it is determined whether the contents of the work area G are empty (step S5706).

If the determination in step S5706 is NO, the search process ends.
If the determination in step S5706 is YES, the next individual identifier list is extracted from the work area G (step S5707), the process returns to step S5704, and the next search is continued.

  FIG. 58 is a flowchart showing an example of an individual identifier list search process in this embodiment, and shows an example of an individual identifier table candidate list creation process based on a hash value of a group identifier.

  First, an index set list J defining an individual identifier table is initialized with an empty list (step S5801).

Next, the divisor list is stored in the work area Q (step S5802).
Next, a hash value list of group identifiers is stored in the work area H (step S5803).

  Next, it is determined whether the work area Q or the work area H is empty (step S5804).

  If the determination in step S5804 is NO, the divisor / hash value pair is extracted from the work areas Q and H and stored in the work area pair (q, h) (step S5805).

  Next, when the remainder of the product is modulo q, a list of pairs of remainders relating to the number q that can be a factor is stored in the work area X (q, h) (step S5806).

  Finally, a list in which each element of the work area X (q, h) is added to the end of each element of J in all combinations is again J (step S5807).

Thereafter, the process returns to step S5804 and the processing is continued.
Finally, when the determination in step S5804 is YES, the process ends.

  FIG. 59 is a flowchart showing an example of the individual identifier list search process in the eleventh embodiment, and shows an example in which a set of remainders using a plurality of divisors is used as the identifier hash value list.

First, the divisor list is stored in the work area Q (step S5901).
Next, it is determined whether or not the work area Q is empty (step S5902).

  If the determination in step S5902 is NO, the divisor q is extracted from the work area Q, the remainder r regarding the identifier q is obtained, and the r is added to the hash value list (step S5903).

Thereafter, the process returns to step S5902 and the processing is continued.
Finally, when the determination in step S5902 is YES, the process ends.

A specific example of the search process is shown below.
The k is fixed at 2 and the prime number used is an odd number greater than 5, and the hash value is "remainder divided by 4" and "remainder divided by 3." An appropriate set of prime numbers is determined and divided into four equal parts by a combination of “remainder divided by 4” and “remainder divided by 3”. Then, the remainder of the product of two prime numbers = the group identifier is as follows.

(Remainder of product)
If the remainder of dividing the product by 4 is 3, then one prime is divided by 4 and the remainder is 1,
The other prime number is divided by 4 and the remainder is 3.
If the remainder when the product is divided by 4 is 1, the remainder when both primes are divided by 4 is the same.
If the product is divided by 3 and the remainder is 2, then one prime number is divided by 3 and the remainder is 1.
The other prime number is divided by 3 and the remainder is 2
If the remainder of dividing the product by 3 is 1, then the remainder of dividing both primes by 3 is the same.

  If you divide the above product by 3 and divide it into a table sorted by the remaining combination conditions when you divide by 4, the table search time will be 1/4.

  In the process of the flowchart of FIG. 58, if Q = {3,4} (divisor) and H = {5,7,11,13,17} (prime number), the left is the remainder when divided by 3 and the right is 4. The following output is obtained to indicate the remainder of the division.

(output)
5-> (2,1)
7-> (1,3)
11-> (2,3)
13-> (1,1)
17-> (2,1)

In the process of the flowchart of FIG. 59, the following four groups are created from Q = {3,4} (divisor).
1. Divide by 3 to get 1 remainder, divide by 4 to get 1 remainder 2. Divide by 3 to get 2 remainders, 4 divide by 4 to get 1 remainder 3. Divided by 3 to get 1 remainder, 4 to divide by 4 4.3 And 2 and 3 when dividing by 4

  The number 55 (= 5 × 11) obtained by multiplying the prime numbers 5 and 11 is one remainder when divided by 3, and three remainders when divided by 4, and belongs to the group of 3 described above.

  According to the eleventh embodiment described above, as in the case of the tenth embodiment, the search range of the individual identifier can be limited.

  In addition, including the case where it is used together with the tenth embodiment as necessary, communication necessary for the reduction of the “group (management / virtual) individual identifier” in the tenth embodiment is unnecessary, By reducing it, the system resource requirement of the reception / relay node 702 in FIG. 7 can be reduced as compared with the case of the tenth embodiment (independent).

  In this embodiment, the amount of communication data does not increase, and the added calculation cost remains within a smaller range than the memory access cost (here, meaning “processing delay accompanying memory access”). For this reason, the memory access cost is greatly reduced by using a combination of a plurality of hash functions.

<Twelfth Embodiment>
Next, a twelfth embodiment will be described.

As in the case of the eleventh embodiment, consider a case where a table is drawn in the process of specifying an individual identifier from a group identifier, or a case where a table is searched by a process for specifying a management target from an individual identifier. As a special case of the hash method mentioned in the eleventh embodiment, an approximate expression obtained by applying “regression analysis” or “discrete Fourier transform” to the next data set can be used. .
{Set of individual identifiers} and {Set of numbers to be managed}
{A set of group identifiers} and {A set of individual identifiers}

  In this embodiment, “regression analysis” or “discrete Fourier transform” is used to narrow the search range in the search processing for identifiers, thereby limiting the memory access amount and speeding up. Although this embodiment can also be considered as a kind of method using the “hash function”, the characteristics are significantly different from the hash function mentioned in the eleventh embodiment. The difference from the eleventh embodiment based on integer arithmetic is that floating point calculation is used.

  In the tenth embodiment, the operation used for the reduction 404 (FIG. 4) is limited to multiplication. However, the present embodiment is also applicable to the case where the operation used for the reduction 404 is additive. The present embodiment can be applied to the following search range.

   Search range when obtaining the number to be managed from the individual identifier (component). The correspondence between the management target number of the objective variable (dependent variable) and the individual identifier of the explanatory variable (independent variable) is one-to-one correspondence. In principle, there can be a “complete hash function”.

  Search range from group identifier (component) to individual identifier (component). Since the correspondence between the group identifier and the individual identifier is not one-to-one, for example, if the minimum, maximum or other “one of the representatives” is determined according to the order relationship between the individual identifiers, Regression analysis can be applied as a function. The order relationship between the individual identifiers (components thereof) is determined by the following relationship, for example. It is a magnitude relationship as a number. The magnitude relation of each component and the overall magnitude relation by lexicographic order between several components. And the “norm” of the algebraic integer, the magnitude relationship between the coefficients, and the magnitude relationship in lexicographic order (relative to the “base” as a vector space) corresponding to each coefficient. In general, when there is no one-to-one correspondence (when there is no inverse function), a regression analysis using only a linear expression of one variable cannot provide an effective approximate expression. Therefore, nonlinear regression analysis is used. For example, when divided into a plurality of sections for each size range, each section has a one-to-one correspondence, and a linear approximation formula may be effective. Discrete Fourier transform and multiple regression analysis (by adding a variable transformed by a periodic function or a function that is not monotonically increasing) (non-linear regression analysis formula) are also effective when they are not one-to-one correspondences.

  In the description of the present embodiment, the case where the individual identifier has a plurality of components as in the sixth embodiment can be handled by the same calculation method as in the fifth embodiment having only one component. For this purpose, the management identifier number (not the management target number itself) is stored in the multi-dimensional array equal to the number of elements of the corresponding component set in each dimension, and the individual identifier component and multi-dimension Match array indexes. In the fifth embodiment, the processing for associating the individual identifier (one-dimensional) with the management target number is equivalent to the processing for obtaining the correspondence between each component of the individual identifier and the index of the multidimensional array in the sixth embodiment. .

  In the following, for the sake of simplicity, the description will be made as (the number of components is 1) in the fifth embodiment unless otherwise specified. This generality is not compromised by the reference to the same calculation method described above.

First, when associating the numbers used as individual identifiers with the numbers to be managed, sort each table in order of size, and for each of the individual identifiers p1, p2 corresponding to the two numbers n1, n2, either Make sure it holds.
(1) Always p1 <p2 when n1 <n2
(2) When n1 <n2, always p1> p2
Here, “regression analysis” is executed between the management target number and the individual identifier to create a first-order approximation formula. For example, when it is desired to know the number when the individual identifier is obtained, a linear approximation formula is created with the explanatory variable as the individual identifier by regression analysis.

  If the primary approximation is n = A * p + B, and the absolute value of the error when the error in this approximation is maximum is E, the search range for obtaining the corresponding number when the individual identifier p is found Is limited to the inside of the interval [zE-1, z + E + 1], where z is the integer closest to the value obtained from the approximate expression. Considering the sign of the error, the search error is limited to the inside of the interval [zE-1, z + F + 1], where E is the maximum error when it is "under" and F is the maximum error when it is "under" Is done. Dividing the range of p into s intervals and taking the sign into each interval, the maximum error {(-E1, F1), ... (-Ei, Fi), ... (-Es, Fs)} Is obtained, the number search range in the i-th interval is limited to the inside of [z−Ei−1, z + Fi + 1].

The above error can be reduced by the following means (including combinations).
Eliminate numbers that increase the error in the approximate expression. If missing numbers are not allowed, renumber and rerun the regression analysis.

    Individual identifiers are divided into groups and different linear approximation formulas are used for each group (in terms of regression analysis, this corresponds to the use of “local linear model” which is a kind of nonlinear regression analysis). For example, they are grouped according to their size and similar size.

    Nonlinear regression analysis is performed on the individual identifier and number using a function other than the linear expression. For example, regression analysis with a linear expression of a set of numbers obtained by transforming elements (or component elements) of one or both sets with an expression such as a power, logarithmic function, exponential function, trigonometric function, or their sum, It becomes a nonlinear regression analysis between the original data sets. If each variable is converted by one or more functions with a function other than a linear expression, and added as a new variable, a “multiple regression analysis” is performed, and the relational expression between the original variables is restored. An approximate expression with improved can be obtained. If you increase the explanatory variables, you can always get a formula with improved fit (at worst, if the coefficient of the added variable is set to 0, the fit cannot get worse). The set of individual identifiers is “data that can be selected at the time of design”, and it is not statistical data in the original sense. It is necessary to consider “validity of adding variables to the model” as in the case of processing statistical data. Absent. In this embodiment, it is only necessary to improve the fit of the formula.

    Perform nonlinear regression analysis by combining linear regression analysis and discrete Fourier transform. For example, a discrete Fourier transform is performed on the error term of the linear approximation obtained by linear regression analysis to create an equation that approximates the error term with the sum of trigonometric functions, and is added to the original linear approximation.

  Note that the procedure for retrieving an individual identifier from a group identifier when using additive reduction is the same as that for retrieving a managed number from an individual identifier, except that the final correspondence is not generally one-to-one. The procedure is the same. This is because, when using the primary approximation formula, if the values of the approximation formulas are finally different in combinations corresponding to the same individual identifier, it is considered that one of the errors is simply large. In the case of using the discrete Fourier transform, there is no particular problem because the same value may appear corresponding to different variables in the approximate expression.

  FIG. 60 to FIG. 65 are flowcharts showing an example of speeding up processing for associating individual identifiers with management target numbers in this embodiment.

  FIG. 60 is a flowchart illustrating an example of a high-speed process for associating an individual identifier and a management target number according to the twelfth embodiment, and a process for creating a primary approximate expression between the management target number and the individual identifier by regression analysis. It is an example.

  First, the sorted list of management target numbers is stored in the work area X (step S6001).

  Next, the sorted list of individual identifiers is stored in the work area Y (step S6002).

  Next, regression analysis is performed on X and Y, and an approximate expression using a linear expression with the other as inputs is calculated (step S6003).

  Further, an error list for each input of the approximate expression obtained by the regression analysis is calculated by subtracting the actual value from the approximate value in each term (step S6004).

  Then, the elements of the error list are arranged, and another list associated with the numbers as the elements of the original list, that is, a table associating the error list with the alignment list of the numbers to be managed is created (step) S6005).

  FIG. 61 is a flowchart showing an example of speeding up processing for associating an individual identifier with a management target number in the twelfth embodiment, and is an example of improving the accuracy of the primary approximation expression by removing a portion with a large error. .

  First, individual identifiers of terms whose primary approximation error is larger than a specified value are removed from the list (step S6101).

  Next, it is determined whether or not the management target number may be skipped (step S6102).

If the determination in step S6102 is YES, the process ends.
If the determination in step S6102 is NO, the regression analysis is re-executed by filling in the numbers where the individual identifiers have been removed (step S6103). Thereafter, the process ends.

  FIG. 62 is a flowchart showing an example of speeding up processing for associating an individual identifier with a management target number in the twelfth embodiment, and is an example of improving the accuracy of an approximate expression using a local linear model.

  First, a portion where the error is larger than the specified value is selected from the error term list arranged in accordance with the error size (step S6201).

  Next, the data set is divided using the number of the location where the error is larger than the specified value as a boundary (step S6202).

  Then, a regression analysis is performed again on each of the divided data sets, and a primary approximate expression for each set is obtained (step S6203).

  FIG. 63 is a flowchart showing an example of speeding up processing for associating an individual identifier with a management target number in the twelfth embodiment, and is an example of improving the accuracy of an approximate expression by discrete Fourier transform of an error.

  First, discrete Fourier transform is performed on the list of error terms obtained by linear regression analysis, and an approximate expression for the error terms is created (step S6301).

  Next, the original primary approximation formula and the error term approximation formula are added to obtain a nonlinear approximation formula (step S6302).

  FIG. 64 is a flowchart showing an example of a speeding up process for associating an individual identifier with a management target number in the twelfth embodiment, and is an example of a non-linear approximation formula creation process (general) by multiple regression analysis.

  First, the sorted list of management target numbers is stored in the work area X (step S6401).

  Next, the sorted list of individual identifiers is stored in the work area Y (step S6402).

  Next, “list of list” composed of a list obtained by converting X and X with one or more nonlinear functions is stored in the work area XX (step S6403).

  Similarly, a “list of lists” composed of Y and Y converted by one or more nonlinear functions is stored in the work area YY (step S6404).

  Subsequently, a multiple regression analysis is performed on X and YY, and an approximate expression using a variable storing the value of each list of X and YY is obtained (step S6405).

  Similarly, a multiple regression analysis is performed on Y and XX, and an approximate expression using a variable storing the value of each list of XX of Y as an input is obtained (step S6406).

  Then, an error list for each input of the approximate expression obtained by the multiple regression analysis is obtained by subtracting the actual value from the approximate value in each term (step S6407).

  Finally, the elements of the error list are aligned, and another list associated with the number as the element of the original list is created (step S6408).

  FIG. 65 is a flowchart showing an example of a high-speed process for associating an individual identifier and a management target number in the twelfth embodiment, and a search process using an approximate expression f (x) created by regression analysis as a hash function It is an example.

  First, a correspondence table between individual identifiers and management target numbers is stored in the work area T (step S6501).

  Next, the lower limit of the search range based on the error list is stored in the work area a (step S6502).

  Next, the upper limit of the search range based on the error list is stored in the work area b (step S6503).

  Further, the identifier or number to be searched is stored in the work area x (step S6504).

  Further, the integer closest to the average value (a + b) / 2 of the values of the work area a and the work area b is stored in the work area c (step S6505).

  After that, after the initial value 0 (zero) is stored in the work area i in step S6506, it is determined that a pair of x and f (c) is included in T in step S6507 while incrementing by +1 in step S6508. Until then, the following processing is repeatedly executed.

  That is, first, it is determined whether or not the value of the work area c is equal to or less than the average value (a + b) / 2 of the value of the work area a and the value of the work area b (step S6509).

  If NO in step S6509, i is added to the value of work area c in step S6510. If YES in step S6509, i is subtracted from the value of work area c in step S6511.

  As a result of the above repeating operation, when the pair of x and f (c) is included in T and as a result, the determination in step S6507 is YES, the search process ends.

  In the twelfth embodiment described above, for example, as in the above-mentioned set of {1627 or more and less than 2 ^ 16-1}, when the application of the linear approximation expression by the above regression analysis is originally good, The conversion of the primary approximation formula is relatively easily improved by excluding the prime numbers from the set of individual identifiers from the set of individual identifiers as necessary, without converting.

  The number of elements in the set of {prime number greater than or equal to 1627 and less than 2 ^ 16-1} is more than 6000, and the number of management targets that can be handled by using multiple (a) 32 bits areas according to the sixth embodiment Can be a power of a number that can be handled in one region. For this reason, even if the number of prime numbers used in one area is reduced to several hundreds, if two 32-bit areas are used, it is possible to deal with tens of thousands to hundreds of thousands of management targets. Thus, when the sixth embodiment is premised, even if another feature is added to the prime number to be used, compared with the second and third embodiments, “in a region of small or equivalent size, The feature of “Available for more management targets” can be easily maintained.

  Furthermore, the application of the first-order approximation can be reliably improved by dividing the range into a plurality of ranges depending on the size.

  In the case of conversion by function, when the first-order approximation is not applicable (when the nonlinearity of the statistical relationship between the number and each set of individual identifiers is large), the number by which the set of individual identifiers is divided by size It is possible to reduce the overhead of condition determination processing when obtaining the number.

  In this embodiment, since the data is an integer, if the approximate expression satisfies the condition that “the error is smaller than 0.5” for all input data, the “complete hash function” is obtained by taking the integer part of the approximate expression. Can do.

  Even if it is not a “perfect hash function”, the search range can be limited to a range of “a fixed width around the approximate value”. That is, the memory reference amount can be kept within a fixed value range.

<13th Embodiment>
Next, a thirteenth embodiment will be described.

  As in the eleventh embodiment, this embodiment is an embodiment that includes a device for speeding up the calculation for obtaining an individual identifier from a group identifier (component thereof) in the fifth or sixth embodiment. As described in the eleventh embodiment, the basic idea for the case where the resolution is limited by the upper limit k and the operation is multiplicative is “multiplying by using uniqueness of prime factorization”. The individual identifier is taken out from the group identifier calculated in the reduction. Therefore, the time required for “prime factorization” is an important factor in speeding up the processing performance of the system.

  For example, by associating an individual identifier component with an index of a multi-dimensional array that stores a management target number, when the individual identifier has a plurality of components as in the sixth embodiment, there is only one component. It can be handled in the same manner as in the fifth embodiment. In the following description, the number of components is assumed to be 1 unless otherwise specified.

  In the eleventh embodiment, when obtaining an individual identifier from a group identifier, it is assumed that elements of a set (or its components) of individual identifiers are sequentially selected and division to the group identifier (or its components) is sequentially executed. As a result, a high-speed method within the framework was used. Therefore, especially when the individual identifier (component) is a prime number, a “method of sequentially dividing by a prime number that can be a factor” (brute force method) is assumed.

In the present embodiment, for example, one or a plurality of combinations of prime factorization algorithms other than the following brute force method are used (a combination with the brute force method may be included in the combination). A feature common to these algorithms (ie, the difference from the brute force method) is that “a set of prime numbers that can be factors” is not used as an input.
ρ method (method using `` pseudo random number sequence '')
p-1 method (effective when p-1 has a relatively small prime factor with respect to prime p)
p + 1 method (effective when p + 1 has a relatively small prime factor with respect to the prime p)
Fermat's method (effective when the prime factor is close to the square root of the original number)
Continued Fraction Method
Multiple Polynomial Quadratic Sieve Method (MPQS)
Elliptic curve method (ECM)

These algorithms themselves are widely known as propositions in the field of mathematics called “number theory” or basic algorithms in computer science, as shown in, for example, the following document [7].
[7] Donald E. Knuth, "The Art of Computer Programming, Volume 2"

  However, as “prime factorization” as a problem of “number theory”, that is, “an operation for obtaining at least one prime factor given as an input an arbitrary integer that is not necessarily known as a prime number” Some algorithms are rarely used. The algorithm is "slow except in the case of a specific minority" or "no prime factor can be obtained except in the case of a specific minority" algorithm, in the general situation that "the number subject to prime factorization is arbitrarily chosen" It is because it is not suitable.

  However, in this embodiment, the purpose is achieved by selecting a set of individual identifiers (components thereof) so that “at least one prime factor can be obtained at a high speed with an algorithm to be used”. It is also possible to effectively use methods (p-1 method, p + 1 method, Fermat's method, etc.) that are considered to be less general as an algorithm for factoring as a problem. For example, the Fermat's method is known to be fast only if the prime factor is close to the square root of the original number, so the individual identifiers (components) should be as large as possible when the resolution is k = 2. You can use it effectively.

  Note that in the prime factorization algorithm other than the brute force method, after the prime factor is obtained, the management target number is acquired separately.

  FIG. 66 is a flowchart showing an example of processing for obtaining at least one prime factor of a given integer by an algorithm other than the brute force method.

First, an empty list is stored in the work area L (step S6601).
Next, the group identifier is stored in the work area X (step S6602).

  Next, one of the prime factors of the value of the work area X is stored in the work area p (step S6603).

  After the initial value 1 is stored in the work area i in step S6604 (step S6604), the value of the work area p is incremented by +1 in step S6607, while the value of the work area p is changed to the work area X in step S6606. A series of processing from step S6605 to step S6607 is repeatedly executed until it is determined that the value of can not be divided.

  In this iterative process, first, a result (X / p) obtained by dividing the value of the work area X by the value of the work area p is newly stored in the work area X (step S6605).

  Next, it is determined whether or not the value of the work area p has divided the value of the work area X (step S6606).

  If the determination in step S6606 is YES, the value of work area i is incremented by +1 and step S6605 is executed again.

  As a result of the above iterative process, if the determination in step S6606 is NO, the prime factor and exponent pair (p, i) of the group identifier is added as an element to the work area L (step S6608).

  Thereafter, it is determined whether or not the value of the work area X is equal to the unit element 1 of the multiplicative calculation (step S6609).

  If the determination in step S6609 is NO, the process returns to step S6603, and the process is repeated for one of the next prime factors of the work area X.

  If the determination in step S6609 is YES, the process of the flowchart in FIG. 66 ends.

  As described above, in the thirteenth embodiment, when a group identifier is obtained from an individual identifier by using a factorization algorithm that does not use a “set of prime numbers that can be factors” as an input, “can be a factor. Compared with the method of referring to the “number table”, the memory reference amount can be reduced. In particular, when one or both of the primes used for the resolution k or the individual identifier component are large, the “group identifier to be factored” is large, which is effective in both speeding up and reducing the processing load.

<Fourteenth embodiment>
Finally, a fourteenth embodiment will be described.

  As in the eleventh and thirteenth embodiments, the present embodiment is an embodiment that includes a device for speeding up the calculation for obtaining an individual identifier from a group identifier in the fifth or sixth embodiment.

  For example, by associating an individual identifier component with an index of a multi-dimensional array that stores a management target number, when the individual identifier has a plurality of components as in the sixth embodiment, there is only one component. It can be handled in the same manner as in the fifth embodiment. In the following description, the number of components is assumed to be 1 unless otherwise specified.

  The present embodiment is premised on a system configuration in which a “quantum computer (a computer including an arithmetic device that performs computation using a qubit)” is a receiving side node.

In order to identify individual identifiers (components) from the group identifiers (components) in the fifth and sixth embodiments by using prime factorization by the Shore algorithm (Shor's algorithm), qubits are used. An arithmetic unit that performs the calculated calculation is used. Reference [8] below discloses a “Shore algorithm” in which prime factorization is performed on a quantum computer in “polynomial time (= time as fast as impossible with a conventional computer)”.
[8] Peter W. Shor, "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer", SIAM Journal on Computing Volume 26 Issue 5, Oct. 1997, Pages 1484-1509
A page containing "5 Prime factorization" in the attachment.

  FIG. 67 is an explanatory diagram of differences between the thirteenth and fourteenth embodiments. In the thirteenth embodiment, a prime factorization algorithm other than the brute force method as shown in FIG. 67 (a) is executed using a normal computer having a general CPU and memory for operating a normal bit. The computer that implements the identifier aggregation mechanism 401 or the identifier analysis mechanism 402 in FIG. On the other hand, in the fourteenth embodiment, in addition to a general CPU and memory for manipulating ordinary bits, a quantum computer which is an arithmetic device for manipulating quantum bits (Qubits) is mounted. The identifier aggregation mechanism 401 or the identifier analysis mechanism 402 is realized.

  Here, the “quantum computer” may be an independent computer, or, as shown in FIG. 67 (b), as “an auxiliary processor having only a function of performing prime factorization by the“ Shore algorithm ””. The arithmetic unit may be used.

  Since the “Shore algorithm” does not draw a table of “numbers that can be factors” in the process of prime factorization, a procedure for obtaining a management target number from the obtained prime factors is performed separately.

  According to the fourteenth embodiment described above, prime factorization can be performed in “polynomial time” (with respect to the size of the number to be primed) by dispersing the Shore algorithm in the quantum computer. In other words, the processing time of prime factorization generally remains large enough to be expressed by a polynomial whose variable is the number of prime factorization targets.

  All the prime factorizations in a method that does not use a known quantum computer take "quasi-exponential time" (the calculation time increases at the same rate as the exponential function with the magnitude of the input data as an argument).

  However, even if the number of factors to be factored is not large enough to be factored in real processing time by other known methods, if the Shore algorithm is used in the quantum computer, the prime factor can be calculated in real processing time. It is possible to perform decomposition.

  Therefore, the present embodiment realizes the case where “the process for obtaining the individual identifier from the group identifier” is “when the component of the group identifier to be factored” is so large that it cannot be handled within the realistic processing time in other embodiments ”. Can be handled within a typical processing time. That is, the number of management targets that can be handled in the fifth and sixth embodiments can be increased by orders of magnitude, and the resolution k can be increased. For example, since it is considered that the application of the identifier aggregation mechanism 401 and the identifier analysis mechanism 402 in FIG. 4 to distributed parallel computation of a large-scale sparse matrix often requires a large resolution k compared to application to state monitoring. This embodiment is particularly effective.

  Currently, as a practical application of prime factorization, p and q can be easily obtained on a conventional computer even if the product pq is disclosed for a large pair of primes p and q in a key exchange in a public key cryptosystem. Since it cannot be calculated, it can be regarded as a “secret key”. This application loses value when prime factorization using Shore's algorithm in quantum computers becomes widespread. On the other hand, in the present embodiment, high-speed execution of prime factorization by the quantum computer leads to expansion of the applicable range.

<Other embodiments>
As described above, the first to fourteenth embodiments are not necessarily mutually exclusive, and can be combined as necessary.

  As described above, the identifier aggregation mechanism 401 and the identifier analysis mechanism 402 in FIG. 4 are the same as the CPU 701-1 or 702-1 of the node 701 or 702 constituting the information aggregation system in FIG. 7, 20, 21, or 22. It can be realized by software processing. In this case, each node 701 or 702 in FIG. 7 or the relay device 703 is provided with a recording medium reading device to read out a control program contained in a recording medium such as a magnetic disk, an optical disk, a magneto-optical disk, and a USB memory. . The control program read by the recording medium reading device is recorded in the memory 701-2 or 702-2 of the predetermined node 701 or 702 directly or via the communication line 704 from the relay device 703. The CPU 701-1 or 702-1 executes the control program recorded in the memory 701-2 or 702-2, whereby the identifier aggregation mechanism 401 and the identifier analysis in FIG. 4 according to the first to fourteenth embodiments are executed. The function of the mechanism 402 is realized.

Regarding the above embodiment, the following additional notes are disclosed.
(Appendix 1)
An identifier aggregating mechanism that is provided in a transmission side node and generates a collective identifier by transmitting an individual identifier unique to a notification source of information and a notification by the individual identifier from the information notification source; and
An identifier analyzing mechanism that is provided in a receiving-side node and that performs processing for receiving the collective identifier and restoring the individual identifier, and processing for specifying a notification source of the information from the individual identifier;
An information aggregating system comprising:
(Appendix 2)
The identifier aggregation mechanism generates an individual identifier unique to the notification source when a condition for notifying the information is satisfied at the information notification source managed by the transmission side node, and the transmission side node When it is not the origin node on the network, it receives the group identifier transmitted by the other transmitting side node, and executes the reduction operation on the generated individual identifier and the received group identifier, and the individual identifier and the Generate a new group identifier that is aggregated with a group identifier and send it to a node on the network,
The identifier analysis mechanism receives a group identifier transmitted by the transmitting node, restores one or more individual identifiers that are generation factors of the group identifier from the received group identifier, and restores the individual identifiers Restoring the notification of the notification source from the identifier;
The information aggregating system according to Supplementary Note 1, wherein
(Appendix 3)
The identifier aggregation mechanism is configured to input a first predetermined value instead of the collective identifier in the reduction operation when the transmitting node is a starting node on the network, and the transmitting node manages When a condition for notifying the information is not satisfied at the information notification source, a second default value is input instead of the individual identifier in the reduction calculation.
The information aggregating system according to supplementary note 2, characterized by:
(Appendix 4)
The first default value and the second default value are unit elements in the reduction operation.
The information aggregating system according to appendix 2 or 3, characterized by the above.
(Appendix 5)
For the identifier aggregation mechanism, an inter-node calculation mechanism provided on a network or a communication device of a node connected to the network,
A synchronization mechanism for performing barrier synchronization for transmission and reception of the collective identifier;
The information aggregation system according to any one of appendices 1 to 4, characterized in that:
(Appendix 6)
Perform a logical OR on the management target in the group in advance on the sending side.
The information aggregating system according to any one of appendices 1 to 5, characterized in that:
(Appendix 7)
Making the sending node correspond to an ordered set of a plurality of integers;
The information aggregating system according to any one of appendices 1 to 6, characterized in that:
(Appendix 8)
The identifier aggregation mechanism uses the uniqueness and multiplication of algebraic integer prime factorization to assign the individual identifiers.
The information aggregating system according to any one of appendices 1 to 7, characterized in that:
(Appendix 9)
The identifier aggregation mechanism uses the uniqueness and addition of algebraic integer prime factorization to assign the individual identifiers.
The information aggregating system according to any one of appendices 1 to 7, characterized in that:
(Appendix 10)
The identifier analysis mechanism restores the individual identifier from the received group identifier using the algebraic integer addition.
The information aggregating system according to supplementary note 9, wherein
(Appendix 11)
Divide the set of identifiers into groups,
The information aggregating system according to any one of appendices 1 to 10, characterized in that:
(Appendix 12)
Use regression analysis or discrete Fourier transform to narrow the search range in the search process for the identifier,
The information aggregation system according to appendix 11, wherein
(Appendix 13)
The identifier analysis mechanism restores the individual identifier from the group identifier using a prime factorization algorithm that does not use a set of prime numbers that can be factors as inputs.
The information aggregating system according to any one of appendices 1 to 7, characterized in that:
(Appendix 14)
The receiving node is a quantum computer;
The information aggregating system according to any one of appendices 1 to 7, characterized in that:
(Appendix 15)
To the computer of the sending node that is connected to the network and notifies information,
A process of generating an individual identifier unique to the notification source when a condition for notifying the information is satisfied at the information notification source managed by the transmitting node;
A process of receiving a collective identifier transmitted by another transmitting node when the transmitting node is not a starting node on the network;
By generating a reduction operation on the generated individual identifier and the received group identifier, a new group identifier in which the individual identifier and the group identifier are aggregated is generated and transmitted to the node on the network. Processing to
A program for running
(Appendix 16)
To the receiving node computer that is connected to the network and collects information,
A process of receiving the collective identifier transmitted by the transmitting node;
Processing for restoring one or more individual identifiers that are generation factors of the group identifier from the received group identifier;
A process of restoring the notification of the notification source from each restored individual identifier;
A program for running
(Appendix 17)
In the transmission side node, an identifier aggregation process is performed in which a unique identifier unique to the information notification source and a notification by the individual identifier from the information notification source are aggregated to generate and transmit a collective identifier.
In the receiving node, execute a process of receiving the collective identifier and restoring the individual identifier, and an identifier analysis process of executing a process of specifying the notification source of the information from the individual identifier.
An information aggregation method characterized by that.
(Appendix 18)
In the identifier aggregation process, an individual identifier unique to the notification source is generated when a condition for notifying the information is established at the information notification source managed by the transmission side node, and the transmission side node When it is not the origin node on the network, it receives the group identifier transmitted by the other transmitting side node, and executes the reduction operation on the generated individual identifier and the received group identifier, and the individual identifier and the Generate a new group identifier that is aggregated with a group identifier and send it to a node on the network,
In the identifier analysis processing, the group identifier transmitted by the transmitting side node is received, one or more individual identifiers that are generation factors of the group identifier are restored from the received group identifier, and each restored individual identifier is restored. Restoring the notification of the notification source from the identifier;
The information aggregating method according to supplementary note 17, characterized by:

101 Management target 102, 201 Sender node 103, 202 Receiver node 104 Gather
105 Reduction 203 NIC (Network Interface Controller)
204, 701-1, 702-1, 1401 CPU (Central Processing Unit)
205 Context 206 Hierarchical Transmission Side Node 401 Identifier Aggregation Mechanism 402 Identifier Analysis Mechanism 403 Identifier Coding System 404 Reduction 701 Transmission Origin Node 702 Reception / Relay Node 703 Relay Device 704 Communication Lines 701-2, 702-2, 1402 Memory 701-3, 702-3 NIC
1403 Input device 1404 Display device 1405 External storage device 1406 Recording medium writing device 1407 Communication interface 1408 Bus 1409 Recording medium 2001 Independent enclosure type inter-node arithmetic device 2101 Node-internal node arithmetic device 2201 Network interface having inter-node arithmetic function

Claims (14)

An identifier aggregation mechanism provided in the transmitting node on the network,
When a predetermined event occurs in a notification source of information managed by the transmission side node , an individual identifier unique to the notification source is generated,
Receiving the collective identifier transmitted by the other transmitting node when the transmitting node is not the origin node on the network;
By generating a reduction operation on the generated individual identifier and the received group identifier, a new group identifier in which the individual identifier and the group identifier are aggregated is generated and transmitted to the node on the network. And
When the transmitting node is a starting node on the network, a first default value is input instead of the collective identifier in the reduction operation,
When the event has not occurred at the notification source, a second default value is input instead of the individual identifier in the reduction calculation.
The identifier aggregation mechanism;
An identifier analysis mechanism provided in the receiving node on the network, the sending node receives a population identifier transmitted, at least one of the individual from the population identifier received a product factor of the population identifiers The identifier analyzing mechanism for restoring an identifier and restoring the notification of the notification source from each restored individual identifier;
Information aggregating system comprising: a. The first default value and the second default value are unit elements in the reduction operation.
The information aggregating system according to claim 1 . For the identifier aggregation mechanism, an inter-node calculation mechanism provided on a network or a communication device of a node connected to the network,
A synchronization mechanism for performing barrier synchronization for transmission and reception of the collective identifier;
The information aggregation system according to claim 1 or 2 , wherein Perform a logical OR on the management target in the group in advance on the sending side.
The information aggregation system according to any one of claims 1 to 3 , wherein Making the sending node correspond to an ordered set of a plurality of integers;
The information aggregation system according to any one of claims 1 to 4 , wherein The identifier aggregation mechanism uses the uniqueness and multiplication of algebraic integer prime factorization to assign the individual identifiers.
The information aggregating system according to any one of claims 1 to 5 . The identifier aggregation mechanism uses the uniqueness and addition of algebraic integer prime factorization to assign the individual identifiers.
The information aggregating system according to any one of claims 1 to 5 . The identifier analysis mechanism restores the individual identifier from the received group identifier using the algebraic integer addition.
The information aggregating system according to claim 7 . Divide the set of identifiers into groups,
The information aggregating system according to any one of claims 1 to 8 . Use regression analysis or discrete Fourier transform to narrow the search range in the search process for the identifier,
The information aggregation system according to claim 9 . The identifier analysis mechanism restores the individual identifier from the group identifier using a prime factorization algorithm that does not use a set of prime numbers that can be factors as inputs.
Aggregation system as claimed in claims 1 to 5, characterized in that. The receiving node is a quantum computer;
Aggregation system as claimed in claims 1 to 5, characterized in that. To a computer used as a sending node on the network,
Events have been established in advance, when the transmitting node is generated in notification source information managed, and generating a unique individual identifier to the notification source,
A process of receiving a collective identifier transmitted by another transmitting node when the transmitting node is not a starting node on the network;
By generating a reduction operation on the generated individual identifier and the received group identifier, a new group identifier in which the individual identifier and the group identifier are aggregated is generated and transmitted to the node on the network. Processing to
When the transmitting node is a starting node on the network, a process of inputting a first default value instead of the collective identifier in the reduction operation;
When the event has not occurred at the notification source, a process of inputting a second default value instead of the individual identifier in the reduction operation;
A program for running An identifier aggregation process executed by a transmitting node on the network ,
When a predetermined event occurs at the information notification source managed by the transmission side node, a process of generating an individual identifier unique to the information notification source;
A process of receiving a collective identifier transmitted by another transmitting node when the transmitting node is not a starting node on the network;
By generating a reduction operation on the generated individual identifier and the received group identifier, a new group identifier in which the individual identifier and the group identifier are aggregated is generated and transmitted to the node on the network. Processing to
When the transmitting node is a starting node on the network, a process of inputting a first default value instead of the collective identifier in the reduction operation;
When the event has not occurred at the notification source, a process of inputting a second default value instead of the individual identifier in the reduction operation;
The sender node executes the identifier aggregation process including :
One or more of the identifier analysis processes executed by the receiving node on the network, receiving the group identifier transmitted by the transmitting node, and generating the group identifier from the received group identifier restore the individual identifier, the receiving node the identifier analysis process is executed to restore the notification of the notification source from the individual identifier of each restored,
An information aggregation method characterized by that.

Images