US-12619482-B2 - Spatial computing

Abstract

There is provided a computer-implemented method of communication between a plurality of processes, each process being responsible for a region of a space, and each process maintaining a routing tree, each node of the routing tree representing a respective one of the plurality of processes and containing an indication of the represented process and an indication of an associated region for which the represented process is responsible. The method comprises: receiving, by a first process, a message addressed to a target region of the space; determining, by the first process and using the routing tree of the first process, a set of subregions of the target region and associated processes; and for each of the determined subregions in the set, sending the message from the first process to the process associated with the determined subregion in the set.

Inventors

• Rashid Mohamed Mansoor
• James Kay
• Christopher Sinclair
• Francis Russell
• Ava Gordon

Assignees

• HADEAN SUPERCOMPUTING LTD

Dates

Publication Date

20260505

Application Date

20210701

Priority Date

20200701

Claims (18)

1. 1 . A computer-implemented method of communication between a plurality of processes, each process being responsible for a region of a space, and each process maintaining a routing tree, each node of the routing tree representing a respective one of the plurality of processes and containing an indication of the represented process and an indication of an associated region for which the represented process is responsible, the method comprising: a) receiving, by a first process, a message addressed to a target region of the space; b) determining, by the first process and using the routing tree of the first process, a set of subregions of the target region and processes associated with the subregions; and c) for each of the determined subregions in the set, sending the message from the first process to the process associated with the determined subregion in the set.
2. 2 . The method of claim 1 , wherein the determining comprises traversing the routing tree of the first process until the subregions in the set cumulatively cover the target region, the traversing comprising, for each of a plurality of traversed nodes in the routing tree: determining a subregion based on at least the region associated with the traversed node in the routing tree, and adding, to the set, the subregion and the process associated with the traversed node in the routing tree.
3. 3 . The method of claim 1 , wherein the determining comprises traversing the routing tree of the first process until the subregions in the set cumulatively cover the target region, the traversing comprising, for each of a plurality of traversed nodes in the routing tree: if the traversed node has one or more children in the routing tree, determining whether, after subtracting the regions associated with each of the one or more children in the routing tree, the target region and the region associated with the traversed node in the routing tree overlap in an overlap region, otherwise, determining whether the target region and the region associated with the traversed node in the routing tree overlap in an overlap region, and responsive to determining that the target region and the region associated with the traversed node in the routing tree overlap, adding, to the set, the overlap region and the process associated with the traversed node in the routing tree.
4. 4 . The method of claim 1 , wherein the determining comprises traversing the routing tree of the first process, the traversing comprising, for each of a plurality of traversed nodes in the routing tree: determining whether the target region and the region associated with the traversed node in the routing tree overlap; and responsive to determining that the target region and the region associated with the traversed node in the routing tree do not overlap, refraining from traversing any child nodes of the traversed node in the routing tree.
5. 5 . The method of claim 1 , further comprising, for each of the determined subregions in the set, determining whether a failure has been detected in transporting the message to the process associated with the determined subregion.
6. 6 . The method of claim 5 , further comprising, for each of the determined subregions in the set, responsive to determining that a failure has been detected in transporting the message to the process associated with the determined subregion, removing the node associated with the determined subregion from the routing tree.
7. 7 . The method of claim 5 , further comprising, d) for each of the determined subregions in the set, responsive to determining that no failure has been detected in transporting the message to the process associated with the determined subregion, subtracting the determined subregion from the target region; and optionally, repeating steps b), c) and d) until the target region is empty.
8. 8 . The method of claim 1 , wherein the message addressed to the target region is received from another process.
9. 9 . The method of claim 8 , wherein the target region and the region associated with the first process do not overlap.
10. 10 . The method of claim 1 , wherein sending the message to the process associated with the determined subregion comprises: altering the message according to the determined subregion; and sending the altered message to the process associated with the determined subregion.
11. 11 . The method of claim 1 , wherein the first process is represented by a first node in the routing tree of the first process, the method further comprising: determining, by the first process, that the first process is overloaded; and responsive to determining that the first process is overloaded: partitioning at least a portion of the region for which the first process is responsible into a plurality of disjoint subregions; creating, by the first process, a plurality of child processes of the first process each responsible for a respective one of the plurality of disjoint subregions; adding, to the routing tree of the first process, a plurality of child nodes of the first node, each of the child nodes containing an indication of one of the child processes and an indication of a corresponding one of the plurality of disjoint subregions for which the one of the child processes is responsible.
12. 12 . The method of claim 1 , further comprising: receiving, by the first process, an indication that at least one child process of the first process is underloaded; and responsive to the receiving of the indication that the at least one child process of the first process is underloaded: sending a termination signal to the at least one child process, and removing, from the routing tree of the first process, the at least one child node representing the at least one child process.
13. 13 . A non-transitory computer-readable medium comprising instructions which, when executed by one or more computers, cause the one or more computers to perform a method of communication between a plurality of processes, each process being responsible for a region of a space, and each process maintaining a routing tree, each node of the routing tree representing a respective one of the plurality of processes and containing an indication of the represented process and an indication of an associated region for which the represented process is responsible, the method comprising: a) receiving, by a first process, a message addressed to a target region of the space; b) determining, by the first process and using the routing tree of the first process, a set of subregions of the target region and processes associated with the subregions; and c) for each of the determined subregions in the set, sending the message from the first process to the process associated with the determined subregion in the set.
14. 14 . A computer system comprising at least one processor configured to perform a method of: communication between a plurality of processes, each process being responsible for a region of a space, and each process maintaining a routing tree, each node of the routing tree representing a respective one of the plurality of processes and containing an indication of the represented process and an indication of an associated region for which the represented process is responsible, the method comprising: a) receiving, by a first process, a message addressed to a target region of the space; b) determining, by the first process and using the routing tree of the first process, a set of subregions of the target region and processes associated with the subregions; and c) for each of the determined subregions in the set, sending the message from the first process to the process associated with the determined subregion in the set.
15. 15 . The method of claim 11 , further comprising communicating, by the first process to at least one other process, an indication that the plurality of child processes have been created by the first process and an indication of the plurality of disjoint subregions for which the plurality of child processes are responsible.
16. 16 . The method of claim 1 , wherein the space is a two-dimensional space partitioned into quadrants, a three-dimensional space partitioned into octants, or a space of three or more dimensions lying on a two-dimensional plane partitioned into quadrants.
17. 17 . The method of claim 1 , wherein the target region and the indications of the associated regions in the routing tree of the first process are encoded using fixed-width coordinates on a space-filling curve.
18. 18 . The method of claim 1 , further comprising: receiving, by the first process from a second process, an indication that a plurality of child processes of the second process have been created by the second process and an indication of a plurality of disjoint subregions for which the plurality of child processes are responsible; and based on the receiving, updating the routing tree of the first process.

