Distributed systems and methods for state generation based on multi-dimensional data

Patent metadata

Field	Value
Publication number	US-9665405-B1
Application number	US-201615386870-A
Country	US
Kind code	B1
Filing date	Dec 21, 2016
Priority date	Feb 12, 2010
Publication date	May 30, 2017
Grant date	May 30, 2017

Abstract

Systems and methods are provided for generating multiple system state projections using a grid computing environment. A central coordinator software component executes on a root data processor and provides commands and data to a plurality of node coordinator software components. A node coordinator software component manages threads which execute on its associated node data processor and which perform a set of matrix operations. Stochastic simulations use results of the matrix operations to generate multiple state projections. Additional processing can be performed by the grid computing environment based upon the generated state projections, such as to develop possible change information for users.

First claim

What is claimed is:

1. An improved state projection generation system comprising:
a grid computing environment including a central coordinator, a plurality of node coordinators in data communication with the central coordinator, and one or more compute nodes associated with each node coordinator and in data communication with a node coordinator;
a non-transitory computer readable storage medium, comprising instructions that, when executed by the central coordinator, the plurality of node coordinators, or the one or more compute nodes cause the central coordinator, the plurality of node coordinators, or the one or more compute nodes to perform operations including:
accessing, by the central coordinator, a multi-dimensional data set, wherein the multi-dimensional data set includes multiple observations with respect to a plurality of dimensions;
generating a cross-product matrix for the multi-dimensional data set;
decomposing, by the node coordinators, the cross-product matrix, wherein
decomposing generates a full decomposed matrix;

providing, by the central coordinator, different random vectors to the node coordinators for use in determining a plurality of state simulation matrices using the full decomposed matrix and the random vectors;
computing, using the one or more compute nodes associated with each node coordinator, one or more state simulation matrices, wherein computing includes determining a product between the random vectors and the full decomposed matrix;
identifying, by the central coordinator, position information corresponding to one or more positions to be evaluated;
distributing, by the central coordinator, a position evaluation function to the plurality of node coordinators for use in evaluating the one or more positions by using the one or more state simulation matrices;
generating position evaluations for the one or more positions, wherein generating includes using the position evaluation function, the position information, and the one or more state simulation matrices;
receiving, by the central coordinator, a query, wherein the query corresponds to a request for evaluation of particular position information;
identifying, by the central coordinator, a plurality of individual position evaluations for use in responding to the query;
aggregating, at the central coordinator, the plurality of individual position evaluations, wherein aggregating includes the node coordinators retrieving a plurality of individual positions from shared memory, and wherein aggregating includes the node coordinators transmitting the retrieved plurality of individual positions to the central coordinator; and
generating a response to the query using the aggregated plurality of individual position evaluations.

2. The system of claim 1 , wherein generating the cross-product matrix for the multi-dimensional data set is performed using distributed computing and includes:
partitioning, by the central coordinator, the multi-dimensional data into multiple data partitions;
indicating, by the central coordinator, unique identifiers to the plurality of node coordinators, wherein a unique identifier allows a node coordinator to identify unique portions of the cross-product matrix that the node coordinator is assigned;
using a wave distribution technique to distribute the multiple data partitions among the plurality of node coordinators, wherein the wave distribution technique includes the central coordinator distributing a first data partition to a first node coordinator and the first node coordinator distributing the first data partition to a second node coordinator, and wherein the wave distribution technique includes the central coordinator distributing a second data partition to a third node coordinator and the third node coordinator distributing the second data partition to a fourth node coordinator;
generating, by the one or more compute nodes associated with each node coordinator, assigned unique portions of the cross-product matrix, wherein generating the assigned unique portions includes using one or more distributed data partitions; and
storing, by the node coordinators or the one or more compute nodes associated with each node coordinators, the assigned unique portions of the cross-product matrix.

3. The system of claim 2 , wherein storing the assigned unique portions of the cross-product matrix includes storing the assigned unique portions of the cross-product matrix to the shared memory.

4. The system of claim 2 , wherein decomposing the unique portions of the cross-product matrix includes each node coordinator assigning separate decomposition tasks to the compute nodes associated with the node coordinators.

5. The system of claim 2 , wherein the operations further include:
storing the multi-dimensional data set as a data set matrix, wherein the data partitions correspond to unique rows of the data set matrix, and wherein the wave distribution technique includes distributing the unique rows of the data set matrix individually.

6. The system of claim 1 , wherein decomposing generates decomposed matrix components, wherein decomposing includes distributing the decomposed matrix components among the plurality of node coordinators to provide the plurality of node coordinators each with the full decomposed matrix, wherein the full decomposed matrix includes each of the decomposed matrix components, and wherein distributing includes the node coordinators transmitting the decomposed matrix components between one another or to the central coordinator.

7. The system of claim 1 , wherein each node coordinator and compute nodes associated with the node coordinator have an associated shared memory independent from other node coordinators and other compute nodes.

8. The system of claim 1 , wherein generating position evaluations for the one or more positions is performed using distributed computing and includes:
distributing the position information among the plurality of node coordinators;
determining, by the one or more compute nodes associated with the node coordinators, a plurality of individual position evaluations, wherein an individual position evaluation is determined by a compute node applying the position evaluation function to an individual state simulation matrix and the position information; and
storing, by the compute nodes associated with the node coordinators, the determined individual position evaluations to shared memory associated with the compute nodes.

9. The system of claim 1 , wherein receiving a query includes receiving multiple unrelated queries and wherein generating responses to the unrelated queries does not require re-generation of the cross-product matrix, the full decomposed matrix, or the position evaluations for the one or more positions for generating responses to the unrelated queries.

10. The system of claim 1 , wherein the operations further include:
performing a statistical analysis on the aggregated plurality of individual position evaluations, wherein the response to the query indicates results of the statistical analysis, wherein performing the statistical analysis includes:
determining a mean of the aggregated plurality of individual position evaluations;
determining a distribution of the aggregated plurality of individual position evaluations; and
delineating a portion of the distribution that includes 95% of the aggregated plurality of individual position evaluations and is centered around the mean.

11. An improved state projection generation method comprising:
accessing, by a central coordinator of a grid computing environment, a multi-dimensional data set, wherein the multi-dimensional data set includes multiple observations with respect to a p

Assignees

• Sas Inst Inc

Inventors

• Goodnight James Howard
• Krueger Steve
• Schabenberger Oliver
• Bailey Christopher D

Classifications

• G06F2209/5017

  Task decomposition · CPC title

• G06F9/5072 Primary

  Grid computing · CPC title

• G06Q10/0635

  Risk analysis of enterprise or organisation activities · CPC title

• G06F17/16

  Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)} · CPC title