Matrix Ordering for Cache Efficiency in Performing Large Sparse Matrix Operations

• US 20160224473A1
• Filed: 02/02/2015
• Published: 08/04/2016
• Est. Priority Date: 02/02/2015
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Acar, Emrah, Bordawekar, Rajesh R., Franceschini, Michele M., Lastras-Montano, Luis A., Puri, Ruchir, Qian, Haifeng, Soares, Livio B.
• Granted Patent: US 9,606,934 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0891 using clearing, invalidating or resetting means
• CPC Class Codes: G06F 12/0895 of parts of caches, e.g. directory or tag array
• CPC Class Codes: G06F 12/12 Replacement control
• CPC Class Codes: G06F 16/328 Management therefor
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 17/16 Matrix or vector computation , e.g. matrix-matrix or matrix-vector multiplication, matrix factorization matrix transposition G06F7/78
• CPC Class Codes: G06F 2212/60 Details of cache memory
• CPC Class Codes: G06F 2212/601 Reconfiguration of cache memory
• CPC Class Codes: G06F 2212/604 Details relating to cache allocation
• CPC Class Codes: G06F 7/08 Sorting, i.e. grouping record carriers in numerical or other ordered sequence according to the classification of at least some of the information they carry by merging two or more sets of carriers in ordered sequence G06F7/16

Abstract

Mechanisms are provided for performing a matrix operation. A processor of a data processing system is configured to perform cluster-based matrix reordering of an input matrix. An input matrix, which comprises nodes associated with elements of the matrix, is received. The nodes are clustered into clusters based on numbers of connections with other nodes within and between the clusters, and the clusters are ordered by minimizing a total length of cross cluster connections between nodes of the clusters, to thereby generate a reordered matrix. A lookup table is generated identifying new locations of nodes of the input matrix, in the reordered matrix. A matrix operation is then performed based on the reordered matrix and the lookup table.

Claims

1. A method, in a data processing system comprising a processor and a memory, for performing a matrix operation, the method comprising:

configuring the processor of the data processing system to perform cluster-based matrix reordering of an input matrix;

receiving, by the processor, the input matrix, wherein the input matrix comprises nodes associated with elements of the matrix;

clustering, by the processor, the nodes into clusters based on numbers of connections with other nodes within and between the clusters;

ordering, by the processor, the clusters by minimizing a total length of cross cluster connections between nodes of the clusters, to thereby generate a reordered matrix;

generating, by the processor, a lookup table identifying new locations of nodes of the input matrix, in the reordered matrix;

storing, in a memory of the data processing system, data corresponding to the nodes in accordance with the new locations of nodes in the reordered matrix; and

performing, by the processor, a matrix operation based on the reordered matrix and the lookup table at least by loading data corresponding to nodes in the reordered matrix into a cache memory of the data processing system, wherein the storage of the data corresponding to the nodes in accordance with the new locations of nodes in the reordered matrix minimizes cache misses in the cache memory when performing the matrix operation.

2. The method of claim 1, wherein the nodes of the input matrix represent at least one of information, concepts, or entities, and wherein the elements of the matrix represent connections or relationships between the nodes where a non-zero element indicates a connection between the nodes associated with the element.

3. The method of claim 1, wherein clustering nodes into clusters further comprises:

identifying one or more cliques of nodes in the input matrix, wherein a clique of nodes comprises only nodes that have connections to one another and vice versa; and

growing at least one clique of nodes in the one or more cliques of nodes into a cluster of nodes by assigning other nodes of the input matrix, not already in a clique of nodes, to the at least one clique based on connections of the other nodes to nodes already in the at least one clique.

4. The method of claim 3, wherein clustering nodes into clusters further comprises:

comparing a size of each clique of nodes in the one or more cliques of nodes to a minimum clique size, wherein the minimum clique size specifies a minimum number of nodes required to be in a clique for growing a cluster based on the clique; and

performing the growing of the at least one clique of nodes only on cliques of nodes in the one or more cliques of nodes that have a size that meets or exceeds the minimum clique size.

5. The method of claim 3, wherein assigning other nodes of the input matrix to the at least one clique comprises assigning each of the other nodes to a respective clique, in the at least one clique, to which the other node has a greatest number of connections.

6. The method of claim 3, wherein growing the at least one clique of nodes comprises assigning other nodes of the input matrix to the at least one clique until a maximum cluster size is reached.

7. The method of claim 6, wherein the maximum cluster size is a proportion of a cache memory size of a cache memory associated with the processor.

8. The method of claim 3, wherein clustering the nodes further comprises, for each cluster, and for each node of each cluster:

refining the cluster by evaluating the node of the cluster to determine if the node has more connections to nodes of another cluster than to nodes within the cluster; and

migrating the node to the other cluster if the node has more connections to nodes of the other cluster than to nodes within the cluster and migrating the node does not violate a maximum cluster size limitation of the other cluster.

9. The method of claim 1, wherein ordering the clusters by minimizing a total length of cross cluster connections between nodes of the clusters, to thereby generate a reordered matrix further comprises performing localized ordering of nodes within each of the clusters, wherein the localized ordering of nodes within each of the clusters comprises moving non-zero elements of the cluster closer to a diagonal of a sub-matrix of the cluster and moving nodes having connections to nodes in adjacent clusters closer to a border of the sub-matrix of the cluster.

10. The method of claim 1, wherein the matrix operation is a multiplication of the matrix by a vector to generate an output vector, and wherein the method further comprises:

performing an analysis operation, based on the matrix operation, to extract information from the input matrix based on the reordered matrix and the lookup table; and

outputting results of the analysis operation.

11. A computer program product comprising a computer readable storage medium having a computer readable program stored therein, wherein the computer readable program, when executed on a computing device, causes the computing device to:

