morgue.tex

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%  BEWARE Dead Code Ahead!     %%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Morgue: Future Writing}

\subsubsection{Variants to Measure}
\hrl{We perhaps want to select some problems with ground truth so that we can have the actual error.}
Here are the combinations of settings that should actually be measured.


Everything after this line is a draft:



\subsubsection{Variations}
    Also include SpMV transpose.

    Mention $A=A^T$, possible additional optimizations,
    including``Fast Bilinear Algorithms for Symmetric Tensor 
    Contractions'', E. Solomonik, J. Demmel, Computational Methods
    in Applied Mathematics, Feb 2020.
    \newline
    https://doi.org/10.1515/cmam-2019-0075



\subsection{Iterative (Jacobi? PCG?) Solve}
	Input (Stage 1):
		Matrix given (e.g. “Boeing/ct20stif” or power-law graph laplacian)
	Input (Stage 2):
		Vector (e.g. uniform random dense vector)
	Compute:
		$y_j = A_ij * x_j$
	Timings:
Report time start stage 1 to start stage 2
Report time start stage 2 to end
Report aggregate time
Some combination of:
1. Allow reorganization of algorithm up to equivalence under arbitrary semirings (treat unsupported functions as uninterpreted) (e.g. thou shalt not do Strassen)
2. Allow reorganization of algorithm up to equivalence under infinite precision
2.5 (2 and 3)
3. Anything you want up to declared empirical accuracy
If algorithm is iterative, run steps until tolerance
If algorithm is non-iterative, report achieved empirical accuracy compared to double.

For SpMV, we compare to the naive implementation and take the L2-norm of the residual. 




\subsection{SpMSpV}
``Sparse-Sparse Matrix-Vector Multiply'' i.e. the matrices and vectors are all sparse.
$$y_i += A_{i,j} * x_j$$

\subsection{SpMM (SpGEMM?)}
	Input (Stage 1):
		Matrix
	Input (Stage 2):
		Vector
	Compute:
		$y_ij = A_ik * x_kj$
	Timings:
Report time start stage 1 to start stage 2
Report time start stage 2 to end
Report aggregate time

SpGEMM from multi-source BFS:
	Computation: Compute BFS parents starting from a particular set of vertices.
	Distribution: If the graph is fixed, you can precompute the BFS parents (not interesting). Thus, this problem is only well-posed on graph generators. I’m not sure if the set of vertices matters, could pick randomly.

