\documentclass[12pt,oneside]{article}

\usepackage{amsmath}
\usepackage{booktabs}
%\usepackage[onlytext]{MinionPro}
\usepackage[letterpaper, margin=1in]{geometry}
\usepackage{enumitem}
\usepackage{graphicx}
\usepackage{hyperref}
\usepackage{fancyvrb}

%% \setlength{\topmargin}{-0.75in}
%% \addtolength{\textheight}{2.00in}
%% \setlength{\parindent}{0in}
\pagestyle{empty}

\begin{document}

\begin{center}
  {\Large Homework 01}\hfill\emph{COSC 273: Parallel and Distributed Computing}, Spring 2023\\
  \hrule
\end{center}

\vspace{0.5em}

\noindent\textbf{Due:} Friday, 02/17/2023 at 11:59 pm

\vspace{0.5em}

\noindent\emph{Instructions:} You may work on this assignment in groups of up to 3 and submit a single solution for your group. All group members are responsible for understanding all submitted solutions.

\vspace{2em}

\noindent\textbf{Exercise 1.}. Suppose a task $T$ is composed of four (purely sequential) sub-tasks $T_1, T_2, T_3, T_4$ which require 360, 210, 210, and 180 elementary operations (respectively) to complete. We have three processors at our disposal $P_1, P_2, P_3$, which can perform 480, 320, and 320 operations per second (respectively).
\begin{enumerate}[label={(\alph*)}]
\item How could the tasks be assigned to processors so as to minimize the latency (i.e., completion time) of the overall computation? What is the latency of the computation?
\item Suppose the speed of the three processors are still 480, 320, 320, but it is not known \emph{which} of the processors is faster. A \emph{greedy} schedule is a schedule for which whenever a process completes a task, the next task that has neither been completed nor is in progress is assigned to that process.  What are the maximum and minimum latencies achieved by greedy scheduling for the three processes? 
\item Again in the case where it is not known which of the processors is fastest, show that there is a greedy schedule in which a non-greedy schedule would have lower latency. (A schedule is \emph{non-greedy} if at some time, there is an idle process as well as a task that is neither completed nor in progess. That is, the task \emph{could} be assigned to the process, but is not.)
\end{enumerate}

\vspace{1em}

\noindent\textbf{Exercise 2.} Suppose you are given a program with a method \texttt{M} that executes sequentially. Use Amdahl's law to answer the following questions, assuming that the remaining operations in the program can be computed in parallel.

\begin{enumerate}[label={(\alph*)}]
\item If \texttt{M} accounts for 20\% of the program's total execution time, what is the maximum possible overall speedup on a 2 processor machine? A 3 processor machine? An 8 processor machine?
\item What is the maximum possible speedup for \emph{any} number of parallel processors (i.e., as the number $n$ of processors becomes arbitrarily large)?
\item Now suppose \texttt{M} is replaced by a method \texttt{N} that accomplishes the same task but in half the time. How much faster is the new program than the old program on a 2 processor machine? A 3 processor machine? An 8 processor machine? An $n$ processor machine (as a function of $n$)?
\end{enumerate}

\clearpage

\noindent\textbf{Exercise 3.} Consider the \texttt{Counter} object described in lecture:

\begin{Verbatim}[numbers=left]
  public class Counter {
    private long count = 0;

    ...

    public void increment() {
      count++;
    }
  }
\end{Verbatim}

Suppose two threads concurrently increment a shared \texttt{Counter} object $n$ times each. That is, both threads execute the following:

\begin{Verbatim}[numbers=left]
  Counter ctr;
  ...
  for (int i = 0; i < n; i++) {
    ctr.increment();
  }
\end{Verbatim}

\begin{enumerate}[label={(\alph*)}]
\item For any given value $c$ satisfying $n \leq c \leq 2n$, describe an execution for which the final value of \texttt{ctr} is $c$.
\item Describe an exection for which the final value of \texttt{ctr} is $2$.
\item Is it possible that the final value of the counter could be $1$? Why or why not?
\end{enumerate}









\end{document}

%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End:
