\documentclass{beamer}
\usetheme{Boadilla}
\usepackage[utf8]{inputenc}
\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage{graphicx}
\usepackage{float}
\usepackage{subfig}
\usepackage{color}
\newcommand{\mysource}[1]{\par\hfill \footnotesize Source:~\itshape#1}
\title{Distributed Fault Tolerant Linear System Solver Based on Erasure Coding\\
\vspace{1cm}}
\author{Xuejiao Kang, David Gleich, Ahmed Sameh, and Ananth Grama}
\institute{Computer Science\\
Purdue University--West Lafayette}
\date{\today}

\begin{document}

\begin{frame}
\titlepage
\label{title-p1}
\end{frame}




\begin{frame}
\frametitle{Outline}
\label{outline-p3}
\begin{itemize}
	\item \Large Background and Motivation
	\item \Large Erasure Coded Linear System Solver
	\item \Large Coding Matrix
	\item \Large Distributed Implementation
	\item \Large Experimental Evaluation
	\item \Large Plan of Research 
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Background: Faults in Parallel and Distributed Systems}
\label{background-p11}
\begin{itemize}
\item \Large As parallel systems scale to millions of cores, faults become one of the most critical challenges.
\item \Large As data centers scale to hundreds of thousands of nodes, faults are a prime consideration for distributed computations.
\item \Large As networks scale from data center to wide area, network faults and partitions constitute a major consideration for wide area distributed computations.
\end{itemize}
\end{frame}


\begin{frame}
\frametitle{Background: Fault Tolerance}
\label{background-p2}
\vspace{-0.5cm}
\Large Algorithmic methods and system-supported approaches. 
\pause
\vspace{0.25}
\begin{itemize}
	\item \Large Algorithmic methods alter the algorithm to make it robust to faults. \\
	\pause
	\vspace{0.5cm}
	\item \Large System-supported methods include checkpoint-restart, active replicas, and 
deterministic replay. 
	\pause
	\vspace{0.45cm}
		\begin{itemize}
			\item \large Checkpoint-restart schemes involve need for consistent checkpointing and potentially high I/O throughput and capacity.
			\pause
			\vspace{0.35cm}
			\item \large Active replicas execute multiple replicas of each task, with associated resource overheads.
			\vspace{0.35cm}
			\item \large Deterministic replay increases job makespan in the event of multiple faults.
		\end{itemize}
	%This requires deep algorithmic and analytical insight to the faults tolerance properties and algorithms. Also, this may change the algorithmic cost and complexity.
\end{itemize}
\end{frame}


%\begin{frame}
%\frametitle{Background}
%\label{background-p22}
%	System-supported methods include checkpoint-				restart, active replicas. 
	%\begin{itemize}
	%	\item Checkpoint-restart schemes involve the  of consistent checkpointing and I/O.% which are expensive for emerging ultra-scale platforms, where I/O capacity and bandwidth are both at a premium relative to the high compute capability.
		%\item Active replicas execute multiple replicas of each task. %The resource overhead of such schemes are high, since tolerating $k$ failures among $p$ processors requires $(k+1)p$ compute elements.
	%\end{itemize}
%\end{frame}



%\begin{frame}
%\frametitle{Background: Fault Tolerant Storage}
%\label{background-p4}
	%Erasure coding schemes augment the data in such a way that the original data can be reconstructed from a subset of the augmented data.
%\Large To tolerant $k$ disk failures for data size $n$, the replicated storage system requires $n(k+1)$ storage, while 
%erasure code just requires $n+k$ storage.
%\begin{figure}
%\includegraphics[scale=0.4]{../storage.png} 
%\end{figure}
%\end{frame}






\begin{frame}
\frametitle{Background: Erasure Codes}
\label{ECC-p2}
\vspace{-0.25cm}
Erasure codes are derived from the Error Correcting Codes, and are typically used in storage systems to deal with known data erasures or loss.
%\large Consider a code that augments $k$ items of data with $m$ redundant items, for a total of $n=k+m$ stored items. %If the code can correct $m$ errors, then the code is space-optimal and is referred to as Maximum Distance Separable(MDS).
\begin{figure}[H!]
    \centering
        \includegraphics[scale=0.45]{./figures/erasure-eps-converted-to.pdf}
    \end{figure}
 \end{frame}


