\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}{Midterm Exam}{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, October 25.

\vspace*{\fill}
\newpage

\begin{questions}


\question
The following code outlines a synchronization pattern. Assume that the two threads begin at the same time, each thread runs on its own core, and there are no other (significant) processes running on the cores.

\vspace{-.15truein}
\begin{verbatim}
void *thread1(void *vargp)
{  while(1)
   {  << do Calculation A >>
      sem_post(&semaphore1);
      << do Calculation B >>
      sem_post(&semaphore2);
      sem_wait(&semaphore3);
   }
}

void *thread2(void *vargp)
{  while(1)
   {  sem_wait(&semaphore1);
      << do Calculation C >>
      sem_post(&semaphore3);
      sem_wait(&semaphore2);
   }
}

sem_t semaphore1, semaphore2, semaphore3;

int main()
{  pthread_t tid;
   sem_init(&semaphore1, 0, 0); // not signaled
   sem_init(&semaphore2, 0, 0); // not signaled
   sem_init(&semaphore3, 0, 0); // not signaled
   pthread_create(&tid, NULL, thread1, NULL);
   pthread_create(&tid, NULL, thread2, NULL);
   while(1){ Sleep(1000); }
}
\end{verbatim}

\begin{parts}

\part[10]
In what way are the two threads synchronized? Give your answer in terms of how the three calculations, A, B, and C, are ordered in time. Explain carefully what role each of the three semaphores plays in the synchronization.

\part[10]
Rewrite this program fragment using condition variables.

\end{parts}



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



\vspace*{\fill}
\newpage


\question
Suppose that we have five C functions
\begin{comment}
\begin{verbatim}
   void functionA(void);
   void functionB(void);
   void functionC(void);
   void functionD(void);
   void functionE(void);
\end{verbatim}
\end{comment}
that together solve some problem. Suppose these functions, labeled {\tt A} through {\tt E}, depend on each other according to the following graph.

\smallskip
\unitlength=1cm
\begin{picture}(5,2.6)
\gasset{linewidth=0.05,AHLength=0.3,AHlength=0.282}
% states
\node(A)(4,2){$A$}
\node(B)(6,2){$B$}
\node(C)(8,2){$C$}
\node(D)(7,1){$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.

\begin{parts}
\part[10]
What is wrong with this sketch of a C program that uses Pthreads to execute the five functions in parallel in a way that adheres to the above dependency graph? How would you improve this program (but still use five worker threads and only the Pthreads functions {\tt pthread\_create()} and {\tt pthread\_join()})?
\begin{verbatim}
void *thread1(void *vargp){ functionA(); }
void *thread2(void *vargp){ functionB(); }
void *thread3(void *vargp){ functionC(); }
void *thread4(void *vargp){ functionD(); }
void *thread5(void *vargp){ functionE(); }
int main()
{  pthread_t tid1, tid2, tid3, tid4, tid5;
   pthread_create(&tid2, NULL, thread2, NULL);
   pthread_create(&tid3, NULL, thread3, NULL);
   pthread_join(tid2, NULL);
   pthread_join(tid3, NULL);
   pthread_create(&tid1, NULL, thread1, NULL);
   pthread_create(&tid4, NULL, thread4, NULL);
   pthread_join(tid1, NULL);
   pthread_join(tid4, NULL);
   pthread_create(&tid5, NULL, thread5, NULL);
   pthread_join(tid5, NULL);
}
\end{verbatim}

\part[10]
Write another sketch of a Pthreads program to execute the above five functions in a way that is maximally parallel, adheres to the above dependency graph, and uses the minimal number of threads possible (including the {\tt main()} thread). Your solution should still use only {\tt pthread\_join()} for synchronization.

\part[10]
Write a sketch of a C program that uses OpenMP to execute the above five functions in a way that is maximally parallel, but adheres to the above dependency graph.
\end{parts}



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



\vspace*{\fill}
\newpage



\question[15]
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 sketch of a C program that uses Pthreads to execute the above six functions in a way that is maximally parallel, but adheres to the above dependency graph. Give a written explanation of how your code solves the problem.



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



\vspace*{\fill}
\newpage



\question[15]
Suppose that we have a computer with 4 cores. Suppose we use OpenMP to parallelize a for-loop that initializes to zero the upper triangle of a $100 \times 100$ matrix.

\begin{verbatim}
   #pragma openmp parallel for private(j) schedule( ... )
   for (i = 0; i < 99; i++)
      for (j = i+1; j < 100; j++)
      {
         a[i][j] = 0.0;
      }
\end{verbatim}

Notice that the {\tt schedule()} clause has been left undefined. Below are six example schedule clauses that could be used. Rank these clause from slowest to fasted. In particular, since each iterate of the inner loop above does just one assignment, we can estimate the execution time by counting how many assignments each thread does (notice that all together, there are exactly 4,950 assignments).

So for each schedule clause, estimate how long the parallelized loop will run. Explain how you arrived at your estimates.

\begin{itemize}
\item {\tt schedule(static)}
\item {\tt schedule(static, 10)}
\item {\tt schedule(static, 1)}
\item {\tt schedule(dynamic, 1)}
\item {\tt schedule(dynamic, 10)}
\item {\tt schedule(dynamic, 20)}
\end{itemize}



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


\vspace*{\fill}
\newpage


\question
Consider the following OpenMP program.
\begin{verbatim}
   #include <stdio.h>
   #include <omp.h>
   #define NUM_OF_COLUMNS 6
   #define NUM_OF_ROWS   (3*(NUM_OF_COLUMNS - 1))

   int whichThread[NUM_OF_ROWS][NUM_OF_COLUMNS];

   void fillColumn(int j)
   {  int i;
      #pragma omp for
      for (i = 0; i < NUM_OF_ROWS; i++)
         whichThread[i][j] = omp_get_thread_num();
   }

   int main()
   {  int i, j;
      for (i = 0; i < NUM_OF_ROWS; i++)  // initialize the array
         for (j= 0; j < NUM_OF_COLUMNS; j++)
            whichThread[i][j] = -1;

      #pragma omp parallel num_threads(NUM_OF_COLUMNS - 1)
         fillColumn(0);

      #pragma omp parallel for num_threads(NUM_OF_COLUMNS - 1)
      for (j = 1; j < NUM_OF_COLUMNS; j++)
         fillColumn(j);

      for (i = 0; i < NUM_OF_ROWS; i++)  // print out the results
      {  for (j= 0; j < NUM_OF_COLUMNS; j++)
            printf(" %2d ", whichThread[i][j]);
         printf("\n");
      }
      return 0;
   }
\end{verbatim}

\begin{parts}
\part[10]
What is the output of this program if it is compiled without the {\tt -fopenmp} compiler flag? Briefly explain why.

\part[10]
What is the output of this program if it is compiled with the {\tt -fopenmp} compiler flag? Explain, very carefully, why the output differs from the output of the serial version of the program.
\end{parts}



\begin{solution}
   % put your solution to the fifth 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}