Transmisión de lista enlazada multiproceso

Question

Dada una lista (doblemente) vinculada de objetos (C++), tengo una operación que me gustaría multihebra, para realizar en cada objeto. El costo de la operación no es uniforme para cada objeto. La lista vinculada es el almacenamiento preferido para este conjunto de objetos por una variedad de razones. El primer elemento en cada objeto es el puntero al siguiente objeto; el segundo elemento es el objeto anterior en la lista.

He resuelto el problema construyendo una matriz de nodos y aplicando OpenMP. Esto dio un rendimiento decente. Luego cambié a mis propias rutinas de subprocesamiento (basadas en primitivas de Windows) y al usar InterlockedIncrement() (que actúa sobre el índice en la matriz), puedo lograr una mayor utilización general de la CPU y un rendimiento más rápido. Esencialmente, los hilos funcionan por "salto-rana" a lo largo de los elementos.

Mi próximo enfoque para la optimización es tratar de eliminar la creación/reutilización de la matriz de elementos en mi lista vinculada. Sin embargo, me gustaría continuar con este enfoque de "salto de rana" y de alguna manera usar una rutina inexistente que podría llamarse "InterlockedCompareDereference" - para comparar atómicamente con NULL (fin de lista) y eliminar condicionalmente la referencia &, devolviendo el valor desreferenciado .

No creo que InterlockedCompareExchangePointer() funcione, ya que no puedo desterrizar atómicamente el puntero y llamar a este método Interlocked(). He leído algo y otros sugieren secciones críticas o bloqueos giratorios. Las secciones críticas parecen pesadas aquí. Estoy tentado de probar las cerraduras giratorias, pero pensé que primero plantearía la pregunta aquí y preguntaría qué están haciendo otras personas. No estoy convencido de que el método InterlockedCompareExchangePointer() en sí mismo pueda usarse como un bloqueo de giro. Entonces uno también tiene que considerar la semántica de adquisición/liberación/valla ...

Ideas? ¡Gracias!

Answer 1

Las secciones críticas no son muy pesadas. Suponiendo que puedan adquirir el bloqueo rápidamente actúan como un bloqueo de giro.

La solución a su problema dependerá de si está modificando la lista o no. Si no está modificando la lista, todo lo que necesita hacer es algo como InterlockedCompareExchange en un valor en su objeto inicializado en 0. El valor de intercambio es 1, si obtiene 0 en ese momento, realiza sus acciones, si obtiene 1 de vuelta, saltas La próxima vez que realice acciones en la lista, cambie en 2 y compruebe 1/2 en lugar de 0/1.

Si está cambiando la lista, entonces todo depende. Si solo quieres avanzar y solo eliminar los nodos actuales, tu mejor opción sería tener un próximo bloqueo en el ítem que bloqueas al hacer el bit de intercambio de comparación, al saltar-frogging (obtener su siguiente nodo) y al eliminar el nodo

Answer 2

Creo que Casta tiene algunos puntos buenos, y yo mismo pondré uno. La solución a este problema va a pesar mucho en las transformaciones idealógicas realizadas en cada nodo, ya sean interdependientes y si la tarea realizada se puede realizar en un barrido singular de la lista.

Si las operaciones no son interdependientes, y el enfoque de barrido tiene sentido, propongo un sistema de búsqueda intermediado. Es prácticamente idéntico a un enfoque de tripulación de trabajo. Cada hilo recibe una referencia al intermediario, que administra la lista. Como cada hilo necesita contenido para procesar, lo solicita del intermediario, que lo bloquea, obtiene el siguiente nodo, avanza el iterador de barrido interno y libera el bloqueo, devolviendo el nodo al hilo solicitante. Esto continúa hasta que la enumeración de la lista finaliza. Para problemas de acumuladores donde cada nodo puede ser visitado más de una vez por un hilo diferente, puede usar una lista circular o algún otro contenedor. Un agente talentoso puede administrar la lista, incluidos los nuevos insertos, eliminaciones, etc., de la misma manera que distribuye: bloqueo, acción, desbloqueo.Obviamente hay muchas actividades que se pueden adaptar a sus necesidades específicas en el lado del corredor. Lo que esas necesidades son puede hacer para un sistema de gestión de grupo elaborado, sin dejar de ser muy eficiente en términos de contención de bloqueo (es decir, casi ninguno).

En pocas palabras, es de esperar evidente. Conozca su conjunto de problemas y los detalles de lo que quiere que cada hilo logre con su nodo actual.

Answer 3

Básicamente, para ejecutar la lista lo más rápido posible, tiene algunas cosas que evitar;

• Lock collisions. Incluso con bloqueos de giro, cada iteración de bucle es una oportunidad perdida para realizar el trabajo.
• Barreras de memoria. Cada vez que realice una operación atómica, una barrera de memoria detendrá su ejecución.
• Trabajo innecesario, como escanear la lista de tareas pendientes.

Voy a tener que estar de acuerdo con su lectura y tomar el lado de las cerraduras giratorias.

Coloque el puntero al encabezado de la lista en un puntero volátil.

Cada hilo, a su vez;

• Toma bloquear el giro
• guarda el valor del puntero en unos temporales
• actualizaciones del puntero a la siguiente entrada de la lista
• Libera el spinlock.

A continuación, puede comenzar a trabajar en la entrada señalada por el temporal.

Esto tiene algunas ventajas al buscar a través de la lista usando un bloqueo por entrada;

• Si el trabajo por elemento no toma un tiempo nada trivial para completar, tendrá muy pocas colisiones por la corta duración de actualizar el puntero.
• Para evitar una colisión, solo tendrá 2 barreras de memoria para cada elemento de la lista, una para el bloqueo y otra para el desbloqueo.
• Sin escanear la lista para obtener un nuevo elemento de trabajo, simplemente obtenga el trabajo de la "cola".

Answer 4

Debido a la alineación, los bits inferiores de los punteros de la lista contienen ceros. Puede aprovechar esto al configurar atómicamente uno de estos bits en uno de los punteros utilizando las instrucciones de comparación y cambio para marcar el objeto como procesado.

Cada hilo haría:

1. inicio recorrer la lista de su cabeza.
2. Para cada nodo de lista, compruebe si su siguiente puntero tiene el bit más bajo establecido.
3. Si el bit está establecido vaya a 7.
4. Compare y cambie el siguiente puntero del nodo de la lista con (next | 1).
5. Si la comparación y el intercambio fallan, vaya a 7.
6. Procese el objeto.
7. Mover al siguiente nodo y Goto 2.

Otra opción es poner esta marca bits en un número entero que tiene un bit no utilizado en el objeto en sí mismo, a menos que el nodo de la lista es una clase base o un miembro del objeto.

De esta forma, los hilos obtendrían los objetos de la lista sin bloquearlos o sin estar ocupados girando en un wait-free fashion.