\begin{frame}
\frametitle{Erasure Coded Computations}
\label{ECC-p3}
\vspace{-1cm}
%\Large Compared to ECC and Erasure coded storage, the erasure coded computations have several significant differences.

We propose a novel concept called {\em erasure coded computation}. In such computations:
\begin{itemize}
	\item \large The goal is to code the result of a computation in a fault tolerant manner, as opposed to data;
	%\pause
	\vspace{0.3cm}
	\item \large Data is not in the form of linear bit strings or blocks but higher order structures such as sparse matrices;
	%\pause
	\vspace{0.3cm}
	\item \large Recovery is numerical in nature (as opposed to computation over a finite field), and therefore easier on conventional hardware.;
	%\item \large Erasure coded computations must deal with failure modes other than erasures.
\end{itemize}
\end{frame}

%\begin{frame}
%\frametitle{Background: Erasure Coded Computation Basic Kernels}
%\label{ECC-p4}
%\vspace{-0.25cm}
%We have showed the idea for erasure coded computations in a simple form for a sparse matrix-vector product.% Assume the matrix is partitioned row-wise across processors.

%\begin{figure}[H!]
 %   \centering
  %      \includegraphics[scale=0.45]{../figures/fig2-1}
%\end{figure}
%\end{frame}


\begin{frame}
\frametitle{Erasure Coded Computation Basic Kernels}
\label{ECC-p5}
\vspace{-0.25cm}
We pre-multiply the given matrix with a coding matrix (also called a distribution matrix) to
obtain an augmented matrix.


%The first $k$ rows of the matrix remain unchanged because of the identity block of rows in the distribution  matrix. The last row is the negative sum of all other rows.
\begin{figure}[H!]
    \centering
        \includegraphics[scale=0.33]{./figures/fig2-2}
\end{figure}
\end{frame}


\begin{frame}
\frametitle{Erasure Coded Computation Basic Kernels}
\label{ECC-p6}
The structure of the distribution matrix allows us to control the structure/ fill in the augmented matrix. This augmented matrix is distributed across nodes to implement a distributed solver. %The augmentation block can itself be distributed among processors for load balance.
\begin{figure}[H!]
    \centering
        \includegraphics[scale=0.33]{./figures/fig2-3}
\end{figure}
\end{frame}

\begin{frame}
\frametitle{Fault Oblivious Distributed Solver: Overview}
\label{background-p5}
\vspace{-1cm}
\Large The concept of fault-oblivious execution based on erasure coded computations is as follows:
\pause
\vspace{0.3cm}
\begin{itemize}
	\item \Large Augment the given input matrix using a suitable distribution matrix.
	\pause
	\vspace{0.3cm}
	\item \Large Execute the solver (in our case, a conjugate gradient solver) on the augmented input in a faulty environment (while being oblivious to faults) to generate an augmented output.
	\pause
	\vspace{0.3cm}
	\item \Large Compute the true output based on the augmented output from the faulty execution.
\end{itemize}
\end{frame}


\begin{frame}
\frametitle{Challenges for Fault Oblivious Execution}
\label{Motivation and Challenges}
\vspace{-0.5cm}
Extending benefits of erasure coding for storage to fault-tolerant computations on linear systems poses a number of challenges.
 \pause
\vspace{0.25cm}
\begin{itemize}
	\item Finding suitable suitable distribution matrices that satisfy required properties, while minimizing fill and reducing communication.
	\pause
	\vspace{0.1cm}
	\item Must be able to use traditional linear system solvers on the augment system.
	\pause
	\vspace{0.1cm}
	\item Easily recover the true solution from augmented solution from potentially faulty execution.
	\pause
	\vspace{0.1cm}
	\item Deliver high parallel/ distributed performance.
	\pause
	\vspace{0.1cm}
	\item Tolerate different fault rates and arrival types.
\end{itemize}
\end{frame}


