Monografias.com > Uncategorized
Descargar Imprimir Comentar Ver trabajos relacionados

Algoritmos paralelos de grafos y búsqueda (página 2)




Enviado por Pablo Turmero



Partes: 1, 2

Monografias.com

Áreas de
Aplicación
Métodos/
Problemas
Arquitecturas
Algoritmos
de Grafos
Traversal

Shortest Paths

Connectivity

Max Flow


GPUs
FPGAs

Servidores
x86 multicore

Arquitecturas
Multihilos
másicas

Cluster de
Multicore

Clouds
Análisis de
Redes Sociales

WWW

Biología
Computacionañ

Computación
Científica

Ingeniería
Halla entidades centrales
Detección de comunidades
Dinámicas de redes
Data size
Problem
Complexity
Particionar grafos
Matching
Coloreado
Regulación de Genes
Rutas metabólicas
Genómica
Marketing
Búsqueda social

CAD para VLSI
Planear rutas

Monografias.com

Esquema general de computar grafos
graph sparsity (m/n ratio)
static/dynamic nature
weighted/unweighted, weight distribution
vertex degree distribution
directed/undirected
simple/multi/hyper graph
problem size
granularity of computation at nodes/edges
domain-specific characteristics
paths
clusters
partitions
matchings
patterns
orderings
Input data
Problem: Find ***
Factors that influence
choice of algorithm
Graph kernel
traversal
shortest path algorithms
flow algorithms
spanning tree algorithms
topological sort
…..
Graph problems are often recast as sparse linear algebra (e.g., partitioning) or linear programming (e.g., matching) computations

Monografias.com

Definiciones y Representación
Un grafo no dirigido G es un par (V,E), donde V es un cjto. finito de puntos llamados vértices y E es un cjto. finito de aristas o arcos.
Una arista e ? E es un par no ordenado (u,v), u,v ? V.
En un grafo dirigido, e es un par ordenado (u,v). Una arista (u,v) es incidente del vértice u y es incidente a v.
Una ruta del vértice v al u es una secuencia < v0,v1,v2,…,vk> de vertices donde v0 = v, vk = u, y (vi, vi+1) ? E para i = 0, 1,…, k-1.
La longitud de la ruta está definida por el número de aristas en la ruta.

Monografias.com

Definiciones y Representación
a) Grafo no dirigido (b) Grafo dirigido

Monografias.com

Definiciones y Representación
Un grafo no dirigido está conectado si cada par de vértices está conectado por una ruta.
Un bosque es un grafo acíclico, y un árbol es un grafo conectado acíclico.
Un grafo que tiene pesos asociados con cada arista es un grafo ponderado.

Monografias.com

Definiciones y Representación
Un grafo se puede representar por una matriz de adyacencia o una lista de aristas (o vértices).
Las matrices de adyacencia tienen un valor ai,j = 1 si los nodos i , j comparten una arista; 0 en caso contrario. En un grafo ponderado, ai,j = wi,j, el peso de la arista.
La lista de adyacencia para un grafo G = (V,E) consiste de un array Adj[1..|V|] de listas. Cada lista Adj[v] es una lista de todos los vértices adyac. a v.
Para un grafo de n nodos, la matriz de adyacencia ocupa espacio de T(n2) y la lista ocupa T(|E|).

Monografias.com

Definiciones y Representación
Grafo no dirigido y su matriz de adyacencia
Grafo no dirigido y su lista de adyacencia

Monografias.com

Minimum Spanning Tree
Un spanning tree de un grafo no dirigido G es un subgrafo de G que es un árbol que contiene todos los vértices de G.
Un un grafo ponderado, el peso de un subgrafo es la suma de los pesos de las aristas del subgrafo.
Un minimum spanning tree (MST) sería el spanning tree con peso mínimo.

Monografias.com

Minimum Spanning Tree
Un grafo no dirigido y
su minimum spanning tree.

Monografias.com

Minimum Spanning Tree: Algoritmo de Prim
Es un algoritmo goloso (greedy).
Empieza escogiendo un vértice arbitrario, y lo incluye en el actual MST.
Hace crecer al actual MST incorporando en él al vértice más cercano a uno de los vértices del actual MST.

Monografias.com

Minimum Spanning Tree: Algoritmo de Prim

Monografias.com

Minimum Spanning Tree: Algoritmo de Prim
Versión secuencial (no paralela)

Monografias.com

