Búsqueda en amplitud paralela

La partición 1D es la forma más sencilla de combinar la búsqueda en amplitud paralela con memoria distribuida. Se basa en la partición de vértices. El equilibrio de carga sigue siendo un aspecto importante para la partición de datos, ya que determina cómo podemos aprovechar la paralelización. En otras palabras, cada unidad de procesamiento con memoria distribuida debe encargarse de aproximadamente el mismo número de vértices y sus aristas salientes. Para la implementación del almacenamiento de datos, cada procesador puede almacenar una matriz de adyacencia de sus vértices locales, donde cada fila para cada vértice es una fila de aristas salientes representadas por los índices de los vértices de destino.

A diferencia de la búsqueda en anchura (BFS) con memoria compartida, el vértice vecino de una unidad de procesamiento puede almacenarse en otra. Por lo tanto, cada unidad de procesamiento es responsable de informar a las demás sobre el estado del recorrido mediante el envío de mensajes. Además, cada unidad de procesamiento debe gestionar los mensajes de todas las demás para construir su frontera local del siguiente vértice. Obviamente, es necesaria una comunicación bidireccional (es decir, cada unidad tiene mensajes diferentes para las demás) en cada paso al intercambiar la frontera actual y la del siguiente vértice.

El siguiente pseudocódigo de un BFS de memoria distribuida unidimensional ^{[ 5 ]} fue diseñado originalmente para sistemas IBM BlueGene/L , que cuentan con una arquitectura de red toroidal tridimensional . Dado que la sincronización representa el principal costo adicional para un BFS paralelizado, los autores de este artículo también desarrollaron una comunicación escalable de todo a todo basada en comunicaciones punto a punto . Posteriormente, redujeron el número de comunicaciones punto a punto, aprovechando el alto ancho de banda de su red toroidal.

Los pasos principales del recorrido BFS en el siguiente algoritmo son:

1. Vista del procesador (línea 8): construir el sistema de archivos frontera con vértices del almacenamiento local.
2. Vista global (líneas 10-11): finalice el recorrido si los sistemas de archivos de todos los procesadores están vacíos.
3. Vista del procesador (línea 13): construye la siguiente frontera basándose en los vértices vecinos de su FS, aunque algunos de sus vecinos pueden estar almacenados en otros procesadores.
4. Vista global (líneas 15-18): ejecute una comunicación de todos a todos para que cada procesador sepa qué vértices locales deben colocarse en su siguiente frontera local.
5. Vista del procesador (líneas 20-22): recibe mensajes de todos los demás procesadores, actualiza el valor de distancia de sus vértices locales en la frontera actual, cambia su NS a FS.

1 define 1_D_distributed_memory_BFS( graph(V,E), source s): 2 //inicialización normal 3 para todos los v en V hacer 4 d[v] = -1; 5 d[s] = 0; nivel = 0; FS = {}; NS = {}; 6 //comienza el recorrido BFS 7 mientras sea verdadero hacer : 8 FS = {el conjunto de vértices locales con nivel} 9 //todos los vértices recorridos 10 si FS = {} para todos los procesadores entonces : 11. Finalizar el bucle while 12 // Construye la red de Nash basada en los vértices locales en la frontera actual. 13 NS = {vecinos de los vértices en FS, tanto vértices locales como no locales} 14 //sincronización: comunicación de todos a todos 15 para 0 <= j < p hacer : 16 N_j = {vértices en NS propiedad del procesador j} 17 enviar N_j al procesador j 18 reciben N_j_rcv del procesador j 19 //combina el mensaje recibido para formar la frontera del siguiente vértice local y luego actualiza el nivel para ellos. 20 NS_rcv = Unión(N_j_rcv) 21 para v en NS_rcv y d[v] == -1 hacer 22 d[v] = nivel + 1

Combinado con el procesamiento multihilo, el siguiente pseudocódigo de BFS de memoria distribuida 1D también especifica la pila de hilos y la barrera de hilos, que proviene del artículo. ^{[ 6 ]}