\begin{frame}
\frametitle{Outline}
\label{outline-t3}
\begin{itemize}
	\item \Large Background and Motivation
	%\item \Large Erasue Correcting Codes,Storage and Computation
	\item \Large \textcolor{red}{Erasure Coded Linear System Solver}
	\item \Large Coding Matrix
	\item \Large Parallel Implementation
	\item \Large Experimental Evaluation
	\item \Large Plan of Research 
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Erasure Coded Linear System Solver}
\label{linearsolver-p1}
\vspace{-0.5cm}
\large For the original system $Ax=b$($A_{n\times n}$ is $SPD$), we have the true solution for $x^*$. Given coding matrix $E_{n \times k}$, we construct the augmented system $\tilde{A}\tilde{x}=\tilde{b}$.\\
\begin{equation}
\tilde{A}=\left[ \begin{array}{cc}
A & AE\\
E^{T}A & E^{T}AE
\end{array} \right], 
\end{equation}
\begin{equation}
\tilde{x}=\left[\begin{array}{c}
x^*\\
0\\ 
\end{array}\right]
\end{equation}

\begin{equation}
\tilde{b}=\left[\begin{array}{c}
b\\
E^{T}b\\ 
\end{array}\right]
\end{equation}
\end{frame}


\begin{frame}
\frametitle{Erasure Coded Linear System Solver}
\label{linearsolver-p2}
Properties of the augmented system can help us recover true solution for the original system:\\
	\begin{itemize}
		\item If $A$ is $SPD$, then $\tilde{A}$ is $SPSD$.
		\item A null space basis of $\tilde{A}$ is $\left[\begin{array}{c}
													E\\
													-I_k\\
													\end{array}\right]$	
		\item Any solution of the augmented system can be written as 			        \begin{equation}
		\left[\begin{array}{c}
				y\\
				z\\ 
				\end{array}\right]=\left[\begin{array}{c}
x*\\
0\\ 
\end{array}\right]+a*\left[\begin{array}{c}
E\\
-I_k\\ 
\end{array}\right]
		\end{equation}
	\end{itemize}
	Based on the properties of $\tilde{A}$, we can recover the true solution as follows:
\begin{equation}
\left[ \begin{array}{c}
x^*\\
0\\
\end{array} \right]=\tilde{x}+\left[ \begin{array}{c}
E\\
-I_k\\
\end{array} \right]r
\end{equation}
\end{frame}






%\begin{frame}
%\frametitle{Erasure Coded Linear System Solver}
%\label{linearsolver-p5}
%\vspace{-0.5cm}
%\large For our erasure coded solver, we need a condition on matrix $E$ such that:
%\vspace{0.3cm}
%	\begin{itemize}
%		\item There is always a solution to the augmented system for faults happening on any rows as long as total number of faults$\leq k$.
%		\vspace{0.3cm}
%		\item Given any solution computed with faulty components, we can extract and recover a solution for the original system.
%	\end{itemize}
%	\vspace{0.3cm}
%\end{frame}










\begin{frame}
\frametitle{Outline}
\label{outline-t4}
\begin{itemize}
	\item \Large Background and Motivation
	\item \Large Erasue Correcting Codes,Storage and Computation
	\item \Large Erasure Coded Linear System Solver
	\item \Large \textcolor{red}{Coding Matrix}
	\item \Large Parallel Implementation
	\item \Large Experimental Evaluation
	\item \Large Plan of Research 
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Coding Matrix}
\label{encoding-p1}
\large The choice of distribution matrix $E$ is critical:
\begin{itemize}
	\item \large Matrix $E$ should satisfy  properties of kruskal rank:
	\begin{block}
	\large Matrix $E$ is Kruskal rank $k$ iff every subset of $k$ rows of matrix $E$ is linearly independent.
	\end{block}
	\item \large It should be as sparse as possible to minimize fill in the augmented matrices.
