# US 8,788,556 B2 · Matrix computation framework > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 8,788,556 B2 - Document ID: US8788556B2 - Status: Granted - Kind: B2 - Application number: 13/105,915 - Filed: 2011-05-12 - Published: 2012-11-15 - Granted: 2014-07-22 - Earliest claimed: 2011-05-12 - Assignees: Microsoft Corporation - Applicants: Zheng Zhang; Zhengping Qian; Xiuwei Chen; Yuan Yu - Inventors: Zheng Zhang; Zhengping Qian; Xiuwei Chen; Yuan Yu - Web page: https://patentgrep.com/patent/US8788556B2 ## CPC - G06F 17/16: Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)} - G06F 11/0709: {in a distributed system consisting of a plurality of standalone computer nodes, e.g. clusters, client-server systems} - G06F 11/0793: {Remedial or corrective actions (recovery from an exception in an instruction pipeline G06F9/3861; by retry G06F11/1402; for recovering from a failure of a protocol instance or entity H04L69/40)} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## 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. ## Claims ### Claim 1 A method, comprising: receiving a computer-executable algorithm that is configured to execute a matrix computation on a tile of a matrix; translating the computer-executable algorithm into a computer-implemented global directed acyclic graph that comprises a plurality of vertices and a corresponding plurality of edges, wherein a vertex in the global directed acyclic graph is configured to perform a sequence of operations on the tile of the matrix and the plurality of edges represent data dependencies between coupled vertices, the translating performed by a computer processor; and representing the vertex in the global directed acyclic graph as a local directed acyclic graph that comprises a plurality of vertices, wherein a vertex in the local directed acyclic graph is configured to execute a mathematical operation on a matrix block that is smaller than the tile, wherein the vertex in the local directed acyclic graph executes the mathematical operation in a data-driven manner, the representing performed by the computer processor. ### Claim 2 (depends on 1) The method of claim 1, wherein executing the mathematical operation in the data driven manner comprises executing the mathematical operation on the block responsive to the block being received at the vertex in the local directed acyclic graph. ### Claim 3 (depends on 2) The method of claim 2, wherein executing the mathematical operation in the data driven manner comprises outputting another block for provision to another vertex in the local directed acyclic graph immediately subsequent to executing the mathematical operation on the block. ### Claim 4 (depends on 1) The method of claim 1, wherein size of the block corresponds to size of a cache of a computing device that comprises the local directed acyclic graph. ### Claim 5 (depends on 1) The method of claim 1, wherein the local directed acyclic graph is represented as skeleton code that causes an operator to fire responsive to receipt of the block. ### Claim 6 (depends on 1) The method of claim 1, further comprising scheduling a plurality of different computing devices to perform a plurality of different matrix computations to generate an output. ### Claim 7 (depends on 1) The method of claim 1, further comprising: detecting a failure with respect to the local directed acyclic graph; and causing the mathematical operation to be re-executed responsive to detecting the failure. ### Claim 8 (depends on 7) The method of claim 7, further comprising: recording identities of blocks output by the vertex in the local directed acyclic graph; and causing the mathematical operation to be re-executed based at least in part upon the identities of the blocks output by the vertex. ### Claim 9 (depends on 8) The method of claim 8, further comprising: prior to causing the mathematical operation to be re-executed, querying children vertices in the local directed acyclic graph for identities of blocks needed by the children vertices; and causing the mathematical operation to be re-executed based at least in part upon identities of the block returned responsive to the querying. ### Claim 10 (depends on 1) The method of claim 1 configured for execution in a high performance computing environment. ### Claim 11 (depends on 1) The method of claim 1, wherein output of the global directed acyclic graph is configured for employment in connection with one of facial recognition and three-dimensional modeling. ### Claim 12 A system that facilitates large-scale distributed matrix computation, the system comprising: a processor; and a memory that comprises a plurality of components that are executed by the processor, the plurality of components comprising: a scheduler component that receives a computation pertaining to a matrix and performs the following actions: causes the computation to be represented as a plurality of vertices that are representative of computations to be undertaken by tiles of the matrix, the plurality of vertices being related by a plurality of edges; and schedules the plurality of vertices to be executed on a corresponding plurality of computing devices; and an executor component that executes the computations in parallel in a data-driven manner. ### Claim 13 (depends on 12) The system of claim 12, wherein the scheduler component causes the computation to be represented as a global directed acyclic graph. ### Claim 14 (depends on 13) The system of claim 13, wherein the scheduler component is further configured, for a vertex in the global directed acyclic graph, cause a matrix computation corresponding to the vertex to be represented as a plurality of child vertices that are configured to execute matrix computations on blocks, wherein the blocks are of a size that is less than the tiles. ### Claim 15 (depends on 14) The system of claim 14, wherein the blocks are the respective sizes of caches of the plurality of computing devices. ### Claim 16 (depends on 12) The system of claim 12, wherein the executor component retrieves at least one matrix computation from a library responsive to computer-executable code represented by a vertex calling the at least one matrix computation from the library. ### Claim 17 (depends on 12) The system of claim 12 being distributed across the plurality of computing devices. ### Claim 18 (depends on 12) The system of claim 12, further comprising a fault detector component that detects that a fault has occurred on at least one computing device and causes the executor component to re-execute at least one computation responsive to detecting that the fault has occurred. ### Claim 19 (depends on 18) The system of claim 18, wherein the fault detector component causes the at least one computation to be re-executed based at least in part upon data retained with respect to child vertices that are dependent upon data from a vertex that represents the at least one computation. ### Claim 20 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; subsequent 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; subsequent to representing the at least one computation as the sequence of operations, translating at least one operation into a global directed acyclic graph that comprises a plurality of vertices that are configured to perform 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; subsequent to translating the at least one operation in the global directed acyclic graph, representing at least one vertex in the global directed acyclic graph as a local directed acyclic graph 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 directed acyclic graph to be executed in a data-driven manner.