  

%%ifdef TITEL_AND_TABLE_OF_CONTENTS 
%begin{comment}
\documentstyle[2up,boxit,fancyheadings,doublespace,comment]{report}

\input{definition}

\renewcommand{\FigureAddSpace}{1cm}

\lfoot{~}
\rfoot{~}
\cfoot{\rightmark}
\chead{\leftmark}
%\lhead{~}
%        \setstretch{1.3}
        \setstretch{2}

        \newcommand{\ReportNumber}{Thesis Proposal}

        \newcommand{\Title}{Super Heterogeneous Systems and
                             Adaptive Heterogeneous Algorithms}

         \lhead{\tiny Technical Report: \\
                 \ReportNumber}

        \pagestyle{empty}

\newfont {\Dunhill}{cmdunh10 scaled 1200}

\begin{document}
        \setcounter{page}{0}

        \begin{minipage}[c]{2.0in}

        \psfig{figure=/home/A10D/gregor/tex/NPACsimple.idr,height=0.8in} 

        \end{minipage}
        \ \
        \begin{minipage}[c]{3.5in}

%       \psfig{figure=/home/A10D/gregor/tex/NPACsignLong.ps,height=1.6in} 

        {\large\bf Northeast Parallel Architectures Center}
        
        \end{minipage}

\begin{center}

\vfill

{\bf\Huge\Title}

\bigskip

{\Large \Author}

\bigskip

{\Large Technical Report\\ \ReportNumber \\}


\end{center}

\vfill



\begin{minipage}[c]{1.5in}

~\psfig{figure=/home/A10D/gregor/tex/SUshadow.idr,height=0.8in} 

\end{minipage}
\ \
\begin{minipage}[c]{3.5in}

\begin{singlespace}
\begin{center}
%{\Large\sf Northeast Parallel Architectures Center \\
% at Syracuse University \\}

%\smallskip

\hrule

\smallskip

Science and Technology Center \\
111 College Place \\
Syracuse, NY 13244-4100 \\
Tel.: (315) 443-1722, 1723; Fax: (315) 443-1973
\end{center}
\end{singlespace}
\end{minipage}




\clearpage
\pagestyle{fancy}
\pagenumbering{roman}
\setcounter{page}{0}

%\chead{\tiny \Title}
%\title{\bf \Title}
%\author{\bf\Author}
 
%\maketitle

\tableofcontents

\clearpage



\pagenumbering{arabic}


 \lhead{\tiny Technical Report: \\
         \ReportNumber}


%end{comment}

%%endif


\clearpage

                                   
\section{Motivation}

	In scientific computing one is most interested in solving a
particular problem in a very short time. While working on large
application codes like the CAPS code I realized that it is not enough
to port a problem just to one particular machine.  A good example is
the CAPS code which requires so much memory that this program can not
be executed in timesharing mode on the CM5. Since this machine is
particular busy it means that this problem is not to be solved on the
CM5 due to a lack of resources.  The other observation is that certain
other supercomputers and e.g. workstations are not as much utilized
than the CM5. 

	The conclusion is to incoorperate these machines in a
Heterogeneous system in order to solve the problem on the part of the
system which provides the best performance in consideration with its
utilization. 

	The new started problem of the climate modeling falls into
the same category like the CAPS code. We will face the same problems
while solving the governing equations.



\section{Heterogeneous Systems}

        Today a lot of research is done in the area of heterogenoeus
computing. Most of the time systems are restricted to the same class
of machines interconnected via a network. The proposed research extends
the current issues in two aspects. First, the Heterogeneous Systems is
truly Heterogeneous. This means that not only a number of more or less
equal workstations are used cooperative to solve the problem but also
many different computers with different characteristics including
supercomputers and a variety of workstation networks.


        Once such a system exists the question arises in which way
one is able to make efficiently use of the available computational
resources.  To do this a Heterogeneous algorithm has to be developed.
It is essentially a distributed algorithm with the difference that the
algorithm is executed on the machine or machines which are at the
moment best suited for the job. This includes for example the current
utilization of the machines and memory requirements of the algorithm.