SpGEMM from setup phase of algebraic multigrid:
	Computation: Compute $R_lA_lP_L$ as described in \url{https://doi.org/10.1145/3571157}.
	Distribution: matrices described in \url{https://doi.org/10.1145/3571157}
SpGEMM with various levels of size prediction difficulty and output reuse:
	Computation: Compute C = A*B
	Distribution: Generate A and B (using RMAT, perhaps?) so that expected number of nonzeros in A and B remain fixed but expected number of nonzeros in C can be very high, very low, or highly variable

\subsection{ATA}

\subsection{MTTKRP}
	Computation: A single MTTKRP 
	Distribution: The dense matrices are random, but the tensor can be fixed or random.


\subsection{Candecomp (deprecated)}
	Computation: Some fixed number of MTTKRPs of the same tensor in alternating transposition orders on the same factor matrices
	Distribution: The tensor can be fixed or random here as well.
Stencil (Same as SpMV, but matrix is a stencil)
	Computation: SpMV or Congugate gradient
	Distribution: Matrix is a toeplitz matrix for a particular stencil, vector is random

\subsection{FFT (deprecated)}
	Computation: SpMV
	Distribution: Matrix is an FFT matrix, vector is random

\subsection{Dynamic PageRank (deprecated)}
	Computation: Compute Pagerank of a matrix
	Stage 1.
		The first (n - d) rows and columns of a matrix are given
	Stage 2.
		The final d rows and columns are given
	Computation:
		Do 20 iterations of pagerank
	Notes: This incentivizes the implementation to use the first portion of the matrix to accelerate the computation in stage 2.
(Gilbert: This is just a power iteration? Willow: It is. I was trying to emphasize the dynamic graph kernel problem, where updates to a graph are received in real time and we are trying to maintain some statistics on the graph as the updates come in. Gilbert: I'm not sure page-rank or similar are incrementalized in practice?  Maybe.  Maybe worth considering social network clustering algorithms here instead?)

\subsection{Quantum Circuits (Deprecated)}
	Computation: Compute the distribution of the quantum circuits outputs
	Distribution: 1 Tensor for each circuit element (10s-100s total)
Transformer Model:
	Computation: Compute the output of a single encoder block in a transformer model with k attention heads
	Distribution: Randomly initialized weights with some sparsification algorithm applied
 
 \begin{align*}
Q[S, E, K] &= \sum_C(I[S, C] * WQ[C, E, K])\\
K[S, E, K] &= \sum_C(I[S, C] * WK[C, E, K])\\
V[S, E, K] &= \sum_C(I[S, C] * WV[C, E, K])\\
AP[S, S’, K] &= \sum_E(Q[S, E, K] * K[S’, E, K]) / 8\\
Z[S, E, K] &= \sum_S’(Sigmoid(AP[S,S’,K]) * V[S’, E, K])\\
CZ[S, E] &= \sum_k(Z[S, E, K] * WZ[K,E])\\
FF[S,FF] &= Relu(CZ[S,E] * WFF1[E,FF])\\
O[S,E] &= Relu(FF[S,FF] * WFF2[FF,E])\\
\end{align*}

\subsection{CountSat (Deprecated?)}
	Computation: Compute the number of satisfying solutions for a sat problem. This is a tensor contraction along each variable of the product of all clause tensors according to matching variables.
	Distribution: Randomly generated sat clauses with variables of length 3-10 (Existing Sat datasets? Are random sat problems unsatisfiable w.h.p.?)

\subsection{Graph Neural Networks (TODO)}
	Computation: Compute one iteration of message passing
	Distribution: Random graph models, random sparsified weights

% WX, BX is a simple affine transform, but it could be NN layers instead
$NeighborMessages[u, v, k’] = A[u, v]*(Sum_k(X[v, k]*WX[k, k’]) +BX[k’])  $

$AggNeighborMessages[u, k’] = Sum_v(NeighborMessage[u, v, k’])$

% This could also be a neural network
$NewX[u, k] = softmax_k(WX’[u,k](X[u, k] +AggNeighborMessages[u,k]) + BX’[k]) $

\subsection{SubGraph Counting (Deprecated?)}
	Computation: Compute the number of subgraphs of a particular kind (triangle, flower, petal, etc.)
	Distribution: Random graph models, directed vs undirected subvariants


\subsection{Quantum Chemistry Stuff}
Oh cool, quantum chemistry stuff!

\subsection{Morgue from Earlier Notes}

Produce a List of all Computation Kernels (Acronyms \& Definitions)
SpMV? SpMM? SpDM3? SpMSpV? SPGEMM? SpLU? SpTRSV/M?

SpMV:
	“Sparse Matrix-Vector Multiply”
Dense x,y, Sparse A
y[i] += A[i, j] * x[j]
SpMSpV:
	“Sparse-Sparse Matrix-Vector Multiply”
Sparse A, x, y
y[i] += A[i, j] * x[j]
SpGEMM:
	“Sparse-Sparse Matrix Multiply”
Sparse C, A, B, often all matrices are square
C[i, j] += A[i, k] * B[k, j]
Masked SpGEMM:
	Sparse (sometimes Boolean) S, C, Sparse A, B
C[i, j] += S[i, j] * A[i, k] * B[k, j]
SDDMM:
	“Sampled Dense Dense Matrix Multiply”
	Sparse (sometimes Boolean) S, C, Dense A, B
C[i, j] += S[i, j] * A[i, k] * B[k, j]

SpMM:
	“Sparse Matrix Multiply”
Dense C, B, Sparse A, often J small constant
C[i, j] += A[i, k] * B[k, j]

MTTKRP:
	“Matricized Tensor Times Khatri-Rao Product”
Sparse B, Dense A, C, D
A[i, j] += B[i, k, l] * C[k, j] * D[l, j]
SpTTM:
	“Sparse Tensor Times Matrix”
Sparse A, B, Dense C, usually K >> L or L >> K
A[i, j, k] += B[i, j, l] * C[k, l]
SpMTTKRP:
Sparse A, B, C, D
A[i, j] += B[i, k, l] * C[k, j] * D[l, j]
SpLU:
	“Sparse LU Factorization”
Sparse A, produce permutations P, Q, sparse lower triangular L, and sparse upper triangular U
such that PAQ=LU
SpTRSV:
	“Sparse Triangular Solve”
	Sparse triangular matrix A, dense vector y, produce dense vector x such that Ax = y
SpTRSM:
	Sparse triangular matrix A, dense matrix Y, produce dense matrix X such that AX = Y

Willow: I’ve taken a stab at listing some kernel definitions. One might group them broadly by:
	1 argument sparse: SpMV, SpMM, SDDMM,MTTKRP, SpTTM
	2+ argument sparse: SpGEMM, SpMSpV, SpMTTKRP
	Loop carry dependency: SpLU, SpTRSV, SpTRSM

%comment: Here is a copy of the call for comments on this benchmark suite, perhaps we can work it into a motivation section above
%Goals the the benchmark suite:
%To discover the best possible approach
%A well-specified benchmark suite that specifies all relevant aspects of problem setup and measurement to facilitate meaningful comparison
%To provide a complete set of problems and data that exercise all important phenomena of sparse kernels and all realistic applications of sparse kernels.
%Ease of use and encouraging participation across a wide variety of participants, from tensor compiler writers targeting many kernels to hardware developers of a single kernel
	
%Why bother doing this?
%We are providing specifications for repeatable benchmarking, accuracy under reduced precision or semirings, and accounting for preprocessing time. 

%Some other people have created tensor benchmarks: PASTA, GAP, Sparsebench
%Why aren’t these sufficient?
%Well, the people on this project haven’t found them sufficient for the papers they published recently (or did they not even try?)
%PASTA doesn’t have a big enough variety of tensors
%All existing benchmarks only provide a single (sparse) matrix or tensor, but most real problems require more than one input.
%Most sparse benchmarks are focused on providing example data to the detriment of specifying computations and measurements
%Sparse problems are highly dependent on format/data-structure choices and/or preprocessing.  (maybe talk about measures instead?)
%Existing benchmarks 
%Current benchmarks do not collect and archive community progress on key problems.
%Are the problems in current benchmarks bullshit problems that no-one really cares about?  (Are ours?)
%The existing datasets are very good for certain sparse applications, but the variety of applications and approaches today are not well represented.
%List of specific, surprising, deficiencies
%There is not sufficient focus on exploring theoretical limits???
%We have an intellectual interest in the best real-world solutions with architectures that exist today.
%The dense world has a roofline model, it implies a certain workflow for crafting dense kernels and focuses development. The sparse world has no model, we don’t know when to stop optimizing. 
%What are the key problems that distill the essence of what “sparse linear/tensor algebra” is about?

%This will benefit the community because it will make it easier to measure progress by having common benchmarks for projects and papers.

%Our benchmark will include a few key features to support our goals: 
%We’re interested in a broad set of benchmarks; our initial kernels include SpMV, SpMM, SpGEMM, SpMTTKRP, Iterative Solvers, Subgraph Counting, and more!
%We will distribute simple, scalable reference implementations for our broad catalog of kernels. We will also include convenient code to generate inputs and compare against the reference.
%We will curate the results online and provide performance metrics that can be used to assess fractions of peak, such as best-known modeled data movement, matrix partitions, and more!

%We have developed this benchmark suite to encourage meaningful comparison among the varieties of solutions, including considerations for different hardware, compiler-based approaches, and multiple languages.


%\hrl{A bit unsure what kind of tensor generator we are looking into, maybe reference? Kernelized generator with pre-specified interactions for big tensor seems to be an open problem, like https://proceedings.mlr.press/v206/wesel23a.html.}