\end{itemize}
\large One such $E$ matrix can be constructed by inserting $p$ nonzeros (randomly instantiated) in each row in a cyclic-staggered fashion: \\
\vspace{0.5cm}
\begin{columns}
\column{0.5\textwidth}
\left[\begin{array}{cccccc}
x&x&x&0&0&0\\
0&x&x&x&0&0\\
0&0&x&x&x&0\\
0&0&0&x&x&x\\
x&0&0&0&x&x\\
x&x&0&0&0&x\\
\end{array}\right]
\column{0.5\textwidth}
\theoremstyle{definition}
\begin{definition}
A $n \times k$ matrix $E$ satisfies the recovery-at-random property if a random subset of $k$ rows(selected uniformly with replacement) is rank $k$ with probability approaching 1.
\end{definition}
\end{columns}
\end{frame}



\begin{frame}
\frametitle{Coding matrix}
\label{encoding-p2}
%\vspace{-1cm}
To keep the coding matrix and the associated augmented matrix sparse, $p$ should as small as possible. %Next theorem will give the expected maximum number of rows that share the same non-zero structure, and will help us select the most suitable $p$.\\
\begin{block}{Proposition}
\large Let $p$ is the number of nonzeros per row in $E$ and Let $E'$ be a submatrix of $E$ formed by selecting any $p$ rows of matrix $E$. The matrix $E'^{T}$ has rank $p$.
\end{block}

\theoremstyle{Theorem}
\begin{theorem}
\large The probability that a randomly chosen set of $k$ rows from matrix $E$ are linearly dependent is less than $(\frac{e}{p+1})^{p+1}$.
\end{theorem}

\theoremstyle{Theorem}
\begin{theorem}
\large The expected number of rows from among $k$ randomly selected rows of matrix $E$ that have same nonzero structure is $O(\frac{\ln k}{\ln\ln k})$.
\end{theorem}

\end{frame}



\begin{frame}
\frametitle{Outline}
\label{outline-t5}
\begin{itemize}
	\vspace{-1cm}
	\item \Large Background and Motivation
	%\item \Large Erasue Correcting Codes,Storage and Computation
	\item \Large Erasure Coded Linear System Solver
	\item \Large Coding Matrix
	\item \Large \textcolor{red}{Parallel Implementation}
	\item \Large Results
	\item \Large Research Plan
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Parallel Implementation of Erasure Coded CG}
\label{CG-1}
\vspace{-0.2cm}
\large Since $A$ is $SPD$ and $\tilde{A}$ is $SPSD$, and we can apply CG to the augmented system.
\begin{algorithm}[H]
\caption{Fault Oblivious CG with a two-term recurrence. 
When we notice a fault, we set $\beta_t = 0$ at that iteration.}
\begin{algorithmic}[1]
\STATE Let $x_0$ be the initial guess and $r_0=b-Ax_0$, $\beta_0=0$.
\FOR{$t=0,1,\ldots$ until convergence}
\STATE $\beta_{t}^{}=(r_t,r_t)/(r_{t-1},r_{t-1})$
\STATE $p_t=r_t+\beta_t^{} p_{t-1}$
\STATE $q_t=A p_t$
\STATE $\alpha_{t}^{} =(r_t,r_t)/(q_t,p_t)$
\STATE $x_{t+1}=x_t+\alpha_t^{} p_t$
\STATE $r_{t+1}=r_t-\alpha_t^{} q_t$
\ENDFOR
\end{algorithmic}
\end{algorithm}
\end{frame}




\begin{frame}
\frametitle{Parallel Implementation of Erasure Coded CG}
\label{CG-2}
Assume that 
each viable process can detect the breakdown of its neighbor processes.
\begin{itemize}
\item Inner products $(r_t,r_t)$ and $(q_t,p_t)$. %The viable processes carry out the all-reduce operation by skipping the faulty components $F_t$ in the vectors.
\begin{align}
(r_t,r_t) &= \left((r_t)_{[n+k]\backslash F_t},(r_t)_{[n+k]\backslash F_t}\right)
\\
(q_t,p_t) &= \left((q_t)_{[n+k]\backslash F_t},(p_t)_{[n+k]\backslash F_t}\right)
\nonumber
\end{align}
\item Matrix-vector multiplication $q_t=A p_t$. %A viable process carries out its local aggregation operation for computing  $A_{I_i,:} p_t$ by skipping the faulty components $F_t$ in $p_t$.
\begin{align}
A_{I_i,:}p_t &= A_{I_i,[n+k]\backslash F_t}(p_t)_{[n+k]\backslash F_t}
\end{align}
\item When we observe a fault,
we truncate the update $p_t=r_t+\beta_t p_{t-1}$ to be
\begin{align}
p_t &= r_t.
\end{align}
This corresponds to a reset of the Krylov process. 
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Parallel Implementation of Erasure Coded CG}
\label{CG-3}
Metis is used to reorder the Original and Augmented matrices. 
\begin{columns}
\column{0.5\textwidth}

