Por supuesto que es. Cualquier tipo de trabajo puede ser paralelizado, pero la distribución del trabajo, el equilibrio de carga y la mecánica de sincronización pueden ser más o menos triviales e inducir una sobrecarga propia, por lo que a veces un mayor grado de paralelismo no necesariamente significa un mejor rendimiento.
Ahora, consideremos cómo podemos paralelizar un montón. En primer lugar, ¿qué operaciones se definen en un montón? Bueno, obviamente, existe la Heapificación de una submatriz. Usted toma un nodo y tamiza el subárbol, enraizado en ese nodo, hasta que se satisfaga la propiedad del montón. No hay una manera significativa de paralelizar esa operación, ya que es de naturaleza secuencial, por lo que la veremos como atómica. Del mismo modo, las operaciones de inserción y eliminación del montón comparten ese movimiento similar de nodos hacia arriba y hacia abajo del montón, por lo que estas operaciones serán atómicas. No tiene sentido que varios hilos muevan un solo nodo.
Por lo tanto, no creo que pueda tener un montón que admita inserciones y eliminaciones paralelas, a menos que acepte el bloqueo, que serializa las cosas y pierde el punto de tener múltiples subprocesos corriendo. Aún así, si los subprocesos hacen muchas otras cosas en paralelo y necesitan hacer inserciones / eliminaciones en el montón solo de vez en cuando, entonces está bien usar bloqueos.
Sin embargo, la construcción de un montón requiere que se lleven a cabo una multitud de operaciones de montón. Específicamente, todos los nodos no hoja (los nodos hoja son triviales, montones singulares) deben ser heapified y esto, por supuesto, puede ser paralelo. Por lo tanto, crea un planificador de trabajos simple como este:
- ¿Cuál es la diferencia entre un árbol AVL y un árbol de búsqueda binario?
- ¿Qué tipos de problemas se pueden resolver usando algoritmos?
- ¿Es posible el algoritmo de compresión que se muestra en Silicon Valley en realidad?
- ¿Qué es el algoritmo? ¿Para qué sirve?
- ¿Cuál es la diferencia entre algoritmos y programación?
- Si un montón tiene niveles H, todos los nodos excepto aquellos en el último nivel deben ser heapified.
- Los subprocesos pueden operar en diferentes niveles, pero un subproceso no puede funcionar en un nodo en el nivel L si sus dos hijos no han sido heapified.
- Mantiene una cola de tareas: la tarea es la heapificación de un nodo. Inicialmente, la cola contiene todos los padres de las hojas.
- Cada subproceso recoge una tarea de una cola y la procesa. (naturalmente, la cola debe estar sincronizada de alguna manera, tal vez un spinlock o una sección crítica simple. Muchos marcos ya tienen una estructura de cola concurrente)
- Las tareas que corresponden a hermanos comparten un estado, que contiene el número de hermanos que se han procesado hasta ahora. Cada vez que un hilo completa una tarea, incrementa (entrelazado) ese número. Cuando ese número se vuelve igual al factor de despliegue del montón (por ejemplo, 2 para montones binarios), el subproceso que trabaja en el último hermano crea una tarea para el nodo principal.
En pocas palabras, así es como resolvería la construcción simultánea del montón.
Ordenar el montón es algo completamente diferente, en mi opinión, y no creo que pueda paralelizarse fácilmente. El punto es: en cada iteración, saca la parte superior del montón, lo reemplaza con el último elemento y vuelve a heapificar (con un tamaño de montón disminuido), pero esto bloquea las operaciones posteriores. Sin embargo, si desea una clasificación paralela, hay formas mucho mejores de hacerlo.