Con el multihilo, los vértices locales en el sistema de archivos frontera se pueden dividir y asignar a diferentes hilos dentro de un mismo procesador, lo que paraleliza aún más el recorrido BFS. A diferencia de los métodos anteriores, se necesitan más estructuras de datos para cada hilo individual. Por ejemplo, la pila de hilos, que se prepara para guardar los vértices vecinos de los vértices de este hilo. Cada hilo tiene p-1 de almacenamiento local, donde p es el número de procesadores. Esto se debe a que cada hilo debe separar los mensajes para todos los demás procesadores. Por ejemplo, colocarán sus vértices vecinos en su j-ésima pila para formar el mensaje que enviarán al procesador j, si este es el propietario de dichos vértices. Además, la barrera de hilos también es necesaria para la sincronización. Como resultado, aunque la memoria distribuida con multihilo puede beneficiarse de una mejor paralelización, también introduce un coste de sincronización adicional para los hilos.

Los pasos principales del recorrido BFS en el siguiente algoritmo son:

1. Vista de hilo (líneas 19-22): basándose en los vértices asignados a sí mismo, encuentra el procesador propietario de los vértices vecinos y colócalos en la pila de hilos en función de sus propietarios.
2. Vista del procesador (línea 23): ejecute una barrera de subprocesos, espere hasta que todos los subprocesos (del mismo procesador) terminen su trabajo.
3. Vista del procesador (líneas 25-26): fusionar todas las pilas de subprocesos de todos los subprocesos que tengan el mismo propietario (aquellos tienen el destino para el siguiente paso).
4. Vista global (líneas 28-30): ejecute una comunicación de todos a todos con el hilo maestro para informar a cada procesador qué vértices locales deben colocarse en la siguiente frontera.
5. Vista del procesador (línea 31): ejecutar una barrera de subprocesos, esperar hasta que finalice la comunicación (del subproceso maestro).
6. Vista del procesador (línea 33): asigna vértices de la siguiente frontera a cada hilo.
7. Vista de hilo (líneas 34–36): si el vértice no se visita, actualiza el valor de distancia para sus vértices y colócalo en la pila de hilos para la siguiente frontera NS.
8. Vista del procesador (línea 37): ejecute una barrera de subprocesos, espere hasta que todos los subprocesos (del mismo procesador) terminen su trabajo.
9. Vista del procesador (línea 39): agrega pilas de subprocesos para la siguiente frontera desde cada subproceso.
10. Vista del procesador (línea 40): ejecute una barrera de subprocesos, espere hasta que todos los subprocesos envíen todos sus vértices en su pila.

1 define 1_D_distributed_memory_BFS_with_threads(graph(V,E), source s): 2 // inicialización normal 3 para todos los v en V hacer 4 d[v] = -1; 5 nivel = 1; FS = {}; NS = {}; 6 // encuentra el índice del procesador propietario del vértice de origen s 7 pu_s = encontrar_propietario(s); 8 si pu_s = index_pu entonces 9 empujes(s,FS); 10 d[s] = 0; 11 // inicialización del mensaje 12 para 0 <= j < p hacer 13 sendBuffer_j = {} // p búferes de mensajes compartidos 14 recvBuffer_j = {} // para comunicación MPI 15 thrdBuffer_i_j = {} //pila local del hilo para el hilo i 16 // comenzar el recorrido BFS 17 mientras FS != {} hacer 18 // recorrer vértices y encontrar propietarios de vértices vecinos 19 para cada u en FS en paralelo hacer 20 para cada vecino v de u hacer 21 pu_v = find_owner(v) 22 push(v, thrdBuffer_i_(pu_v)) 23 Barrera de subprocesos 24 // combinar la pila de subprocesos para formar sendBuffer 25 para 0 <= j < p hacer 26 fusionar thrdBuffer_i_j en paralelo 27 // comunicación de todos a todos 28 Paso colectivo de todos a todos con hilo maestro: 29 1. enviar datos en sendBuffer 30 2. Recibir y agregar los vértices recién visitados en recvBuffer 31 Barrera de hilos 32 // nivel de actualización para vértices recién visitados 33 para cada u en recvBuffer en paralelo hacer 34 si d[u] == -1 entonces 35 d[u] = nivel 36 push(u, NS_i) 37 Barrera de Hilo 38 // agregar NS y formar un nuevo FS 39 FS = Unión(NS_i) 40 Barrera de Hilo 41 nivel = nivel + 1f

