Technologies for automatic reordering of sparse matrices

One or more non-transitory machine-readable storage media comprising a plurality of instructions stored thereon that, in response to execution by a computing device, cause the computing device to:

• determine a distributivity of an expression defined in a code region of a program code, wherein the expression is determined to be distributive if semantics of the expression are unaffected by a reordering of an input or output of the expression and wherein the expression is determined to be non-distributive in response to a determination that at least one of (i) the expression requires bitwise reproducibility or (ii) the expression includes a function unknown to a compiler of the computing device;
• determine a liveness of one or more variables in the code region, wherein the liveness of a given variable is indicative of whether the variable is used in a programming point in the program code subsequent to a programming point corresponding to the code region;
• perform inter-dependent array analysis on the expression to determine one or more clusters of inter-dependent arrays of the expression, wherein each array of a cluster of the one or more clusters is inter-dependent on each other array of the cluster and wherein the inter-dependent array analysis is performed in response to a determination that each expression defined in the code region is distributive;
• perform bi-directional data flow analysis on the code region by iterative backward propagation and forward propagation of reorderable arrays through the expressions in the code region based on the one or more clusters of the inter-dependent arrays, wherein the backward propagation is based on a backward transfer function and the forward propagation is based on a forward transfer function and wherein the bi-directional data flow analysis is optimized based on the determined liveness of the one or more variables in the code region;
• and
• transform the program code based on the bi-directional data flow analysis to reorder at least one array.

A computer-implemented method of automatic reordering of sparse matrices, the method comprising:

• determining, by a computing device, a distributivity of an expression defined in a code region of a program code, wherein the expression is determined to be distributive if semantics of the expression are unaffected by a reordering of an input or output of the expression and wherein the expression is determined to be non-distributive in response to a determination that at least one of (i) the expression requires bitwise reproducibility or (ii) the expression includes a function unknown to a compiler of the computing device;
• determining a liveness of one or more variables in the code region, wherein the liveness of a given variable is indicative of whether the variable is used in a programming point in the program code subsequent to a programming point corresponding to the code region;
• performing, by the computing device, inter-dependent array analysis on the expression to determine one or more clusters of inter-dependent arrays of the expression, wherein each array of a cluster of the one or more clusters is inter-dependent on each other array of the cluster and wherein the inter-dependent array analysis is performed in response to a determination that each expression defined in the code region is distributive;
• performing, by the computing device, bi-directional data flow analysis on the code region by iterative backward propagation and forward propagation of reorderable arrays through the expressions in the code region based on the one or more clusters of the inter-dependent arrays, wherein the backward propagation is based on a backward transfer function and the forward propagation is based on a forward transfer function and wherein the bi-directional data flow analysis is optimized based on the determined liveness of the one or more variables in the code region;
• and
• transforming the program code based on the bi-directional data flow analysis to reorder at least one array.