configure the computing device to perform cluster-based matrix reordering of an input matrix;

receive the input matrix, wherein the input matrix comprises nodes associated with elements of the matrix;

cluster the nodes into clusters based on numbers of connections with other nodes within and between the clusters;

order the clusters by minimizing a total length of cross cluster connections between nodes of the clusters, to thereby generate a reordered matrix;

generate a lookup table identifying new locations of nodes of the input matrix, in the reordered matrix;

store, in a memory of the computing device, data corresponding to the nodes in accordance with the new locations of nodes in the reordered matrix; and

perform a matrix operation based on the reordered matrix and the lookup table at least by loading data corresponding to nodes in the reordered matrix into a cache memory of the computing device, wherein the storage of the data corresponding to the nodes in accordance with the new locations of nodes in the reordered matrix minimizes cache misses in the cache memory when performing the matrix operation.

12. The computer program product of claim 11, wherein the nodes of the input matrix represent at least one of information, concepts, or entities, and wherein the elements of the matrix represent connections or relationships between the nodes where a non-zero element indicates a connection between the nodes associated with the element.

13. The computer program product of claim 11, wherein the computer readable program causes the computing device to cluster nodes into clusters at least by:

identifying one or more cliques of nodes in the input matrix, wherein a clique of nodes comprises only nodes that have connections to one another and vice versa; and

growing at least one clique of nodes in the one or more cliques of nodes into a cluster of nodes by assigning other nodes of the input matrix, not already in a clique of nodes, to the at least one clique based on connections of the other nodes to nodes already in the at least one clique.

14. The computer program product of claim 13, wherein the computer readable program causes the computing device to cluster nodes into clusters at least by:

comparing a size of each clique of nodes in the one or more cliques of nodes to a minimum clique size, wherein the minimum clique size specifies a minimum number of nodes required to be in a clique for growing a cluster based on the clique; and

performing the growing of the at least one clique of nodes only on cliques of nodes in the one or more cliques of nodes that have a size that meets or exceeds the minimum clique size.

15. The computer program product of claim 13, wherein assigning other nodes of the input matrix to the at least one clique comprises assigning each of the other nodes to a respective clique, in the at least one clique, to which the other node has a greatest number of connections.

16. The computer program product of claim 13, wherein growing the at least one clique of nodes comprises assigning other nodes of the input matrix to the at least one clique until a maximum cluster size is reached.

17. The computer program product of claim 16, wherein the maximum cluster size is a proportion of a cache memory size of a cache memory associated with the processor.

18. The computer program product of claim 13, wherein the computer readable program causes the computing device to cluster the nodes at least by, for each cluster, and for each node of each cluster:

refining the cluster by evaluating the node of the cluster to determine if the node has more connections to nodes of another cluster than to nodes within the cluster; and

migrating the node to the other cluster if the node has more connections to nodes of the other cluster than to nodes within the cluster and migrating the node does not violate a maximum cluster size limitation of the other cluster.

19. The computer program product of claim 11, wherein the computer readable program causes the computing device to order the clusters by minimizing a total length of cross cluster connections between nodes of the clusters, to thereby generate a reordered matrix at least by performing localized ordering of nodes within each of the clusters, wherein the localized ordering of nodes within each of the clusters comprises moving non-zero elements of the cluster closer to a diagonal of a sub-matrix of the cluster and moving nodes having connections to nodes in adjacent clusters closer to a border of the sub-matrix of the cluster.

20. An apparatus comprising:

a processor;

a cache coupled to the processor; and

a memory coupled to the processor, wherein the memory comprises instructions which, when executed by the processor, configure the processor to perform cluster-based matrix reordering of an input matrix and to;

receive the input matrix, wherein the input matrix comprises nodes associated with elements of the matrix;

cluster the nodes into clusters based on numbers of connections with other nodes within and between the clusters;

order the clusters by minimizing a total length of cross cluster connections between nodes of the clusters, to thereby generate a reordered matrix;

generate a lookup table identifying new locations of nodes of the input matrix, in the reordered matrix;

store, in the memory, data corresponding to the nodes in accordance with the new locations of nodes in the reordered matrix; and

perform, by the processor, a matrix operation based on the reordered matrix and the lookup table at least by loading data corresponding to nodes in the reordered matrix into the cache, wherein the storage of the data corresponding to the nodes in accordance with the new locations of nodes in the reordered matrix minimizes cache misses in the cache when performing the matrix operation.

21. A Question and Answer (QA) system, comprising:

at least one processor; and

an interface for accessing one or more storage devices that store a corpus of natural language content that is processed by the QA system to generate answers to received questions, wherein the at least one processor is configured to implement;

a QA system pipeline that receives an input question and generates one or more answers to the input question at least by processing the corpus of natural language content;

a matrix ordering engine coupled to the QA system pipeline, wherein the matrix reordering engine is configured to;

receive an input matrix, wherein the input matrix comprises nodes associated with elements of the matrix, and wherein the nodes represent concepts found in the natural language content and the elements of the matrix represent connections between the concepts found in the natural language content;

cluster the nodes into clusters based on numbers of connections with other nodes within and between the clusters;

order the clusters by minimizing a total length of cross cluster connections between nodes of the clusters, to thereby generate a reordered matrix;

generate a lookup table identifying new locations of nodes of the input matrix, in the reordered matrix;

store, in the memory, data corresponding to the nodes in accordance with the new locations of nodes in the reordered matrix; and

perform, by the processor, a matrix operation based on the reordered matrix and the lookup table at least by loading data corresponding to nodes in the reordered matrix into the cache, wherein the storage of the data corresponding to the nodes in accordance with the new locations of nodes in the reordered matrix minimizes cache misses in the cache when performing the matrix operation.