Dado que el algoritmo BFS siempre utiliza la matriz de adyacencia como representación del grafo, la descomposición bidimensional natural de la matriz también puede ser una opción a considerar. En la partición bidimensional, cada procesador tiene un índice bidimensional (i,j). Las aristas y los vértices se asignan a todos los procesadores mediante una descomposición en bloques bidimensional, donde se almacena la matriz de subadyacencia.

Si en total hay P=R·C procesadores, entonces la matriz de adyacencia se dividirá como se muestra a continuación:

Tras esta división, quedan C columnas y R·C filas de bloques. Cada procesador se encarga de C bloques; es decir, el procesador (i,j) almacena A _i,j ⁽¹⁾ a A _i,j ^(C) bloques. La partición convencional unidimensional es equivalente a la partición bidimensional con R=1 o C=1.

En general, el procesamiento paralelo de bordes basado en particionamiento 2D se puede organizar en 2 fases de comunicación, que son la fase de "expansión" y la fase de "plegado". ^{[ 6 ]}

En la fase de "expansión", si la lista de aristas para un vértice dado es la columna de la matriz de adyacencia, entonces para cada vértice v en la frontera, el propietario de v es responsable de informar a los demás procesadores en su columna de procesador que v ha sido visitado. Esto se debe a que cada procesador solo almacena listas parciales de aristas de los vértices. Después de esta comunicación, cada procesador puede recorrer la columna según los vértices y encontrar sus vecinos para formar la siguiente frontera. ^{[ 5 ]}

En la fase de "plegado", los vértices de la siguiente frontera resultante se envían a sus procesadores propietarios para formar la nueva frontera localmente. Con la partición 2D, estos procesadores están en la misma fila de procesadores. ^{[ 5 ]}

Los pasos principales del recorrido BFS en este algoritmo de particionamiento 2D son (para cada procesador):

1. fase de expansión (líneas 13-15): basándose en vértices locales, solo se envían mensajes a los procesadores en la columna de procesadores para indicarles que estos vértices están en la frontera, y se reciben mensajes de estos procesadores.
2. (líneas 17-18): fusionar todos los mensajes recibidos y formar la frontera de red N. Nótese que no todos los vértices de los mensajes recibidos deben colocarse en la siguiente frontera, ya que algunos podrían haber sido visitados. La siguiente frontera solo contiene vértices con un valor de distancia de -1.
3. fase de plegado (líneas 20-23): basándose en los vértices locales en la siguiente frontera, envíe mensajes a los procesadores propietarios de estos vértices en la fila del procesador.
4. (líneas 25–28): fusionar todos los mensajes recibidos y actualizar el valor de distancia de los vértices en la siguiente frontera.

El pseudocódigo que aparece a continuación describe más detalles del algoritmo BFS 2D, que proviene del artículo: ^{[ 5 ].}

1 define 2_D_distributed_memory_BFS( graph(V,E), source s): 2 // inicialización normal 3 para todos los v en V hacer 4 d[v] = -1; 5 d[s] = 0; 6 // comienza el recorrido BFS 7 para l = 0 hasta infinito hacer : 8 F = {el conjunto de vértices locales con nivel l} 9 // todos los vértices recorridos 10 si F = {} para todos los procesadores entonces : 11. Finalizar el bucle while 12 // Recorre los vértices enviando un mensaje al procesador seleccionado 13 Para todos los procesadores q en esta columna de procesadores, haz lo siguiente : 14 Enviar F al procesador q 15 Reciba F q r de q 16 // procesar la información recibida después del recorrido de la frontera 17 F r = Unión{F q r } para todo q 18 N = {vecinos de los vértices en F r usando listas de aristas en este procesador} 19 // Transmite los vértices vecinos enviando un mensaje a su procesador propietario 20 para todos los procesadores q en esta fila de procesadores hacer : 21 N q = {vértices en N propiedad del procesador q} 22 Enviar N q al procesador q 23 Reciba N q r de q 24 // forma la siguiente frontera utilizada para el recorrido de la siguiente capa 25 N r = Unión{N q r } para todo q 26 // actualización de la distancia de la capa 27 para v en N r y d(v) = -1 hacer : Nivel 28 = l + 1

