% Created 2024-11-14 Thu 16:19
% Intended LaTeX compiler: pdflatex
\documentclass[dvipsnames,colorlinks,aspectratio=169]{beamer}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{graphicx}
\usepackage{longtable}
\usepackage{wrapfig}
\usepackage{rotating}
\usepackage[normalem]{ulem}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{capt-of}
\usepackage{hyperref}
\usepackage{color}
\usepackage{listings}
\usepackage{pdfpages}
\usepackage{xcolor}
\usepackage{graphicx}
\usepackage{xspace}
\usepackage{siunitx}
\usepackage{libertine}
\usepackage{fontawesome}
\mode<beamer>{\usetheme{Boadilla}}
\setbeamertemplate{navigation symbols}{}
\setbeamerfont{alerted text}{series=\bfseries}
\setbeamercolor{alerted text}{fg=blue}
\usecolortheme{default}
\usefonttheme{serif}
\usefonttheme{professionalfonts}
\usetheme{default}
\author{Brett Viren}
\date{\today}
\title{Sparse arrays for 3D sim}
\hypersetup{
 pdfauthor={Brett Viren},
 pdftitle={Sparse arrays for 3D sim},
 pdfkeywords={},
 pdfsubject={},
 pdfcreator={Emacs 28.2 (Org mode 9.7-pre)}, 
 pdflang={English}}
\begin{document}

\maketitle
\begin{frame}[label={sec:org3c073f2},shrink=10]{Problem reminder}
Calculate the \emph{measure} of a \emph{signal} observed through some \emph{response} operation:

\[M = R \circ S\]

We model \(R\) is a set of field responses giving the induced current at equal
time steps along a family of paths that begin on a sub-pixel 2D grid of \emph{impact
positions} that span each of a 2D grid of pixels.  The measurement is a sum over
the impact positions and the operation becomes a \emph{partitioned convolution}:

\[M = \sum_p R_p*S_p\]

Where:

\begin{itemize}
\item All arrays are 3D: 1D ticks \texttimes{} 2D pixels.
\item \(p \in 10 \times 10 = 100\) selects the rows in \(R\) or \(S\) that correspond to a common (relative) \emph{impact position} across the pixels.
\item \(S_p\) is shaped (ticks \(\times\) pixels) of about \(10,000 \times 100 \times 100 = 10^8\) elements
\item \(R_p\) is shaped \(1000 \times 5 \times 5 = 2.5\times10^4\) elements
\end{itemize}
\end{frame}
\begin{frame}[label={sec:org3c673d5}]{Strategy - exploit sparseness of signal}
\(S_p\) is sparse, and we should (must) exploit that.  Two basic strategies:

\begin{enumerate}
\item Apply \(R_p * S_p\) convolution to \alert{sparse array} representations.

\item Chunk \(S_p\), ignore empty chunks, solve the rest densely, stitch the per-chunk solutions.
\end{enumerate}

Here, we consider the implications of strategy 1.
\end{frame}
\begin{frame}[label={sec:orgbc8947d},fragile,shrink=10]{Sparse arrays}
 \begin{block}{Several ways to represent \alert{2D arrays} sparsely}
\begin{description}
\item[{COO}] coordinate, list of \texttt{(row,col,val)}
\item[{CSR}] compressed sparse row, lists: \texttt{row\_extens, col\_indices, values}
\item[{CSC}] transpose of CSR
\item[{BSR}] block-sparse row, common-sized blocks and their locations
\item[{DIA}] diagonal storage, list of block-diagonal dense matrices
\item[{DOK}] dictionary of keys, \texttt{(row,col)->val}
\item[{LIL}] list-of-lists, list of rows, row is list of \texttt{(col,val)}
\end{description}
Different formats have different speed/memory depending on nature of sparseness.
\end{block}
\begin{block}{Different array dimensionality}
The formats defined in terms of 2D, extension possible, but not common in practice.
\begin{itemize}
\item Numpy/SciPY, CuPY and Torch support most of these formats for 2D.
\begin{itemize}
\item CuPY sparse arrays are built from initial SciPY arrays
\end{itemize}
\item Only Torch supports 3D sparse arrays.
\end{itemize}
\end{block}
\end{frame}
\begin{frame}[label={sec:org8b1e726}]{Library support for sparse convolution}
To best I can find, there is only support for 2D.
\begin{itemize}
\item That is either in ``experimental'' modules or NN-related (or both).
\end{itemize}
\end{frame}
\begin{frame}[label={sec:orga1627e5}]{Direct, interval-space sparse convolution}
We may implement convolution on sparse N-D array ``by hand''

