Method of operation for parallel LCP solver

• US 7,937,359 B1
• Filed: 04/27/2009
• Issued: 05/03/2011
• Est. Priority Date: 03/08/2004
• Status: Active Grant

• Current Assignee: NVIDIA Corporation
• Original Assignee: NVIDIA Corporation
• Inventors: Tonge, Richard, Sequeira, Dilip, Zhang, Lihua, Maher, Monier
• Primary Examiner(s): Fernandez Rivas; Omar F
• Application Number:
  US12/430,431
• Time in Patent Office: 736 Days
• Field of Search: None
• US Class Current: 706/62
• CPC Class Codes: G06F 17/11 for solving equations , e.g. nonlinear equations, general mathematical optimization problems optimization specially adapted for a specific administrative, business or logistic context G06Q10/04

Abstract

A method of operating a Linear Complementarity Problem (LCP) solver is disclosed, where the LCP solver is characterized by multiple execution units operating in parallel to implement a competent computational method adapted to resolve physics-based LCPs in real-time.

Claims

1. A computing device for resolving linear complementarity problems (LCPs) related to a physics-based initial data set characterizing a plurality of objects and a plurality of constraints restricting movement of at least one object in the plurality of objects, the computing device comprising:

a main memory;

a central processing unit (CPU) configured to;

generate the physics-based initial data set characterizing the plurality of objects and the plurality of constraints, and

store the physics-based initial data set and the plurality of constraints in the main memory restricting movement of at least one object in the plurality of objects; and

a co-processing unit comprising a plurality of island processing engines (IPEs) arranged in parallel and configured to;

receive the physics-based initial data set from the main memory,

define a plurality of island data sets from the physics-based initial data set, wherein each one of the plurality of island data sets corresponds to at least one LCP,

transfer each one of the plurality of island data sets to a corresponding one of the plurality of IPEs for processing to produce output data, and

animate a physics-based interaction of the plurality of objects based on the output data for display,

wherein each IPE comprises a plurality of execution units arranged in parallel and configured to;

define a plurality of data portions from an island data set, wherein each one of the plurality of data portions comprises data associated with an object or a constraint characterized in the initial data set,

transfer each one of the plurality of data portions to a corresponding one of the plurality of execution units, and

process each one of the plurality of data portions in parallel to produce output data that solves the corresponding at least one LCP.

2. The computing device of claim 1, wherein at least one of the plurality of execution units comprises a vector processor.

3. The computing device of claim 1, wherein each IPE further comprises:

an IPE memory storing the island data set; and

an island control unit (ICU) configured to control the transfer of data from the IPE memory to the plurality of execution units.

4. The computing device of claim 3, wherein each IPE is further configured to calculate at least one Jacobian corresponding to the island data set.

5. The computing device of claim 4, wherein the island data set comprises a plurality of constraint rows, and wherein each IPE is configured to define the plurality of data portions from the island data set by selecting a group of constraint rows from the plurality of constraint rows in order to define each one of the plurality of data portions.

6. The computing device of claim 5, wherein selecting a group of constraint rows comprises selecting only neighbored constraint rows related to an object or a constraint characterized in the initial data set.

7. The computing device of claim 5, wherein each IPE is further configured to resolve each data portion of the plurality of data portions in parallel by:

analyzing the type of the data portion;

selecting a computational method from a group of defined computational methods corresponding to the type of the data portion; and

applying the selected computational method to resolve the data portion.

8. The computing device of claim 1, wherein the co-processing unit further comprises:

a co-processor memory;

a co-processor control engine configured to control overall operation of the co-processing unit; and

a data movement engine (DME) configured to control the step of transferring the plurality of island data sets from the main memory to the co-processor memory.

9. The computing device of claim 8, wherein the step of transferring is performed via at least one protocol selected from a group of protocols defined by USB, USB2, Firewire, PC I, PCI-X, PCI-Express, and Ethernet.

10. The computing device of claim 1, wherein the co-processing unit is a graphics processing unit (GPU).

11. A computing device for resolving linear complementarity problems (LCPs) related to a physics-based initial data set characterizing a plurality of objects and a plurality of constraints restricting movement of at least one object in the plurality of objects, the computing device comprising:

a main memory;

a central processing unit (CPU) configured to;

generate an initial data set defining a physics-based problem, and

store the initial data set in the main memory;

a graphics processing unit (GPU) configured to animate a physics-based interaction of the plurality of objects for display; and

a physics processing unit (PPU) comprising a plurality of island processing engines (IPEs) arranged in parallel and configured to;

receive the physics-based initial data set from the main memory,

define a plurality of island data sets from the physics-based initial data set, wherein each one of the plurality of island data sets corresponds to at least one LCP,

transfer each one of the plurality of island data sets to a corresponding one of the plurality of IPEs for processing to produce output data, and

transfer the output data to the GPU for animating the physics-based interaction,

wherein each IPE comprises a plurality of execution units arranged in parallel and configured to;

define a plurality of data portions from an island data set, wherein each one of the plurality of data portions comprises data associated with an object or a constraint characterized in the initial data set,

transfer each one of the plurality of data portions to a corresponding one of the plurality of execution units, and

process each one of the plurality of data portions in parallel to produce output data that solves the corresponding at least one LCP.

12. A processing unit for resolving linear complementarity problems (LCPs) related to a physics-based initial data set characterizing a plurality of objects and a plurality of constraints restricting movement of at least one object in the plurality of objects, the processing unit configured to:

store an island data set derived from the initial data set in a memory, wherein the island data set defines a whole gradient vector;

define a plurality of subspaces based on the island data set, wherein each one of the plurality of subspaces has a data type and comprises a group of constraint rows that corresponds to a portion of the whole gradient vector;

assign a first subspace in the plurality of subspaces to a first execution unit within the processing unit based on the data type associated with the first subspace;

assign a second subspace in the plurality of subspaces to a second execution unit within the processing unit based on the data type associated with the second subspace;

process the first subspace and the second subspace in parallel to produce output data that resolves at least a portion of the LCP; and

based on the output data, animate a physics-based interaction of the plurality of objects for display.

13. The processing unit of claim 12, wherein the step of defining a plurality of subspaces comprises grouping neighbored constraint rows influencing a common object within a common subspace.

14. The processing unit of claim 13, wherein the step of defining a plurality of subspaces further comprises omitting a neighbored constraint row from a subspace where resolution of omitted constraint row in the common subspace would adversely influence the resolution of another subspace.

15. The processing unit of claim 12, wherein the step of processing includes generating a first set of data for the first subspace and a second set of data for the second subspace, and combining the first set of data and the second set of data to produce the output data.