Algoritmo de Prim paralelo
El “while”– es difícil ejecutarlos en paralelo.
El “for” interno es más fácil de paralelizar. Sea p el número de procs., y n el número de vértices.
La matriz de adyacencia se particiona en bloques 1-D, con el vector de distancia d particionado así también.
En cada paso, el proc. escoge el nodo más cerca localmente, luego se hace una reducción global para escoger el nodo más cercano global.
Se inserta ese nodo al MST, y se hace el broadcast respectivo a todos los procs.
Cada proc. actualiza su parte del vector d localmente.

Monografias.com

Algoritmo de Prim paralelo
La partición del vector de distancia d y la matriz de adyacencia A entre p procs.

Monografias.com

Algoritmo de Prim paralelo
El costo de seleccionar el nodo más cercano es O(n/p + log p).
El costo del broadcast es O(log p).
El costo de actualización local del vector d es O(n/p).
El tiempo paralelo por iteración es O(n/p + log p).
El tiempo total paralelo es O(n2/p + n log p).
La isoeficiencia es O(p2log2p).

Monografias.com

Ruta más corta – un solo origen
En un grafo ponderado G = (V,E,w), el problema de la ruta más corta con un solo origen es encontrar las rutas más cortas de un vértice v ? V a los demás vértices en V.
El algoritmo de Dijkstra es parecido al de Prim. Mantiene un conjunto de nodos de los cuáles se sabe sus rutas más cortas.
Este conjunto crece basado en el nodo más cercano al origen usando uno de los nodos en el actual conjunto de ruta más corta.

Monografias.com

Algoritmo de Dijkstra
Algoritmo de Dijkstra, secuencial

Monografias.com

Algoritmo de Dijkstra paralelo
Similar a Prim paralelo para MST.
La matriz de adyacencia ponderada se particiona usando bloques 1-D.
Cada proceso escoge, localmente, el nodo más cercano al origen, seguido por una reducción global para escoger el siguiente nodo.
Se hace broadcast de ese nodo y del vector l actualizado a todos los procesadores
Performance paralela es idéntica al Prim paralelo

Monografias.com

Rutas más cortas – todos los pares
Dado un grafo ponderado G(V,E,w), el problema de todos los pares de rutas más cortas es encontrar las rutas más cortas entre todos los pares de vértices vi, vj ? V.
Hay varios algoritmos que resuelven este problema.

Monografias.com

Rutas más cortas – todos los pares:Algoritmo basado en MatMult
Considere la multiplicación de la matriz de adyacencia ponderada consigo misma – pero reemplaze las multiplicaciones de números x*y por sumas x+y, y las sumas x+y por min(x,y).
El “producto” de la matriz de adyacencia ponderada consigo misma = una matriz que contiene las rutas más cortas de longitud 2 entre cualquier par de nodos.
Luego, “ An ” contiene todas las rutas más cortas.

Monografias.com

Algoritmo basado en MatMult

Monografias.com

Algoritmo basado en MatMult
“An” es calculado doblando las potencias: A, A2, A4, A8, …
Se necesita log n MatMults, cada una se tarda O(n3).
Complejidad serial: O(n3log n).
Hay mejores algoritmos, con complejidad O(n3).

Monografias.com

Algoritmo basado en MatMult, en paralelo
Cada una de las log n MatMults se pueden hacer en paralelo.
Se pueden usar n3/log n procs para computar cada producto matriz-matriz en tiempo log n.
Tiempo total: O(log2n).

Monografias.com

Dijkstra para todos los pares
Ejecutar n instancias de Dijkstra para 1 solo origen, uno para cada uno de los n vértices como origen.
Complejidad es O(n3).

Monografias.com

Dijkstra para todos los pares, en paralelo
Hay dos estrategias para paralelizar – ejecutar cada uno de los n problemas de ruta más corta con un solo origen en un diferente procs. (partición de los orígenes), o usar la versión paralela de la ruta más corta con un solo origen (paralelizar cada origen).

Monografias.com

Partición de los orígenes
Use n procs, cada proc Pi calcula las rutas más cortas desde el vértice vi a los demás vertices con Dijkstra secuencial.
No hay comunicación entre procesadores (suponiendo que la matriz de adyacencia esta replicada en todos los procs).
Tiempo paralelo: T(n2).
Es de costo óptimo, pero solo puede usarse n procs. ? La isoeficiencia es p3.

Monografias.com

Paralelizar cada origen
Cada ruta más corta de un solo origen es hecha en paralelo. Se pueden usar hasta n2 procs. si combino con método anterior.
Dados p procs (p > n), cada problema individual es ejecutado por p/n procs.
Tomaría un tiempo de:

