Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de...
-
Upload
bernardita-soliz -
Category
Documents
-
view
216 -
download
0
Transcript of Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de...
![Page 1: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/1.jpg)
Conceptos, Tecnologías e Investigación en Procesamiento Paralelo
Mauricio Marín (Universidad de Magallanes, Chile)
Centro de Investigaciones de la Web
(www.ciw.cl)
Modelo de computación
Aplicación del modeloa problemas de la Weby recuperación de laInformación.
Problemas deinvestigación.
![Page 2: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/2.jpg)
Modelo de Computación
Hardware
Software
![Page 3: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/3.jpg)
Paralelismo= Un objetivo con la ayuda de varios procesadores actuando de manera sincronizada y comunicante.
![Page 4: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/4.jpg)
Desde aplicaciones en computación científica surgió por primera vez la necesidad de utilizar paralelismo.
![Page 5: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/5.jpg)
Actualmente existe una demanda creciente por paralelismo desde aplicaciones tales como simulación de clima global o servidores para La Web, que requieren procesar grandes cantidades de datos.
Sin embargo, Computación paralela NO es una técnica ampliamente utilizada.
![Page 6: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/6.jpg)
Son más de 30 años de proposiciones de modelos y lenguajes para computación paralela.
Ninguno de ellos ha sido ampliamente adoptado.
Alto nivel de abstracción Mala eficienciaBajo nivel de abstracción Buena eficiencia
![Page 7: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/7.jpg)
En contraste, computación secuencial ha sido muy exitosa, y sus aplicaciones han llegado a todo tipo de usuarios.
![Page 8: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/8.jpg)
![Page 9: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/9.jpg)
Propiedades de un buen modelo de computación,
* Fácil de comprender.
* Metodología de ingeniería de software.
* Independiente de la arquitectura del computador.
* Predicción de desempeño.
* Desempeño eficiente y escalable.
* Fácil de programar.
30 años después....
![Page 10: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/10.jpg)
Computación Paralela Portable y Escalable
SUPER-OBJETIVO
![Page 11: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/11.jpg)
Un modelo de computación en el centro del amplio espectro de modelos y lenguajes para computación paralela:
The Bulk-Synchronous Parallel (BSP) Model
Prof. L. Valiant, Harvard University Prof. W.F. McColl, Oxford University http://www.bsp-worldwide.org
W.F. McColl
![Page 12: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/12.jpg)
Actualmente hay una convergencia en las arquitecturas paralelas
Memoria Distribuida Arquitectura Escalable
![Page 13: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/13.jpg)
SuperSteps
Paradigm of parallel computation (PVM MPI BSPpub BSPlib).
Barrier
Barrier
Barrier
msgmsgmsg
Comp.
Processors
![Page 14: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/14.jpg)
w
max
h=2 G
L
w + h*G + L
Costo de cada Superstep
![Page 15: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/15.jpg)
Cualquier computador paralelo puede ser visto como una máquinaBSP que tiene valores específicos para los parámetros G y L.
Los valores de G y L pueden ser determinados empíricamente paradistintas máquinas, y esta información puede ser utilizada parapredecir el desempeño de programas BSP sobre diversas plataformas.
![Page 16: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/16.jpg)
![Page 17: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/17.jpg)
Sincroniza
“Broadcast” en un sistema de P procesadores
1 + P*G + L
Algoritmos Fundamentales
![Page 18: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/18.jpg)
Para un sistema con gran número de procesadores se puedeutilizar una solución más eficiente:
(1 + 2*G + L )* log(P)
Sincroniza
Sincroniza
Sincroniza
![Page 19: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/19.jpg)
source
destination
Superstep 1
Superstep 2
Processors
Example: Two-stage Broadcast
m + m G + 2 L
m
m / p
m p + m p G + L
![Page 20: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/20.jpg)
![Page 21: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/21.jpg)
BSP como metodología de desarrollo de software
No existen deadlocks.
La depuración de programases sencilla.
La verificación no es más difícil que en el caso de programas secuenciales.
Es posible predecir eldesempeño de programas.
![Page 22: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/22.jpg)
El modelo de costo de BSP puede ser utilizado para:
* Guiar el proceso de diseño e implementación de programas.
* Predecir el desempeño del programa al ser portado a otras máquinas.
* Seleccionar automáticamente los algoritmos que mejor se ajustan a una máquina en particular.
* Guiar el proceso de compra de computadores se conocen las características de los programas BSP que correrán en ellos.
![Page 23: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/23.jpg)
La estructura del modelo BSP permite el uso de herramientasgráficas de perfil de ejecución de supersteps.
![Page 24: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/24.jpg)
![Page 25: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/25.jpg)
![Page 26: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/26.jpg)
![Page 27: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/27.jpg)
![Page 28: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/28.jpg)
Internet
Switch
Server PC clusterBSP machine
Clients
![Page 29: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/29.jpg)
SStep 1
P1 P2 P3 P4
SStep 2
Query
BSP Cluster
Result
![Page 30: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/30.jpg)
SStep 1
SStep 2
BROKER
BSP Cluster
Queries
Results
![Page 31: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/31.jpg)
Bases de Datos Relacionales
Servidor Web
Servidor B.D.Servidor B.D. Servidor B.D.
ClienteHTML
![Page 32: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/32.jpg)
La base de datos esta distribuida en varios computadores
Front-end
![Page 33: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/33.jpg)
Solución basada en software de dominio público
![Page 34: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/34.jpg)
0
1000
2000
3000
4000
5000
6000
PRODUCTOS
Segundos
PAR
SEQ
350 versus 5600 Seg => 16 veces más rápido con 4 máquinas
Consultas a un servidor de Libros“Cantidad vendida por cada tema”
![Page 35: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/35.jpg)
Tiempo de Procesamiento TP, Tiempo de Sincronización TS, Tiempo de Acceso a la Base de Datos TB, Tiempo de Comunicación TC.
![Page 36: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/36.jpg)
Tiempo de Procesamiento TP, Tiempo de Sincronización TS, Tiempo de Acceso a la Base de Datos TB, Tiempo de Comunicación TC.
![Page 37: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/37.jpg)
![Page 38: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/38.jpg)
![Page 39: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/39.jpg)
El número de páginas Web es del orden de 1000 millones (año 2000).
La Web
![Page 40: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/40.jpg)
Buscadores de la Web
Interface
Máquina deBúsqueda
Recolector
Indexador
Usuarios
Base de Documentos
Web
![Page 41: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/41.jpg)
Robots
WEBPlanificador
Lista URLs
Proceso de “Crawling”
![Page 42: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/42.jpg)
W
B and T and X and Z
B
T
X
Z
W
W
W
Vocabulary Inverted Lists
Query =
MAQUINA DE BUSQUEDA: Inverted Files
Document identifiers
![Page 43: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/43.jpg)
BROKER
Servidor Paralelo
Consultas
Proceso de consultasRanking de resultadosBalance de Carga
Menor carga posible
Usuarios
![Page 44: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/44.jpg)
Processsor 1
Processor 2
Global Index approach
N
![Page 45: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/45.jpg)
Local Index approach
Procesador 1 Procesador 2
N/P N/P
![Page 46: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/46.jpg)
Processsor 1
Processor 2
Composite Inverted Lists
X
X
A
B
C
D
![Page 47: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/47.jpg)
a a a ab b b c
c d d de f g h
a a a a b b b
c c d d d e f g h
Bucket Inverted Lists
Processor 1 Processor 2 Processor 3 Processor 4
List 1 List 2
![Page 48: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/48.jpg)
• Balance de Carga
• ¿Cómo distribuir los “buckets” en los procesadores?
• ¿Distribución basada en “log” de consultas?
• ¿Distribución aleatoria y cambio dinámico?
• Scheduling
• ¿En qué procesador realizar el ranking de documentos?
• ¿Cuantos documentos enviar al procesador de ranking?
![Page 49: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/49.jpg)
Processsor 1
Processor 2
Servicio de Noticias
A B C D
A
B
C
D
Escritura A and B and C and DLectura
W(A,1) W(B,1) W(C,1) W(D,1)
Timestamp
R(A,2) R(B,2) R(C,2) R(D,2)
R(A,0) R(D,0)
![Page 50: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/50.jpg)
Control de Concurrencia
W(A,1) R(A,2)R(B,2) W(B,1)
Procesador 1 Procesador 2
R(C,2) R(D,2) W(D,1) W(C,1)
Sort by Timestamp Sort by Timestamp
W(A,1) W(B,1)
R(A,2) R(A,2)
W(D,1)W(C,1)
R(C,2) R(D,2)
R(A,0) R(D,0)
R(A,0) R(D,0)
![Page 51: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/51.jpg)
Sequential Suffix Arrays
![Page 52: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/52.jpg)
text
text
Binary-searching “text”
![Page 53: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/53.jpg)
Problem: Pointers to every-where in the text
![Page 54: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/54.jpg)
“Pruned Suffixes”
is
exa
dat
an
a of
tex
tex
thi
![Page 55: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/55.jpg)
BSP Cluster
Distributed Query Processing
The text database is evenly distributed upon the processors.
![Page 56: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/56.jpg)
Processor 1 Processor 2
The local index approach
![Page 57: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/57.jpg)
SStep 1
SStep 2
BROKER
BSP Cluster
Queries
ResultsSStep 3
![Page 58: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/58.jpg)
Processor 1 Processor 2
The global index approach
is
exa
dat
an
a of
tex
tex
thi
![Page 59: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/59.jpg)
SStep 1
SStep 2
BROKER
BSP Cluster
Queries
Results
![Page 60: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/60.jpg)
Dealing with load-imbalance (Multiplexion)
28 38 11 6 1 14 17 25 30
Processor 1 Processor 2
is
exa
dat
an
a of
tex
tex
thi
![Page 61: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/61.jpg)
Binary search accross processors
Processor i
Processor i + p / 2
Processor i + p / 4
![Page 62: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/62.jpg)
A minor but practical improvement to the Global Index Strategy
Proc 1 Proc 2 Proc 3 Proc 4
Proc 1 Proc 2 Proc 3 Proc 4
Global
Virtual Global
![Page 63: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/63.jpg)
Seq
Local
DB Size
RunningTime
Processing q queries on p processors upon a text of n chars
Virtual Global
Global Multiplexed
![Page 64: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/64.jpg)
Server 1
Server 2
Server 3
Scheduling Problem (uniform routing)
Distributed allocation of Parallel Servers
![Page 65: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/65.jpg)
![Page 66: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/66.jpg)
ServerBSP Machine
Número de procesadores requeridos
Tiempos de ejecución
![Page 67: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/67.jpg)
0 1
F(P, G, L, Ns, Np)
![Page 68: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/68.jpg)
Simulación por Eventos Discretos
El sistema se representa como un conjunto de variables de estado.
Los eventos cambian las variables de estado en puntos discretos del tiempo de simulación.
Simulación en Paralelo
Las variables relacionadas se agrupan dentro de procesos lógicos que se comunican entre sí mediante mensajes.
![Page 69: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/69.jpg)
Tiempo
e1 e2 e3 e4 e5 e6
Tiempo
e1 e3 e5 e6
Tiempo
e2 e4
LP1
LP2
![Page 70: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/70.jpg)
MensajesNuevos
+
+
+
+
-
+
Lista deEventos
A B C D E F
Tiempo
Procesador Superstep i
+
- - - - -
Mensaje(Evento)
SendEventos procesados
Proceso Lógico
![Page 71: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/71.jpg)
MensajesNuevos
+
+
+
+
-
+
Lista deEventos
A B C D E F
Procesador Superstep i+1
- - - - -
G
Rollback
Send
![Page 72: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/72.jpg)
Procesador 1 Procesador P
K K
En cada procesador se procesan hasta K eventos.
Cada procesador puede tener un K distinto.
K se mantiene fijo, independiente de los eventos re-simulados.
![Page 73: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/73.jpg)
![Page 74: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/74.jpg)
![Page 75: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/75.jpg)
S
S + AL
R
L
R
S
S + A
S + 1
S + A + 1
Contador
Mensajeenviado
AA <= S
Mensajenuevo
A
A > S
Cada proceso lógico mantiene un contador de supersteps.
En cada mensaje se transmite el valor de un contador de supersteps.
![Page 76: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/76.jpg)
![Page 77: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/77.jpg)
![Page 78: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/78.jpg)
![Page 79: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/79.jpg)
Carga baja y alta Número de procesadores= 4, 16, 64 y 256
![Page 80: Conceptos, Tecnologías e Investigación en Procesamiento Paralelo Mauricio Marín (Universidad de Magallanes, Chile) Centro de Investigaciones de la Web.](https://reader033.fdocumento.com/reader033/viewer/2022051622/5665b4421a28abb57c907c79/html5/thumbnails/80.jpg)
Conclusiones
• Se ha mostrado cómo utilizar un modelo que incorpora conceptos modernos de computación paralela en el diseño de algunas aplicaciones de gran popularidad e importancia en la Web.
• El modelo BSP es mucho más que una biblioteca de comunicaciones tal como PVM o MPI, es un estilo o método estructurado de diseño de software paralelo.
PREGUNTAS ?