\section{Polynomial time exact algorithm for fixed number of block levels: Proof of theorem \ref{thm:reverse}  }
There exists a dynamic program algorithm to solve the {\DOPT} problem that runs in time
$O(n^{3+m})$ for m block levels.

The dynamic program algorithm(Algorithm~\ref{algo:doptdualDP}) is similar to that for the exact algorithm (Algorithm~\ref{algo:doptDP}) 
with the main difference being that instead of iterating over lengths we iterate over the decode times of the tree.

Let $\dual(i,\lvl,T)$ denote the minimum codelength amongst all forests rooted at level $\lvl$,
having $i$ internal nodes with decode time at most $T$. Also, define ${\cal T}=\sum\limits_{c=1}^{n}\cdot  \sum\limits_{i=1}^{m}q_i$ 
(here, the decode time of the forest is the sum of the decode times of the trees in the forest)

For a fixed number of block levels, $m$, the following lemma holds:
\begin{lemma}\label{seq_of_xi}
The number of possible values of decode time contribution of a structure $T$ are $n^m$.
\end{lemma}
\begin{proof}
Let there be $x_i$ characters in the $i$th block level $\forall i\in[1,m]$ and $x_0$ be the number of characters which are not present in the forest corresponding to $\dual(i,\lvl,T)$. These characters corresponding to $x_0$ will not have any decode time contribution for $T$. We have $\sum_{i=0}^{m} x_i = n$. There are $O(n^m)$ possible sequences of $x_i$'s satisfying this. For each sequence of $x_i$'s, we can uniquely determine the decode time value. Hence there are $O(n^m)$ possible decode time values.
\end{proof}

A dynamic program using the above recurrence can be designed as follows:

{\em Base Case:}
For all forests with no merges, i.e. no internal nodes, we initialize the decode time to $0$, i.e.,
$$ \forall ~\lvl \in [0,n] ~and ~T\in[0,{\cal T}]:~~\dual(0,\lvl,T)=0$$

