¿Debo usar el enhebrado y la recursión juntos?

Question

He estado retocando con árboles BSP desde hace un tiempo y también estoy jugando con hilos. Al agregar un triángulo a un árbol BSP, surge la oportunidad de crear un nuevo hilo para el procesamiento de datos en paralelo.

 
insert(triangle, bspnode) 
{ 
    .... 
    else if(triangle spans bspnode) 
    { 
    (frontpiece, backpiece) = plane_split(triangle, bspnode) 

    insert(frontpiece, bspnode.front) 
    insert(backpiece, bspnode.back) 
    } 
    .... 
} 

Las dos operaciones de inserción anteriormente podrían ser ejecutadas por dos hilos, y puesto que no modifiquen los mismos datos, sincronización barato pueden ser utilizados.

 
insert(triangle, bspnode) 
{ 
    .... 
    else if(triangle spans bspnode) 
    { 
    (frontpiece, backpiece) = split(triangle, bspnode) 

    handle = beginthread(insert(backpiece, bspnode.front)) 
    insert(frontpiece, bspnode.back) 
    if(handle) 
    { 
     waitforthread(handle) 
    } 
    else 
    { 
     insert(backpiece, bspnode.front) 
    } 
    } 
    .... 
} 

Este nuevo método trata de crear un hilo para completar la operación en paralelo, pero no debe fallar si el hilo no se puede crear (simplemente volverá al algoritmo original).

¿Es esta una práctica de programación de sonido, o estoy utilizando hilos de forma incorrecta? No he podido encontrar literatura sobre esta técnica. Me gusta que tiende a usar mi CPU al máximo (2 núcleos), y teóricamente escala a cualquier cantidad de procesadores disponibles. No me gusta que pueda ser terriblemente inútil en CPU y memoria.

Answer 1

Los subprocesos son geniales si alguna parte del proceso está esperando en algo externo (entrada de usuario, E/S, algún otro procesamiento): el subproceso que está esperando puede seguir esperando, mientras que un subproceso que no está esperando se forja adelante.

Sin embargo, para tareas de procesamiento intensivo, más subprocesos que procesadores realmente crean sobrecarga. Parece que tus hilos están haciendo todo el "trabajo de la CPU", así que me quedaría con un hilo por core-test para encontrar el número óptimo.

La sobrecarga más grande creada es desde el cambio de contexto (congelar un hilo y cargar el contexto de ejecución del siguiente), así como errores de caché cuando los hilos están haciendo tareas con memoria diferente (si el hilo puede usar el caché de CPU efectivamente)

Answer 2

su mejor opción sería crear un grupo de subprocesos, y luego usarlo 'de forma transparente' para agregar nodos.

por ejemplo, cree 2 hilos al inicio del programa, pídales que esperen en un semáforo o evento. Cuando tenga nodos para agregar, inserte los datos en una cola y luego active el semáforo. Esto activa uno de los hilos que saca los datos de la cola y realiza el procesamiento. (asegúrese de que el acceso a la cola es seguro para los hilos, es mejor sincronizarlo completamente con una sección crítica).

El rendimiento general de su aplicación es más lento ya que tiene más sobrecarga, al copiar datos en la cola y ejecutar los hilos adicionales, pero si solía ejecutar en un solo núcleo, ahora se ejecutará en 2. Funciona lo mejor es que el procesamiento enhebrado sea costoso.

Answer 3

Claro, por ejemplo, Quicksort se puede programar multiproceso con bastante facilidad y obtener grandes ganancias de rendimiento en sistemas multi-core, y algunas pequeñas pérdidas de rendimiento en multihilo. Solo recuerde que está agregando dos veces la sobrecarga ahora, una para el guardado de pila en la recursión y otra en el hilo, por lo que si realiza una gran cantidad de recursiones, podría abrumar a un sistema más rápido que un enfoque no multiproceso.