#LyX 1.5.2 created this file. For more info see http://www.lyx.org/
\lyxformat 276
\begin_document
\begin_header
\textclass article
\begin_preamble



\usepackage{geometry}

%\geometry{verbose,letterpaper,tmargin=1.5in,bmargin=1.25in,lmargin=1in,rmargin=1in,headheight=1in,headsep=1in,footskip=1in}

\input{macros}

\makeatletter

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.

%% Bold symbol macro for standard LaTeX users



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands.
\usepackage{wasysym}


\AtBeginDocument{
  \renewcommand{\labelitemii}{\(\blacktriangleright\)}
}


\makeatother
\end_preamble
\options 12pt
\language english
\inputencoding latin1
\font_roman default
\font_sans default
\font_typewriter default
\font_default_family default
\font_sc false
\font_osf false
\font_sf_scale 100
\font_tt_scale 100
\graphics default
\paperfontsize default
\spacing single
\papersize default
\use_geometry false
\use_amsmath 1
\use_esint 0
\cite_engine basic
\use_bibtopic false
\paperorientation portrait
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\defskip medskip
\quotes_language english
\papercolumns 1
\papersides 1
\paperpagestyle default
\tracking_changes false
\output_changes false
\author "" 
\author "" 
\end_header

\begin_body

\begin_layout Title
Foundations I
\end_layout

\begin_layout Date

\end_layout

\begin_layout Author
Sanjay Rajopadhye
\end_layout

\begin_layout Standard
\begin_inset LatexCommand tableofcontents

\end_inset


\end_layout

\begin_layout Section
Introduction & Motivation
\end_layout

\begin_layout Standard
\begin_inset LatexCommand label
name "sec:intro"

\end_inset


\end_layout

\begin_layout Standard
These notes describe the mathematical foundations of some of the the important
 concepts that we encounter in this class.
 We will cover (i) specification of computations as equations; (ii) a taxonomy
 of equations; (iii) manipulation/transformation of equations; (iii) 
\begin_inset Quotes eld
\end_inset

executing
\begin_inset Quotes erd
\end_inset

 equations (i.e., deriving code from equations); (iv) polyhedra, their representat
ion and their manipulations.
\end_layout

\begin_layout Subsection
Why Equations?
\end_layout

\begin_layout Standard
A large class of algorithms, especially those of interest to this class,
 can be described cleanly and concisely as mathematical equations.
 Here are a few examples.
\end_layout

\begin_layout Paragraph
Forward Substitution
\end_layout

\begin_layout Standard
Given an 
\begin_inset Formula $n\times n$
\end_inset

 lower triangular matrix 
\begin_inset Formula $L$
\end_inset

 (whose diagonal elements are unity), and an 
\begin_inset Formula $m$
\end_inset

-vector, 
\begin_inset Formula $b$
\end_inset

, solve for the vector 
\begin_inset Formula $x$
\end_inset

 in 
\begin_inset Formula $Lx=b$
\end_inset

.
\end_layout

\begin_layout Standard
Let us write down the definition of matrix-vector product:
\end_layout

\begin_layout Standard
\begin_inset Formula \[
b_{i}=\sum_{j=1}^{n}L_{i,j}x_{j}\]

\end_inset


\end_layout

\begin_layout Standard
But since 
\begin_inset Formula $L$
\end_inset

 is lower triangular, every row 
\begin_inset Quotes eld
\end_inset

ends
\begin_inset Quotes erd
\end_inset

 at the diagonal, so the summation can be truncated at 
\begin_inset Formula $i$
\end_inset

, as follows:
\end_layout

\begin_layout Standard
\begin_inset Formula \[
b_{i}=\sum_{j=1}^{i}L_{i,j}x_{j}\]

\end_inset


\end_layout

\begin_layout Standard
Now we take the 
\begin_inset Quotes eld
\end_inset

last term outside the summation
\begin_inset Quotes erd
\end_inset

 to get (after some obvious simplification):
\end_layout

