Patent No. | 10,191,998 |
---|---|

Issue Date | January 29, 2019 |

Title | Methods Of Data Reduction For Parallel Breadth-first Search Over Graphs Of Connected Data Elements |

Inventorship | Paul Burkhardt, North Potomac, MD (US) |

Assignee | The United States of America, as represented by the Director, National Secu... |

1. A computer-implemented method of constructing a logical pathway between an initial search frontier and a target data element in an undirected graph of data elements, in a system comprising 1) a plurality of parallel processors each having a local memory, 2) an inter-processor communication (IPC) network, and 3) a master controller having a local memory and logically coupled to the plurality of parallel processors via the IPC network, the method comprising:receiving, at the master controller in the local memory, a data structure defining a symmetric matrix having size n×n, wherein the value of each matrix element corresponds to one of 1) a presence of, and 2) an absence of, an undirected edge between a pair of data elements in the graph of data elements defined by a row and a column of the matrix element;

receiving, at the master controller in the local memory, a first vector of length n, wherein the value of each element in the vector corresponds to one of 1) a presence of, and 2) an absence of, a data element of the graph of data elements in the initial search frontier;

at the master controller in the local memory, initializing 1) a counter variable and 2) a tracking array, wherein the tracking array contains array elements that are configured to track dimensionality reduction parameters for the matrix;

repeatedly performing the operations of:

multiplying a subset of the matrix defined by the array element corresponding to the counter variable, by a subset of the first vector defined by the array element corresponding to the counter variable, to generate a second vector corresponding to an updated search frontier corresponding to the counter variable, wherein multiplying the subset of the matrix by the subset of the first vector comprises:

providing, from the master controller via the IPC network to a first processor of the plurality of parallel processors, the first vector and at least one first portion of the matrix;

at the first processor in the first processor's local memory, multiplying the first vector by the at least one first portion of the matrix to produce a first result;

providing, from the first processor via the IPC network to the master controller, the first result;

providing, from the master controller via the IPC network to a second processor of the plurality of parallel processors, the first vector and at least one second portion of the matrix;

at the second processor in the second processor's local memory, multiplying the first vector by the at least one second portion of the matrix to produce a second result;

providing, from the second processor via the IPC network to the master controller, the second result; and

combining, at the master controller in the local memory, the first result and the second result to generate the second vector corresponding to the updated search frontier;

incrementing the counter variable;

updating the first vector based on the updated search frontier; and

updating an array element in the tracking array corresponding to the counter variable based on the non-zero values of the first vector, such that the updated array element corresponds to a larger dimensionality reduction of the matrix than the previously used array element;

until 1) the updated search frontier contains a non-zero element corresponding to the target data element, or 2) the matrix is reduced to a minimum dimension; and

constructing the logical pathway based on the tracking array.

receiving, at the master controller in the local memory, a first vector of length n, wherein the value of each element in the vector corresponds to one of 1) a presence of, and 2) an absence of, a data element of the graph of data elements in the initial search frontier;

at the master controller in the local memory, initializing 1) a counter variable and 2) a tracking array, wherein the tracking array contains array elements that are configured to track dimensionality reduction parameters for the matrix;

repeatedly performing the operations of:

multiplying a subset of the matrix defined by the array element corresponding to the counter variable, by a subset of the first vector defined by the array element corresponding to the counter variable, to generate a second vector corresponding to an updated search frontier corresponding to the counter variable, wherein multiplying the subset of the matrix by the subset of the first vector comprises:

providing, from the master controller via the IPC network to a first processor of the plurality of parallel processors, the first vector and at least one first portion of the matrix;

at the first processor in the first processor's local memory, multiplying the first vector by the at least one first portion of the matrix to produce a first result;

providing, from the first processor via the IPC network to the master controller, the first result;

providing, from the master controller via the IPC network to a second processor of the plurality of parallel processors, the first vector and at least one second portion of the matrix;

at the second processor in the second processor's local memory, multiplying the first vector by the at least one second portion of the matrix to produce a second result;

providing, from the second processor via the IPC network to the master controller, the second result; and

combining, at the master controller in the local memory, the first result and the second result to generate the second vector corresponding to the updated search frontier;

incrementing the counter variable;

updating the first vector based on the updated search frontier; and

updating an array element in the tracking array corresponding to the counter variable based on the non-zero values of the first vector, such that the updated array element corresponds to a larger dimensionality reduction of the matrix than the previously used array element;

until 1) the updated search frontier contains a non-zero element corresponding to the target data element, or 2) the matrix is reduced to a minimum dimension; and

constructing the logical pathway based on the tracking array.