\section{A Simple Example}

A program using this principle should be formulated in a simple
manner. Assume the system has a CM5, a network of SUN4 and a DECmpp.
The problem is to factorize a large matrix. The program is written in
the following way:

\begin{algo}
~~~~\tt
        PROGRAM factorization


        REAL, ARRAY (N,N) a
        REAL, ARRAY (N) b
        REAL, ARRAY (N) x


        CALL Solve (A(:,:),x(:),b(:))


        END PROGRAM
\end{algo}

For each of the machines exists an algorithm solving the problem on
this particular machine.  Dependent on the actual load of the machine
and the performance of the algorithm the best suitable machine is
chosen for the execution of the problem.

\section{Extensions}

        An extension to this would be if the matrix would be
distributed over the different machines and the Solving algorithm is
itself distributed. To enable this a static and dynamic approach is
possible. At this time I make only suggestions for a static approach.

	For each variable which should be distributed over the
different processors on can specify the machine onto which this
variable is mapped. In this way we are able to 

\begin{itemize}

	\item either distribute a variable or better array over the
		machines

	\item or define a data dependency over the machines in 
                pipelined fashion.

\end{itemize}








To simplify the mapping of e.g. array segments to a particular machine
I suggest to extend HPF with a new directive called machine.  In
addition to the block distribution one can specify the machine on
which this block should be stored.

\section{Application}

I could imagine three different types of applications as an ideal
testbed for such a computing environment. First, a distributed genetic
algorithm as introduced in my Master's Thesis. Second, a subset of the
LAPACK routines which might be available on MIMD machines as part of
ScalPACK. The advantage of using LAPACK is that the code is well
maintained,  it is already partially available for MIMD machines, and
performance data for the different algorithms is relatively easy to
obtain. 

The third one would be the CAPS or the NASA code.

\section{Load Balancing}

Load balancing is on of the mayor issues in distributed computing.
Naturally one wants to distribute the load in such a way that the over
all speed of the computation is minimized.  We are not interested in a
balanced use of all possible computer platforms integrated in the
system. This is from importance when for example the calculation is to
small to be distributed over more than one machine or due to resource
restrictions of the machine (e.g. parallel IO).  The Figure shows how
the load balancing would work. This is a scheme for static
loadbalancing. I am intending to extend this scheme for dynamical load
balancing caused by process creation and utilization changes on the
system.

\section{Heterogeneous Platform}

For the conducted research I plan to use the machines available at
NPAC.  They include 

\begin{itemize}

\item (MIMD) CM5, nCube2\footnote{Is assigned to ORACLE project}
\item (SIMD) DECmpp
\item (Network) Network of IBM Rs6000, Network of DEC alpha's
                Network of SUN4 SPARC's

\end{itemize}

As one can see this includes one or more members of the major classes
of parallel programming environments.


\FIGURE{p}
       {system.idr} 
        {width=3.5in}     
        {Outline of the static load balancing scheme} 
        {P:decompose}

\section{System Detail}

As shown in the figure a possible system for controling the load
balance could be desinged in the following way

\begin{enumerate}

\item Select Software Package

\item Obtain performance of the subroutines/programs on the machines.

\item Establish a database with the performace data

\item Measure the Utilization of the machines

\item Predict the performance of the algorithm using the utilization
and the performance data.

\item {\em Design} an algorithm which performs best on the given
heterogenous system at the given time.

\item run the application.

\item in case of utilization changes evaluate if a change of the
algorithm leads to a better performance (Go back to the Measure
Utilization step)

\item give result on completion.   

\end{enumerate}

\section{Goal}

The research goals  are quite a few.

\begin{enumerate}

\item explore the dynamical load balancing in a Heterogeneous environment

\item  show the practical use of a Heterogeneous environment

\item define necessary language extensions useful for defining
       distributed algorithms 

\item evaluate if the distribution of array segments on different 
	machines is possible.
	
\item evaluate if SIMD and MIMD machines can be used efficiently in
	one environment.

\item see in which way a combination of SIMD and MIMD algorithms can 
	speed up the performance


\end{enumerate}

\end{document}