En la partición 2D, solo las columnas o filas de procesadores participan en la comunicación durante las fases de "expansión" o "reducción", respectivamente. ^{[ 5 ]} Esta es la ventaja de la partición 2D sobre la partición 1D, ya que en esta última todos los procesadores participan en la comunicación entre todos. Además, la partición 2D ofrece mayor flexibilidad para un mejor equilibrio de carga, lo que facilita un enfoque más escalable y eficiente en cuanto al almacenamiento.

Además de los conceptos básicos de la búsqueda en amplitud paralela (BFS paralela), se pueden utilizar algunas estrategias de optimización para acelerar el algoritmo y mejorar su eficiencia. Ya existen varias optimizaciones para la BFS paralela, como la optimización direccional, el mecanismo de equilibrio de carga y la mejora de la estructura de datos, entre otras.

Estructura de datos

Existen algunas estructuras de datos especiales de las que puede beneficiarse la búsqueda en amplitud paralela (BFS), como CSR (Fila Dispersa Comprimida), estructura de bolsa, mapa de bits , etc.

En el CSR, todas las adyacencias de un vértice se ordenan y almacenan de forma compacta en un bloque contiguo de memoria, con la adyacencia del vértice i+1 junto a la adyacencia de i. En el ejemplo de la izquierda, hay dos matrices, C y R. La matriz C almacena las listas de adyacencia de todos los nodos. La matriz R almacena el índice en C; la entrada R[i] apunta al índice inicial de las listas de adyacencia del vértice i en la matriz C. El CSR es extremadamente rápido porque el acceso a la adyacencia de un vértice solo requiere un tiempo constante. Sin embargo, solo es eficiente en cuanto a espacio para particiones 1D. ^{[ 6 ]} Se puede encontrar más información sobre CSR en. ^{[ 9 ]} Para particiones 2D, DCSC (Columnas Dispersas Doblemente Comprimidas) para matrices hiperdispersas es más adecuado. ^{[ 10 ]}

En el artículo ^{[ 4 ]} , los autores desarrollan una nueva estructura de datos llamada bag-structure. Bag-structure se construye a partir de la estructura de datos pennant. Un pennant es un árbol de 2k ^nodos , donde k es un entero no negativo. Cada raíz x en este árbol contiene dos punteros, x.left y x.right, a sus hijos. La raíz del árbol tiene solo un hijo izquierdo, que es un árbol binario completo de los elementos restantes. ^{[ 4 ]}

La estructura de la bolsa es la colección de banderines con una matriz base S. Cada entrada S[i] en S es un puntero nulo o un puntero a un banderín de tamaño s ⁱ . La operación de inserción en una bolsa toma ⁠${\displaystyle O(1)}$⁠ tiempo amortizado y la unión de dos bolsas toma ⁠${\displaystyle \theta (\lg n)}$tiempo . La división de la bolsa también lleva${\displaystyle \theta (\lg n)}$⁠ tiempo. Con esta estructura de bolsa, se permite que BFS paralelo escriba los vértices de una capa en una única estructura de datos en paralelo y luego los recorra eficientemente en paralelo. ^{[ 4 ]}

Además, el mapa de bits también es una estructura de datos muy útil para memorizar qué vértices ya se han visitado, independientemente de si se ha realizado una búsqueda en amplitud (BFS) de abajo hacia arriba. ^{[ 11 ]} o simplemente para comprobar si se han visitado vértices en la búsqueda en amplitud (BFS) de arriba hacia abajo. ^{[ 9 ]}