

%%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}

        \newcommand{\ReportNumber}{Thesis Proposal}

        \newcommand{\Title}{Super Heterogenous Sytems and
                             Adaptive Heterogenous 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

                                   
                                   


        Today a lot of research is done in the area of heterognous
computing. Most of the time systems are restricted to the same class
of machines interconected via a network. The proposed research extends
the current issues in two aspects. First, the heterogenous sytems is
truely heterogenous. This means that many different computers with
different charateristics are part of the network. This includes
different networks consiting of totaly different clients but also
supercomputers. This motivates the ussage of the term {\em Super
Heterogenous}. 

        Once such a sustem is existing the question arrises who one is
able to make efficiently use of the available computational resources.
To do this the concept of a heterogenous algorithm is
developed.\footnote{Is there an overlap between LINDA tuple space?} I
define a heterogenous algorithm in such a way that the program
 is able to adapt to variations in the system utilisation. I would
like to illustrate this on a simple example:

        Assume the sytem has a CM5, a network of SUN4 and a DECmpp.
The problem is to factorize a large matix. 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 would enable to choose the
machine suitable for the execution of the problem. 

        An extension to this would be if the matrix would be
distributed over the different machines and the Solving algorithm is
itself distributed. (in the first pahse of the project this problem
will not be studied since I have the felling it might not be possible
to implement such algorithm in large on this many machines because the
algorithm part is in forground and not the ussage of the system)

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. 

I could imagine two 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 avaialable on MIMD machines as part of
ScalPACK. The advantage of using LAPACK is that the code is well
maintained,  it is already partialy available for MIMD machines, and
performance data for the different algorithms is relatively easy to
obtain. 




Research Plan

NASA optimal interpolation 


parallel algorithms scalpack

distributed computing

data parallel vs. message passing evaluation (NASA goal)
MIMD vs. SIMD

heterogenous environment


\section{Heterogenous Algorithm}

An interesting aspect might be the development of an heterogenous
algorithm. Today

\section{Load Balancing}

Load balancing is on of the mayor issius 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).


\section{Heterogenous 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.

\end{document}