Algoritmos paralelos de grafos y bsqueda (pt.1: grafos)Glen RodrguezAlgoritmos paralelos

AgendaVista general de las AplicacionesDefiniciones y Representacin rbol recubridor mnimo (Minimum Spanning Tree): Alg. de PrimRuta ms corta (con un solo origen): Dijkstra's Algorithm Todas los pares de Rutas ms cortasClausura transitiva (Transitive Closure)Componentes conectados

Redes de transporte, rutas ms cortas: 15 segs (nave) 10 microsegsRuteo en transporte terrestreH. Bast et al., Fast Routing in Road Networks with Transit Nodes, Science 27, 2007.

La web se puede representar como grfico dirigidoWeb search , web crawl: traversal (recorrido de grafo)Anlisis de links, ranking: Page rank, HITSClasificacin y clustering (agrupamiento) de documentosLas topologas de Internet (redes de routers) are se modelan naturalmente como grafosInternet y la WWW

Reordernar cols/filas en matr.dispersasPara reducir/concentrar el llenoParticionar, eigen-vectoresDiagonal pesada para menos pivotingEstructuras de datos para explotar mejor el patrn dispersoOptimizacinMatroides, colorear grafos, spanning treesPreconditionadoresFactorizacin incompletaParticionar dominiosGrafos en multigridIndependent sets, matchings, etc.Teora de soprteSpanning trees & graph embeddingCmputo cientficoB. Hendrickson, Graphs and HPC: Lessons for Future Architectures, http://www.er.doe.gov/ascr/ascac/Meetings/Oct08/Hendrickson%20ASCAC.pdfImage source: Yifan Hu, A gallery of large graphsImage source: Tim Davis, UF Sparse Matrix Collection.

Abstraer algo como grafo es til parta analizar data con relaciones/estructura complicada.Fuentes de data: simulaciones de peta-escala, sensores en experimentos, Internet, redes de sensoresDesafios: enorme tamao de data, heterogeneidad, incertidumbre, calidad de la dataAnlisis de grandes cantidades de dataAstrofsica: datasets masivos, variaciones en el tiempoBioinformtica: calidad de data, heterogeneidadRedes sociales: anisis, incertidumbreImage sources: (1) http://physics.nmt.edu/images/astro/hst_starfield.jpg (2,3) www.visualComplexity.com

Estudio de la interaccin entre componentes de un sistema biolgicoSe usan mucho los grafos:Predecir nuevas interacciones: modeladoAnotacin funcional de nuevas protenas: matching, clusteringIdentificar rutas metablicas: rutas, clusteringIdentificar nuevos complejos de protenas: clustering, centralidadAnlisis de data y Alg. de grafos en Biologa SistmicaImage Source: Giot et al., A Protein Interaction Map of Drosophila melanogaster, Science 302, 1722-1736, 2003.

Image Source: Nexus (Facebook application)Grafos y las redes socialesIdentificar comunidades: clusteringPublicidad personalizada: centralidadDifusin de la informacin: modelado

[Krebs 04] Anlisis de redes terroristas usando informacin pblica (luego de Torres Gemelas).Determinar lderes de los patrones de interaccin: centralidad

Vista globla de las entidades arroja ms lucesDetectar actividades anormales isomorfismo de subgrafos exacto o aproximadoImage Source: http://www.orgnet.com/hijackers.htmlAnlisis de redes para Inteligencia y VigilanciaImage Source: T. Coffman, S. Greenblatt, S. Marcus, Graph-based technologies for intelligence analysis, CACM, 47 (3, March 2004): pp 45-47

reas deAplicacinMtodos/ProblemasArquitecturasAlgoritmosde GrafosTraversal

Shortest Paths

Connectivity

Max Flow

GPUsFPGAs

Servidoresx86 multicore

ArquitecturasMultihilosmsicas

Cluster deMulticore

CloudsAnlisis deRedes Sociales

WWW

Biologa Computaciona

ComputacinCientfica

IngenieraHalla entidades centralesDeteccin de comunidadesDinmicas de redesData sizeProblemComplexityParticionar grafosMatchingColoreadoRegulacin de GenesRutas metablicasGenmicaMarketingBsqueda social

CAD para VLSI Planear rutas

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 orderingsInput dataProblem: Find ***Factors that influence choice of algorithmGraph 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

Definiciones y Representacin Un grafo no dirigido G es un par (V,E), donde V es un cjto. finito de puntos llamados vrtices 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 vrtice u y es incidente a v. Una ruta del vrtice v al u es una secuencia 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 nmero de aristas en la ruta.