\begin_layout Standard
\begin_inset Formula \[
b_{i}=\left\{ \begin{array}{lcl}
i=1 & : & x_{i}\\
i>1 & : & {\displaystyle x_{i}+\sum_{j=1}^{i-1}L_{i,j}x_{j}}\end{array}\right.\]

\end_inset


\end_layout

\begin_layout Standard
Now we want to use this equation to 
\begin_inset Quotes eld
\end_inset

solve
\begin_inset Quotes erd
\end_inset

 for 
\begin_inset Formula $x$
\end_inset

.
 We do this simply by 
\begin_inset Quotes eld
\end_inset

taking 
\begin_inset Formula $x$
\end_inset

 to the left hand side (lhs),
\begin_inset Quotes erd
\end_inset

 yielding: 
\begin_inset Formula \begin{equation}
x_{i}=\left\{ \begin{array}{lcl}
i=1 & : & b_{i}\\
i>1 & : & {\displaystyle b_{i}-\sum_{j=1}^{i-1}L_{i,j}x_{j}}\end{array}\right.\label{eq:fs}\end{equation}

\end_inset


\end_layout

\begin_layout Standard
Is this a 
\emph on
program
\emph default
 to solve a lower triangular system of equations? 
\end_layout

\begin_layout Subsection
Equations as programs
\end_layout

\begin_layout Standard
We have made the case that the mathematical reasoning needed to solve many
 problems leads to equations, and these equations are in some sense, a very
 high level specification of an algorithm.
 The next step would be to actually make these equations the program itself.
 It is therefore useful to 
\begin_inset Quotes eld
\end_inset

codify
\begin_inset Quotes erd
\end_inset

 these equations so that they define a programming language (or rather,
 a sublanguage, since not everything that we want to program---such as file
 I/O---can be written as equations).
 Before we do this however, let us recap some of the advantages and issues
 that arise when viewing equations as programs.
\end_layout

\begin_layout Standard
A primary advantage is that equations are amenable to formal resoning: we
 can prove properties of equations, analyze the dependence properties, and
 as we shall see later on, determine how to parallelize them, and how, starting
 from equations, to generate code (which may be sequential or parallel)
 or even hardware descriptions (VHDL) of parallel circuits that can be implement
ed on FPGA platforms.
 We now illustrate some examples of such reasoning.
\end_layout

\begin_layout Paragraph
Program complexity
\end_layout

\begin_layout Standard
Consider the example for foward substitution (Eqn.\InsetSpace ~

\begin_inset LatexCommand ref
reference "eq:fs"

\end_inset

).
 Notice that for an 
\begin_inset Formula $n\times n$
\end_inset

 matrix, 
\begin_inset Formula $L$
\end_inset

, there are 
\begin_inset Formula $n$
\end_inset

 values of 
\begin_inset Formula $x$
\end_inset

 that need to be determined (for 
\begin_inset Formula $i=1\ldots n$
\end_inset

, the subscripts on the lhs).
 Further, for any given 
\begin_inset Formula $i$
\end_inset

, the values that 
\begin_inset Formula $j$
\end_inset

 can take can be deduced from the bounds of the summation: 
\begin_inset Formula $j=1\ldots(i-1)$
\end_inset

.
 Hence the set of 
\begin_inset Quotes eld
\end_inset

index values
\begin_inset Quotes erd
\end_inset

 where we need to do an 
\begin_inset Quotes eld
\end_inset

elementary
\begin_inset Quotes erd
\end_inset

 computation (here a multiply-accumulate) can be viewed as a triangle defined
 by 
\begin_inset Formula $\{\langle i,j\rangle\mid1\leq j<i\leq n\}$
\end_inset

.
 There are about 
\begin_inset Formula $\frac{1}{2}n^{2}$
\end_inset

 points in the triangle, so the complexity of our 
\begin_inset Quotes eld
\end_inset

equational program
\begin_inset Quotes erd
\end_inset

 for forward substitution is 
\begin_inset Formula $\Theta(n^{2})$
\end_inset

.
\end_layout

\begin_layout Standard
Similarly, the complexity of the backward substitution (Eqn.\InsetSpace ~

\begin_inset LatexCommand ref
reference "eq:bs"

\end_inset

) is also 
\begin_inset Formula $\Theta(n^{2})$
\end_inset

, and that of LU decomposition (Eqns.\InsetSpace ~

\begin_inset LatexCommand ref
reference "eq:lu-u"

\end_inset

-
\begin_inset LatexCommand ref
reference "eq:lu-l"

\end_inset

) is 
\begin_inset Formula $\Theta(n^{3})$
\end_inset

 (more precisely, there are 
\begin_inset Formula $\frac{1}{3}n^{3}$
\end_inset

 integer points in its 
\begin_inset Quotes eld
\end_inset

pyramid shaped domain.
\begin_inset Quotes erd
\end_inset

 Similarly, the complexity of Eqn.\InsetSpace ~

\begin_inset LatexCommand ref
reference "eq:los"

\end_inset

 is also 
\begin_inset Formula $\Theta(n^{3})$
\end_inset

 since there are 
\begin_inset Formula $\frac{1}{2}n^{3}$
\end_inset

 integer points in its domain.
\end_layout

\begin_layout Section
Recurrence Equations
\end_layout

\begin_layout Standard
\begin_inset LatexCommand label
name "sec:sre"

\end_inset


\end_layout

\begin_layout Standard
In what follows, 
\begin_inset Formula $\Z{}$
\end_inset

 denotes the set of integers, and 
\begin_inset Formula $\N{}$
\end_inset

 the set of natural numbers.
\end_layout

\begin_layout Standard
\begin_inset ERT
status collapsed

\begin_layout Standard


\backslash
begin{definition}
\end_layout

\end_inset

 
\begin_inset LatexCommand label
name "re-def"

\end_inset

 A 
\series bold
Recurrence Equation
\series default
 defining a function (variable) 
\begin_inset Formula $X$
\end_inset

 at all points, 
\begin_inset Formula $z$
\end_inset

, in a domain, 
\begin_inset Formula $D$
\end_inset

, is an equation of the form 
\begin_inset Formula \begin{equation}
X[z]=D^{X}~~:~~g(\ldots X[f(z)]\ldots)\label{re-def-eq}\end{equation}

\end_inset

 
\begin_inset ERT
status collapsed

\begin_layout Standard


\backslash
end{definition}
\end_layout

\end_inset


\end_layout

\begin_layout Standard

\newpage

\end_layout

\begin_layout Subsection*
Reductions
\end_layout

\begin_layout Standard
The key difficulty you must have encountered is that we have no syntax for
 the 
\emph on
reduction
\emph default
 operations: associative and commutative operators like addition, multiplication
, 
\begin_inset Formula $\max$
\end_inset

, etc., applied to a collection of values.
\end_layout

\begin_layout Standard
We will now introduce a simple, yet powerful syntax for this.
 We simply allow the function 
\begin_inset Formula $g$
\end_inset

 to have the form, 
\begin_inset Formula $\mathtt{reduce}(\mathtt{op},f',\mathtt{expr})$
\end_inset

.
 Here, 
\end_layout

\begin_layout Itemize

\family typewriter
op
\family default
 is an associative and commutative operator; 
\end_layout

\begin_layout Itemize

\family typewriter
expr
\family default
 is an expression (it is most convenient to assume that the expression is
 just a new variable, 
\begin_inset Formula $Y$
\end_inset

, and to assume that there is an equation 
\begin_inset Formula $Y=\mathtt{expr}$
\end_inset

 defined over an appropriate domain 
\begin_inset Formula $D^{Y}$
\end_inset

); 
\end_layout

\begin_layout Itemize
\begin_inset Formula $f'$
\end_inset

 is a many-to-one mapping from indices to indices, usually it maps 
\begin_inset Formula $\Z{n}$
\end_inset

 to 
\begin_inset Formula $\Z{n-k}$
\end_inset

 (where the 
\family typewriter
expr
\family default
 is 
\begin_inset Formula $n$
\end_inset

-dimensional).
 
\end_layout

\begin_layout Section
Fine Grain Parallel Hardware with SREs
\end_layout

\begin_layout Standard
We conclude these notes by briefly describing how the fine grain parallel
 architectures in which we are interested can be described by 
\begin_inset ERT
status collapsed

\begin_layout Standard


\backslash
sre
\end_layout

\end_inset

 s.
 First, consider a simple finite state machine.
 It has two sets of 
\begin_inset Quotes eld
\end_inset

registers,
\begin_inset Quotes erd
\end_inset

 a 
\emph on
state
\emph default
 and an 
\emph on
output
\emph default
.
 At any time step, the next value of there registers is given by a pair
 of functions of the current values of the state and the input.
 In other words, a finite state machine is described by the following two
 functions: 
\end_layout

\begin_layout Section
\begin_inset Quotes eld
\end_inset

Manipulating
\begin_inset Quotes erd
\end_inset

 Equations
\end_layout

\begin_layout Standard
We now describe what we can do with equations, in a more formal manner,
 as well as the tools that such manipulation requires.
\end_layout

\begin_layout Subsection*
Change of Basis (CoB)
\end_layout

\begin_layout Standard
\begin_inset LatexCommand label
name "sec:cob"

\end_inset


\end_layout

\begin_layout Standard
The most important manipulation that we can perform on an 
\begin_inset ERT
status collapsed

\begin_layout Standard


\backslash
sre
\end_layout

\end_inset

\InsetSpace \space{}
is called a 
\emph on
change of basis
\emph default
 of its variable(s) (also called a 
\emph on
reindexing transformation
\emph default
 or 
\emph on
space-time mapping
\emph default
).
 The transformation, 
\begin_inset Formula ${\cal T}$
\end_inset

 must admit a 
\emph on
left inverse
\emph default
 for all points in the domain of the variable.
 When applied to the variable 
\begin_inset Formula $X$
\end_inset

 of an 
\begin_inset ERT
status collapsed

\begin_layout Standard


\backslash
sre
\end_layout

\end_inset

\InsetSpace \space{}
defined as follows: 
\begin_inset Formula \begin{eqnarray}
X[z] & = & \left\{ \begin{array}{rcl}
\multicolumn{3}{c}{\vdots}\\
D_{i}^{X} & : & g_{i}(\ldots Y[f(z)]\ldots)\\
\multicolumn{3}{c}{\vdots}\end{array}\right.\end{eqnarray}

\end_inset

 the 
\begin_inset ERT
status collapsed

\begin_layout Standard


\backslash
sre
\end_layout

\end_inset

\InsetSpace \space{}
obtained by applying the following rules is provably equivalent to the original:
 
\end_layout

\begin_layout Standard
\begin_inset ERT
status collapsed

\begin_layout Standard


\backslash
itemsep
\end_layout

\end_inset

 0mm 
\end_layout

\begin_layout Itemize
Replace each 
\begin_inset Formula $D_{i}^{X}$
\end_inset

 by 
\begin_inset Formula ${\cal T}(D_{i}^{X})$
\end_inset

, the image of 
\begin_inset Formula $D_{i}^{X}$
\end_inset

 by 
\begin_inset Formula ${\cal T}$
\end_inset

.
 
\end_layout

\begin_layout Itemize
On the right hand side (rhs) of the equation for 
\begin_inset Formula $X$
\end_inset

, replace each dependency 
\begin_inset Formula $f$
\end_inset

 by 
\begin_inset Formula $f\circ{\cal T}^{-1}$
\end_inset

, the composition
\begin_inset Foot
status collapsed

\begin_layout Standard
Recall that function composition is right associative, i.e., 
\begin_inset Formula $(g\circ h)(z)=g(h(z))$
\end_inset

.
\end_layout

\end_inset

 of 
\begin_inset Formula $f$
\end_inset

 and 
\begin_inset Formula ${\cal T}^{-1}$
\end_inset

.
 
\end_layout

\begin_layout Itemize
In all occurrences 
\begin_inset Formula $X[g(z)]$
\end_inset

 on the rhs of 
\emph on
any
\emph default
 equation, replace the dependency 
\begin_inset Formula $g$
\end_inset

 by 
\begin_inset Formula ${\cal T}\circ g$
\end_inset

.
 
\end_layout

\begin_layout Standard
The occurrences of 
\begin_inset Formula $X$
\end_inset

 on the rhs of the equation for 
\begin_inset Formula $X$
\end_inset

 itself constitute a special case where the last two rules are 
\emph on
both
\emph default
 applicable, and we replace the dependency 
\begin_inset Formula $f$
\end_inset

 by 
\begin_inset Formula ${\cal T}\circ f\circ{\cal T}^{-1}$
\end_inset

.
\end_layout

\begin_layout Subsection*
Domains, Polyhedra and Representations
\end_layout

\begin_layout Standard
The (data) variables defined in an 
\begin_inset ERT
status collapsed

\begin_layout Standard


\backslash
sre
\end_layout

\end_inset

\InsetSpace \space{}
may also be viewed as multidimensional array variables (stored in some memory
 locations if the 
\begin_inset ERT
status collapsed

\begin_layout Standard


\backslash
sre
\end_layout

\end_inset

\InsetSpace \space{}
is viewed as a recursively evaluated program), or alternatively as mappings
 from tuples of indices to values.
 Hence, the domains over which the 
\begin_inset ERT
status collapsed

\begin_layout Standard


\backslash
sre
\end_layout

\end_inset

 s are defined play a crucial role in our analysis.
\end_layout

\end_body
\end_document