\begin{block}{Original Matrix}
\begin{figure}[H!]
    \centering
        \includegraphics[width=1.625in,height=1in]{./figures/bcsstk18_orig.png}
    \end{figure}
\end{block}

\begin{block}{Reordered Original Matrix}
\begin{figure}[H!]
    \centering
        \includegraphics[width=1.625in,height=1in]{./figures/bcsstk18_orig_reorder.png}
        %\label{fig:bcsstk18_orig_reorder}
\end{figure}
\end{block}
   
\column{0.5\textwidth}
	\begin{block}{Augmented Matrix}
	\begin{figure}[H!]
    \centering
        \includegraphics[width=1.625in,height=1in]{./figures/bcsstk18_aug.png}
        %\label{fig:bcsstk18_aug}
    \end{figure}
	\end{block}

	\begin{block}{Reordered Augmented Matrix}
	\begin{figure}[H!]
    \centering
        \includegraphics[width=1.625in,height=1in]{./figures/bcsstk18_aug_reorder.png}
        %\label{fig:bcsstk18_aug_reorder}
	\end{figure}
	\end{block}
\end{columns} 
\end{frame}
















\begin{frame}
\frametitle{Outline}
\label{outline-t6}
\vspace{-1cm}
\begin{itemize}
	\item \Large Background and Motivation
	%\item \Large Erasue Correcting Codes,Storage and Computation
	\item \Large Erasure Encoded Linear System Solver
	\item \Large Coding Matrix
	\item \Large Parallel Implementation
	\item \Large \textcolor{red}{Experimental Evaluation}
	\item \Large Plan of Research 
\end{itemize}
\end{frame}

%\begin{frame}
%\frametitle{Experiment Results: Outline}
%\label{results outline-t1}
%\vspace{-0.5cm}
%\begin{itemize}
%	\item \Large \textcolor{red}{Data and Experiment Settings}
%	\vspace{0.25cm}
%	\item \Large Convergence of Systems
%	\vspace{0.25cm}
%	\item \Large Parallel Performance of the Solver on Augmented 			Systems
%	\vspace{0.25cm}
%	\item \Large Effect of Fault Rate on Results
%	\vspace{0.25cm}
%	\item \Large Effect of Fault Pattern on Convergence
%\end{itemize}
%\end{frame}

\begin{frame}
\frametitle{Input Matrices and Experiments Setting}
\label{input matrix}
\large Four matrices from University of Florida Matrix Collection
\begin{center}
\begin{tabular}{|c|c|c|}
\hline
Name & Rows & Nonzeros\\
\hline \hline
bcsstk18 & 11948 & 149K\\
\hline
cfd2 &123440 &3085K\\
\hline
inline&503712&36816K\\
\hline
Geo$\_$1438 &1438976&60236K\\
\hline
\end{tabular}
\end{center}
\begin{itemize}
	\item \large Maximum iteration counts are set to 10000,10000,25000, and 50000, respectively.
	\item \large Relative error tolerance is set to 1e-10 for all matrices.
	\item \large In initial set of experiments, the faults arrive uniformly starting from iteration 1000, and occur every 100 iterations.
\end{itemize}
\end{frame}