Definiciones y Representacina) Grafo no dirigido (b) Grafo dirigido

Definiciones y RepresentacinUn grafo no dirigido est conectado si cada par de vrtices est conectado por una ruta. Un bosque es un grafo acclico, y un rbol es un grafo conectado acclico. Un grafo que tiene pesos asociados con cada arista es un grafo ponderado.

Definiciones y RepresentacinUn grafo se puede representar por una matriz de adyacencia o una lista de aristas (o vrtices). 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 vrtices adyac. a v. Para un grafo de n nodos, la matriz de adyacencia ocupa espacio de (n2) y la lista ocupa (|E|).

Definiciones y RepresentacinGrafo no dirigido y su matriz de adyacenciaGrafo no dirigido y su lista de adyacencia

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 vrtices 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) sera el spanning tree con peso mnimo.

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

Minimum Spanning Tree: Algoritmo de PrimEs un algoritmo goloso (greedy). Empieza escogiendo un vrtice arbitrario, y lo incluye en el actual MST. Hace crecer al actual MST incorporando en l al vrtice ms cercano a uno de los vrtices del actual MST.

Minimum Spanning Tree: Algoritmo de Prim

Minimum Spanning Tree: Algoritmo de PrimVersin secuencial (no paralela)

Algoritmo de Prim paraleloEl while es difcil ejecutarlos en paralelo. El for interno es ms fcil de paralelizar. Sea p el nmero de procs., y n el nmero de vrtices. La matriz de adyacencia se particiona en bloques 1-D, con el vector de distancia d particionado as tambin. En cada paso, el proc. escoge el nodo ms cerca localmente, luego se hace una reduccin global para escoger el nodo ms 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.

Algoritmo de Prim paralelo

La particin del vector de distancia d y la matriz de adyacencia A entre p procs.

Algoritmo de Prim paraleloEl costo de seleccionar el nodo ms cercano es O(n/p + log p). El costo del broadcast es O(log p). El costo de actualizacin local del vector d es O(n/p). El tiempo paralelo por iteracin es O(n/p + log p). El tiempo total paralelo es O(n2/p + n log p). La isoeficiencia es O(p2log2p).

Ruta ms corta un solo origenEn un grafo ponderado G = (V,E,w), el problema de la ruta ms corta con un solo origen es encontrar las rutas ms cortas de un vrtice v V a los dems vrtices en V. El algoritmo de Dijkstra es parecido al de Prim. Mantiene un conjunto de nodos de los cules se sabe sus rutas ms cortas. Este conjunto crece basado en el nodo ms cercano al origen usando uno de los nodos en el actual conjunto de ruta ms corta.

Algoritmo de Dijkstra

Algoritmo de Dijkstra, secuencial

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 ms cercano al origen, seguido por una reduccin global para escoger el siguiente nodo. Se hace broadcast de ese nodo y del vector l actualizado a todos los procesadoresPerformance paralela es idntica al Prim paralelo

Rutas ms cortas - todos los pares

Dado un grafo ponderado G(V,E,w), el problema de todos los pares de rutas ms cortas es encontrar las rutas ms cortas entre todos los pares de vrtices vi, vj V. Hay varios algoritmos que resuelven este problema.

Rutas ms cortas - todos los pares:Algoritmo basado en MatMultConsidere la multiplicacin de la matriz de adyacencia ponderada consigo misma pero reemplaze las multiplicaciones de nmeros 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 ms cortas de longitud 2 entre cualquier par de nodos. Luego, An contiene todas las rutas ms cortas.

Algoritmo basado en MatMult

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).

Algoritmo basado en MatMult, en paraleloCada 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).

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

Dijkstra para todos los pares, en paraleloHay dos estrategias para paralelizar ejecutar cada uno de los n problemas de ruta ms corta con un solo origen en un diferente procs. (particin de los orgenes), o usar la versin paralela de la ruta ms corta con un solo origen (paralelizar cada origen).

Particin de los orgenes Use n procs, cada proc Pi calcula las rutas ms cortas desde el vrtice vi a los dems vertices con Dijkstra secuencial. No hay comunicacin entre procesadores (suponiendo que la matriz de adyacencia esta replicada en todos los procs). Tiempo paralelo: (n2). Es de costo ptimo, pero solo puede usarse n procs. La isoeficiencia es p3.

Paralelizar cada origen

Cada ruta ms corta de un solo origen es hecha en paralelo. Se pueden usar hasta n2 procs. si combino con mtodo anterior.Dados p procs (p > n), cada problema individual es ejecutado por p/n procs. Tomara un tiempo de:

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

