%% LyX 1.3 created this file.  For more info, see http://www.lyx.org/.
%% Do not edit unless you really know what you are doing.
\documentclass[brazil]{article}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\usepackage{float}

\makeatletter

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
\newcommand{\noun}[1]{\textsc{#1}}
%% Bold symbol macro for standard LaTeX users
\newcommand{\boldsymbol}[1]{\mbox{\boldmath $#1$}}

%% Because html converters don't know tabularnewline
\providecommand{\tabularnewline}{\\}
\floatstyle{ruled}
\newfloat{algorithm}{tbp}{loa}
\floatname{algorithm}{Algorithm}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands.
\usepackage{algorithmic}

\usepackage{babel}
\makeatother
\begin{document}

\title{Projeto e Análise de Algoritmo}


\title{4º Trabalho Prático}


\author{Tiago Alves Macambira < tmacam@dcc.ufmg.br >}


\date{4 de Agost de 2003}

\maketitle

\section{Os algorítmos}

Nesse trabalho utilizamos 2 dos 3 algoritmos estudados no 3º trabalho
prático: o shit-and exato e o shift-end aproximado. Ambos utilizam
uma idéia simples, a de usar um autômato finíto não-determinístico
(NDFA) pare realizar a busca de um padrão no texto. Contudo, a implementação
desses algoritmos é feita com tal geniosidade que temos um algoritmo
não somente eficiente mas relativamente fácil de entender. Esses dois
algoritmos utilizam o paralelismo de bits das palavras de um computador,
de forma muito engenhosa. tanto para representar as transições possíveis
entre estados como para representar o próprio estado do autômata (estados
ativos).

Uma explicação mais detalhada do funcionamento de ambos os algoritmos
pode ser obtido no trabalho prático anterior e em \cite{ziviani}.


\section{Paralelismo}

Nesse trabalho prático pedia-se que fosse projetado ''\emph{um algoritmo
paralelo para recuperar ocorrências de padrões em arquivos constituídos
de documentos e distribuídos através de uma rede de estações de trabalho}''\cite{hp}.

Para tanto, foram implementados 2 programas:

\begin{itemize}
\item um programa \noun{escravo}, responsável por fazer a busca por padrão;
\item um programa \noun{mestre} que gerenciava os programas escravos,
enviando a estes requisições de busca por padrões.
\end{itemize}
Ambos os programas foram feitos utilizando sockets em ambiente unix. 


\subsection{Mestre}

Este programa é o responsável por receber, através da linha de comando,
requisições de busca por casamento de padrões em texto e enviá-las
para os vários programas escravos, para que estes fizessem a pesquisa.
Após receber os resultados dos escravos, esse programa sumariza essas
informações e as retorna para o usuário.

Diferentemente do que foi solicitado em \cite{hp}, não estamos informando
as linhas onde ocorreram os casamentos, mas apenas a quantidade total
de linhas onde encontramos ocorrências. Apesar de ser uma vesão mais
simples do problema, não diminuímos o esforço computacional realizado,
apenas simplificamos o processo de comunicação.

A estrutura geral do programa \emph{master} é mostrada em no Algorítmo\ref{alg:master1}.
Esse programa utiliza, no passo onde ocorre o processamento dos resultados
dos escravos a função \noun{select} para gerenciar a comunicação
entre os vários clientes de forma eficiente.

%
\begin{algorithm}

\caption{\label{alg:master1}Master}

\begin{algorithmic}

\STATE Processa a linha de comando

\STATE Conecta-se com os escravos

\STATE Envia as requisições aos escravos

\STATE Processa o resultado dos escravos

\end{algorithmic}
\end{algorithm}



\subsection{Escravos}

Este programa é o responsável por fazer, sob pedido do programa mestre,
buscas por casamentos de padrões. Ele fica num \emph{loop} infinito
a espera de requisições e, sempre que uma for recebida, ele a processa,
retorna o resultado para o mestre e volta a esparar por uma nova requisição.
Dessa forma, pode-se utilizar um mesmo escravo várias vezes.%
\footnote{mas não concorrentemente. %
}

Para cada requisição, o programa escravo retorna

\begin{itemize}
\item o número de linhas com ocorrências encontradas sua respectiva partição
dos dados;
\item o tempo que ele levou para realizar a consulta.
\end{itemize}
Com esses dados, o mestre pode, ao somar os valores relatados por
cada escravo individualmente, informar o número total de linhas com
ocorrências existentes nos arquivos pesquisados. Pode também observar
quais escravos trabalham mais lentamente%
\footnote{Tal informação pode ser útil para observar problemas com os escravos
ou com as máquinas onde os escravos estão rodando.%
}.


\section{Resultados}


\subsection{Considerações Iniciais}

Antes de iniciarmos uma discursão sobre os resultados obtidos, alguimas
considerações devem ser feitas para que possamos observar de forma
mais clara o significado dos resultados, o motivo pelo qual alguns
resultados inesperados foram obtidos, etc.


\subsubsection{Sobre a implementação}

O algoritmo de busta implementado no programa \noun{slave} (slave.c
e search.c) realiza um \emph{loop} no qual ele lê, linha a linha,
através da função \noun{fgets}, o conteúdo do arquivo. Cada linha
é individualmente passada para a função de busca e casamento de padrões
que retorna tão logo seja encontrado um casamento. Essa função por
sua vez, a cada chamada, realiza um processo de inicilização para
o processo de casamento. Esse processo é mais custoso no algoritmo
para casamento aproximado.

Devido a essa estrutura, intuitiva mas ineficiente, os valores de
tempo de execução do algoritmo são consideravelmente altos quando
comparados com o tempo que uma execução, com os mesmos parâmetros,
do programa \emph{agrep}.


\subsubsection{Sobre o processo de execução das consultas}

Esse processo foi automatizado utilizando-se uma script chamada \noun{faz\_tudo.sh}.
Essa script realiza todas as chamadas necessárias ao programa master
e relata algumas informações sobre o andamento do processo de execução
na tela. Estas informações, juntamente com a saída das várias instâncias
do programa master são posteriormente condensadas num arquivo CSV
através de uma outra script, a \noun{parse\_estatisticas.pl}. Esse
arquivo CSV pode ser lido em praticamente qualquer planilha eletrônica
e desta forma permite uma fácil extração dos dados.


\subsubsection{Sobre o ambiente\label{sub:Sobre-o-ambiente}}

Durante o processo de execução das consultas, foi verificado que a
máquima \noun{wolverine}, utilizada tanto para os testes com 2 e
com 4 escravos, estava inacessível. Devido a isso, nos resultados
abaixo, quando conveniente, utilizaremos a média de tempo das outras
máquinas como sendo o valor de tempo utilizado pela máquina wolverine.

Observou-se também que, em paralelo à execução do programa escravo,
durante o tempo destinado a esse experimento, na máquina \noun{ciclope}
também era executado o seguinte programa: \emph{''tcsh -c /usr/bin/nice
-1 perl /home/pos/aldo/processatp2.pl''.} Esse script, rodando com
prioridade acima da normal, executava um programa escrito em java.
Devido a isso, para as consultas utilizando 4 escravos, encontaremos
discrepâncias entre os tempos de execução consumidos nos escravos,
o que refletirá negativamente no tempo de execução total dessas consultas
e, conseqüentemente no \emph{speed-up} conseguido com 4 escravos.

Para ilustrar esse fato, observe a tabela \ref{cap:Busca-exata-4-escravos},
onde consta o tempo de relógio utilizado em cada escravo para o processamento
de uma consulta e o tempo total reportado pelo programa mestre para
essa consulta:

%
\begin{table}
\begin{tabular}{|c|c|c|c|}
\hline 
Máquina&
Tempo no escravo&
Relativo ao nó mais veloz&
Relativo ao tempo no mestre\tabularnewline
\hline
\hline 
vampira&
32,625158s&
1&
0.16363\tabularnewline
\hline 
ciclope&
199,375697s&
6.111&
0.99996\tabularnewline
\hline 
fera&
35,628149s&
1.092&
0.17869\tabularnewline
\hline
\hline 
\textbf{Total}&
199,382762&
6.111&
1\tabularnewline
\hline
\end{tabular}


\caption{\label{cap:Busca-exata-4-escravos}Busca exata pelo pedrão ''State
Department'' com 4 escravos}
\end{table}


Observa-se que o tempo de execução, nessa instância, na máquina ciclope,
foi 6 vezes mais lento do que nas outras máquinas, que possuem tempos
próximos. Esses comportamento não ocorreu isoladamente, sendo na verdade
a regra para todo o processo de execução das consultas utilizando
4 escravos. Fossem as máquinas iguais em condições de processamento
no instante dos testes, os resultados obtidos seriam mais significativos
para os propositdos do trabalho.


\subsection{Saída do Programa}

A saída da execução do programa contra-se em anexo e disponível ná
versão eletrônica deste documento, no arquivo \noun{src/typescript}.
O arquivo com dados condensados da saída das consultas encontra-se
em src/estatiticas.csv. Nesse arquivo, para a execução com 4 escravos,
os tempos do escravo n° 0,1,2 e 3 referem-se, respectivamente, aos
tempos reportados pelos escravos rodando nas máquinas vampira, ciclope,
fera e wolverine%
\footnote{Lembrando: A máquina wolverine encontrava-se inacessível durante os
testes, motivo pelo qual todos os tempos reportados para essa máquina
serão iguais a 0.%
}.


\subsection{Avaliação empírica}


\subsubsection{Speedup}

Define-se speedup como sendo:

\[
\begin{array}{ccc}
S & = & \frac{T(1)}{T(n)}\end{array}\]


onde $T(1)$é o tempo levado pela versão seqüêncial do algorítmo e
$T(n)$ como o tempo levado pelo do algorítmo paralelo usando $n$
processadores.

Nos nossos experimentos conseguimos os seguintes valores pra \emph{speedup}
( na média):

\smallskip{}
\begin{center}\begin{tabular}{|c|c|c|c|}
\hline 
N° de&
\multicolumn{3}{c|}{N° de escravos}\tabularnewline
Erros&
1&
2&
4\tabularnewline
\hline
\hline 
0&
1&
2,13&
0,67\tabularnewline
\hline 
1&
1&
2,07&
0,64\tabularnewline
\hline 
2&
1&
2,05&
0,64\tabularnewline
\hline 
3&
1&
2,03&
0,64\tabularnewline
\hline
\end{tabular}\end{center}
\smallskip{}

Observe que o speedup obtido com 4 máquinas é completamente inesperado:
a performance cai para níveis inferiores aos das execuções seqüênciais.
Isso deve-se a máquina \noun{ciclope}, que, como mencionado na seção
\ref{sub:Sobre-o-ambiente}, estava dividindo seu tempo de processamento
com outras tarefas.

Observe também que quando contabilizamos os tempo de execução para
2 escravos estamos na verdade contabilizando o tempo utilizado apenas
para uma máquina, uma vez que a máquina \noun{wolverine} estava
inacessível. 

Se levarmos em consideração que 

\begin{itemize}
\item o tempo gasto pela parte serial desse algoritmo é muito pequeno frente
ao tempo gasto na parte paralela;
\item os tempos da máquina \noun{ciclope} estão muito acima do esperado
e que tal comportamento não seria encontrado num ambiente paralelo
dedicado;
\item que nos tempos obtidos nas execuções com 4 escravos, os resultados
da máquina \noun{fera} são muito próximo da máquina vampira
\end{itemize}
talvez seja interessante observar apenas o \emph{speedup} médio conseguido
pela máquina \noun{vampira.} É fato que esses valores não refletirão
o tempo gasto com a parte serial do algoritmo ( enviar requisições,
tratar requisições e respostas, etc ) mas, pelo exposto acima, julga-se
que tais valores darão uma idéia aproximada do que consigiríamos em
condições ideiais%
\footnote{Ou pelo menos em condições mais favoráveis%
}:

\smallskip{}
\begin{center}\begin{tabular}{|c|c|c|c|}
\hline 
N° de&
\multicolumn{3}{c|}{N° de escravos}\tabularnewline
Erros&
1&
2&
4\tabularnewline
\hline
\hline 
0&
1&
2,14&
4,11\tabularnewline
\hline 
1&
1&
2,14&
4,11\tabularnewline
\hline 
2&
1&
2,14&
4,11\tabularnewline
\hline 
3&
1&
2,14&
4,11\tabularnewline
\hline
\end{tabular}\end{center}
\smallskip{}


\subsubsection{Tempos}

Na tabela abaixo, mostramos a soma dos valores de tempo em $\mu$segundos
reportados pelo processo mestre, variando-se o número de escravos
e o número de erros permitidos:

\smallskip{}
\begin{center}\begin{tabular}{|c|c|c|c|}
\hline 
N° de&
\multicolumn{3}{c|}{N° de escravos}\tabularnewline
Erros&
1&
2&
4\tabularnewline
\hline
\hline 
0&
403496181&
188662236&
600745342\tabularnewline
\hline 
1&
833135954&
401834900&
1295250003\tabularnewline
\hline 
2&
1079122466&
524683586&
1693878512\tabularnewline
\hline 
3&
1330272313&
653271495&
2088663245\tabularnewline
\hline
\hline 
\textbf{Total}&
3646026914&
1768452217&
5678537102\tabularnewline
\hline
\end{tabular}\end{center}
\smallskip{}


\section{Versão Eletrônica}

A versão eletrônica desse documento bem como os fontes dos programas,
scripts, saídas dos programas, planilhas, gráficos, etc encontram-se
disponíveis em\noun{:}

\begin{center}\textsf{http://www.dcc.ufmg.br/\textasciitilde{}tmacam/PAA/PAA4/}\end{center}

\begin{thebibliography}{1}
\bibitem{ziviani}''Projeto de Algoritmos com implementações em Pascal e C''. Ziviani,
Nívio. 5a./6a. edição
\bibitem{hp}http://www.dcc.ufmg.br/\textasciitilde{}nivio/cursos/pa03/tp4/pa03tp4.html\end{thebibliography}

\end{document}