{\em Inductive Case:}
To compute $\dual(i,\lvl,T)$, we iterate over the number of internal nodes that are at depth strictly greater than $\lvl$.
If $j$ internal nodes are at depth strictly greater than $\lvl$, then there are $(2i-j)$ characters at depth strictly greater than $\lvl$, then $q_{\lvl+1}\cdot P_{2i-j}$ is the decode-time contribution
of all the characters having level $>\lvl$, due to the access at level $(\lvl+1)$. 
Furthermore, $\dual(j,\lvl+1,T')$ denotes the decode time contributed by all accesses made at depths greater than $\lvl+1$. 
This yields the following recurrence:
\begin{eqnarray}
\label{eq:recA}
\\\dual(i,\lvl,T) =  \min_{j \in [max(0,2i-n),i-1]} \left\{ \dual(j,\lvl+1,T')  +  P_{2\cdot i-j} \right\} & &
\end{eqnarray}
where $T' = T - \hat{q}_{lvl+1}\cdot P_{2\cdot i-j} $. We only need to recursively check if $T'>0$. The tree with the optimal decode time can be obtained by maintaining the parent pointers of each update and then backtracking.

Note that we only update entries of $\dual$ for which the $T$ parameter corresponds to a sequence of  $<$ $x_0,x_1,x_2,\ldots,x_m$ $>$, from lemma \ref{seq_of_xi}.
The decode time for a sequence $<$ $x_0,x_1,x_2,\ldots,x_m$ $>$ is $Dec(<x_i>)= \sum_{i=1}^{m} x_i\cdot \hat{q}_i$

It is easy to see that the $T$ parameter will take on only $O(n^m)$ values. 
The table can accordingly be compressed and maintained only for these entries,
however we omit these implementation details in the interest of better exposition.

After the DP is filled, we check all the entries of the form $\dual(n-1,0,.)$ which have length less than $\ell$ and find the the optimal decode corresponding to it.






{\em Time complexity}: We note that $i$ and $\ell$ can take $n$ possible values each and $T$ takes $n^m$ possible values.
So, there are $n^{m+2}$ cells in the DP. Each cell can be filled in at most $O(n)$ time. So, the time complexity of the DP is $O(n^{m+3})$. Checking the DP table to find the optimal decode time will take $O(n^{m+1})$ time. 
Hence, we can solve the $DOPT$ problem in $O(n^{m+3})$ time when the number of block levels is a constant $m$.

\begin{algorithm}[t!]
\DontPrintSemicolon
\KwIn{Alphabet $\alphabet=\{c_1, c_2, \ldots, c_n\}$; with $frequencies=\{f_1, f_2, \ldots, f_n\}$;}
\KwOut{Minimum possible decode time ${\cal T}$}
\For{ $\lvl \gets 0 ~\textbf{to}~ n$}{
    \For{\textbf{all} sequence $<x_i>$ satisfying Lemma~\ref{seq_of_xi}}{
        $T \gets Dec(<x_i>) $\\
        $\dual(0,\lvl,T):=0$        
    }
}
\For{$i \gets ~1~\textbf{to}~(n-1)$}{
    \For{$\lvl \gets (n-1) ~\textbf{downto}~ 0$ }{
        \For{\textbf{all} sequence $<x_i>$ satisfying lemma~\ref{seq_of_xi}}{
            $bestLen:=\infty $;\\
            $T \gets Dec(<x_i>) $\\
            \For{$j \gets \max(0,2 i-n) ~\textbf{to}~i-1$}{    
                $codLen:= \infty $\\
                $T' = T - \hat{q}_{lvl+1}\cdot P_{2i-j}$\\
                \uIf{$0\leq L'$}{$codLen:=\dual(j,\lvl+1,T')+ P_{2 i-j}$}
                
                \uIf{$codLen < bestLen $}{
                    $bestLen:=codLen$
                }
            }
            $\dual(i,\lvl,T):=bestLen$
        }
    }
}
$minCodeLength=\min_{t}(\dual(n-1,0,t))$\\
\uIf{$minCodeLength>{\cal L}$}{
    \Return{"No Valid Tree"}
}
\Return{$\argmin_{t}(\dual(n-1,0,t)\leq {\cal L})$};
\caption{Exact algorithm for $DOPT$ with constant number of block levels}
\label{algo:doptdualDP}
\end{algorithm}
\section{An exact DP (ALG1): Proof of Theorem~\ref{thm:exact}}
We start with a simple proposition.
\begin{proposition}
A character having higher frequency will appear at the same or lower level
(that is  closer to the root) than a character having lower frequency.
\end{proposition}
The proposition is easy to verify - if this was not true, one could simply swap
the two characters thereby improving the code length as well as the decode time.

A key aspect of the dynamic program for minimizing the codelength presented in the previous section
is that for a prefix tree of height $h$, the codelength could be represented as sum of $h$ prefix-sums 
where each prefix-sum represents the codelength contribution by the corresponding level. 
We will now show that the decode time can also be written as a sum of $h$ terms, 
where each term corresponds to the decode time contribution by the corresponding level in the tree, 
i.e. the codelength contribution multiplied by the access cost at that level. 
This result is captured in Lemma~\ref{lem:dectime}.
For this, we shall associate cost, $\hat{q}_i$ with a level $i$ in the tree as follows: if the level $i$ corresponds to
the first (top) level of block $j$, then we take $\hat{q}_i = q_j$, else we take $\hat{q}_i = 0$.
Note that if $h$ represents the total height of the tree.
\begin{lemma}
\label{lem:dectime}
$$\Delta(T) = \sum_{\lvl=0}^{h-1} \hat{q}_{\lvl+1}\cdot (P_{2 i_\lvl - i_{\lvl+1}})$$
\end{lemma}
\begin{proof}

By definition of $\cost(T)$ and $\cost_T(c)$ (Eqn~\ref{def:costchar} and \ref{def:costtree}) we have
\begin{eqnarray*}
\cost(T) & = & \sum_{c \in \alphabet} \left( \freq(c) \cdot (\cost_T(c)) \right) \\
& = & \sum_{c \in \alphabet}  \left( \freq(c) \cdot \left(\sum_{i \le \bdT(c)} q_i \right) \right)
\end{eqnarray*}
By using the definition of $\hat{q}_i$ we get
$$\cost(T)=\sum_{c \in \alphabet} \left( \freq(c) \cdot \left(\sum_{i \le \dT(c)} \hat{q}_i \right) \right)$$
By rearranging the summation over each level and using proposition 2.1 we get
$$\cost(T)=\sum_{\lvl=0}^{h-1} \left( \hat{q}_{\lvl+1} \cdot \sum_{j=1}^{2 i_\lvl - i_{\lvl+1}}f_j \right)$$
and using Theorem~\ref{prefixtree} we get
$$\cost(T)=\sum_{\lvl=0}^{h-1} \hat{q}_{\lvl+1} \cdot P_{2 i_\lvl - i_{\lvl+1}}$$

This completes the proof of the Lemma.
\end{proof}

Thus, it remains to find a sequence of $i_l$'s as before except that now the goal is to minimize the
decode-time, $\Delta(T)$, of the tree. We describe a recurrence to obtain such a sequence.
Let $D(i,\lvl,L)$ denote the minimum decode time amongst all forests rooted at level $\lvl$,
having $i$ internal nodes with codelength at most $L$ 
(here, the codelength of the forest is the sum of the codelengths of the trees in the forest).

A dynamic program using the above recurrence can be designed as follows. 
Let $h$ be some upper bound on the height of the optimal prefix tree.

{\em Base Case:}
For all forests with no internal nodes, we initialize the decode time to $0$, i.e.,
$$ \forall ~\lvl \in [0,h] ~and ~L\in[0,{\cal L}]:~~D(0,\lvl,L)=0$$

{\em Inductive Case:}
To compute $D(i,\lvl,L)$, we iterate over the number of internal nodes that are at depths strictly greater than $\lvl$.
If $j$ internal nodes are at depths strictly greater than $\lvl$, 
then there are $(2i-j)$ characters at depths strictly greater than $\lvl$ and 
$\hat{q}_{\lvl+1}\cdot P_{2i-j}$ is the decode-time contribution
of all the characters having level(depth) $>\lvl$, due to the access at level $(\lvl+1)$.
Furthermore, $D(j,\lvl+1,L')$ denotes the decode time contributed by all accesses made at depths greater than $\lvl+1$. 
This yields the following recurrence:
\begin{eqnarray}
\label{eq:rec0}
D(i,\lvl,L) = \min_{j \in [max(0,2i-n),i-1]} \left\{ D(j,\lvl+1,L')  + \hat{q}_{\lvl+1}\cdot P_{2 i-j} \right\} & &
\end{eqnarray}
where $L' = L - P_{2i-j}$. We only need to recurse if $L'>0$. The tree with the optimal decode time can be obtained by maintaining the parent pointers of each update and backtracking.

{\em Time complexity: }
There are $h$ levels, $O(n)$ characters and $O({\cal L})$ values for code length;
hence there are $O(nh {\cal L})$ cells in the table. Each cell can be filled in $O(n)$ time.
Hence the time complexity is $O(n^2 h {\cal L})$.
Taking the upper bound for the height, $h$, as $n$, we get the time complexity to be $O(n^3 {\cal L})$.
As ${\cal L}$ may not be polynomial in $n$, this is a pseudo-polynomial time algorithm.

\begin{algorithm}[t!]
\DontPrintSemicolon
\KwIn{Alphabet $\alphabet=\{c_1, c_2, \ldots, c_n\}$; with $frequencies=\{f_1, f_2, \ldots, f_n\}$; Codelength Restriction ${\cal L}$}
\KwOut{Minimum Decode Time among trees having codelength less than ${\cal L}$}
\For{$\lvl \gets 0 ~\textbf{to}~ h$ }{
    \For{$L \gets 0 ~\textbf{to}~ {\cal L}$ }{
        $D(0,\lvl,L):=0$        
    }
}
\For{$i \gets ~1~\textbf{to}~(n-1)$}{
    \For{$\lvl \gets (h-1) ~\textbf{downto}~ 0$ }{
        \For{$L \gets 0 ~\textbf{to}~ {\cal L}$ }{
            $bestTime:=\infty $;\\
            \For{$j \gets \max(0,2i-n) ~\textbf{to} ~i-1$}{    
                $decTime:= \infty $\\
                $L' = L - P_{2i-j}$\\
                \uIf{$0\leq L'$}{$decTime:=D(j,\lvl+1,L')+\hat{q}_{(l+1)}\cdot P_{2 i-j}$}
                
                \uIf{$decTime < bestTime $}{
                    $bestTime:=decTime$
                }
            }
            $D(i,\lvl,L):=bestTime$
        }
    }
}
\Return{$D(n-1,0,{\cal L})$};
\caption{Exact algorithm}
\label{algo:doptDP}
\label{alg:exact}
\end{algorithm}

In practice, the number of block levels, $m$ in the blocking scheme is often a constant.
A slight modification of our dynamic program can solve the problem exactly for this case in strongly polynomial time.
The proof is deferred to the appendix.
\begin{theorem}
\label{thm:reverse}
There exists a dynamic program algorithm to solve the ${\DOPT}({\cal L})$ problem that runs in time
$O(n^{3+m})$ for $m$ block levels.
\end{theorem}

\section{Preliminaries: a DP for Huffman codes}
Our algorithm builds on the dynamic program for Huffman codes proposed by Larmore and Przytycka\cite{parallelhuffman}.
This dynamic program was proposed to provide a more efficient parallel implementation; 
though it is an $O(n^2)$ algorithm in the sequential setting, it runs in $O(\log n)$ time in the PRAM model.

\begin{figure}
    \centering
    \includegraphics[width=3.5in]{golin.pdf}
    \caption{Illustration of the calculation of the number of characters below level $\lvl$ ($2i_\lvl - i_{\lvl+1}$). 
    This figure is taken from \cite{golin}.}
    \label{fig:golin_example}
\end{figure}


Consider a prefix tree, $T$. The nodes of $T$ can be classified as either leaf nodes (i.e.,
nodes with no child nodes), or internal nodes (i.e., nodes with exactly $2$ child nodes).
Leaf nodes represent characters of the alphabet.
Let $\dT(u)$ denote the depth of any node in the tree, $T$ (with the root being at depth $0$). 
The depth (or height) of the tree, denoted $h(T)$ is the maximum depth of any node in the tree, i.e.,
$h(T) = \max_{u \in T} \{ \dT(u) \}$.
We use the variable $\lvl$ to refer to the level starting from the top of the tree ($\lvl=0$ for the root).
Further, let $i_\lvl$ denote the number of internal nodes at or deeper than level $\lvl$.
This is illustrated in Figure~\ref{fig:golin_example}.

The following proposition relates the number of characters below some level with the number of internal nodes
at different levels.
\begin{proposition}
The number of characters below (deeper than) level $\lvl$ is $2i_\lvl - i_{\lvl+1}$.
\end{proposition}
The formal proof of the proposition can be found in \cite{golin}.
The intuitive idea is as follows:
to form each internal node we need two child nodes (can be either internal or leaf). 
Hence, for $i_\lvl$ internal nodes we would require $2 i_\lvl$ nodes at or deeper than level $(\lvl+1)$.
Since of these $2 i_\lvl$ nodes $i_{\lvl+1}$ are internal nodes at or deeper than level $(\lvl+1)$, 
the number of characters or leaf nodes below level $\lvl$ must be $2 i_\lvl - i_{\lvl+1}$.

The following result from Golin and Zhang\cite{golin} specifies a condition for us to be able to 
construct a valid prefix tree.
The proof can be found in \cite{golin}.
\begin{theorem}
\label{valid}
Given a decreasing sequence of integers, 
$<$$i_0=n-1,i_1,\ldots,i_h=0$$> \ \ $, such that 
$\forall \lvl \le h-1, \\ 2 i_\lvl - i_{\lvl+1} \leq n $, 
it is possible to construct a prefix tree of height $h$ such that the number of internal nodes
at or below level $\lvl$ is $i_\lvl$.
\end{theorem}
Lastly, the following result from Golin and Zhang\cite{golin} helps us to rewrite the 
codelength of the code represented by a prefix tree as the sum of contributions of prefix sums at each level.
\begin{theorem}\label{prefixtree}
Let $P$ be prefix sum array of frequencies $P_i=\sum_{j=1}^{i}f_j$, where frequencies are sorted in increasing order
of the depths of the characters in the tree $T$. 
Then the codelength of the tree, $T$, can be written as a sum of $h$ prefix sums, 
where each sum represents the codelength contribution by each level of the tree, i.e.,
$$ len(T)= \sum_{\lvl=0}^{h-1}P_{2 i_\lvl - i_{\lvl+1}}.$$
\end{theorem}
The formal proof can be found in \cite{golin}. The intuitive idea is as follows:
by the definitions of $len(T)$ and $\dT(c)$ (Eqn~\ref{def:len} and \ref{def:costchar}), we have
$$ len(T)=\sum_{c \in \alphabet} \freq(c) \cdot \dT(c) = \sum_{c \in \alphabet} \sum_{\lvl=1}^{\dT(c)} \freq(c)$$
By rearranging the summation over each level and using proposition 1, we get
$$ len(T)=\sum_{\lvl=0}^{h-1} \sum_{j=1}^{2 i_\lvl - i_{\lvl+1}}f_j$$
and viewing the inner sum as prefix sum, we get
$$ len(T) = \sum_{\lvl=0}^{h-1}P_{2 i_\lvl - i_{\lvl+1}}$$


The goal of Golin and Zhang\cite{golin} is to determine a prefix tree, $T$, for which the codelength, i.e., $len(T)$ is minimum.
The idea of their dynamic program is as follows.
Let $H(i)$ denote the minimum codelength amongst all forests having exactly $i$ internal nodes.  
Then $H(n-1)$ yields the optimal codelength.
As mentioned in theorem \ref{valid}, it suffices to obtain a sequence of $i_\lvl$'s to determine the prefix tree.
Suppose that $i_\lvl=i$ and $i_{\lvl+1}=j$, then it is straightforward to see that
$H(i) = H(j) + P_{2 i-j}$. This allows us to design the
following recurrence to determine optimal values of $i_\lvl$'s:
$$H(i) = \min_{j \in [max(0,2i-n),i-1]} H(j) + P_{2 i-j}$$
Here, $H(0)$ and $P_0$ are initialized to $0$.

{\em Time complexity:}
As there are $n$ entries of $H$ and each entry requires $O(n)$ computations to compare the recurrences, 
the algorithm takes $O(n^2)$ time.

\begin{algorithm}[t!]
\DontPrintSemicolon
\KwIn{Alphabet $\alphabet=\{c_1, c_2, \ldots, c_n\}$; with $frequencies=\{f_1, f_2, \ldots, f_n\}$;}
\KwOut{Huffman codelength}

$H(0):=0$\;
\For{$i \gets 1 ~\textbf{to} ~(n-1)$ } {
    $bestLen:=\infty$\\
    \For{$j \gets\max(0,2 i-n) ~\textbf{to}~ i-1$}{
        $codeLen:=H(j)+P_{2 i-j}$\\
        \uIf{$codLen\leq bestLen$}{
            $bestLen:=codLen$\\
        }
    }
    $H(i):=bestLen$
}
\Return{$H(n-1)$}\;
\caption{DP for Huffman}
\label{algo:huffmanDP}
\end{algorithm}

{\em Remark:} We use a slightly different notion of level than \cite{golin}. 
While \cite{golin} considers levels starting with the bottom most level as $0$ and increasing up to the root, 
we consider levels to start with $0$ from the root and increasing down the tree.
The above theorems and lemmas have been rephrased accordingly.


\section{A more efficient DP (ALG3): Proof of Theorem~\ref{thm:pseudo}}
Consider the blocking scheme in the definition of the $\DOPT$ problem. 
As mentioned in the introduction, the number of memory hierarchies, $k$,
is typically a small constant in practice. 
We now present a more efficient dynamic program based pseudo-approximation algorithm for the case 
when the number of hierarchies is constant.

We first prove some results (c.f. Propositions~\ref{prop:comp}, \ref{prop:squash} and Lemma~\ref{lem:dist}) 
required in the formulation of our new dynamic program.
The following proposition shows that given a set of characters,
we can construct a (nearly complete) prefix tree of depth $\lceil \log n \rceil$.
\begin{proposition}
\label{prop:comp}
Let $C$ denote a set of characters. There exists a prefix tree for $C$ having depth $\lceil \log |C| \rceil$.
\end{proposition}
\begin{proof}
It is easy to verify that we can place $2^{\lceil \log |C| \rceil}-|C|$ characters at depth 
$\lceil \log |C| \rceil - 1$ in the subtree and the remaining characters
at depth $\lceil \log |C| \rceil$ to form a valid prefix tree 
(additional nodes are added to serve as internal nodes).
\end{proof}

Consider a set of characters, $C$. 
The following proposition shows that given an arbitrary tree, $T$, with characters of $C$ appearing as leaf nodes in $T$,
we can always construct a valid prefix tree over $C$ that has height no more than that of $T$ and in which each character
appears at a lower depth than it does in $T$.
\begin{proposition}
\label{prop:squash}
Let $C$ denote a set of characters. 
Given a tree, $T$, in which the characters of $C$ appear as leaf nodes,
there exists a valid prefix tree, $T'$, over $C$ that has no greater height than $T$ and 
in which $d_{T'}(c) \le d_T(c)$ $\forall c \in C$.
\end{proposition}
\begin{proof}
We start with the tree $T$ and iteratively modify it until we obtain a valid prefix tree.


We find a node that violates any of these conditions and modify the tree as follows:
\begin{itemize}
\item If there is a node $u$ that is a leaf node but does not correspond to a character:
      We simply delete the node $u$.
\item If there is a node $u$ that has only one child: 
      Let the child node be $v$. We simply remove $u$ and directly attach $v$ to the parent of $u$.
\end{itemize}
It is easy to see that when no more violating nodes are left, we get a valid prefix tree.
It is also straightforward to observe that we never increase the depth of any node in this process.
\end{proof}

The following Lemma shows that there cannot be too many levels in the optimal prefix tree 
between two consecutive characters of the alphabet when sorted in order of frequencies.
\begin{lemma}
\label{lem:dist}
If $c_i$ is a character at level $\lvl$ and $c_{i+1}$ is at level $\lvl'$ then $\lvl'-\lvl$ $<$ $\lceil \log(n) \rceil$.
\end{lemma}
\begin{proof}
We prove this by contradiction.
Suppose in the optimal tree $T$, $\dT(c_{j+1})-\dT(c_j) \geq \lceil \log(n) \rceil$ for some $j$. 
Let $C$ denote the set of all the characters having depth more than $\dT(c_{j+1})$.
Note that these characters have depth more than $\dT(c_{j})+\lceil \log n \rceil$.
Using Proposition~\ref{prop:comp}, we can construct a valid prefix tree $T_C$ over the characters $C$
having depth at most $\lceil \log |C| \rceil$.
Consider any internal node, say $u$ at the same depth as $c_j$
(such a node must exist as there are more characters at depth $> \dT(c_j$)).
We first delete all the characters of $C$ from $T$ and then
we delete the subtree at $u$ and replace it with $T_C$ (root of $T_C$ replacing $u$).
Note that in the resulting tree, all the characters are at a depth no more than their depth in $T$.
Now, by Proposition~\ref{prop:squash}, we can modify this tree to make it a valid prefix tree.
In the process, we have only reduced the height of the characters and therefore reduced both
the decode time as well as the codelength. Hence the tree $T$ could not have been an optimal tree -- contradiction.
\end{proof}

The following lemma shows that there exists a tree having bounded height that has almost the same
code length and decode time as the optimal prefix tree of $\DOPT$.
\begin{lemma}
\label{lem-ht}
There exists a prefix tree, $T'$, for which the decode time and the code length are respectively at most 
$(1+\delta)$ times those of $\DOPT$ and the height of $T'$ is no more than
$2 k \cdot \lceil {1}/{\delta} \rceil \cdot \lceil \log n \rceil$.
\end{lemma}
\begin{proof}
Let $h^*$ denote the height (total number of levels) of the optimal prefix tree (solution to $DOPT$). 
If $h^* \leq 2k \cdot \lceil {1}/{\delta} \rceil \cdot \lceil \log(n) \rceil$, then the
claim is trivially satisfied. We therefore focus on the case when
$h^* > 2k \cdot \lceil {1}/{\delta} \rceil \cdot \lceil \log(n) \rceil$.
As there are at most $k$ memory hierarchies, at least one of these has more than 
$2\cdot \lceil {1}/{\delta} \rceil \cdot \lceil \log(n) \rceil$ levels. 
Let us focus on one such memory hierarchy.
Consider $2 \cdot \lceil {1}/{\delta} \rceil$ partitions of these levels,
each comprising of $\lceil \log n \rceil$ consecutive levels in this hierarchy. 
Lemma~\ref{lem:dist} implies that each of these partitions has at least one character. 
Pick one such character $c_i$ from the $\lceil {1}/{\delta} \rceil^{th}$ partition, 
and let it's level be $\lvl$ in the tree. 

Let $T^*$ be the prefix tree corresponding to the optimal solution $DOPT({\cal L})$. 
We modify $T^*$ to construct another prefix tree, $T'$ as follows:
\begin{itemize}
\item all the characters up to $\lvl+\lceil \log n \rceil$ retain the same level as in $T^*$, 
      except for $c_i$ (described next);
\item $c_i$ is replaced with a new internal node, say $u$, and $c_i$ is made the child of $u$ (now $c_i$ is at level $\lvl+1$). 
\item We call a character of $T^*$ {\em deep} if it has depth more than
      $ 2k\cdot \lceil {1}/{\delta} \rceil \cdot \lceil \log(n) \rceil$.
      Let $\gamma$ be the number of deep characters in $T^*$.
      Using proposition~\ref{prop:comp}, there exists a subtree comprising of all the deep characters of $T^*$,
      having depth at most $\lceil \log \gamma \rceil \le \lceil \log n \rceil$.
      We attach this subtree as the second
      child of $u$. 
      The level of any of the characters in this subtree is no more than $\lvl+\lceil \log n \rceil + 1$.
     
\end{itemize}




We now show that the codelength and decode time  of $T'$ are no more than $(1+\delta)$ times the corresponding parameters of $T^*$.

Note that both the code length and decode time of the deep characters of $T^*$ only reduces
as their depth reduces in $T'$. Therefore the code length and decode time can only increase due to the character $c_i$ moving 
one level down. 

Let us first analyze the increase in code length due to $c_i$ moving one level down.
Recall that the memory hierarchy to which $c_i$ belonged was divided into $2\lceil 1/\delta \rceil$ partitions
and $c_i$ belongs to the $\lceil 1/\delta \rceil^{th}$ partition. Moreover each partition contains a character.
Thus there are at least $\lceil 1/\delta \rceil$ characters having level same or above that of $c_i$ with higher frequencies.
Thus $len(T^*) \ge \lceil 1/\delta \rceil \cdot f_i$. The increase in code length incurred by moving 
$c_i$ down one level is $f_i$. 
Thus $f_i \le \delta \cdot ( \lceil 1/\delta \rceil \cdot f_i ) \le \delta \cdot len(T^*)$.
Therefore $len(T') \le (1+\delta)\cdot len(T^*) \le  (1+\delta)\cdot {\cal L}$.



            

 

We analyze the increase in decode time due to $c_i$ moving one level down.
Let the block access cost of the memory hierarchy to which $c_i$ belongs be $q$.
As there are at least $\lceil 1/\delta \rceil$ characters at levels above $c_i$ having higher frequencies
and belonging to the same memory hierarchy, it follows that $\Delta(T^*) \ge \lceil 1/\delta \rceil \cdot q \cdot f_i$.
Moreover, as there are more partitions below $c_i$, the next level must also be in the same memory hierarchy.
It is possible that the next level corresponds to the start of a new block.
Thus the increase in decode time due to $c_i$ moving to the next level is at most $q \cdot f_i$.
Thus $q \cdot f_i \le \delta \cdot ( \lceil 1/\delta \rceil \cdot q \cdot f_i ) \le \delta \cdot \Delta(T^*)$.
Therefore $\Delta(T') \le (1+\delta) \cdot \Delta(T^*)$.

\end{proof}

Given the above Lemma, the algorithm is quite straightforward - 
we simply run the dynamic program for the pseudo-approximation algorithm described in the previous 
section by bounding the $h$ parameter by $2k\cdot \lceil \log(n) \rceil \left\lceil{{1}/{\delta}}\right\rceil$.

{\em Time Complexity:} The analysis is same as that of Algorithm~\ref{algo:doptptasDP} in the previous section;
we know that the time taken is $O(h^2n^2/\epsilon)$.
Taking the bound on the height $h$ to be $2k\cdot \lceil \log(n) \rceil \left\lceil{{1}/{\delta}}\right\rceil$,
the running time becomes $O\left(\dfrac{n^2\cdot k^2 \log^2(n)}{\epsilon \cdot \delta^2}\right)$.
For constant $k$, this yields a complexity of $O\left(\dfrac{n^2\cdot \log^2(n)}{\epsilon \cdot \delta^2}\right)$.

\section{A pseudo approximation algorithm  (ALG2): Proof of Theorem~\ref{thm:ptas}}
The algorithm presented in the previous section has linear running time dependency on the parameter ${\cal L}$.
In this section, we propose a pseudo approximation algorithm that runs in time $O(n^4/\epsilon)$
and returns a prefix tree having codelength bounded by $(1+\epsilon)\cdot{\cal L}$.
For this we restrict the parameter $L$ to only take on values that are multiples of $\lambda = \lfloor (\epsilon \cdot {\cal L})/2h \rfloor$
ranging from $0 \cdot \lambda$ upto $((2h/\epsilon) + h) \cdot \lambda$ 
where $h$ is some upper bound on the height of the optimal prefix tree 
(Since we do not know the actual height of the optimal tree, we will eventually take $h$ to be $n$).
We denote the dynamic program table maintained by this algorithm with $\overline{D}$.

We define a rounding function ${\mathbf r}$ as follows:
$${\mathbf r}(x) = \left\lceil \dfrac{x}{\lambda} \right\rceil \cdot \lambda.$$
The recurrence for the dynamic program in the previous section is now changed as follows.
The base case is modified as follows:
for all forests with no internal nodes, we initialize the decode time to $0$, i.e.,
$\forall ~\lvl \in [0,h]$ and $L$ a multiple of $\lambda$ and $L$ $\in[0,{\mathbf r}({\cal L})+h\lambda]$:
$$D(0,\lvl,L)=0.$$
and the inductive step is modified as follows:
\begin{eqnarray}
\label{eq:rec}
\overline{D}(i,\lvl,L) = \min_{j \in [max(0,2i-h),i-1]} \left\{ \overline{D}(j,\lvl+1,L')  + \hat{q}_{\lvl+1}\cdot P_{2 i-j} \right\} & &
\end{eqnarray}
where $L' = L-{\mathbf r}(P_{2 i-j})$.
Note that we only update entries of $\overline{D}$ for which the $L$ parameter is itself a multiple of $\lambda$.
It is easy to see that the $L$ parameter will take on only $O(h/\epsilon)$ values. 
The table can accordingly be compressed and maintained only for these entries,
however we omit these implementation details in the interest of better readability.

The following Lemma shows we can get decode time $\le \DOPT({\cal L})$ by sacrificing 
an additive $\lambda$ factor for every level in the code length.
\begin{lemma}
For any valid values of $i$, $\lvl$ and $L$:
$$D(i,\lvl, L) \ \ge \ \overline{D}(i,\lvl,{\mathbf r}(L)+(h-\lvl)\cdot \lambda)$$
\end{lemma}
\begin{proof}
In our proof we will be using the following fact:
\begin{proposition}
\label{prop:req}
Let $L'$ and $L''$ be multiples of $\lambda$. Then,
$\overline{D}(z,\lvl+1,L') \ge \overline{D}(z,\lvl+1,L'')$ whenever $L' \le L''$.
\end{proposition}
This proposition holds because the best solution having code length at most $L'$ is also a candidate solution
having code length at most $L''$ (other parameters remaining same).

We now prove the lemma by induction on the value of $\lvl$ decreasing from $h$ to $0$.

\par\noindent
For $\lvl=h$: 
From our initialization, the entries of $D$ and $\overline{D}$
are all initialized to $0$ for $\lvl=h$ and hence the claim trivially holds.

\par\noindent
For $\lvl < h$:
Consider $D(i,\lvl,L)$.
From recurrence~(\ref{eq:rec}), there must be some choice of $j$ for which
$D(i,\lvl,L)$ is minimized. Let $z$ be that choice of $j$, i.e.,
$$D(i,\lvl,L) = D(z,\lvl+1,L-P_{2i-z}) + \hat{q}_{\lvl+1} \cdot P_{2i-z} $$

Taking $\theta=\hat{q}_{\lvl+1} \cdot P_{2i-z}$ we obtain the following relations:
\begin{flalign*}
& D(i,\lvl,L) & \\
& \ \ = D(z,\lvl+1,L-P_{2i-z}) + \theta & \\
& \ \ \ge \overline{D}(z,\lvl+1,{\mathbf r}(L-P_{2i-z})+(h-\lvl+1)\lambda) + \theta & \\
& \ \ \ge \overline{D}(z,\lvl+1,{\mathbf r}(L)-[{\mathbf r}(P_{2i-z})-\lambda]+(h-\lvl+1)\lambda) + \theta & \\
& \ \ = \overline{D}(z,\lvl+1,{\mathbf r}(L)-{\mathbf r}(P_{2i-z})+(h-\lvl)\lambda) + \theta & \\
& \ \ \ge \overline{D}(i,\lvl,{\mathbf r}(L)) & 
\end{flalign*}
where the first inequality follows by induction,
the second inequality follows from Proposition~\ref{prop:req}
and the last inequality follows from the fact that
every $z$ that is a candidate for consideration in recurrence~(\ref{eq:rec0})
for $D(i,\lvl,L)$ is also a candidate for consideration in recurrence~(\ref{eq:rec}) for $\overline{D}(i,\lvl,{\mathbf r}(L))$.




This completes the proof of the Lemma.
\end{proof}

From the previous section, we know that the optimal solution is captured by $D(h-1,0,{\cal L})$.
Hence the above Lemma implies that the optimal solution is also captured by 
$\overline{D}(h-1,0,{\mathbf r}({\cal L}) + h \cdot \lambda )$.

\begin{algorithm}[t!]
\DontPrintSemicolon
\KwIn{Alphabet $\alphabet=\{c_1, c_2, \ldots, c_n\}$; with $frequencies=\{f_1, f_2, \ldots, f_n\}$;
Codelength Restriction ${\cal L}$; Approximation constant $\epsilon$}
\KwOut{Minimum Decode Time among trees having codelength less than $(1+\epsilon)\cdot {\cal L}$}
$\lambda = \lfloor (\epsilon \cdot {\cal L})/2h \rfloor$\\

\For{$\lvl \gets 0 ~\textbf{to}~ n$ }{
    \For{$b \gets 0 ~\textbf{to}~ ((2h/\epsilon) + h)$}{
        $L=b\cdot \lambda$\\
        $\overline{D}(0,\lvl,L):=0$    
    }
}
\For{$i \gets ~1~\textbf{to}~(n-1)$}{
    \For{$\lvl \gets (h-1) ~\textbf{downto}~ 0$ }{
        \For{$b \gets 0 ~\textbf{to}~ ((2h/\epsilon) + h)$ }{
            $L=b\cdot \lambda$\\
            $bestTime:=\infty $\\
            \For{$j \gets \max(0,2 i-n) ~\textbf{to}~ i-1$}{    
                $decTime:= \infty $\\
                $L' = L - {\mathbf r}(P_{2 i-j})$\\
                \uIf{$0\leq L'$}{$decTime:=\overline{D}(j,\lvl+1,L')+\hat{q}_{(l+1)}\cdot P_{2i-j}$}
                
                \uIf{$decTime < bestTime $}{
                    $bestTime:=decTime$
                }
            }
            $\overline{D}(i,\lvl,L):=bestTime$
        }
    }
}
\Return{$D(n-1,0,{\mathbf r}({\cal L})+h \cdot \lambda)$};
\caption{Pseudo-approximate algorithm}
\label{algo:doptptasDP}
\label{alg:pseudo}
\end{algorithm}

{\em Time complexity:} 
There are at most $O(h)$ levels and $O(n)$ characters. $L$ can have at most $O(h/ \epsilon)$ possible values. 
Hence, there are $O(nh^2/\epsilon)$ cells in the table. 
Each cell can be filled in at most $O(n)$ time. 
So the time complexity is $O({n^2h^2}/{\epsilon})$. 
Since there are a total of $h$ recursive calls, the error in code length is bounded by $h\lambda \le \epsilon \cdot {\cal L}$.
Thus, we can find a prefix tree having code length less than $(1+\epsilon)\cdot {\cal L}$ and  
decode time $\le \DOPT({\cal L})$ in $O( {n^2h^2}/{\epsilon} )$ time. 
Taking the upper bound for the height, $h$, as $n$, we get the time complexity to be $O( {n^4}/{\epsilon} )$.



\section{Introduction}
Data compression algorithms aim to reduce the number of bits required to represent data
in order to save storage capacity, speed up file transfer, and decrease costs for storage 
hardware and network bandwidth.
Compression techniques are primarily divided into two categories: lossless and lossy.
Lossless compression enables the data to be restored to its original state, without the loss of a single bit of data,
when it is uncompressed (decoded).
Huffman encoding is a basic and popular approach for lossless data compression; 
it is based on variable length prefix encoding\cite{huffman},
where the characters of the alphabet are encoded with variable length code words and no character encoding is the
prefix of another.
Huffman encoding is widely used in many mainstream applications including file compression (e.g. GZIP\cite{pkzip}, PKZIP\cite{pkzip}, BZIP2\cite{bzip2}, etc.) and image and video storage formats (JPEG\cite{jpeg}, PNG\cite{png}, MP3\cite{mp3}, etc.).

While most compression techniques focus on achieving maximum compression,
there is an inherent cost of decompressing or decoding the data that can be prohibitive
for certain real time applications.
One such application is inference task in deep learning.
The sizes of deep learning models are quite large, 
for instance AlexNet is 240MB\cite{alexnet} and VGGNet-16 is 552 MB\cite{vgg16}.
Smaller models are obtained by using various techniques such as quantization of model parameters\cite{quantization},
use of lower precision\cite{lowprec} and more sophisticated approaches such as 
use of depth-wise separable convolutions, e.g. MobileNetV2\cite{mobilenet}.
MobileNetV2 is particularly designed for environments such as edge devices, mobile devices and sensors where the resource
constraints are more stringent.
Data compression is often used in conjunction with the above techniques to further reduce the memory consumption;
for instance Han et al.\cite{HanMD15} employ Huffman encoding to compress the model after applying quantization.
The model is decoded in real-time when inference has to be performed.

In such settings, that require decoding to be performed in real-time, it is acceptable to sacrifice
the compression ratio to a small extent if it results in improved decode time as this is a critical aspect for
a good user experience.
Moreover, as the data is encoded only once, it is acceptable to spend extra time in the encoding process
to suitably compress the data so that it can be decoded quickly.

Decoding of Huffman coded data is typically performed using lookup tables;
code trees are employed where small tables are used to represent subtrees\cite{634683}. 
Thus a number of input bits are used to lookup a table; if $w$ bits are used (called the width of the table),
then the size of the table is $2^w$.
If a prefix of the lookup bits forms a valid code word, then the table entry points to the corresponding
code word and the input slides ahead by the number of bits used in the encoding of the code word.
Otherwise, the table entry points to another table wherein a lookup is performed with the next
fixed number of bits (possibly different than $w$) of the input; this is repeated until a valid word is decoded.
This is illustrated in Figure~\ref{fig:multi-tables}.
The prefix tree can be viewed as multiple levels of blocks where each block corresponds to a lookup table
used during decoding. We refer to this scheme of using multiple lookup tables (blocks) as \textit{blocking}.
Figure~\ref{fig:blocking} provides an illustration of a blocking scheme.

\begin{figure}[t!]
    \centering
    \includegraphics[width=3.3in]{lut.pdf}
    \caption{\small Consider an alphabet with frequencies and Huffman encoding as shown in Table (a).
    Tables (b) and (c) illustrate the $1^{st}$ and $2^{nd}$ level lookup tables of width 2 and 3 bits respectively. 
    If the code word is not found in the first table, it is redirected to the $2^{nd}$ level lookup table.
    The number of input bits to skip is also stored in the table along with the decoded character.}
    \vspace*{-.2in}
\label{fig:multi-tables}
\end{figure}



The choice of the size of the blocks provides a trade-off between memory consumption and decode time;
if a single large block is used, memory may be wasted whereas if a complete
code tree is used then too many conditional statements are required for decoding impacting the decode time.
In a related setting, lookup tables (blocks)  are used for decoding based on the memory hierarchy; the initial level
blocks are placed in fast small memories such as cache or scratchpad and typically have a small size,
and subsequent blocks are larger and are placed in main memory. In this setting, the cost of accessing
different blocks varies as a function of memory hierarchy levels.
The faster memories can be quite small limiting the size of the tables that can be kept in them.
For instance the unified cache can be as small as 4KB in ARM processors that are frequently used in
sensor devices \cite{wiki4kb}.On GPUs, the shared memory that serves as a user managed scratchpad can be as small as 16KB and is shared
by many threads.
Moreover, operations other than decoding also compete for fast memory resources.

\begin{figure}[t!]
    \centering
    \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \includegraphics[width=2.5in]{blocking.pdf}
    \caption{\small Illustration of blocking scheme $<$$(3,1),(2,1)$$>$.}
    \label{fig:blocking}
    \label{fig:dummy}
   
\end{figure}


Though the Huffman tree is the optimal prefix tree in terms of code length, it is not
optimal in terms of decode time as accommodating more frequent characters in \textit{block levels}
clsoser to root can reduce the decode time.
Figure~\ref{fig:example} demonstrates an example in which the Huffman tree 
(shown in (a)) has a higher decode time in comparison to 
another prefix tree (shown in (b)).
\textit{Note that in the absence of blocking, the Huffman tree would be the best prefix tree
with respect to both, code length as well as decode time}.

Motivated by the above scenarios, we define a new problem wherein we seek to find the best prefix tree, i.e., 
having the minimum decode time under the constraint that the code length does not exceed a specified threshold. 
We next define the problem formally.
\subsection{Problem Definition.}
Consider an alphabet $\alphabet$. 
For each character $c$ in $\alphabet$, let the attribute $\freq(c)$ denote the frequency of $c$ 
in the input data to be encoded. 
Given a prefix tree $T$ corresponding to a prefix code for $\alphabet$,
let $\dT(c)$ denote the depth of the leaf corresponding to the encoding of $c$ in the tree. 
Note that $\dT(c)$ is also the length of the codeword for character $c$. 
The average code length of the encoding represented by the tree $T$ is given by
\begin{eqnarray}
\label{def:len}
\len(T)=\sum_{c \in \alphabet} \freq(c) \cdot \dT(c)
\end{eqnarray}

A \textit{blocking scheme} of $m$ \textit{block levels} is a sequence of $m$ block parameters, $<$$(w_1,q_1),$$(w_2,q_2),$$\ldots,$$(w_m,q_m)$$>$,
where $w_j$ and $q_j$ specify the width (number of bits) used to address a block and the access cost of a block 
respectively at \textit{block level} $j$ in the tree.
For a blocking scheme, $BS$, the number of memory hierarchies, denoted $k(BS)$,
is the number of times the  access cost changes when traversing the blocks in order, i.e., 
$$k(BS) = 1+\sum_{i \in [2,m]: q_i \ne q_{i-1}} 1$$

For a character $c$ having depth $\dT(c)$ in a prefix tree $T$,
the cost of looking up (decoding) the character under the scheme $BS$, $\cost_T(c)$,
is given by the total sum of the cost of accessing the blocks starting from the 
first \textit{block level} up to the \textit{block level} to which the character belongs, i.e.,
\begin{eqnarray}
\label{def:costchar}
\cost_T(c) = \sum_{i \le \bdT(c)} q_i
\end{eqnarray}
$$\mbox{ where } \bdT(c) = \argmin_h \left\{ \sum_{j=1}^{h} w_j \ge \dT(c) \right\}$$

The decode time of the encoding for a prefix tree $T$ is given by:
\begin{eqnarray}
\label{def:costtree}
\cost(T)=\sum_{c \in \alphabet} \freq(c)\cdot \cost_T(c).
\end{eqnarray}

\par\noindent
{\sc Definition: }
({\DOPT}) Given a blocking scheme $BS$ and parameter ${\cal L}$, called the {\em permitted code length},
the goal of our problem is to determine a prefix tree, $T$,
that minimizes $\cost(T)$ subject to 
$\len(T) \le {\cal L}$. 
We call this the {\em decode optimal prefix tree problem} and denote it by {\DOPT}({\cal L}).
With slight abuse of notation, 
we shall also refer to the decode time of the associated solution as {\DOPT}({\cal L}).

\begin{figure}[t!]
    \centering  
    \includegraphics[width=3.2in]{example.pdf}
    \caption{\small Consider the alphabet of Figure~\ref{fig:multi-tables} and the blocking scheme
    where the first block is of width 2 bits \& access cost 1 unit and the 
    second block is of width 3 bits \& access cost q units i.e. BS is $<$$(2,1),(3,q)$$>$.
    (a) Illustrates the corresponding Huffman tree that has code length of 
        $5\cdot1+5\cdot1+4\cdot4+3\cdot6+2\cdot9+1\cdot25 = 87$ and decode time of
        $(1+q)\cdot1+(1+q)\cdot1+(1+q)\cdot4+(1+q)\cdot6+1\cdot9+1\cdot25 = 46+12q$; 
    (b) Illustrates another prefix tree with higher code length of 
        $4\cdot1+4\cdot1+3\cdot4+2\cdot6+2\cdot25+2\cdot9=100$
        but a better decode time of $(1+q)\cdot1+(1+q)\cdot1+(1+q)\cdot4+1\cdot6+1\cdot25+1\cdot9=46+6q$ }
    \label{fig:example}
   
\end{figure}

\subsection{Related work.} 

There have been several efforts to improve the decode time. 
However, to the best of our knowledge, there is no prior work that gives any 
provable theoretical guarantees for minimizing decode time along with the code length.

Sen et al \cite{cacmodel} proposed a multiple hierarchy model which is an extension of Aggarwal and Vitter's IO model \cite{IO_complexity}. Their model can be represented using our model. Each hierarchy $L_i$ of their model can be translated to some $k_i$ blocks of different widths each having the same access cost in our model. That is each $L_i$ corresponds to $< (w_{r+1},q),\cdots(w_{r+k_i},q)>$ for some $r$, where $\sum_{j=1}^{k_i} w_{r+j} = L_i$ in our blocking scheme.

Moffat and Turpin \cite{634683} propose a method for fast decoding of Huffman trees
that looks up one entry of an {\em offset} array (sequentially) for every bit of the compressed data
read from the input. 
To further speed up their algorithm, they use a lookup table using a fixed number
of bits from the input; this exactly corresponds to the first level block in the blocking scheme setup.
This is then followed by looking up an entry of the offset array for every subsequent bit of the input.
Thus, their scheme can be viewed as a $<$$(w,1),(1,q),(1,q),\ldots$$>$ in our setup
where $w$ is the bit-width of the table and $q$ is the access cost of the memory where the array is stored.
We note that the blocking scheme is a generalization of the lookup table scheme employed in \cite{634683}.
We also note that \cite{634683} do not restructure the prefix tree by 
changing the length of any character in the encoding.
Thus our algorithms can be used in conjunction with the method of \cite{634683}; 
we show some results to this effect in the experimental results section.

In Length limited Huffman coding\cite{llhc}, the authors consider building an optimal prefix tree having
minimum code length given a bound on the height of the tree. However, their work does not support
the concept of blocking (for multiple lookup tables) and does not consider memory hierarchies.

As mentioned earlier, lookup tables\cite{634683} are commonly used to improve the decode time.
However, there is no existing work that considers lookup tables in the hierarchical memory setting.
Moreover, this line of work only considers given prefix encodings; 
they do not design new encodings to take advantage of the lookup table sizes. 
Lookup tables form the basis for our work as this technique has been successfully used in practice
and has been shown to give good speedups for decode time.

Hashemian\cite{hashemian} used a tree clustering algorithm to improve the decode time.
Their work does not provide any theoretical guarantees.









\subsection{Our Contributions.} 
Our first result is an exact algorithm to compute an optimal solution:
\begin{theorem}
\label{thm:exact}
There exists a dynamic program algorithm to solve the {\DOPT}(${\cal L}$) problem that runs in time
$O(n^3 \cdot {\cal L})$.
\end{theorem}

Our second result is a strongly polynomial pseudo approximation algorithm:
\begin{theorem}
\label{thm:ptas}
There exists a dynamic program algorithm that returns a prefix-tree having codelength at most
$(1+\epsilon) \cdot {\cal L}$ and decode time $\le {\DOPT}({\cal L})$. 
The running time of the algorithm is $O(n^4 / \epsilon)$.
\end{theorem}

In practice, the number of memory hierarchies, $k$, is typically a small constant. 
Our next result is a more efficient pseudo approximation algorithm for this case:
\begin{theorem}
\label{thm:pseudo}
For the case where the number of memory hierarchies, $k$, is a constant,
there exists a dynamic program algorithm that returns a prefix tree having code-length at most 
$(1+\epsilon) \cdot (1+\delta) \cdot {\cal L}$ and decode time $\le (1+\delta) \DOPT({\cal L})$. 
The running time of the algorithm
is $O\left(\frac{n^2\cdot k^2 \log^2(n)}{\epsilon \cdot \delta^2}\right)$.
This is $O\left(\frac{n^2\cdot \log^2(n)}{\epsilon \cdot \delta^2}\right)$
when $k$ is a constant.
\end{theorem}

We also run our algorithm on real-world data sets. We implement our algorithms on the GPU
for deep learning inference task and observe 8\%-26\% improvement in decode time
with 2-3\% relaxation over the Huffman encoding code length for various blocking schemes.
We also simulate the decoding for different architectures with a varying range of practical memory access 
latencies and predict up to $\sim$2x reduction in decoding time for different blocking schemes.

\section{Experimental results}  

One of the more popular and effective techniques for reducing the decode time is that of table lookups.
In \cite{634683}, the authors compare several algorithms 
and demonstrate the effectiveness of table lookups.
In our experiments we consider table lookups with Huffman encoding as a baseline;
thus the speedups can be attributed to the restructuring of
the prefix trees by our algorithms. $\epsilon$ represents the total relaxation in Huffman codelength (including the relaxation due to approximation in ALG2) in the Figures ~\ref{fig:gpu_exp}, \ref{fig:rw_exp}.

\paragraph{Inference task for deep learning models on the GPU:}
We first experiment with inference task on a compressed version of the popular Mobilenet-V2 dataset 
with different levels of quantization. We conduct experiments on the K80/V100 GPUs with three different blocking schemes.
In all these experiments, the first level block is kept in the shared memory and the remaining blocks are kept 
on the GPU device memory.
As noted before this memory is shared by many threads.
We run the decode routine using a single thread to measure the speedup 
(this avoids any unwanted effects due to thread parallelism).
The results are shown in Figure~\ref{fig:gpu_exp}.
In the first configuration, we use a uniform blocking scheme, $<(4,1),(4,1),\ldots>$,
i.e., multi-level lookup tables of 16 entries each with uniform access cost.
With just 2\% relaxation in the code length, we observe up to 26\% improvement in the 
decode time using our modified prefix encoding.
In the second configuration, we use the blocking scheme, $<(4,1),(4,20),(4,20),\ldots>$,
i.e., the access cost of subsequent tables is about 20x the access cost of the first table.
This is representative of the ratio of the GPU device memory cost to share memory cost\cite{acccost}.
As expected, our scheme performs better as the alphabet size increases and as we 
allow for more relaxation in the decode length. We observe gains of up to 7\%
even with just 2\% relaxation in the decode length.
In the third configuration, we use the blocking scheme, $<(4,1),(1,20),(1,20),\ldots>$;
this is representative of the setup of Moffat \& Turpin\cite{634683}, wherein the first level comprises
of a lookup table in the shared memory followed by one access per bit of subsequent input
to the GPU device memory. We observe gains of up to 8\% with this blocking scheme.

\begin{figure}[t!]
\centering
    \begin{minipage}{\textwidth}
    \small
    \centering
    \begin{tabular}{ r|c|c|c|c|c|c|c  }
             \hline
             Alphabet & BS1 & \multicolumn{3}{c|}{Blocking Scheme BS2} & \multicolumn{3}{c}{BS3} \\ \cline{2-8}
             size \ \ \ \ & $\epsilon=0.02$ & $\epsilon=0.02$ & $\epsilon=0.03$ & $\epsilon=0.06$ &
                            $\epsilon=0.02$ & $\epsilon=0.03$ & $\epsilon=0.06$    \\
             \hline \hline
            64 \ \ \ \ & 1.01 & 1.03 & 1.03 & 1.04 & 1.00 & 1.00 & 1.00 \\
            128 \ \ \ \ & 1.08 & 1.02 & 1.04 & 1.06 & 1.04 & 1.06 & 1.08 \\
            256 \ \ \ \ & 1.15 & 1.05 & 1.06 & 1.07 & 1.04 & 1.04 & 1.06 \\
            512 \ \ \ \ & 1.10 & 1.07 & 1.07 & 1.07 & 1.01 & 1.01 & 1.01 \\
            1024 \ \ \ \ & 1.26 & - & - & - & - & - & - \\
             \hline
    \end{tabular}
    \end{minipage}
    \caption{\small Speedup obtained on the GPU for Mobilenet-V2 with varying 
             quantization states (alphabet size)
             using the pseudo-approximation  algorithm (ALG2). 
             The first level lookup table is kept in the shared memory.
             All lookup tables are 4-bit. The blocking schemes used are BS1: $<$$(4,1),(4,1),\ldots$$>$; 
             BS2: $<$$(4,1),(4,20),(4,20),\ldots$$>$; and BS3: $<$$(4,1),(1,20),(1,20),\ldots$$>$.}
    \label{fig:gpu_exp}
\end{figure}

\paragraph{Decoding other real world data sets on different architectures:}
We next experiment with two other real world data sets:
    (i) JPEG: George H. W. Bush's face image\cite{gwbush} from the Labeled Faces in the Wild, image database; and 
    (ii) Text: The King Jame's Version of the Bible.
We predict the speedups that can be obtained using our algorithms on different architectures
by simulating the decode process given the memory access latencies.
We consider the setting where the first level block is kept in the first level memory 
and the remaining blocks are kept in the second level memory.
We experiment with settings where the second level memory is a factor of 1x, 10x and 100x 
of the first level memory. These are of the same order as the latencies of L1 cache, L2 cache and main memory
on typical systems.
In these experiments,
the decode-time is calculated directly from the blocking scheme and the prefix tree. 
The results are shown in Figure~\ref{fig:rw_exp}.
In the first configuration, we use the blocking scheme, $<(4,1),(4,x),(4,x),\ldots>$,
i.e., the access cost of subsequent tables is about $x$ factor more than the access cost of the first table.
In the second configuration, we use the blocking scheme, $<(8,1),(8,x),(8,x),\ldots>$.
In general, the gains from restructuring are better with larger ratio of the memory access costs
and also with larger relaxations. Also, the second blocking scheme seems to yield better benefits
as it allows for more characters to be encoded with lower cost.
We predict gains of the order of 15\%-25\% for these data sets 
for the blocking scheme $BS1$ when $x$ lies between 10x and 100x.
Similarly, We predict gains of the order upto 2x-3x for these data sets 
for the blocking scheme $BS2$ when $x$ lies between 10x and 100x.
In general, JPG seems to offer better gains due to more restructuring of the prefix code
than text data.


\begin{figure}[t!]
\centering
    \begin{minipage}{\textwidth}
    \small
    \centering
    \begin{tabular}{ r|c|c|c|c|c|c|c|c|c|c|c|c  }
             \hline
             Second level memory & \multicolumn{3}{c|}{ JPG (BS1)}  & \multicolumn{3}{c|}{ JPG (BS2)} & \multicolumn{3}{c|}{ Text (BS1)}& \multicolumn{3}{c}{ Text (BS2)}\\ \cline{2-13}
             latency factor ($x$) & $\epsilon=0.02$ & $0.03$ & $0.06$ &
                            $0.02$ & $0.03$ & $0.06$ & $0.02$ & $0.03$ & $0.06$ & $0.02$ & $0.03$ & $0.06$  \\
             \hline \hline
            1x \ \ \ \ & 1.08 & 1.09 & 1.09 & 1.11 & 1.13 & 1.16 & 1.09 & 1.09 & 1.09 & 1.11 & 1.13 & 1.16 \\
            10x \ \ \ \ & 1.16 & 1.18 & 1.23 & 1.57 & 1.66 & 1.97 & 1.15 & 1.15 & 1.15 & 1.46 & 1.59 & 1.79 \\
            100x \ \ \ \ & 1.18 & 1.20 & 1.25 & 1.95 & 2.16 & 2.95 & 1.17 & 1.17 & 1.17 & 1.67 & 1.89 & 2.29 \\
             \hline
    \end{tabular}
    \end{minipage}
    \caption{\small Speedup predicted for JPG and text data using simulations for different architectures using the pseudo-approximation  algorithm (ALG2).
             The blocking schemes used are BS1: $<$$(4,1),(4,x),(4,x),\ldots$$>$; and
             BS2: $<$$(8,1),(8,x),(8,x),\ldots$$>$ where the second level memory latency is $x$ times that 
             of the first level.}
    \label{fig:rw_exp}
    \vspace*{-.2in}
\end{figure}


\eat{

These speedups are quite consistent with the speedups obtained directly using the model
(See Figure~\ref{fig:results2} (b)).



We use 3 different real-world datasets: 
    (i) Deep learning model: MobileNetV2 model trained on Imagenet dataset after quantization of the model weights\cite{HanMD15}; 
    (ii) JPEG: George H. W. Bush's face image\cite{gwbush} from the Labeled Faces in the Wild, image database; and 
    (iii) Text: The King Jame's Version of the Bible (beginning 10\% of the text).
For MobileNetV2, we use 256 levels of quantization on the weights unless specified otherwise.

There have been several works that reduce the decode time of prefix encodings.
One of the more popular and effective schemes is that of table lookups.
In \cite{634683}, the authors compare several algorithms that improve decode time
and demonstrate the effectiveness of table lookups.
As mentioned before, our work also builds on table lookups.
In our experiments we consider table lookups with Huffman encoding as a baseline to compare the speedups
obtained with our algorithms; thus the speedups can be attributed to the restructuring of
the prefix trees by our algorithms.
We report speedup achieved in decode-time for our algorithm
compared to the decode-time of Huffman encoding when using lookup tables with the same blocking schemes. 

The decode-time is calculated directly from the blocking scheme and the prefix tree. We also implement
the decode routine on the GPU. We ran our experiments on the Tesla K40 GPU with the first 
level block (lookup table) residing in the shared memory. 
As noted before this memory is shared by many threads.
We run the decode routine using a single thread to measure the speedup 
(this avoids any unwanted effects due to thread parallelism).

\paragraph{Effect of permitted code length parameter ($L$):}
We first study the speedup
when we relax the ${\cal L}$ parameter to 1\%, 2\%, 5\% and 10\% more than Huffman encoding code length.
The results obtained with the exact DP (Algorithm~\ref{alg:exact}) are shown in Figure~\ref{fig:results} (a). 
As expected, the speedup increases as we relax the permitted code length. 
It is interesting to note that even with as little as 2\% relaxation in ${\cal L}$, we see an improvement of
7.5\% to 15\% in the decode time across the data sets.
The results with the pseudo approximation DP (Algorithm~\ref{alg:pseudo}) are shown in Figure~\ref{fig:results2} (a). 
We note that the decode-time speedups are observed to be almost the same as with the case of the exact DP.

\paragraph{Effect of the alphabet size ($n$):}
We next study the effect of different alphabet sizes on the decode time.
We use different levels of quantization in the MobileNetV2 model to generate alphabets of different sizes,
namely 256, 128 and 64 characters.
The results obtained with the exact DP (Algorithm~\ref{alg:exact}) are shown in the table in Figure~\ref{fig:results} (b). 
It can be noted that speedups drop as the alphabet size is reduced.
This is expected as there is not much rearrangement possible with a very small alphabet
and most of the characters fit in the lower level blocks.
The results with the pseudo approximation DP (Algorithm~\ref{alg:pseudo}) are shown in Figure~\ref{fig:results2} (b). 
We note that we obtain better decode-time speedups in comparison to the exact DP for the same alphabet sizes;
this is attributed to the flexibility in prefix tree configurations due to the additional 1\% relaxation
allowed in the code length.
As this algorithm is more efficient in comparison to the exact DP,
we are able to run this with larger alphabet sizes of 512 and 1024 as well (which we were not able
to run with the exact DP).
As before, speedups increase with increase in alphabet size due to the possibility of more arrangements.


\paragraph{Effect of the access cost ($q$):}
In hierarchical memory settings, top (lower) level blocks are kept in faster memory as they are accessed more often and
and the access time, $q$, increases as we go to the blocks at the bottom level that are kept in slower memory. 
We consider reasonable approximations of $1$ cycle, $20$ cycles and $100$ cycles for the L1, L2 caches and main memory
access costs respectively. Thus, with a blocking scheme of $<$$(4,1),(4,20),(4,100),(4,100),\ldots$$>$ 
where the tables from $3^{rd}$ level onwards are kept in the main memory, 
we study the effect of setting the ${\cal L}$ parameter to 1\%, 2\%, 5\% and 10\% more than 
Huffman encoding code length on the speedup. 
The results obtained with the exact DP (Algorithm~\ref{alg:exact}) are shown in the table in Figure~\ref{fig:results} (c).
We observe significant speedups of up to 3x in the decode time. Even with just 2\% relaxation for ${\cal L}$,
we observe a 2x speedup. To analyze this further, we record the number of characters encoded at each block level.
These are shown in Figure~\ref{fig:results} (d).
We can see that this gain can be attributed to our algorithm moving more characters 
to lower level blocks having lower access cost.
We see that higher the relaxation, more are the characters that are moved to the lower level blocks.

\begin{figure}[t!]
\centering
\begin{minipage}{.45\textwidth}
    \centering
    \includegraphics[width=2.5in]{kjb_full3.pdf}
    \captionof{figure}{\small Speedups obtained for KJB using the block Huffman coding scheme
             with the pseudo-approximation algorithm (Algorithm~\ref{alg:pseudo}) employing $\epsilon=0.01$
             and block sizes $<(8,1),(8,20),(8,20),\ldots>$ and 
             $<(4,1),(4,20),(4,20),(4,20),\ldots>$.}
            
    \label{fig:my_label}
 
\end{minipage
\ \ \ \ 
\begin{minipage}{.52\textwidth}
    \small
    \centering
    \begin{tabular}{ r|r  }
             \hline
             Alphabet & Speedup on GPU \\
             size \ \ \ \ & \\
             \hline \hline
            1024 \ \ \ \ & 1.26 \ \ \  \\
            512 \ \ \ \ & 1.10 \ \ \  \\
            256 \ \ \ \ & 1.15 \ \ \  \\
            128 \ \ \ \ & 1.08 \ \ \ \\
            64 \ \ \ \ & 1.01 \ \ \ \\
             \hline
    \end{tabular}
    \captionof{figure}{\small Speedup obtained on the GPU for Mobilenet-V2 with varying quantization states (alphabet size)
             using the pseudo-approximation
             algorithm (Algorithm~\ref{alg:pseudo}) with $\epsilon=0.01$. 
             The first level lookup table is kept in the shared memory.
             All lookup tables are 4-bit.  }
    \label{fig:gpu_exp}
   
\end{minipage}
\end{figure}

The corresponding results with the pseudo approximation DP (Algorithm~\ref{alg:pseudo}) are shown in 
Figure~\ref{fig:results2} (c) and (d) respectively. 
We note that there is considerable improvement in the speedups when compared to the exact DP.
This is again attributed due to the additional $1\%$ relaxation allowed in the code length.
Figure~\ref{fig:results2} (d) demonstrates that code length relaxation results in more characters
being pushed into the low cost lower level blocks in comparison to the exact DP (Figure~\ref{fig:results} (d)).


\paragraph{Effect of lookup table size:}
We next run experiments with different lookup table sizes.
We consider a larger first level memory that can hold $256$ entries.
We consider two different blocking schemes of $<$$(8,1),(8,20),(8,20),\ldots$$>$ and 
$<$$(4,1),(4,20),(4,20),(4,20),\ldots$$>$.
We use the KJB data set. In this experiment, we use the block Huffman coding scheme
described by Mannan and Kaykobad\cite{bhuffman}, which is often used in practice.
In this scheme, the alphabet is constructed by creating blocks of fixed number of characters from the input
and treating these blocks as the new alphabet.
This leads to better compression ratios~ \cite{bhuffman}. 
In our experiment, the alphabet is created by combining every pair of characters appearing in the input.
We observe considerable gains in the speedup for the blocking schemes
with larger lookup tables {as it allows more characters with high frequencies in the first cache level after restructuring.} 





\eat{
\paragraph{Effect of Block size}
We next study the speedup trends with varying values of the block width, $w$.
The table in Figure~\ref{fig:results} (c) shows the speedup obtained for MobileNetV2 when the block parameters
are uniformly all set to $(w,1)$ with as many block levels used as required, and $w$ is varied to take values $4,6,8,10$.

\paragraph{Effect of Alphabet size}
for the following blocking schemes($BS$):  denotes, <(4,1),(4,1),\ldots>, $BS$ of constant block width and constant access cost q; $Vw-Cq$ denotes, <(2,1),(4,1),(6,1),\ldots>, $BS$ of variable block width and constant access time; $Vw-Vq$ denotes, <(2,1),(4,20),(6,100),(8,100),\ldots>, $BS$ of variable block width and variable access time The relaxation is kept constant to 2\%. $Vw-Vq$ has higher speedup becuase of variable access cost, $Cw-Cq$ and $Vw-Cq$ have similar gains as all the block levels are indistinguishable in memory cost due to constant access costs. With increase in $n$ there is a steep rise in speedup i.e., even with as little as 2\% relaxation in compression, we can restructure the Huffman tree, with respect to the memory structure, in order to gain big amounts in decode time.

}











   

}
\section{Problem Specification.}In this paper, we consider the solution of the $N \times
N$ linear
system
\begin{equation} \label{e1.1}
A x = b
\end{equation}
where $A$ is large, sparse, symmetric, and positive definite.  We consider
the direct solution of (\ref{e1.1}) by means of general sparse Gaussian
elimination.  In such a procedure, we find a permutation matrix $P$, and
compute the decomposition
\[
P A P^{t} = L D L^{t}
\]
where $L$ is unit lower triangular and $D$ is diagonal.


\section{Design Considerations.}Several good ordering algorithms (nested dissection and
minimum degree)
are available for computing $P$  \cite{GEORGELIU}, \cite{ROSE72}.
Since our interest here does not
focus directly on the ordering, we assume for convenience that $P=I$,
or that $A$ has been preordered to reflect an appropriate choice of $P$.

Our purpose here is to examine the nonnumerical complexity of the
sparse elimination algorithm given in  \cite{BANKSMITH}.
As was shown there, a general sparse elimination scheme based on the
bordering algorithm requires less storage for pointers and
row/column indices than more traditional implementations of general
sparse elimination.  This is accomplished by exploiting the m-tree,
a particular spanning tree for the graph of the filled-in matrix.

\begin{theorem} The method  was extended to three
dimensions. For the standard multigrid
coarsening
(in which, for a given grid, the next coarser grid has $1/8$
as many points), anisotropic problems require plane
relaxation to
obtain a good smoothing factor.\end{theorem}

Our purpose here is to examine the nonnumerical complexity of the
sparse elimination algorithm given in  \cite{BANKSMITH}.
As was shown there, a general sparse elimination scheme based on the
bordering algorithm requires less storage for pointers and
row/column indices than more traditional implementations of general
sparse elimination.  This is accomplished by exploiting the m-tree,
a particular spanning tree for the graph of the filled-in matrix.
Several good ordering algorithms (nested dissection and minimum degree)
are available for computing $P$  \cite{GEORGELIU}, \cite{ROSE72}.
Since our interest here does not
focus directly on the ordering, we assume for convenience that $P=I$,
or that $A$ has been preordered to reflect an appropriate choice of $P$.

\begin{proof} In this paper we consider two methods. The first method
is
basically the method considered with two differences:
first, we perform plane relaxation by a two-dimensional
multigrid method, and second, we use a slightly different
choice of
interpolation operator, which improves performance
for nearly singular problems. In the second method coarsening
is done by successively coarsening in each of the three
independent variables and then ignoring the intermediate
grids; this artifice simplifies coding considerably.
\end{proof}

Our purpose here is to examine the nonnumerical complexity of the
sparse elimination algorithm given in  \cite{BANKSMITH}.
As was shown there, a general sparse elimination scheme based on the
bordering algorithm requires less storage for pointers and
row/column indices than more traditional implementations of general
sparse elimination.  This is accomplished by exploiting the m-tree,
a particular spanning tree for the graph of the filled-in matrix.

\begin{Definition}{\rm We describe the two methods in \S 1.2. In \S\ 1.3. we
discuss
some remaining details.}
\end{Definition}

Our purpose here is to examine the nonnumerical complexity of the
sparse elimination algorithm given in  \cite{BANKSMITH}.
As was shown there, a general sparse elimination scheme based on the
bordering algorithm requires less storage for pointers and
row/column indices than more traditional implementations of general
sparse elimination.  This is accomplished by exploiting the m-tree,
a particular spanning tree for the graph of the filled-in matrix.
Several good ordering algorithms (nested dissection and minimum degree)
are available for computing $P$  \cite{GEORGELIU}, \cite{ROSE72}.
Since our interest here does not
focus directly on the ordering, we assume for convenience that $P=I$,
or that $A$ has been preordered to reflect an appropriate choice of $P$.

Our purpose here is to examine the nonnumerical complexity of the
sparse elimination algorithm given in  \cite{BANKSMITH}.
As was shown there, a general sparse elimination scheme based on the
bordering algorithm requires less storage for pointers and
row/column indices than more traditional implementations of general
sparse elimination.

\begin{lemma} We discuss first the choice for $I_{k-1}^k$
which is a generalization. We assume that $G^{k-1}$ is
obtained
from $G^k$
by standard coarsening; that is, if $G^k$ is a tensor product
grid $G_{x}^k \times G_{y}^k \times G_{z}^k$,
$G^{k-1}=G_{x}^{k-1} \times G_{y}^{k-1} \times G_{z}^{k-1}$,
where $G_{x}^{k-1}$ is obtained by deleting every other grid
point of $G_x^k$ and similarly for $G_{y}^k$ and $G_{z}^k$.
\end{lemma}

To our knowledge, the m-tree previously has not been applied in this
fashion to the numerical factorization, but it has been used,
directly or indirectly, in several optimal order algorithms for
computing the fill-in during the symbolic factorization phase
[4] - [10], [5], [6]. In \S 1.3., we analyze the complexity of the old and new
approaches to the intersection problem for the special case of
an $n \times n$ grid ordered by nested dissection. The special
structure of this problem allows us to make exact estimates of
the complexity. To our knowledge, the m-tree previously has not been applied in this
fashion to the numerical factorization, but it has been used,
directly or indirectly, in several optimal order algorithms for
computing the fill-in during the symbolic factorization phase
[4] - [10], [5], [6].

In \S 1.2, we review the bordering algorithm, and introduce
the sorting and intersection problems that arise in the
sparse formulation of the algorithm.
In \S 1.3., we analyze the complexity of the old and new
approaches to the intersection problem for the special case of
an $n \times n$ grid ordered by nested dissection. The special
structure of this problem allows us to make exact estimates of
the complexity. To our knowledge, the m-tree previously has not been applied in this
fashion to the numerical factorization, but it has been used,
directly or indirectly, in several optimal order algorithms for
computing the fill-in during the symbolic factorization phase
[4] - [10], [5], [6].


For the old approach, we show that the
complexity of the intersection problem is $O(n^{3})$, the same
as the complexity of the numerical computations.  For the
new approach, the complexity of the second part is reduced to
$O(n^{2} (\log n)^{2})$.

To our knowledge, the m-tree previously has not been applied in this
fashion to the numerical factorization, but it has been used,
directly or indirectly, in several optimal order algorithms for
computing the fill-in during the symbolic factorization phase
[4] - [10], [5], [6]. In \S 1.3., we analyze the complexity of the old and new
approaches to the intersection problem for the special case of
an $n \times n$ grid ordered by nested dissection. The special
structure of this problem allows us to make exact estimates of
the complexity. To our knowledge, the m-tree previously has not been applied in this
fashion to the numerical factorization, but it has been used,
directly or indirectly, in several optimal order algorithms for
computing the fill-in during the symbolic factorization phase
[4] - [10], [5], [6].
This is accomplished by exploiting the m-tree,
a particular spanning tree for the graph of the filled-in matrix.
To our knowledge, the m-tree previously has not been applied in this
fashion to the numerical factorization, but it has been used,
directly or indirectly, in several optimal order algorithms for
computing the fill-in during the symbolic factorization phase
\cite{EISENSTAT} - \cite{LIU2}, \cite{ROSE76},  \cite{SCHREIBER}.

\subsection{Robustness.}We do not
attempt to present an overview
here, but rather attempt to focus on those results that
are relevant to our particular algorithm.
This section assumes prior knowledge of the role of graph theory
in sparse Gaussian elimination; surveys of this role are
available in \cite{ROSE72} and \cite{GEORGELIU}. More general
discussions of elimination trees are given in
\cite{LAW} - \cite{LIU2}, \cite{SCHREIBER}.
Thus, at the $k$th stage, the bordering algorithm consists of
solving the lower triangular system
\begin{equation} \label{1.2}
 L_{k-1}v = c
\end{equation}
and setting
\begin{eqnarray}
\ell &=& D^{-1}_{k-1}v , \\
\delta &=& \alpha - \ell^{t} v .
\end{eqnarray}

\begin{figure}
\vspace{14pc}
\caption{This is a figure 1.1.}
\end{figure}

\section{Robustness.} We do not
attempt to present an overview
here, but rather attempt to focus on those results that
are relevant to our particular algorithm.

\subsection{Versatility.}The special
structure of this problem allows us to make exact estimates of
the complexity.  For the old approach, we show that the
complexity of the intersection problem is $O(n^{3})$, the same
as the complexity of the numerical computations
\cite{GEORGELIU}, \cite{ROSEWHITTEN}.  For the
new approach, the complexity of the second part is reduced to
$O(n^{2} (\log n)^{2})$.

To our knowledge, the m-tree previously has not been applied in this
fashion to the numerical factorization, but it has been used,
directly or indirectly, in several optimal order algorithms for
computing the fill-in during the symbolic factorization phase
[4] - [10], [5], [6]. In \S 1.3., we analyze the complexity of the old and new
approaches to the intersection problem for the special case of
an $n \times n$ grid ordered by nested dissection. The special
structure of this problem allows us to make exact estimates of
the complexity. To our knowledge, the m-tree previously has not been applied in this
fashion to the numerical factorization, but it has been used,
directly or indirectly, in several optimal order algorithms for
computing the fill-in during the symbolic factorization phase
[4] - [10], [5], [6].

In \S 1.2, we review the bordering algorithm, and introduce
the sorting and intersection problems that arise in the
sparse formulation of the algorithm.
In \S 1.3., we analyze the complexity of the old and new
approaches to the intersection problem for the special case of
an $n \times n$ grid ordered by nested dissection. The special
structure of this problem allows us to make exact estimates of
the complexity. To our knowledge, the m-tree previously has not been applied in this
fashion to the numerical factorization, but it has been used,
directly or indirectly, in several optimal order algorithms for
computing the fill-in during the symbolic factorization phase
[4] - [10], [5], [6].


For the old approach, we show that the
complexity of the intersection problem is $O(n^{3})$, the same
as the complexity of the numerical computations.  For the
new approach, the complexity of the second part is reduced to
$O(n^{2} (\log n)^{2})$.

To our knowledge, the m-tree previously has not been applied in this
fashion to the numerical factorization, but it has been used,
directly or indirectly, in several optimal order algorithms for
computing the fill-in during the symbolic factorization phase
[4] - [10], [5], [6]. In \S 1.3., we analyze the complexity of the old and new
approaches to the intersection problem for the special case of
an $n \times n$ grid ordered by nested dissection. The special
structure of this problem allows us to make exact estimates of
the complexity. To our knowledge, the m-tree previously has not been applied in this
fashion to the numerical factorization, but it has been used,
directly or indirectly, in several optimal order algorithms for
computing the fill-in during the symbolic factorization phase
[4] - [10], [5], [6].
This is accomplished by exploiting the m-tree,
a particular spanning tree for the graph of the filled-in matrix.
To our knowledge, the m-tree previously has not been applied in this
fashion to the numerical factorization, but it has been used,
directly or indirectly, in several optimal order algorithms for
computing the fill-in during the symbolic factorization phase
\cite{EISENSTAT} - \cite{LIU2}, \cite{ROSE76},  \cite{SCHREIBER}.


\section{Old Experimental results}  


We use 3 different real-world datasets: 
    (i) Deep learning model: MobileNetV2 model trained on Imagenet dataset after quantization of the model weights\cite{HanMD15}; 
    (ii) JPEG: George H. W. Bush's face image\cite{gwbush} from the Labeled Faces in the Wild, image database; and 
    (iii) Text: The King Jame's Version of the Bible (beginning 10\% of the text).
For MobileNetV2, we use 256 levels of quantization on the weights unless specified otherwise.

There have been several works that reduce the decode time of prefix encodings.
One of the more popular and effective schemes is that of table lookups.
In \cite{634683}, the authors compare several algorithms that improve decode time
and demonstrate the effectiveness of table lookups.
As mentioned before, our work also builds on table lookups.
In our experiments we consider table lookups with Huffman encoding as a baseline to compare the speedups
obtained with our algorithms; thus the speedups can be attributed to the restructuring of
the prefix trees by our algorithms.
We report speedup achieved in decode-time for our algorithm
compared to the decode-time of Huffman encoding when using lookup tables with the same blocking schemes. 

The decode-time is calculated directly from the blocking scheme and the prefix tree. We also implement
the decode routine on the GPU. We ran our experiments on the Tesla K40 GPU with the first 
level block (lookup table) residing in the shared memory. 
As noted before this memory is shared by many threads.
We run the decode routine using a single thread to measure the speedup 
(this avoids any unwanted effects due to thread parallelism).

\paragraph{Effect of permitted code length parameter ($L$):}
We first study the speedup
when we relax the ${\cal L}$ parameter to 1\%, 2\%, 5\% and 10\% more than Huffman encoding code length.
The results obtained with the exact DP (Algorithm~\ref{alg:exact}) are shown in Figure~\ref{fig:results} (a). 
As expected, the speedup increases as we relax the permitted code length. 
It is interesting to note that even with as little as 2\% relaxation in ${\cal L}$, we see an improvement of
7.5\% to 15\% in the decode time across the data sets.
The results with the pseudo approximation DP (Algorithm~\ref{alg:pseudo}) are shown in Figure~\ref{fig:results2} (a). 
We note that the decode-time speedups are observed to be almost the same as with the case of the exact DP.

\paragraph{Effect of the alphabet size ($n$):}
We next study the effect of different alphabet sizes on the decode time.
We use different levels of quantization in the MobileNetV2 model to generate alphabets of different sizes,
namely 256, 128 and 64 characters.
The results obtained with the exact DP (Algorithm~\ref{alg:exact}) are shown in the table in Figure~\ref{fig:results} (b). 
It can be noted that speedups drop as the alphabet size is reduced.
This is expected as there is not much rearrangement possible with a very small alphabet
and most of the characters fit in the lower level blocks.
The results with the pseudo approximation DP (Algorithm~\ref{alg:pseudo}) are shown in Figure~\ref{fig:results2} (b). 
We note that we obtain better decode-time speedups in comparison to the exact DP for the same alphabet sizes;
this is attributed to the flexibility in prefix tree configurations due to the additional 1\% relaxation
allowed in the code length.
As this algorithm is more efficient in comparison to the exact DP,
we are able to run this with larger alphabet sizes of 512 and 1024 as well (which we were not able
to run with the exact DP).
As before, speedups increase with increase in alphabet size due to the possibility of more arrangements.


\paragraph{Effect of the access cost ($q$):}
In hierarchical memory settings, top (lower) level blocks are kept in faster memory as they are accessed more often and
and the access time, $q$, increases as we go to the blocks at the bottom level that are kept in slower memory. 
We consider reasonable approximations of $1$ cycle, $20$ cycles and $100$ cycles for the L1, L2 caches and main memory
access costs respectively. Thus, with a blocking scheme of $<$$(4,1),(4,20),(4,100),(4,100),\ldots$$>$ 
where the tables from $3^{rd}$ level onwards are kept in the main memory, 
we study the effect of setting the ${\cal L}$ parameter to 1\%, 2\%, 5\% and 10\% more than 
Huffman encoding code length on the speedup. 
The results obtained with the exact DP (Algorithm~\ref{alg:exact}) are shown in the table in Figure~\ref{fig:results} (c).
We observe significant speedups of up to 3x in the decode time. Even with just 2\% relaxation for ${\cal L}$,
we observe a 2x speedup. To analyze this further, we record the number of characters encoded at each block level.
These are shown in Figure~\ref{fig:results} (d).
We can see that this gain can be attributed to our algorithm moving more characters 
to lower level blocks having lower access cost.
We see that higher the relaxation, more are the characters that are moved to the lower level blocks.

\begin{figure}[t!]
\centering
\begin{minipage}{.45\textwidth}
    \centering
    \includegraphics[width=2.5in]{kjb_full3.pdf}
    \captionof{figure}{\small Speedups obtained for KJB using the block Huffman coding scheme
             with the pseudo-approximation algorithm (Algorithm~\ref{alg:pseudo}) employing $\epsilon=0.01$
             and block sizes $<(8,1),(8,20),(8,20),\ldots>$ and 
             $<(4,1),(4,20),(4,20),(4,20),\ldots>$.}
            
    \label{fig:my_label}
 
\end{minipage
\ \ \ \ 
\begin{minipage}{.52\textwidth}
    \small
    \centering
    \begin{tabular}{ r|r  }
             \hline
             Alphabet & Speedup on GPU \\
             size \ \ \ \ & \\
             \hline \hline
            1024 \ \ \ \ & 1.26 \ \ \  \\
            512 \ \ \ \ & 1.10 \ \ \  \\
            256 \ \ \ \ & 1.15 \ \ \  \\
            128 \ \ \ \ & 1.08 \ \ \ \\
            64 \ \ \ \ & 1.01 \ \ \ \\
             \hline
    \end{tabular}
    \captionof{figure}{\small Speedup obtained on the GPU for Mobilenet-V2 with varying quantization states (alphabet size)
             using the pseudo-approximation
             algorithm (Algorithm~\ref{alg:pseudo}) with $\epsilon=0.01$. 
             The first level lookup table is kept in the shared memory.
             All lookup tables are 4-bit.  }
    \label{fig:gpu_exp}
   
\end{minipage}
\end{figure}

The corresponding results with the pseudo approximation DP (Algorithm~\ref{alg:pseudo}) are shown in 
Figure~\ref{fig:results2} (c) and (d) respectively. 
We note that there is considerable improvement in the speedups when compared to the exact DP.
This is again attributed due to the additional $1\%$ relaxation allowed in the code length.
Figure~\ref{fig:results2} (d) demonstrates that code length relaxation results in more characters
being pushed into the low cost lower level blocks in comparison to the exact DP (Figure~\ref{fig:results} (d)).


\paragraph{Effect of lookup table size:}
We next run experiments with different lookup table sizes.
We consider a larger first level memory that can hold $256$ entries.
We consider two different blocking schemes of $<$$(8,1),(8,20),(8,20),\ldots$$>$ and 
$<$$(4,1),(4,20),(4,20),(4,20),\ldots$$>$.
We use the KJB data set. In this experiment, we use the block Huffman coding scheme
described by Mannan and Kaykobad\cite{bhuffman}, which is often used in practice.
In this scheme, the alphabet is constructed by creating blocks of fixed number of characters from the input
and treating these blocks as the new alphabet.
This leads to better compression ratios~ \cite{bhuffman}. 
In our experiment, the alphabet is created by combining every pair of characters appearing in the input.
We observe considerable gains in the speedup for the blocking schemes
with larger lookup tables {as it allows more characters with high frequencies in the first cache level after restructuring.} 



\paragraph{Experiments on GPU:}
We implemented our lookup table based decoding on the GPU.
We experiment with the Mobilenet-V2 dataset for different alphabet sizes.
using a blocking scheme of $<(4,1),(4,1),\ldots>$.
The results are shown in Figure~\ref{fig:gpu_exp}.
The first level block is kept in the shared memory and the remaining blocks are kept 
on the GPU device memory.
We see reasonable speedups with different alphabet sizes;
with alphabet size 1024, we obtain 26\% speedup.
These speedups are quite consistent with the speedups obtained directly using the model
(See Figure~\ref{fig:results2} (b)).



\eat{
\paragraph{Effect of Block size}
We next study the speedup trends with varying values of the block width, $w$.
The table in Figure~\ref{fig:results} (c) shows the speedup obtained for MobileNetV2 when the block parameters
are uniformly all set to $(w,1)$ with as many block levels used as required, and $w$ is varied to take values $4,6,8,10$.

\paragraph{Effect of Alphabet size}
for the following blocking schemes($BS$):  denotes, <(4,1),(4,1),\ldots>, $BS$ of constant block width and constant access cost q; $Vw-Cq$ denotes, <(2,1),(4,1),(6,1),\ldots>, $BS$ of variable block width and constant access time; $Vw-Vq$ denotes, <(2,1),(4,20),(6,100),(8,100),\ldots>, $BS$ of variable block width and variable access time The relaxation is kept constant to 2\%. $Vw-Vq$ has higher speedup becuase of variable access cost, $Cw-Cq$ and $Vw-Cq$ have similar gains as all the block levels are indistinguishable in memory cost due to constant access costs. With increase in $n$ there is a steep rise in speedup i.e., even with as little as 2\% relaxation in compression, we can restructure the Huffman tree, with respect to the memory structure, in order to gain big amounts in decode time.

}











   