\begin{frame}
\frametitle{Experiment Results: Outline}
\label{results outline-t2}
\vspace{-1cm}
\begin{itemize}
	\item \Large Data and Experiment Settings
	\vspace{0.4cm}
	\item \Large Convergence of Original and Augmented Systems
	\vspace{0.4cm}
	\item \Large Parallel Performance of the Solver on Augmented 			Systems
	\vspace{0.4cm}
	\item \Large Effect of Fault Rate on Results
	\vspace{0.4cm}
	\item \Large Effect of Fault Pattern on Convergence
\end{itemize}
\end{frame}


%\begin{frame}
%\frametitle{Convergence of Original and Augmented Systems-1}
%\label{conv-1}
% Compute the relative error w.r.t the augmented systems.
%\begin{figure}[htbp]
 %   \centering
  %  \subfloat[bcsstk18}]{
   %     \includegraphics[width=1.8in,height=1.2in]{f11_bcsstk18.png}}
    %\subfloat[cfd2]{
     %   \includegraphics[width=1.8in,height=1.2in]{f11_cfd2.png}}
% \end{figure}
 % \vspace{-1cm}
 %\begin{figure}[htbp]
  %  \centering
   % \subfloat[inline]{
    %    \includegraphics[width=1.8in,height=1.2in]{f11_inline.png}}
    %\subfloat[Geo\_1438]{
     %   \includegraphics[width=1.8in,height=1.2in]{f11_Geo.png}}
%\end{figure}
%\end{frame}

\begin{frame}
\frametitle{Convergence of Original and Augmented Systems}
\label{convergence}
%\Large Compute the relative error w.r.t the original systems.
\vspace{-0.5cm}
\begin{figure}[htbp]
    \centering
    \subfloat[bcsstk18]{
        \includegraphics[width=1.8in,height=1.2in]{./figures/f12_bcsstk18.png}}
    \subfloat[cfd2]{
        \includegraphics[width=1.8in,height=1.2in]{./figures/f12_cfd2.png}}
 \end{figure}
  \vspace{-1cm}
 \begin{figure}[htbp]
    \centering
    \subfloat[inline]{
        \includegraphics[width=1.8in,height=1.2in]{./figures/f12_inline.png}}
    \subfloat[Geo\_1438]{
        \includegraphics[width=1.8in,height=1.2in]{./figures/f12_Geo.png}}
\end{figure}
\end{frame}

%\begin{frame}
%\frametitle{Experiment Results: Outline}
%\label{results outline-t3}
%\vspace{-1cm}
%\begin{itemize}
%	\item \Large Data and Experiment Settings
%	\vspace{0.4cm}
%	\item \Large Convergence of Original and Augmented Systems
%	\vspace{0.4cm}
%	\item \Large \textcolor{red}{Parallel Performance of the Solver on Augmented 			Systems}
%	\vspace{0.4cm}
%	\item \Large Effect of Fault Rate on Results
%	\vspace{0.4cm}
%	\item \Large Effect of Fault Pattern on Convergence
%\end{itemize}
%\end{frame}

\begin{frame}
\frametitle{Parallel Performance of Augmented System}
\label{pp-1}
\begin{figure}[htbp]
    \centering
    \subfloat[bcsstk18]{
        \includegraphics[width=1.8in,height=1.2in]{./figures/f2_bcsstk18.png}}
    \subfloat[cfd2]{
        \includegraphics[width=1.8in,height=1.2in]{./figures/f2_cfd2.png}}
 \end{figure}
  \vspace{-1cm}
 \begin{figure}[htbp]
    \centering
    \subfloat[inline]{
        \includegraphics[width=1.8in,height=1.2in]{./figures/f2_inline.png}}
    \subfloat[Geo\_1438]{
        \includegraphics[width=1.8in,height=1.2in]{./figures/f2_Geo.png}}
\end{figure}
\end{frame}



\begin{frame}
\frametitle{Speedups of Augmented Systems}
\label{speed-1}
\begin{figure}[htbp]
    \centering
    \subfloat[bcsstk18]{
        \includegraphics[width=1.8in,height=1.2in]{./figures/f3_bcsstk18.png}}
    \subfloat[cfd2]{
        \includegraphics[width=1.8in,height=1.2in]{./figures/f3_cfd2.png}}
 \end{figure}
  \vspace{-1cm}
 \begin{figure}[htbp]
    \centering
    \subfloat[inline]{
        \includegraphics[width=1.8in,height=1.2in]{./figures/f3_inline.png}}
    \subfloat[Geo\_1438]{
        \includegraphics[width=1.8in,height=1.2in]{./figures/f3_Geo.png}}
