×

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
First Claim
Patent Images

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.

View all claims
  • 1 Assignment
Timeline View
Assignment View
    ×
    ×