MULTITHREADED PHYSICS ENGINE WITH PREDICTIVE LOAD BALANCING

• US 20110321057A1
• Filed: 06/24/2010
• Published: 12/29/2011
• Est. Priority Date: 06/24/2010
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Mejdrich, Eric O., Schardt, Paul E., Shearer, Robert A., Tubbs, Matthew R.
• Granted Patent: US 8,627,329 B2
• Time in Patent Office: Days
• US Class Current: 718/105
• CPC Class Codes: G06F 2209/5019 Workload prediction
• CPC Class Codes: G06F 9/505 considering the load
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system

Abstract

A circuit arrangement and method utilize predictive load balancing to allocate the workload among hardware threads in a multithreaded physics engine. The predictive load balancing is based at least in part upon the detection of predicted future collisions between objects in a scene, such that the reallocation of respective loads of a plurality of hardware threads may be initiated prior to detection of the actual collisions, thereby increasing the likelihood that hardware threads will be optimally allocated when the actual collisions occur.

Claims

1. A circuit arrangement, comprising:

network on chip hardware logic including a plurality of processing cores defining a plurality of hardware threads and an on chip network coupling the plurality of processing cores to one another;

a memory subsystem coupled to the plurality of processing cores and storing a plurality of level of detail components for a plurality of objects in a scene;

a physics engine executed by at least a portion of the plurality of hardware threads, the physics engine including a multithreaded software pipeline including a plurality of stages configured to detect collisions between objects from among the plurality of objects; and

at least one component loader hardware thread and a plurality of collision detection hardware threads defined among the plurality of stages, the component loader hardware thread configured to retrieve level of detail components for objects in the scene from the memory subsystem and stream each level of detail component to sequences of collision detection hardware threads among the plurality of collision detection hardware threads such that the collision detection hardware threads are able to access the level of detail components streamed thereto without directly accessing the memory subsystem, each collision detection hardware thread allocated to a spatial region of the scene and configured to perform collision detection for the spatial region using the level of detail components streamed thereto, and at least one collision detection hardware thread configured to stream level of detail components to another collision detection hardware disposed later in the multithreaded software pipeline, wherein the plurality of collision detection hardware threads are further configured to detect future collisions between objects in the scene, and wherein the component loader hardware thread is configured to initiate a workload reallocation among the plurality of collision detection hardware threads in response to a detected future collision.

2. A method of load balancing among a plurality of hardware threads in a multithreaded physics engine, the method comprising:

allocating workload among the plurality of hardware threads in the multithreaded physics engine;

detecting a future collision between objects in a scene; and

initiating a workload reallocation among the plurality of hardware threads in response to detecting the future collision.

3. The method of claim 2, wherein the plurality of hardware threads includes a plurality of collision detection hardware threads configured to detect collisions between objects in the scene, wherein initiating the workload reallocation includes reallocating the workload among the plurality of collision detection hardware threads.

4. The method of claim 2, wherein the plurality of hardware threads includes a plurality of impulse propagation hardware threads configured to propagate impulses between objects in the scene, wherein initiating the workload reallocation includes reallocating the workload among the plurality of impulse propagation hardware threads.

5. The method of claim 2, further comprising, after detecting the future collision, detecting a current collision corresponding to the future collision.

6. The method of claim 5, wherein initiating the workload reallocation includes completing the workload reallocation prior to detecting the current collision.

7. The method of claim 2, further comprising determining a number of objects involved in the future collision, wherein initiating the workload reallocation is selectively performed based upon the determination.

8. The method of claim 2, further comprising determining a property of at least one object involved in the future collision, wherein initiating the workload reallocation is selectively performed based upon the determination.

9. The method of claim 8, wherein the property is selected from the group consisting of rigidity, deformability, elasticity, speed, mass, spring constant, and combinations thereof.

10. The method of claim 2, wherein detecting the future collision includes detecting an intersection with an object sweep projected over multiple time intervals.

11. The method of claim 2, wherein the multithreaded physics engine comprises a multithreaded software pipeline utilizing the plurality of hardware threads, the multithreaded software pipeline including a plurality of stages configured to detect collisions between objects in a scene, the plurality of stages including at least one component loader stage and a plurality of collision detection stages assigned to the plurality of hardware threads, the component loader stage configured to retrieve level of detail components for a plurality of objects in the scene from a memory and stream each level of detail component to at least one of the plurality of collision detection hardware threads, and each collision detection stage configured to perform collision detection using the level of detail components streamed thereto, wherein initiating the workload reallocation includes reallocating workload among the plurality of collision detection hardware threads.

12. A circuit arrangement, comprising:

a plurality of hardware threads; and

program code implementing at least a portion of a multithreaded physics engine and executed by the plurality of hardware threads, the program code configured to allocate workload among the plurality of hardware threads, detect a future collision between objects in a scene, and initiate a workload reallocation among the plurality of hardware threads in response to detecting the future collision.

13. The circuit arrangement of claim 12, wherein the plurality of hardware threads includes a plurality of collision detection hardware threads configured to detect collisions between objects in the scene, wherein the program code is configured to initiate the workload reallocation by reallocating the workload among the plurality of collision detection hardware threads.

14. The circuit arrangement of claim 12, wherein the plurality of hardware threads includes a plurality of impulse propagation hardware threads configured to propagate impulses between objects in the scene, wherein the program code is configured to initiate the workload reallocation by reallocating the workload among the plurality of impulse propagation hardware threads.

15. The circuit arrangement of claim 12, wherein the program code is further configured to, after detecting the future collision, detect a current collision corresponding to the future collision.

16. The circuit arrangement of claim 15, wherein the program code is further configured to complete the workload reallocation prior to detecting the current collision.

17. The circuit arrangement of claim 12, wherein the program code is further configured to determine a number of objects involved in the future collision, and wherein the program code is configured to selectively initiate the workload reallocation based upon the determination.

18. The circuit arrangement of claim 12, wherein the program code is further configured to determine a property of at least one object involved in the future collision, and wherein the program code is configured to selectively initiate the workload reallocation based upon the determination.

19. The circuit arrangement of claim 18, wherein the property is selected from the group consisting of rigidity, deformability, elasticity, speed, mass, spring constant, and combinations thereof.

20. The circuit arrangement of claim 12, wherein the program code is configured to detect the future collision by detecting an intersection with an object sweep projected over multiple time intervals.

21. The circuit arrangement of claim 12, further comprising a multithreaded software pipeline utilizing the plurality of hardware threads, the multithreaded software pipeline including a plurality of stages configured to detect collisions between objects in a scene, the plurality of stages including at least one component loader stage and a plurality of collision detection stages assigned to the plurality of hardware threads, the component loader stage configured to retrieve level of detail components for a plurality of objects in the scene from a memory and stream each level of detail component to at least one of the plurality of collision detection hardware threads, and each collision detection stage configured to perform collision detection using the level of detail components streamed thereto, wherein the program code is configured to initiate the workload reallocation by reallocating workload among the plurality of collision detection hardware threads.

22. An integrated circuit device including the circuit arrangement of claim 21.

23. A program product comprising a non-transitory computer readable medium and logic definition program code resident on the non-transitory computer readable medium and defining the circuit arrangement of claim 21.