Algoritmo de FloydPara cada par de vrtices vi, vj V, considere todas las rutas de vi a vj cuyos vrtices intermedios pertenecen a {v1,v2,,vk}. Sea pi(,kj) (de peso di(,kj) ) la ruta ms corta de entre ellas. Si vk est en la ruta ms 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 vrtices de {v1,v2,,vk-1}.

Algoritmo de FloydLa siguiente relacin de recurrencia se observa: Esta ecuacin debe ser computada por cada par de nodos y para k = 1,, n. Complejidad serial es de O(n3).

Algoritmo de FloydComputa todas las rutas ms cortas entre todos los pares de vrtices del grafo G = (V,E) con matriz de adyacencia A.

Algoritmo de Floyd en paralelo con Bloques 2-DMatriz D(k) se divide en p bloques de tamao (n / p) x (n / p). Cada proc. actualiza su parte de la matriz durante cada iteracin. Para computar dl(,kk-1) el proc Pi,j debe obtener dl(,kk-1) and dk(,kr-1). En general, durante la iteracin kesima, cada uno de los p procs conteniendo parte de la fila kesima la enva a los p - 1 procs de la misma columna. De la misma forma, cada uno de los p procs que contienen parte de la kesima columna la envan a los p - 1 procs de la misma fila.

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

Algoritmo de Floyd en paralelo con Bloques 2-D(a) Patrones de comunicacin 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 p procs que contiene la kesima fila y columna las enva junto con columnas y filas.

Algoritmo de Floyd en paralelo con Bloques 2-DFloyd 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

Algoritmo de Floyd en paralelo con Bloques 2-DDurante cada iteracin 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 tamao del broadcast es n/p elementos, tiempo: ((n log p)/ p). El paso de sincronizar toma (log p). El tiempo de computacin es (n2/p). Tiempo paralelo de Floyd con bloques 2D es:

Algoritmo de Floyd en paralelo con Bloques 2-DSe puede usar O(n2 / log2 n) procs a costo ptimo. Isoeficiencia es (p1.5 log3 p). Se puede mejorar si se relaja la sincronizacin estricta luego de cada iteracin.

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

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 despus. Proc 1 (en el boundary) no reenva elemento despus de recibirlo.

Floyd acelerado con Pipelining

En cada paso, n/p elementos de la 1ra fila se envan desde Pi,j al Pi+1,j. Similarmente, elementos de la 1ra columna se envan de Pi,j al Pi,j+1. Cada paso demora: (n/p). Luego de (p) pasos, el proc Pp ,p obtiene los elementos relevantes de la 1ra cola y 1ra col en tpo (n). Los valores de otras filas y cols siguen luego de (n2/p) modo pipeline. Proc Pp ,p termina su parte de computacin en (n3/p) + (n). Cuando el proc Pp ,p ha terminado en la iteracin (n-1)th, enva los valores relevantes de la nth fila y columna a otros procs.

Floyd acelerado con Pipelining

Tiempo paralelo:

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

Comparacin

La performance y escalabilidad de varios algoritmos se muestra.

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 = 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.

Componentes conectadosLos componentes conectados de un gafo no dirigido son las clases equivalentes de vrtices bajo la relacin es alcanzable desdeGrafo con 3 componentes conectados: {1,2,3,4}, {5,6,7}, y {8,9}.

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 grfico en (a).

Componentes conectados en paraleloParticionar 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.

Componentes conectados en paraleloLa 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.

Componentes conectados en paraleloPara 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 operacin.

Componentes conectados en paraleloPara unir el bosque A con el B, para cada arista (u,v) de A, se efecta una operacin find para determinar si los vrtices estn en el mismo rbol de B. Si no, los dos rboles (cjtos) de B conteniendo u y v se unen con una operacin unin. Caso contrario, no se hace union. Por lo tanto, unir A y B requiere no ms de 2(n-1) find y (n-1) union.

Componentes conectados: paralelo con Bloques 1-DLa matriz de adyacencia de tamao n x n es particionada en p bloques.Cada proc puede computar su spanning forest en tiempo (n2/p). Merging se hace incrustando un rbol logico en la topologa. Hay log p etapas del merging, c/u. tarda (n). el costo del merging es (n log p). En cada etapa, los spanning forests se envan entre vecinos. Ojo, se transmiten (n) aristas de los spanning forest.

Componentes conectados: paralelo con Bloques 1-DTiempo en paralelo:

Para costo ptimo tengo p = O(n / log n). La isoeficiencia es (p2 log2 p).

*********