\begin{itemize}
\item Exhaustive looping is far too slow.

\item Parallelism subject to the many-to-many accumulation problem.
\end{itemize}
\end{frame}
\begin{frame}[label={sec:orgbab4c87}]{Convolution matrix representation}
2D convolution can be converted to matrix-vector multiplication

\[B = K*A \to \vec{b} = M_k\cdot\vec{a}\]

With:

\begin{itemize}
\item \emph{Unrolled} 2D arrays \(\to\) 1D vectors \(A \to \vec{a},\ B \to \vec{b}\) of sizes \(n_a,\ n_b\), respectively.
\item Transform the kernel array to a matrix \(K \to M_k\) of shape \((n_b, n_a)\)
\end{itemize}

The \(M_k\) is sparse matrix, each row has all the rows of \(K\) placed in according to how that row transforms \(\vec{a}\) into one element of \(\vec{b}\) through the elements of \(K\).

See section 4.1 of \url{https://arxiv.org/abs/1603.07285} for nice example.

We can now contemplate performing \(M_k\cdot\vec{a}\) via sparse matrix-vector multiply.
\end{frame}
\begin{frame}[label={sec:orgaa77946}]{Sparse matrix-vector multiply}
\[\vec{b} = M\cdot\vec{a}\]

Mathematically, either or both of \(M\) and \(\vec{a}\) may be sparse.
\begin{itemize}
\item No GPU library supports having both sparse.
\item Oddly, SciPy supports only (csc)\(\cdot\)(csr) and (dia)\(\cdot\)(dok)
\end{itemize}

So, in practice we may only pick one as sparse.  For our problem:

\begin{itemize}
\item \(\vec{a}\) is size \(10^8\) with small but hard to estimate density.
\item \(M_k\) is shape \((10^8,10^8)\) with density \(2.5\times 10^4/10^8 = 0.025\%\)
\end{itemize}

\(M_k\) is impossible to have dense in any case so we must require \(\vec{a}\) to be dense.
\end{frame}
\begin{frame}[label={sec:orgfd9bf34},shrink=10]{Scaling of timing}
\begin{block}{Method}
Dense matrix-vector multiply of dimension size N scales as \(\mathcal{O}(N^2)\)
\begin{itemize}
\item Perform sparse and dense matrix multiply timings at \(N=10^5\).
\begin{itemize}
\item Take best time over supported sparse formats
\end{itemize}
\item Scale by \(N^2\) from \(10^5 \to 10^8\).
\begin{itemize}
\item Caveat: the actual sparse scaling is unknown (by me).
\end{itemize}
\item Check density \(2.5\times 10^{-4}\) which and more dense \(2.5\times 10^{-3}\)
\end{itemize}
\end{block}
\begin{block}{Results at density \(2.5\times 10^{-4}\)}
\begin{center}
\begin{tabular}{llrrll}
library & device & dense (s) & sparse (s) & dense \(10^8\) & sparse \(10^8\)\\
\hline
scipy & CPU & 0.5 & 0.2 & 5.8 days & 2.3 days\\
torch & CPU & 0.6 & 0.03 & 6.9 days & 8.3 hours\\
torch & GPU & 0.003 & 0.001 & 50 minutes & 17 minutes\\
cupy & GPU & 0.003 & 0.004 & 50 minutes & 67 minutes\\
\end{tabular}
\end{center}

The artificially denser \(2.5\times 10^{-3}\) is a few to \(10\times\) slower.
\end{block}
\end{frame}
\begin{frame}[label={sec:orgff3582f}]{Conclusions}
\begin{itemize}
\item Novel development needed to support 3D sparse array data type.
\begin{itemize}
\item Unless PyTorch used.
\end{itemize}
\item Novel development needed to support 3D sparse convolution.
\item Sparse convolution-matrix method is untenable even with GPU.
\item Computation time increases with density (unsurprising).
\end{itemize}

\begin{center}
Sparse array approach is not worth pursuing.
\end{center}
\end{frame}
\end{document}
