Matrix ordering for cache efficiency in performing large sparse matrix operations

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;
• and
• perform a matrix operation, based on the reordered matrix, at least by loading data corresponding to nodes in the reordered matrix into a cache memory of the computing device and executing the matrix operation on the data corresponding to the nodes in the reordered matrix loaded into the cache memory, wherein executing the matrix operation on the data corresponding to the nodes in the reordered matrix loaded into the cache memory causes fewer cache misses than performing the matrix operation on data loaded into the cache memory in accordance with the input matrix.

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;
• and
• perform, by the processor, a matrix operation, based on the reordered matrix, at least by loading data corresponding to nodes in the reordered matrix into the cache and executing the matrix operation on the data corresponding to the nodes in the reordered matrix loaded into the cache, wherein executing the matrix operation on the data corresponding to the nodes in the reordered matrix loaded into the cache causes fewer cache misses than performing the matrix operation on data loaded into the cache in accordance with the input matrix.

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;
• and
• perform, by the processor, a matrix operation, based on the reordered matrix, at least by loading data corresponding to nodes in the reordered matrix into the cache and executing the matrix operation on the data corresponding to the nodes in the reordered matrix loaded into the cache, wherein executing the matrix operation on the data corresponding to the nodes in the reordered matrix loaded into the cache causes fewer cache misses than performing the matrix operation on data loaded into the cache in accordance with the input matrix.