\documentstyle{article}
\title {\bf PROGRAMACION EN PARALELO II}
\author {Casiano Rodr\'{\i}guez Le\'on}
\date {31 de Mayo 1999}
%\pagestyle{empty}
%\pagenumbering{roman}
\begin{document}
\maketitle
\thispagestyle{empty}
\vskip 4 pt
\centerline {\bf PRACTICA FINAL}
\vskip 4 pt
\centerline {\bf RAMIFICACION Y ACOTACION EN BSP}
\vskip 8 pt

La pr\'actica consiste en llevar algunas de las ideas
desarrolladas en el esqueleto de ramificaci\'on y acotaci\'on 
visto en clase para el modelo PRAM al modelo BSP y a HPF.

Un esquema del algoritmo (pero no te sientas limtado por \'el) puede ser el siguiente: 

Cada procesador {\it name} comprueba que la cola global no esta vacia
mediante una operaci\'on de reducci\'on (se podr\'{\i}a utilizar para ello bsp\_sumI). Tambi\'en se podrma aprovechar ese momento para actualizar
el valor de la mejor soluci\'on (BestSol). En este caso ser\'{\i}a
mas conveniente utilizar una reducci\'on general (bsp\_fold).
Puedes encontrar un ejemplo de uso de bsp\_fold() en:

\begin{verbatim} 
    ftp.csi.ull.es/pub/asignas/PRGPAR1/bsp/prim/prim_ctes_bsp.c
\end{verbatim}

Despu\'es se intenta sacar un problema de la cola privada. Si
existe tal problema, se ramifica el problema enviando los problemas hijo
c\'{\i}clicamente a los procesadores {\it name}, {\it name+1}, etc. 
mediante bsp\_send.  Despu\'es de un barrier (bsp\_sync()), todos los
procesadores proceden a recolectar los problemas recibidos e
insertarlos en sus colas privadas.  


Prueba a cambiar el grano de las sincronizaciones asi como el
grano de la distribuci\'on. Ensaya otras pol\'{\i}ticas de
distribuci\'on. Haz todas las modificaciones que
consideres pueden mejorar el tiempo de ejecuci\'on.

Realiza pruebas y cronometra el programa paralelo resultante en la
cola {\it  exclusiva } de cpu.ull.es. Determina cual es la aceleraci\'on alcanzada.

Realiza una versi\'on para HPF utilizando al m\'aximo las
propiedades vectoriales del lenguaje.
\end{document}
