
%%%%%%%% other macros  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\work}{\mbox{$W_{1}$} }
\newcommand{\critpath}{\mbox{$W_{\infty}$} }
\newcommand{\totthreads}{\mbox{$S_{1}$} }
\newcommand{\threadsinpath}{\mbox{$S_{\infty}$} }
\newcommand{\tp}{\mbox{$T_{p}$} }
\newcommand{\toptp}{\mbox{$T_{\mbox{\footnotesize opt-}p}$} }

%%%%%%%% speed macros %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\pitot}{\mbox{$\pi_{tot}$} }
\newcommand{\piave}{\mbox{$\pi_{ave}$} }
\newcommand{\pimax}{\mbox{$\pi_{max}$} }
\newcommand{\pimin}{\mbox{$\pi_{min}$} }
\newcommand{\pione}{\mbox{$\pi_1$} }
\newcommand{\pitwo}{\mbox{$\pi_2$} }
\newcommand{\pithree}{\mbox{$\pi_3$} }
\newcommand{\pifour}{\mbox{$\pi_4$} }
\newcommand{\pip}{\mbox{$\pi_{p}$} }
\newcommand{\pipminusone}{\mbox{$\pi_{p-1}$} }
\newcommand{\pii}{\mbox{$\pi_{i}$} }
\newcommand{\pij}{\mbox{$\pi_{j}$} }
\newcommand{\piiminusone}{\mbox{$\pi_{i-1}$} }
\newcommand{\pijminusone}{\mbox{$\pi_{j-1}$} }
\newcommand{\pikminusone}{\mbox{$\pi_{k-1}$} }
\newcommand{\piof}[1]{\mbox{$\pi_{#1}$} }


%%%%%%%%  thread macros %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\thread}[1]{\mbox{$T_{#1}$} }
\newcommand{\threadone}{\mbox{$\thread{1}$} }
\newcommand{\threadtwo}{\mbox{$\thread{2}$} }
\newcommand{\threadthree}{\mbox{$\thread{3}$} }
\newcommand{\threadi}{\mbox{$\thread{i}$} }
\newcommand{\threadj}{\mbox{$\thread{j}$} }
\newcommand{\threadk}{\mbox{$\thread{k}$} }
\newcommand{\threadalpha}{\mbox{$\thread{\alpha}$} }
\newcommand{\threadp}{\mbox{$\thread{p}$} }

\newcommand{\shadowthread}[1]{\mbox{$ST_{#1}$} }
\newcommand{\stone}{\mbox{$\shadowthread{1}$} }
\newcommand{\sttwo}{\mbox{$\shadowthread{2}$} }
\newcommand{\stthree}{\mbox{$\shadowthread{3}$} }
\newcommand{\stp}{\mbox{$\shadowthread{p}$} }
\newcommand{\sti}{\mbox{$\shadowthread{i}$} }
\newcommand{\stj}{\mbox{$\shadowthread{j}$} }
\newcommand{\stk}{\mbox{$\shadowthread{k}$} }
\newcommand{\stalpha}{\mbox{$\shadowthread{\alpha}$} }
\newcommand{\stiminusone}{\mbox{$\shadowthread{i-1}$} }
\newcommand{\stjminusone}{\mbox{$\shadowthread{j-1}$} }
\newcommand{\stpminusone}{\mbox{$\shadowthread{p-1}$} }

%%%%%%%%  processor macros %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\procone}{\mbox{$\proc{1}$} }
\newcommand{\proctwo}{\mbox{$\proc{2}$} }
\newcommand{\procthree}{\mbox{$\proc{3}$} }
\newcommand{\procp}{\mbox{$\proc{p}$} }
\newcommand{\procpminusone}{\mbox{$\proc{p-1}$} }
\newcommand{\proci}{\mbox{$\proc{i}$} }
\newcommand{\procj}{\mbox{$\proc{j}$} }
\newcommand{\prock}{\mbox{$\proc{k}$} }
\newcommand{\prociminusone}{\mbox{$\proc{i-1}$} }
\newcommand{\procjminusone}{\mbox{$\proc{j-1}$} }
\newcommand{\prockminusone}{\mbox{$\proc{k-1}$} }


\documentclass[11pt]{article}
\usepackage{fullpage}
\usepackage{6895}

\begin{document}

\problems{Due: Monday, September 22nd}{1}{3}

\begin{problem}(Exercise 1-3 from Minicourse on Multithreaded Programming)
  Prove that a greedy scheduler achieves the stronger bound:
  \begin{equation}
    T_P \le \frac{(T_1 - T_{\infty})}{P} + T_{\infty}\,.
  \end{equation}
\end{problem}

\begin{problem}(Exercise 1-6 from Minicourse on Multithreaded Programming)
  Professor Tweed takes some measurements of his (deterministic)
  multithreaded program, which is scheduled using a greedy scheduler,
  and finds that $T_4 = 80$ seconds and $T_{64} = 10$ seconds.  What
  is the fastest that the professor's computation could possibly run
  on 10 processors?
\end{problem}
  
\begin{problem}(Different Speed Processors)
In this problem we consider how to schedule on processors of different
speeds.  Let there be $p$ processors $1\ldots p$, where processor $i$
has speed $\pii$ steps/time. Assume that
$\pione\geq\pitwo\geq\cdots\geq\pip$.  Let $\work$ represent the {\em
total work\/}, that is the total number of nodes in the dag $G$.  Let
$\critpath$ represent the {\em critical path length\/} of the graph,
that is, the number of nodes in the longest chain in $G$. Let $\piave$
steps/time be the {\em average speed\/} of the processors, that is,
$\piave=\sum_{i=1}^{p}\piof{i}/p$. Let $\tp$ represent the {\em
optimal time\/} to execute $G$ on $p$ processors.

\begin{problempart}
  Briefly explain why an arbitrary greedy schedule may perform poorly.
\end{problempart}
\begin{problempart}
  Describe a good greedy scheduler for this system.
\end{problempart}
\begin{problempart}
  Prove an analog of Graham/Brent for your scheduler.  You should be
  able to show that:
  \begin{eqnarray}
    \tp\,& \leq\, & 
    \frac{\work}{p\,\piave} + \left(\frac{p-1}{p}\right)
    \frac{\critpath}{\piave} \,.
  \end{eqnarray}
\end{problempart}
\begin{problempart}
  Can you still show that the time to complete all tasks is within a
  factor of $2$ of optimal?  Why or why not?
\end{problempart}
\end{problem}

\end{document}