Description

This application is the U.S. National Stage of International Application No. PCT/EP2021/068247, filed Jul. 1, 2021, which designates the U.S., published in English, and claims priority under 35 U.S.C. § 119 or 365 (c) to European Application No. 20183569.1, filed Jul. 1, 2020. The entire teachings of the above applications are incorporated herein by reference. FIELD The present disclosure relates to a method of communication for use in spatial computing. In particular, the disclosure relates to a method of communication between processes which are each responsible for a region of space. BACKGROUND Spatial computation on a metric space can easily grow in complexity to the point where it is not possible for the computation to be performed by a single processor without exceeding a reasonable time bound or the amount of memory addressable by a single processor, requiring either a distributed cluster of processors or dedicated custom hardware. In order to use a cluster of processors, a distributed data structure that supports spatial computation is called for. SUMMARY Aspects of the present disclosure are defined in the accompanying independent claims. OVERVIEW OF DISCLOSURE There is provided a computer-implemented method of communication between a plurality of processes, each process being responsible for a region of a space, and each process maintaining a routing tree, each node of the routing tree representing a respective one of the plurality of processes and containing an indication of the represented process and an indication of an associated region for which the represented process is responsible, the method comprising: a) receiving, by a first process, a message addressed to a target region of the space;b) determining, by the first process and using the routing tree of the first process, a set of subregions of the target region and processes associated with the subregions; andc) for each of the determined subregions in the set, sending the message from the first process to the process associated with the determined subregion in the set. Optionally, wherein the subregions in the set are disjoint. In this way, the message is sent to each part of the target region at most once. Optionally, wherein the subregions in the set cumulatively cover the target region. In this way, the message is sent to each part of the target region at least once. Optionally, wherein the determining comprises traversing the routing tree of the first process, the traversing comprising, for each of a plurality of traversed nodes in the routing tree: determining a subregion based on (at least) the region associated with the traversed node in the routing tree, andadding, to the set, the subregion and the process associated with the Optionally, wherein the traversing is performed until the subregions in the set cumulatively cover the target region. Optionally, wherein the subregion is based on (at least) an overlap between the target region and the region associated with the traversed node in the routing tree. Optionally, wherein the adding is performed responsive to determining that the target region and the region associated with the traversed node in the routing tree overlap. Optionally, wherein the determining comprises traversing the routing tree of the first process, the traversing comprising, for each of a plurality of traversed nodes in the routing tree: if the traversed node has one or more children in the routing tree, determining whether, after subtracting the regions associated with each of the one or more children in the routing tree, the target region and the region associated with the traversed node in the routing tree overlap in an overlap region,otherwise, determining whether the target region and the region associated with the traversed node in the routing tree overlap in an overlap region, andresponsive to determining that the target region and the region associated with the traversed node in the routing tree overlap, adding, to the set, the overlap region and the process associated with the traversed node in the routing tree. Optionally, wherein the traversing is performed in breadth-first order. Optionally, wherein the traversing is performed in depth-first order. Optionally, wherein the traversing comprises, for each of a plurality of traversed nodes in the routing tree: determining whether the target region and the region associated with the traversed node in the routing tree overlap; andresponsive to determining that the target region and the region associated with the traversed node in the routing tree do not overlap, refraining from traversing any child nodes of the traversed node in the routing tree. Optionally, wherein the determining comprises traversing the routing tree of the first process until the subregions in the set cumulatively cover the target region, the traversing comprising, for each of a plurality of traversed nodes in the routing tree: determining whether the target region and the region assoc