HIGHLY SCALABLE CLUSTER ENGINE FOR HOSTING SIMULATIONS OF OBJECTS INTERACTING WITHIN A SPACE

摘要

A highly scalable cluster of computing nodes simulates large numbers of objects interacting in a space defined by an octree of cubical elements. Each cube of the octree is enclosed within a corresponding padding sphere. Interacting objects are quickly identified by determining which of the padding spheres are candidate spheres that satisfy an interaction criterion, considering candidate objects located in the cubes that correspond to the candidate spheres, and determining which of the candidate objects meet the interaction criterion. The computing workload can be efficiently parallelized among nodes of the cluster by assigning the objects to the nodes in approximately equal numbers, each node being responsible for managing the objects assigned thereto. Inter-node data traffic can be minimized by reassigning frequently interacting objects to the same node. The cluster can be scaled simply by adding more nodes to the cluster, and redistributing the objects equally among the nodes.

主权项

1. A system for hosting a simulation of a plurality of simulated objects interacting within a simulated space, the system comprising non-transient media containing software configured for operation on a cluster computing engine, the cluster computing engine including a plurality of computing nodes organized into an intercommunicating cluster, the cluster computing engine being in network communication with a plurality of user access devices, the software being configured to:
assign the simulated objects to the nodes, so that each of the nodes is responsible for parameter storage and computations in support of the simulated objects that are assigned to it; organize the simulated space into an octree of cubes, each of the cubes being contained within a corresponding padding sphere; and identify all objects that interact with a target object assigned to a host node by causing the nodes to carry out steps including:
communicating by the host node to the other “remote” nodes of a position of the target object and an interaction criterion of the target object;each of the nodes identifying which padding spheres in their octree are candidate spheres, the candidate spheres being those padding spheres that meet the interaction criterion;each of the nodes considering candidate objects, the candidate objects being all simulated objects that are located in the cubes that correspond with the candidate spheres;each of the nodes determining which of the candidate objects meet the interaction criterion;communicating by the remote nodes to the host node of positions and other details regarding all objects that meet the interaction criterion; andthe host node simulating interactions between the target object and the objects that meet the interaction criterion.