\end{figure}
\end{frame}

%\begin{frame}
%\frametitle{Experiment Results: Outline}
%\label{results outline-t4}
%\vspace{-1cm}
%\begin{itemize}
%	\item \Large Data and Experiment Settings
%	\vspace{0.4cm}
%	\item \Large Convergence of Original and Augmented Systems
%	\vspace{0.4cm}
%	\item \Large Parallel Performance of the Solver on Augmented 			Systems
%	\vspace{0.4cm}
%	\item \Large \textcolor{red}{Effect of Fault Rate on Results}
%	\vspace{0.4cm}
%	\item \Large Effect of Fault Pattern on Convergence
%\end{itemize}
%\end{frame}


\begin{frame}
\frametitle{Effect of Fault Rate on Convergence}
\label{rate-1}
\begin{figure}[htbp]
    \centering
    \subfloat[bcsstk18]{
        \includegraphics[width=1.8in,height=1.2in]{./figures/f4_bcsstk18.png}}
    \subfloat[cfd2]{
        \includegraphics[width=1.8in,height=1.2in]{./figures/f4_cfd2.png}}
\vspace{-1cm}
 \end{figure}
 \begin{figure}[htbp]
    \centering
    \subfloat[inline]{
        \includegraphics[width=1.8in,height=1.2in]{./figures/f4_inline.png}}
    \subfloat[Geo\_1438]{
        \includegraphics[width=1.8in,height=1.2in]{./figures/f4_Geo.png}}
\end{figure}
\end{frame}

%\begin{frame}
%\frametitle{Experiment Results: Outline}
%\label{results outline-t5}
%\vspace{-1cm}
%\begin{itemize}
%	\item \Large Data and Experiment Settings
%	\vspace{0.4cm}
%	\item \Large Convergence of Original and Augmented Systems
%	\vspace{0.4cm}
%	\item \Large Parallel Performance of the Solver on Augmented 			Systems
%	\vspace{0.4cm}
%	\item \Large Effect of Fault Rate on Results
%	\vspace{0.4cm}
%	\item \Large \textcolor{red}{Effect of Fault Pattern on Convergence}
%\end{itemize}
%\end{frame}

\begin{frame}
\frametitle{Convergence for Different Fault Arrival Patterns}
\label{arrival-1}
\begin{figure}[htbp]
    \centering
    \subfloat[bcsstk18]{
        \includegraphics[width=1.8in,height=1.2in]{./figures/f51_bcsstk18.png}}
    \subfloat[cfd2]{
        \includegraphics[width=1.8in,height=1.2in]{./figures/f51_cfd2.png}}
 \end{figure}
 \vspace{-1cm}
 \begin{figure}[htbp]
    \centering
    \subfloat[inline]{
        \includegraphics[width=1.8in,height=1.2in]{./figures/f51_inline.png}}
    \subfloat[Geo\_1438]{
        \includegraphics[width=1.8in,height=1.2in]{./figures/f51_Geo.png}}
\end{figure}
\end{frame}

\begin{frame}
\frametitle{Conclusion}
\label{conclusion}
We present a new concept called erasure coded computation and demonstrate it in the context of 
a fault oblivious linear system solver. \\
\begin{itemize}
	\item Such schemes have the potential for radically lower resource requirements for
fault tolerance.
	\item They can adapt to varying fault arrival models.
	\item They are highly adaptive in terms of tradeoffs between maximum faults tolerated and associated computation overheads.
	\item The scheme can be applied to a number of other important computational kernels (forthcoming work).
\end{itemize}
\end{frame}