Costo óptimo p = O(n2/log n) , isoeficiencia es T((p log p)1.5)

Monografias.com

Algoritmo de Floyd
Para cada par de vértices vi, vj ? V, considere todas las rutas de vi a vj cuyos vértices intermedios pertenecen a {v1,v2,…,vk}. Sea pi(,kj) (de peso di(,kj) ) la ruta más corta de entre ellas.
Si vk está en la ruta más corta de vi a vj, entonces pi(,kj) es la misma que pi(,kj-1)
Si vk está en pi(,kj), entonces podemos partir a pi(,kj) en 2 rutas – una de vi a vk y otra de vk a vj . Cada una de estas rutas usan vértices de {v1,v2,…,vk-1}.

Monografias.com

Algoritmo de Floyd
La siguiente relación de recurrencia se observa:
Esta ecuación debe ser computada por cada par de nodos y para k = 1,…, n. Complejidad serial es de O(n3).

Monografias.com

Algoritmo de Floyd
Computa todas las rutas más cortas entre todos los pares de vértices del grafo G = (V,E) con matriz de adyacencia A.

Monografias.com

Algoritmo de Floyd en paralelo con Bloques 2-D
Matriz D(k) se divide en p bloques de tamaño (n / vp) x (n / vp).
Cada proc. actualiza su parte de la matriz durante cada iteración.
Para computar dl(,kk-1) el proc Pi,j debe obtener dl(,kk-1) and dk(,kr-1).
En general, durante la iteración kesima, cada uno de los vp procs conteniendo parte de la fila kesima la envía a los vp – 1 procs de la misma columna.
De la misma forma, cada uno de los vp procs que contienen parte de la kesima columna la envían a los vp – 1 procs de la misma fila.

Monografias.com

Algoritmo de Floyd en paralelo con Bloques 2-D
(a) Matriz D(k) distribuida en bloques 2-D mapeados así: vp x vp subbloques, (b) el subbloque de D(k) asignado al proc Pi,j

Monografias.com

Algoritmo de Floyd en paralelo con Bloques 2-D
(a) Patrones de comunicación en mapeo en bloques 2-D. Al computar di(,kj), info debe mandarse a los procs subrayados desde otros 2 procs en la misma fila y columna. (b) La fila y columna de vp procs que contiene la kesima fila y columna las envía junto con columnas y filas.

Monografias.com

Algoritmo de Floyd en paralelo con Bloques 2-D
Floyd en paralelo usando blqoues 2-D. P*,j son todos los procs en la jesima columna, y Pi,* son todos los procs en la fila iesima. La matriz D(0) es la matrix de adyacencia

Monografias.com

Algoritmo de Floyd en paralelo con Bloques 2-D
Durante cada iteración del algoritmo, la fila kesima y la columna kesima de procs hacen un broadcast 1-a-todos a lo largo de sus filas/columnas.
El tamaño del broadcast es n/vp elementos, tiempo: T((n log p)/ vp).
El paso de sincronizar toma T(log p).
El tiempo de computación es T(n2/p).
Tiempo paralelo de Floyd con bloques 2D es:

Monografias.com

Se puede usar O(n2 / log2 n) procs a costo óptimo.
Isoeficiencia es T(p1.5 log3 p).
Se puede mejorar si se relaja la sincronización estricta luego de cada iteración.

Algoritmo de Floyd en paralelo con Bloques 2-D

Monografias.com

Floyd acelerado con Pipelining
El paso de sincronización del Floyd paralelo se puede remover sina afectar los resultados.
Un proc comienza a trabajar en la kth iteración apenas se ha computado la iteración (k-1)esima y tiene partes relevantes de la matriz D(k-1)

Monografias.com

Floyd acelerado con Pipelining
Asume que elproc 4 en el tiempo t acaba de computar de la columna kesima de la matriz D(k-1). Manda el segmento a procs 3 y 5. Estos procs reciben el segmento en el momento t + 1 (1 tiempo= lo que tarda un segmento de un nodo a su vecino inmediato). Procs lejos del 4 reciben el segmento después. Proc 1 (en el boundary) no reenvía elemento después de recibirlo.

Monografias.com

Floyd acelerado con Pipelining
En cada paso, n/vp elementos de la 1ra fila se envían desde Pi,j al Pi+1,j.
Similarmente, elementos de la 1ra columna se envían de Pi,j al Pi,j+1.
Cada paso demora: T(n/vp).
Luego de T(vp) pasos, el proc Pvp ,vp obtiene los elementos relevantes de la 1ra cola y 1ra col en tpo T(n).
Los valores de otras filas y cols siguen luego de T(n2/p) modo pipeline.
Proc Pvp ,vp termina su parte de computación en T(n3/p) + T(n).
Cuando el proc Pvp ,vp ha terminado en la iteración (n-1)th, envía los valores relevantes de la nth fila y columna a otros procs.

