\documentclass[12pt]{exam}

\usepackage{amsmath}
\usepackage{verbatim}
%\usepackage{graphicx}
\usepackage{gastex}
%\usepackage{timestamp} % http://brasserie-seul.com/?Recipes&nr=16

%\addpoints

\renewcommand{\solutiontitle}{\noindent\textbf{Solution:}\par\noindent}

\begin{document}

\printanswers

\pagestyle{head}
\firstpageheader{CS 52500}{Exam 2}{Fall 2012}

% just in case we need an image file
%\includegraphics[width=2in]{problem.png}

The following questions ask you to analyze some code fragments and to write some code fragments. When you analyze some code, your analysis should be written in complete sentences organized into paragraphs. Do not write sentence fragments and do not write the most terse answer that you can think of (even if it is essentially correct). You are being graded on your ability to communicate, not just on your ability to arrive at correct solutions.

\bigskip

When you write code fragments, you do not need to write compilable code. Just make sure that your code is not in any way ambiguous.

\bigskip

Write all of your answers neatly on separate pieces of paper. If you want, you can write your answers using a text editor, Word, or even \LaTeX. If your answers are all contained in an electronic document (e.g., text file, Word document, pdf file, etc.), then you can submit your exam to me by Blackboard. If you write up your solutions long hand, then turn in your exam in my mailbox in the Mathematics Department office or in class.

\bigskip

Each person should work on this exam by them self. If you have any questions about the exam, feel free to send me an e-mail or call me on the phone.

\bigskip

This exam should be turned in on Thursday, December 13.

\vspace*{\fill}
\newpage

\begin{questions}


\question
Suppose that we have five C functions
\begin{verbatim}
   void functionA(void);
   void functionB(void);
   void functionC(void);
   void functionD(void);
   void functionE(void);
\end{verbatim}
that together solve some problem (strictly by using side effects, since there are no parameters or return values). Suppose these function depend on each other according to the following graph.

\smallskip
\unitlength=1cm
\begin{picture}(5,3.5)
\gasset{linewidth=0.05,AHLength=0.3,AHlength=0.282}
% states
\node(A)(4,3){$A$}
\node(B)(6,3){$B$}
\node(C)(8,3){$C$}
\node(D)(7,2){$D$}
\node(E)(5,0){$E$}
% transitions
\drawedge(A,E){}
\drawedge(B,D){}
\drawedge(C,D){}
\drawedge(D,E){}
\end{picture}

\smallskip
Each edge of the graph denotes a dependency between two of these functions. For example, the edge from node B to node D means that {\tt functionB} must be called, and must return, before {\tt functionD} can be called.

\smallskip
Write a C program that uses MPI to execute the above five functions in a way that is maximally parallel, but adheres to the above dependency graph. (Don't worry about how the five functions do their side effects when they are on different processors. Just assume that the side effects happen.)


\begin{solution}
   % put your solution to the first problem here
\end{solution}


\vspace*{\fill}
\newpage


\question
Suppose that we have six C functions
\begin{verbatim}
   void functionA(void);
   void functionB(void);
   void functionC(void);
   void functionD(void);
   void functionE(void);
   void functionF(void);
\end{verbatim}
that together solve some problem. Suppose these function depend on each other according to the following dependency graph.

\smallskip
\unitlength=1cm
\begin{picture}(5,3.5)
\gasset{linewidth=0.05,AHLength=0.3,AHlength=0.282}
% states
\node(A)(4,3){$A$}
\node(B)(6,3){$B$}
\node(C)(8,3){$C$}
\node(D)(7,2){$D$}
\node(F)(4.5,1.5){$F$}
\node(E)(5,0){$E$}
% transitions
\drawedge(A,F){}
\drawedge(B,D){}
\drawedge(B,F){}
\drawedge(C,D){}
\drawedge(D,E){}
\drawedge(F,E){}
\end{picture}

\smallskip
Write a C program that uses MPI to execute the above six functions in a way that is maximally parallel, but adheres to the above dependency graph.


\begin{solution}
   % put your solution to the second problem here
\end{solution}


\vspace*{\fill}
\newpage



\question
Here is a sketch of a possible way that an implementation of MPI might implement the {\tt MPI\_barrier()} function. This implementation of {\tt MPI\_barrier()} is in terms of the more primitive MPI functions {\tt MPI\_Send()} and {\tt MPI\_Recv()}.

\begin{verbatim}
int MPI_Barrier(MPI_Comm comm)
{  int p, rank, i, mesg = 0, tag = 1;
   MPI_Status status;
   MPI_Comm_size(comm, &p);
   MPI_Comm_rank(comm, &rank);
   if (rank == 0)
   {
      for(i = 1; i < p; i++)
         MPI_Recv(&mesg, 1, MPI_INT, i, tag, comm, &status);
      for(i = 1; i < p; i++)
         MPI_Send(&mesg, 1, MPI_INT, i, tag, comm);
   }
   else
   {
      MPI_Send(&mesg, 1, MPI_INT, 0, tag, comm);
      MPI_Recv(&mesg, 1, MPI_INT, 0, tag, comm, &status);
   }

   return 0;
}
\end{verbatim}

\begin{parts}

\part
Why is this a poor way to implement the barrier function? (Hint: This implementation is too serialized.)

\bigskip

\part
Give a sketch of a way to implement at least a slightly better version of the barrier function (but still in terms of the more primitive MPI functions {\tt MPI\_Send()} and {\tt MPI\_Recv()}). Explain how your version is better. (Hint: Find a way to ``parallelize'' the implementation of the barrier.)
\end{parts}


\begin{solution}
   % put your solution to the third problem here
\end{solution}


\vspace*{\fill}

%Total of \numpoints\ points

%\hfill\timestamp  % add a time stamp at lower right hand corner

\end{questions}

\end{document}