%\begin{frame}
%\frametitle{Preliminary Results on Eigensolver}
%\label{pagerank_intro}
%\LARGEWhat PageRank: \normal A method for rating the importance of web pages objectively and mechanically using the link structure of the web\\
%As number of web pages increases every year, thus Pagerank is very important. 
%\vspace{-0.5cm}
%\begin{figure}[H!]
 %   \centering
  %      \includegraphics[scale=0.35]{../pagenumber.png}
  %  \end{figure}

%\end{frame}


%\begin{frame}
%\frametitle{PageRank}
%\label{pagerank-example}
%\begin{columns}
%\column{0.5\textwidth}
%\Large An example page graph.
%\begin{figure}[H!]
%\includegraphics[scale=0.5]{../pagerank.png} 
%\end{figure}
%\column{0.5\textwidth}
%\begin{block}{Adjacency Matrix A}
%\left[\begin{array}{ccccc}
%0 & 1 & 0 & 1 & 1\\
%1&0&1&1&1\\
%0&1&0&1&0\\
%1&1&1&0&1\\
%1&0&0&1&0
%\end{array}\right]
%\end{block}

%\begin{block}{Degree Matrix D}
%\left[\begin{array}{ccccc}
%3 & 0 & 0 & 0 & 0\\
%0&4&0&0&0\\
%0&0&2&0&0\\
%0&0&0&4&0\\
%0&0&0&0&2
%\end{array}\right]
%\end{block}
%\end{columns}
%\end{frame}

%\begin{frame}
%\frametitle{Google Matrix}
%\label{google matrix}
%\vspace{-0.5cm}
%\Large Let $A$ is the Adjacency matrix and $D$ is the Degree matrix for a graph.\\
%\begin{itemize}

%\item \Large The correspond column random matrix for a graph:
%\begin{center}
%$P=A^T D^{-1}$.
%\end{center} 
%\vspace{0.3cm}
%\item \Large The Google Matrix is constructed as follows:\\
%\begin{center}
%$G=\alpha P+(1-\alpha)\frac{ee^T}{n}$.
%\end{center}
%\vspace{0.3cm}
%\item \Large The power method iteration: $Gx=x$.
%\end{itemize}
%\end{frame}

%\begin{frame}
%\frametitle{Linear System for PageRank}
%\label{linearsys}
%\Large From $Gx=x$, we get the following linear equation:\\
%\begin{center}
%$(I-\alpha P)x=\frac{(1-\alpha)e}{n}$.
%\end{center}
%\Large Multiplying $D^{-1}$ both side:\\
%\begin{center}
%$(D^{-1}-\alpha D^{-1}AD^{-1})x=\frac{(1-\alpha)d}{n}$
%\end{center}
%where $d$ is a column vector constructed from diagonal elements of $D^{-1}$.
%\end{frame}

%\begin{frame}
%\frametitle{Preliminary Results: Data and Setting}
%\label{pagerank data}
%\large Two graph from SNAP of Stanford University
%\begin{center}
%\begin{tabular}{|c|c|c|}
%\hline
%Name & Rows & Nonzeros\\
%\hline \hline
%Slashdot &77360 &905468\\
%\hline
%Email-AllEu & 224832 & 395270 \\
%\hline
%\end{tabular}
%\end{center}

%\begin{itemize}
%	\item \large Maximum Iteration is set as 10000.
%	\item \large Relative error tolerance is set as 1e-15.
%	\item \large Faults arrive uniformly starting from iteration 1000, and occur every 100 iterations.
%\end{itemize}
%\end{frame}

%\begin{frame}
%\frametitle{Preliminary Results: Convergence}
%\label{result-conv}
%\vspace{-0.5cm}
%\begin{figure}[htbp]
 %   \centering
    %\subfloat{
     %   \includegraphics[width=3in,height=1.5in]{../slashdot.png}}
 %\end{figure} 
% \vspace{-0.3cm}
 %\begin{figure}[htbp]
  %  \centering     
   % \subfloat{
    %    \includegraphics[width=3in,height=1.5in]{../Email.png}}
 %\end{figure}
%\end{frame}

\begin{frame}
\frametitle{Acknowledgments}
\label{research plan}
This work is funded by the US Department of Energy and National Science Foundation. \\ \\

Thank you.
\end{frame}


\end{document}
