Realizing Mathematics of Arrays Operations as Custom Architecture Hardware-Software Co-Design Solutions

2.1. Why a New Theory of Arrays?

Existing array theories and compiler optimizations on array loops, are proper subsets of MoA. All of NumPy’s array and tensor operations can be formulated in MoA. In MoA one algorithm, thus, one circuit, describes the Hadamard Product, Matrix Product, Kronecker Product, and Reductions(Contractions) versus four. Consequently less circuitry, power, and energy.

2.2. The Simplicity of MoA: Shapes and the Psi Function

Scalar operations are at the heart of computation, ${\sigma }_{l}f{\sigma }_r$, and in general for n-d arrays, ${\xi }_{l}f{\xi }_r$, where f is an arbitrary scalar function.

That is, indexing distributes over scalar operations, or in compiler optimization terms, loop fusion.

This means, with an array’s shape, $\rho \xi$, generate an array of indices, $\iota \left(\rho \xi \right)$. Then, using that array as an argument to Psi, the original array ξ, is returned.

2.3. Why MoA Inner and Outer Products?

2.4. Examples: MM, KP and, HP

5.1. Python with NumPy

5.2. MoA Definitions

5.3. Small Example of Psi Reduction to DNF, ONF, and Generic Program

(1)

Psi Reduce to DNF:

(a)

Get the Shape:

$$\rho \left(a{\mathrm{N}\mathrm{P}}_{multiply}b\right){\mathrm{N}\mathrm{P}}_{multiply}b\equiv <22>$$

By definition, shapes must be conformable. So the shape of $\left(a{\mathrm{N}\mathrm{P}}_{multiply}b\right)$ must be equivalent to the shape of b and the shapes of a and b must be the same.

(b)

Get the Components: Here the Psi function is used because layout of the arrays does not matter. Psi Reduction is applied based on the definitions to compose the indices to it’s DNF, or semantic normal form, the least amount of computation AND memory needed to perform the operations. With the shape we have the bounds of indices i and j:

$$\forall i\ni 0\le i<2\mathrm{a}\mathrm{n}\mathrm{d}0\le j<2$$

Now use the Psi function to Psi Reduce to the DNF:

$$\begin{array}{ccc}\hfill <ij>\psi \left(a{\mathrm{N}\mathrm{P}}_{multiply}b\right){\mathrm{N}\mathrm{P}}_{multiply}b& \equiv & (<ij>\psi \left(a{\mathrm{N}\mathrm{P}}_{multiply}b\right))\times (<ij>\psi b)\hfill \\ & \equiv & \left(\right(<ij>\psi a)\times (<ij>\psi b\left)\right)\times (<ij>\psi b)\hfill \\ & \equiv & (<ij>\psi a)\times (<ij>\psi b)\times (<ij>\psi b)\hfill \\ & & \mathrm{T}\mathrm{h}\mathrm{i}\mathrm{s} \mathrm{i}\mathrm{s} \mathrm{t}\mathrm{h}\mathrm{e} \mathrm{D}\mathrm{N}\mathrm{F}\hfill \end{array}$$

(3)

In order to turn the DNF to ONF, layout of the arrays in memory is needed. Assume a and b are layout in row major order. A family of gamma functions, i.e., layout functions that map indices to their offset in memory exist. For this example ${\gamma }_{row}$ is used. Gamma takes an index and a shape.

(2)

Get the ONF:

rav is a function that flattens an array based on layout. Bracket notation is now used to illustrate the building phase of design:

$$(<ij>\psi a)\times (<ij>\psi b)\times (<ij>\psi b)$$

$$\equiv (\mathrm{r}\mathrm{a}\mathrm{v} a)\left[\gamma \right(<i;j>;<22>\left)\right]\times (\mathrm{r}\mathrm{a}\mathrm{v} b)\left[\gamma \right(<i;j>;<22>\left)\right]\times (\mathrm{r}\mathrm{a}\mathrm{v} b)\left[\gamma \right(<i;j>;<22>\left)\right]$$

$$\equiv (\mathrm{r}\mathrm{a}\mathrm{v} a)[j+(2\times i\left)\right]\times (\mathrm{r}\mathrm{a}\mathrm{v} b)\left[\right(j+(2\times i)]\times (\mathrm{r}\mathrm{a}\mathrm{v} b\left)\right[j+(2\times i)]$$

This is the ONF.

$$(@a+j+(2\times i\left)\right)\times (@b+j+(2\times i\left)\right)\times (@b+j+(2\times i\left)\right)$$

(3)

Generic Program:

Finally, using standard notation for the generic program letting C to denote the result, and A and B to denote a and b.

$$\mathbf{C}[j+(2\times i\left)\right]:=\mathbf{A}[j+(2\times i\left)\right]\times \mathbf{B}[j+(2\times i\left)\right]\times \mathbf{B}[j+(2\times i\left)\right]$$

This is the Generic Program and illustrates the process of going from a high level mathematical specification in NumPy formulated in MoA, Psi Reduced to the DNF, ONF and finally to a generic program.

5.4. Returning to the Python Example