Monografias.com

Floyd acelerado con Pipelining
Tiempo paralelo:

Usa hasta O(n2) procesadores eficientemente.
Isoeficiencia es T(p1.5).

Monografias.com

Comparación
La performance y escalabilidad de varios algoritmos se muestra.

Monografias.com

Clausura transitiva (Transitive Closure)
Si G = (V,E) es un grafo, entonces la transitive closure de G es el grafo G* = (V,E*), donde E* = {(vi,vj) | hay un path del vi al vj en G}
La matriz de conectividad G es una matriz A* = (ai*,j) tal que ai*,j = 1 si hay alguna ruta de vi a vj a i = j, y ai*,j = 8 de otra manera.
Para computar A* se asigna un peso de 1 para cada arista E y se usa cualquiera de las rutas mas cortas – todos los pares.

Monografias.com

Componentes conectados
Los componentes conectados de un gafo no dirigido son las clases equivalentes de vértices bajo la relación “es alcanzable desde”
Grafo con 3 componentes conectados: {1,2,3,4}, {5,6,7}, y {8,9}.

Monografias.com

Usando alg. Depth-First Search
Hacer DFS en el grafo para obtener un bosque- cada árbol de la forest es un “connected component” separado
(b) Es un bosque obtenido de un trasverse DF del gráfico en (a).

Monografias.com

Componentes conectados en paralelo
Particionar el grafo entre los procs y correr algoritmos independientes en cada proc. En este punto, tenemos p “spanning forests”.
En el segundo paso, se combinan estas “forest” de 2 en 2 hasta que solo quede 1.

Monografias.com

Componentes conectados en paralelo
La matriz de adyacencia de G en (a) se particiona en dos (b). Cada proceso consigue un subgrafo de G ((c) y (e)). Cada proceso computa el spanning forest de su subgrafo ((d) y (f)). Finalmente, los dos bosques se combinan en uno.

Monografias.com

Componentes conectados en paralelo
Para unir pares de bosques, el algoritmo usa conjuntos disjuntos de aristas.
Definimos estas operaciones en esos conjuntos:
find(x)
Devuelve un puntero al elemento representativo del cjto conteniendo x . Cada cjto tiene su propio y único representativo.
union(x, y)
Une los conjuntos conteniendo los elementos x , y. se asume que los dos cjtos eran disjuntos antes de esta operación.

Monografias.com

Componentes conectados en paralelo
Para unir el bosque A con el B, para cada arista (u,v) de A, se efectúa una operación find para determinar si los vértices están en el mismo árbol de B.
Si no, los dos árboles (cjtos) de B conteniendo u y v se unen con una operación unión.
Caso contrario, no se hace “union”.
Por lo tanto, unir A y B requiere no más de 2(n-1) “find” y (n-1) “union”.

Monografias.com

Componentes conectados: paralelo con Bloques 1-D
The n x n adjacency matrix is partitioned into p blocks.
Each processor can compute its local spanning forest in time T(n2/p).
Merging is done by embedding a logical tree into the topology. There are log p merging stages, and each takes time T(n). Thus, the cost due to merging is T(n log p).
During each merging stage, spanning forests are sent between nearest neighbors. Recall that T(n) edges of the spanning forest are transmitted.

Monografias.com

Componentes conectados: paralelo con Bloques 1-D
The parallel run time of the connected-component algorithm is

For a cost-optimal formulation p = O(n / log n). The corresponding isoefficiency is T(p2 log2 p).

Partes: 1, 2
 Página anterior Volver al principio del trabajoPágina siguiente 

Nota al lector: es posible que esta página no contenga todos los componentes del trabajo original (pies de página, avanzadas formulas matemáticas, esquemas o tablas complejas, etc.). Recuerde que para ver el trabajo en su versión original completa, puede descargarlo desde el menú superior.

Todos los documentos disponibles en este sitio expresan los puntos de vista de sus respectivos autores y no de Monografias.com. El objetivo de Monografias.com es poner el conocimiento a disposición de toda su comunidad. Queda bajo la responsabilidad de cada lector el eventual uso que se le de a esta información. Asimismo, es obligatoria la cita del autor del contenido y de Monografias.com como fuentes de información.

Categorias
Newsletter