%\documentclass[dvips,12pt]{amsart}
\documentclass[pdftex,12pt]{amsart}
\usepackage{amsmath}
\usepackage[portuges]{babel}
\usepackage{enumerate}

\usepackage{hyperref}
\def\hbref#1#2#3{\href{#1#2}{#3}}

\def\crseurl{http://www.inf.ufes.br/~raulh/ufes/teaching/courses/lpii}

\def\cwurl{\crseurl/page/cw/0/}

\def\inmacros#1{\input{$HOME/tex/macros/#1}}

\inmacros{defport}

\def\stb#1#2{\ensuremath{st.#1.b.#2}}
\def\xstb#1#2#3{\ensuremath{\stb#1#2=\langle#3\rangle}}
\def\xoldstb#1#2#3{\ensuremath{#1\in\stb#2#3}}

\def\stdin{\emph{stdin}}
\def\stdout{\emph{stdout}}
\def\tarball{\emph{tarball}}
\def\mailto#1{\href{mailto:#1}{#1}}
\title{Trabalho 0: \\ Programa\c{c}\~ao Paralela via BMF\\
       Final}

\author{Raul H.C. Lopes}
\def\radixsort{\emph{radix sort}}
\def\splitter{\emph{splitter}}
\def\quicksort{\emph{quick sort}}
\def\mergesort{\emph{merge sort}}
\def\prefsum{prefix sum}
\def\real{Real}


\def\scref#1{sc. \ref{#1}}
\def\exref#1{ex. \ref{ex:#1}}
\def\tabref#1{tab. \ref{tab:#1}}

\begin{document}

\maketitle

\section{Preliminares}
Neste trabalho voc\^e implementar\'a um conjujnto de algoritmos que podem
que t\^em o fato de que podem ser facilmente derivados usando os
formalismos de \emph{Bird-Meertens} e \emph{powerlists}.
O trabalho consiste de exerc\'{\i}cios sobre  ordena\c{c}\~ao paralela e 
exerc\'{\i}cos de
c\'alculo de seq\"u\^encias.

Algumas dicas importantes sobre a execu\c{c}\~ao do trabalho seguem.
\begin{enumerate}
	\item N\~ao deixe de ler este documento por completo antes de iniciar o
		trabalho.
	\item Siga estritamente as especifica\c{c}\~oes deste documento: qualquer
		desvio delas pode significar a anula\c{c}\~ao de um
		exerc\'{\i}cio ou de todo o trabalho.
	\item Comece a trabalhar de imediato: o trabalho foi concebido
		para ser realizado em quatro semanas. Depois disso, 
		voc\^e ter\'a outro
		trabalho e nova prova.
\end{enumerate}

O trabalho pode ser executado em grupos, mas, como estabelecido na se\c{c}\~ao 
\ref{credits}, grupos maiores recebem menos cr\'editos. 

\section{C\'alculo de seq\"u\^encias}

\begin{ex}\label{ex:primes}
	Implemente o algoritmo para c\'alculo de todos os primos menores
	do que um inteiro, apresentado em sala no dia 14/05/06.

	Seu programa compilado ter\'a o nome \textbf{primes}.

	Seu programa receber\'a um \'unico argumento na linha de comando: o
	inteiro limite superior dos primeiros a gerar. Ele produzir\'a os
	primeiro em \stdout, um por linha.
\end{ex}

\begin{ex}\label{ex:primes:test}
	\textbf{Opcional.}
	Apresente testes similares aos do \exref{sort}.
\end{ex}

\def\hrefvishkin{\href{http://portal.acm.org/citation.cfm?id=384252}%
{Experiments with list ranking for explicit multi-threaded (XMT) instruction parallelism}}
\begin{ex}
	\label{ex:vishkin}
	Implemente um dos  algoritmos de Vishkin and Vishkin,  
	veja em \hrefvishkin,
	para c\'alculo
	dos \emph{ranking} de uma lista. Escolha entre os algoritmos
	\emph{No-Cut} e \emph{Cut-6}.

	Seu programa compilado ter\'a o nome \textbf{vishkin}.

	Seu programa receber\'a um \'unico argumento na linha de comando: o 
	n\'umero de n\'os na lista. Ele receber\'a o vetor de \'{\i}ndices de
	sucessores de n\'os de \stdin, um por linha, e exibir\'a em \stdout,
	um por linha, os rankings calculados.
\end{ex}

\def\hrefhjaja{\href{http://citeseer.ist.psu.edu/helman98prefix.html}%
			{Prefix Computations on Symmetric Multiprocessors}}
\begin{ex}
	\label{ex:hjaja}
	Implemente o algoritmo de Helman-J\'aj\'a, veja em  \hrefhjaja,
	para c\'alculo
	dos prefixos de uma lista encadeada de inteiros.

	Seu programa compilado ter\'a o nome \textbf{hjaja}.

	Seu programa receber\'a um \'unico argumento na linha de comando: o 
	n\'umero de n\'os na lista. Ele receber\'a o vetor de \'{\i}ndices de
	sucessores de n\'os de \stdin, um por linha, e exibir\'a em \stdout,
	um por linha, os rootings calculados. Note que voc\^e estar\'a
	calculando, via soma de prefixos, a dist\^ancia de cada n\'o at\'e  o
	in\'{\i}cio da lista.
\end{ex}

\begin{ex}\label{ex:pref:test}
	\textbf{Opcional.}
	Apresente testes similares aos do \exref{sort}.
\end{ex}

\section{Ordena\c{c}\~ao}

\begin{ex}
	\label{ex:radix}
	Implemente o algoritmo de radix sort paralelo apresentado em sala para
	ordenar inteiros positivos.

	Seu programa compilado ter\'a o nome \textbf{radix}.

	Seu programa receber\'a um \'unico argumento da linha de comando:
	o n\'umero de inteiros a ordenar. Ele ler\'a os inteiros de \stdin,
	um por linha, e exibir\'a o resultado da ordena\c{c}\~ao em \stdout,
	um por linha.
\end{ex}

\begin{ex}
	\label{ex:bitonic}
	Implemente uma vers\~ao paralela n\~ao recursiva do algoritmo
	\emph{bitonic sort}.

	Seu programa compilado ter\'a o nome \textbf{bitonic}.

	Seu programa receber\'a um \'unico argumento da linha de comando:
	o n\'umero de inteiros a ordenar. Ele ler\'a os inteiros de \stdin,
	um por linha, e exibir\'a o resultado da ordena\c{c}\~ao em \stdout,
	um por linha.
\end{ex}

\def\hrefcole{\href{http://portal.acm.org/citation.cfm?id=61987}%
			{Parallel merge sort}}
\begin{ex}
	\label{ex:cole}
	Implemente uma vers\~ao n\~ao recursiva do algoritmo de \emph{merge
	sort} paralelo de Cole, veja em  \hrefcole.

	Seu programa compilado ter\'a o nome \textbf{merge}.

	Seu programa receber\'a um \'unico argumento da linha de comando:
	o n\'umero de inteiros a ordenar. Ele ler\'a os inteiros de \stdin,
	um por linha, e exibir\'a o resultado da ordena\c{c}\~ao em \stdout,
	um por linha.
\end{ex}

\begin{ex}
	\label{ex:sort}
	Apresente quadro de testes comparativo dos algoritmos dos 
	exerc\'{\i}cios \ref{ex:radix}, \ref{ex:bitonic},\ref{ex:cole}.
	Seu quadro abordar\'a os seguintes testes:
	\begin{itemize}
		\item Para um n\'umero fixo de inteiros (ao menos, $2^{20}$),
			os tempos de execu\c{c}\~ao para 4, 6, 8, 16
			processadores.
		\item Para 16 processadores, os tempos de execu\c{c}\~ao para
			$2^{16}, 2^{20}, 2^{24}$ itens.
	\end{itemize}
\end{ex}

\section{Cr\'editos}


A defini\c{c}\~ao dos  crit\'erios de avalia\c{c}\~ao 
A atribui\c{c}\~ao de nota para o trabalho ocorrer\'a em duas fases:
\begin{enumerate}
	\item Atribui\c{c}\~ao de cr\'editos pelo trabalho submetido, de 
		acordo com crit\'erios apresentados na \scref{credits}.
	\item Defini\c{c}\~ao do multiplicador de acordo com a tabela
		\ref{tab:mult}.
\end{enumerate}

\subsection{Defini\c{c}\~ao do n\'umero de cr\'editos}\label{credits}
Todos os exerc\'{\i}os, com a exce\c{c}\~ao dos opcionais, t\^em o mesmo
peso. Os exerc\'{\i}cios opcionais substituem at\'e metade do valor 
de qualquer exerc\'{\i}cio n\~ao conclu\'{\i}do deste trabalho.


\subsection{Defini\c{c}\~ao de multiplicador}

A nota  de cada trabalho \'e dada pelo n\'umero de cr\'editos obtidos pelo
trabalho multiplicado pelo fator da tabela \ref{tab:mult}.

\begin{table}
	\centering
	\begin{tabular}{|l|r|}\hline
		Fator & Multiplicador \\\hline
		Grupos de 1 aluno & $110/100$ \\
		Grupos de 2 alunos & $ 100/100$ \\
		Grupos de 3 alunos & $ 75/100$ \\
		Grupos de 4 alunos & $ 60/100$ \\
	 	Grupos de mais 4 alunos & $0$ \\
		Pl\'agio & $0$ \\ \hline
	\end{tabular}\\[\baselineskip]
	\caption{Tabela de multiplicadores}
	\label{tab:mult}
\end{table}

Em caso de pl\'agio todos os trabalhos de grupos envolvidos s\~ao anulados.
Poder\'a ser enquadrado como pl\'agio qualquer trabalho em que um mais 
alunos do grupo n\~ao tenham conhecimento de qualquer item do trabalho. Esse
conhecimento dever\'a ser demonstrado em prova e/ou enttrevista.

\section{A submiss\~ao para corre\c{c}\~ao}\label{submit}
\def\haskell{\textbf{Haskell}}
\def\makefile{\textbf{Makefile}}
\def\frp{\textbf{frp}}

Submeta sua trabalho por \href{mailto:raulh@inf.ufes.br}{e-mail}.
Corrigirei quaisquer trabalhos submetidos at\'e \`as 12 horas do dia 11/08/05.

A mensagem de submiss\~ao do seu trabalho dever\'a conter:
\begin{itemize}
	\item \textbf{Subject:} \textbf{pp.tp0}
	\item \textsl{Attachment}: \textbf{tp0.tar.bz2}
\end{itemize}

O corpo da mensagem ser\'a desprezado. O arquivo anexdo dever\'a ser
obrigatoriamente denominado 

\centerline{\textbf{tp0.tar.bz2}}

e conter\'a todo os fontes necess\'arios para compilar  seu trabalho pr\'atico,
incluindo fontes em \LaTeX, \haskell, \makefile e arquivo de
identifica\c{c}\~ao. 

As seguintes regras devem ser rigorosamente seguidas:
\begin{itemize}
	\item Nenhum compilado deve ser enviado.
	\item O \tarball\ do seu trabalho conter\'a a seguinte estrutura:
		\begin{itemize}
			\item arquivo de \textbf{id}

				Conter\'a uma linha inicial com \emph{e-mail}
				de contato do grupo e, depois, uma linha de
				identifica\c{c}\~ao para elemento do grupo,
				contendo n\'umero de matr\'{\i}cula e nome
				completo separados por '\textbf{:}' (dois
				pontos.) Por exemplo:

				\begin{verbatim}
				jolero@gmail.com
				99900089:Ze' do lero 
				\end{verbatim}
			\item arquivo \textbf{Makefile}
			\item diret\'orio \textbf{doc}

				Conter\'a a descri\c{c}\~ao e resultados
				dos testes realizados. Esses resultados
				podem ser apresentados em formato texto.
				Nao leio nada que venha em formato
				propriet\'ario.
		\end{itemize}
	\item seu \tarball\ ser\'a aberto e  compilado com as seguintes linhas:

		\begin{verbatim}
		tar -jxf tp0.tar.gz
		make all
		\end{verbatim}

\end{itemize}



\end{document}

