High performance method and system for performing fault tolerant matrix multiplication

A computer-implemented method comprising:

• receiving a matrix multiplication task;
• applying a matrix-multiplication algorithm to perform a parallelized computation of said task in multiple stages, using a first set of P hardware processors;
• partitioning said task into a plurality of matrix partitions, wherein a number of said matrix partitions corresponds to said number P;
• during each of said stages of said algorithm:
• (i) distributing, for calculation, said matrix partitions equally among said hardware processors in said first set, and
• (ii) operating a second set of hardware processors to determine and store an error correction code representing said matrix partitions, and
• (iii) upon detecting a fault in said calculation by one or more of said hardware processors in said first set, recovering a result of said calculation using said error correction code;
• and
• determining a result of said task;
• wherein a number of said hardware processors in said second set needed to permit said recovering is no greater than an expected maximal number h of faults in a single stage of said algorithm.

A system comprising:

• at least one hardware processor;
• and
• a non-transitory computer-readable storage medium having stored thereon program instructions, the program instructions executable by the at least one hardware processor to
• receive a linear algebra computational task,
• select a bilinear algorithm to perform a parallelized computation of said task in multiple stages, using a first set of P hardware processors,
• partition said task into a plurality of sub-computations, wherein a number of said sub-computations corresponds to said number P,
• during each of said stages of said algorithm:
• distribute, for calculation, said sub-computations equally among said hardware processors in said first set, and
• (ii) operate a second set of hardware processors to determine and store an error correction code representing a said sub-computations, and
• (iii) upon detecting a fault in said calculation by one or more of said hardware processors in said first set, recover a result of said calculation using said error correction code, and
• determine a result of said task,
• wherein a number of said hardware processors in said second set that is needed to permit said recovering is set between:
• (a) a minimal number equal to a constant value associated with said selected algorithm, multiplied by an expected maximal number h of faults in a single stage of said algorithm, and
• (b) a maximal number equal to a square root of P multiplied by h.

A computer implemented method, comprising:

• receiving a linear algebra computational task;
• selecting a bilinear algorithm to perform a parallelized computation of said task in multiple stages, using a first set of P hardware processors;
• partitioning said task into a plurality of sub-computations, wherein a number of said sub-computations corresponds to said number P;
• during each of said stages of said algorithm:
• (i) distributing, for calculation, said sub-computations equally among said hardware processors in said first set, and
• (ii) operating a second set of hardware processors to determine and store an error correction code representing a said sub-computations, and
• (iii) upon detecting a fault in said calculation by one or more of said hardware processors in said first set, recovering a result of said calculation using said error correction code;
• and
• determining a result of said task;
• wherein a number of said hardware processors in said second set that is needed to permit said recovering is set between:
• (a) a minimal number equal to a constant value associated with said selected algorithm, multiplied by an expected maximal number h of faults in a single stage of said algorithm, and
• (b) a maximal number equal to a square root of P multiplied by h.