¿Debo usar hilo y recursión juntos?

Question

He estado jugando con árboles BSP por un tiempo y también estoy jugando con hilos. Al agregar un triángulo a un árbol BSP, surge una oportunidad para 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 anteriores podrían ejecutarse mediante dos subprocesos, y como no modifican los mismos datos, se puede usar la sincronización barata.

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 intenta crear un hilo para completar la operación en paralelo, pero no debería fallar si el hilo no se puede crear (simplemente volverá al algoritmo original).

¿Se trata de una práctica de programación sensata o estoy utilizando subprocesos incorrectamente? No he podido encontrar ninguna literatura sobre esta técnica. Me gusta que tiende a usar mi CPU al máximo (2 núcleos) y, en teoría, se escala a cualquier número de procesadores disponibles. No me gusta que pueda ser un desperdicio horrible en la CPU y la memoria.

Answer 1

Los subprocesos son excelentes si alguna parte del procesamiento está esperando algo externo (entrada del usuario, E / S, algún otro procesamiento): el subproceso que está esperando puede seguir esperando, mientras que un subproceso que no espera continúa adelante. .

Sin embargo, para tareas de procesamiento intensivo, más subprocesos que procesadores en realidad crean gastos generales. Parece que sus subprocesos están haciendo todo el "trabajo de CPU", por lo que me quedaría con un subproceso por núcleo; sin embargo, pruebe para encontrar el número óptimo.

La sobrecarga más grande creada es el cambio de contexto (congelar un hilo y cargar el contexto de ejecución del siguiente), así como la falta de caché cuando los hilos están realizando tareas con diferente memoria (si su hilo puede usar el caché de la CPU de manera efectiva) .

Answer 2

tu mejor apuesta sería crear un conjunto de subprocesos y luego usarlo 'de forma transparente' para agregar nodos.

por ejemplo, cree 2 hilos al inicio del programa, haga que esperen en un semáforo o evento. Cuando tiene nodos para agregar, coloca los datos en una cola y luego activa el semáforo. Esto despierta uno de los hilos que saca los datos de la cola y realiza el procesamiento. (Asegúrese de que el acceso a la cola sea seguro para subprocesos; lo mejor es 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 subprocesos adicionales, pero si solía ejecutar en un solo núcleo, ahora se ejecutará en 2. Funciona mejor si el procesamiento roscado es caro.

Answer 3

Claro, por ejemplo, Quicksort puede programarse multiproceso con bastante facilidad y obtener grandes ganancias de rendimiento en sistemas multi-core, y algunas pequeñas pérdidas de rendimiento en no multiproceso. Solo recuerde que ahora está agregando gastos generales dos veces: una vez para la pila, guarde en la recursividad y otra en el hilo, por lo que si está haciendo una gran cantidad de recursiones, podría abrumar un sistema más rápido que un enfoque no multiproceso.