Matrix computation framework

Abstract

Described herein are technologies pertaining to matrix computation. A computer-executable algorithm that is configured to execute perform a sequence of computations over a matrix tile is received and translated into a global directed acyclic graph that includes vertices that perform a sequence of matrix computations and edges that represent data dependencies amongst vertices. A vertex in the global directed acyclic graph is represented by a local directed acyclic graph that includes vertices that perform a sequence of matrix computations at the block level, thereby facilitating pipelined, data-driven matrix computation.

What is claimed is: 
     
         1 . A computing system, comprising:
 a processor; and   a memory that comprises a system that is executed by the processor, the system configured to:
 express matrix computations as a sequence of operations to be performed over a tile of a matrix, the tile being a portion of the matrix; 
 translate the sequence of operations into a global directed acyclic graph (DAG); and 
 cause the sequence of operations to be executed based upon the global DAG. 
   
     
     
         2 . The computing system of  claim 1 , the global DAG includes vertices and edges, a vertex in the vertices of the global DAG is representative of a sub-sequence of operations in the sequence of operations, the edges representative of data dependencies between vertices of the global DAG. 
     
     
         3 . The computing system of  claim 2 , the system further configured to schedule the vertices at respective computing devices in a distributed computing environment. 
     
     
         4 . The computing system of  claim 3 , the system further configured to reschedule the vertex responsive to receipt of an indication that a computing device that has been assigned the vertex has a fault corresponding thereto. 
     
     
         5 . The computing system of  claim 3 , the system further configured to transmit a block of the matrix to a computing device in the respective computing devices responsive to receipt of an indication that another computing device in the respective computing devices has a fault corresponding thereto. 
     
     
         6 . The computing system of  claim 2 , the system further configured to translate the vertex in the global DAG into a local DAGs, wherein the local DAG represents a sequence of operations to be performed over a block of the matrix, the block of the matrix being a portion of the tile of the matrix. 
     
     
         7 . The computing system of  claim 6 , the local DAG comprises vertices and edges, a vertex in the vertices of the local DAG is representative of a sub-sequence of the sequence of operations to be performed over the block of the matrix, the edges representative of data dependencies between vertices of the local DAG. 
     
     
         8 . The computing system of  claim 7 , the system further configured to transmit the local DAG to another computing device, the another computing device configured to perform the sequence of operations over the block of the matrix responsive to receiving the local DAG. 
     
     
         9 . The computing system of  claim 8 , the system further configured to transmit another block of the matrix to the another computing device, the another computing device configured to perform the sequence of operations over the block of the matrix based upon the another block of the matrix. 
     
     
         10 . The computing system of  claim 1 , the system further configured to identify blocks of the matrix that are to be tracked over time to facilitate efficient fault tolerance. 
     
     
         11 . A method comprising:
 receiving a matrix computation that is to be performed over a matrix;   expressing the matrix computation as sequences of operations to be performed over tiles of the matrix, the tiles being portions of the matrix;   translating, by a processor, a sequence of operations to be performed over a tile of a matrix as a global directed acyclic graph (DAG) that comprises vertices and edges, the vertices representative of sub-sequences of operations to be performed over blocks of the tile, the edges representative of data dependencies between the vertices; and   scheduling the vertices at computing devices in a distributed computing environment.   
     
     
         12 . The method of  claim 11 , further comprising:
 translating a vertex in the vertices into a local DAG, the local DAG representative of a sequence of operations to be performed over a block of the tile, the local DAG comprises vertices and edges, the vertices of the local DAG representative of a sub-sequence of the operations to be performed over the block, the edges representative of data dependencies between the vertices.   
     
     
         13 . The method of  claim 12 , the translating of the vertex into the local DAG being based upon a size of a memory cache of a computing device that is to receive the local DAG. 
     
     
         14 . The method of  claim 13 , wherein the local DAG is represented as skeleton code that causes an operator to fire responsive to receipt of the block. 
     
     
         15 . The method of  claim 13 , further comprising transmitting blocks of the matrix to the computing devices. 
     
     
         16 . The method of  claim 11 , further comprising:
 receiving an indication that execution of a sub-sequence of operations represented by a vertex in the global DAG has failed at a computing device; and   rescheduling the vertex at another computing device responsive to receiving the indication.   
     
     
         17 . A computer-readable medium comprising instructions that, when executed by a processor, cause the processor to perform acts, comprising:
 receiving at least one computation that is to be executed over a matrix;   responsive to receiving the at least one computation, representing the at least one computation as a sequence of operations that are to be undertaken on tiles of the matrix;   responsive to representing the at least one computation as the sequence of operations, translating at least one operation into a global directed acyclic graph (DAG) that comprises:
 a plurality of vertices that represent a corresponding plurality of sequential operations on at least one tile of the matrix; and 
 a plurality of edges that represent data dependencies between the plurality of vertices; and 
   responsive to translating the at least one operation into the global DAG, scheduling the vertices of the global DAG at a plurality of computing devices in a distributed computing environment, wherein the plurality of computing devices collectively perform the at least one operation over the matrix.   
     
     
         18 . The computer-readable medium of  claim 17 , the instructions further comprising:
 responsive to translating the at least one operation into the global DAG, representing a vertex in the global DAG as a local DAG that comprises a plurality of vertices that are configured to perform a corresponding plurality of sequential operations on at least one block that corresponds to the matrix, wherein a size of the block is smaller than a size of the at least one tile; and   causing the sequential operations that are represented by the plurality of vertices in the local DAG to be executed in a data-driven manner.   
     
     
         19 . The computer-readable medium of  claim 18 , the acts further comprising:
 setting the size of the block based upon size of a cache of a computing device in the plurality of computing devices that is to executed the local DAG over the block.   
     
     
         20 . The computer-readable medium of  claim 17 , further comprising:
 receiving an indication that a computing device in the computing devices has a fault corresponding thereto; and   rescheduling a vertex assigned to the computing device to another computing device responsive to receiving the indication.