multithreading - ¿Qué paquete de subprocesos múltiples para Lua "simplemente funciona" tal como se envió?

parallel-processing

Question

Codificando en Lua, tengo un ciclo triple anidado que pasa por 6000 iteraciones. Las 6000 iteraciones son independientes y pueden paralelizarse fácilmente. ¿Qué paquete de hilos para Lua compila de la caja y obtiene aceleraciones paralelas decentes en cuatro o más núcleos?

Esto es lo que sé hasta ahora:

• luaproc proviene del núcleo del equipo de Lua, pero el paquete de software en luaforge es antiguo, y la lista de correo tiene informes de segfaulting. Además, no es obvio para mí cómo usar el modelo escalar de paso de mensajes para obtener finalmente resultados en un hilo padre.

• Lua Lanes hace afirmaciones interesantes, pero parece ser una solución compleja y pesada. Muchos mensajes en la lista de correo informan problemas para que Lua Lanes los construya o trabaje para ellos. Yo mismo he tenido problemas para que funcione el mecanismo subyacente de distribución de "rocas Lua".

• LuaThread requiere bloqueo explícito y requiere que la comunicación entre subprocesos esté mediada por variables globales que están protegidas por bloqueos. Podría imaginarme algo peor, pero estaría más feliz con un mayor nivel de abstracción.

• Concurrent Lua proporciona un modelo atractivo de transmisión de mensajes similar a Erlang, pero dice que los procesos no comparten memoria. No está claro si el spawn realmente funciona con cualquier función Lua o si hay restricciones.

• Russ Cox propuso un modelo de subprocesos ocasional que funciona solo para subprocesos C. No es útil para mi

Respaldaré todas las respuestas que informen sobre la experiencia real con estos o con cualquier otro paquete de subprocesos múltiples, o cualquier respuesta que proporcione nueva información.

Como referencia, aquí está el ciclo que me gustaría paralelizar:

for tid, tests in pairs(tests) do
  local results = { }
  matrix[tid] = results
  for i, test in pairs(tests) do
    if test.valid then
      results[i] = { }
      local results = results[i]
      for sid, bin in pairs(binaries) do
        local outcome, witness = run_test(test, bin)
        results[sid] = { outcome = outcome, witness = witness }
      end
    end
  end
end

La función run_test se pasa como un argumento, por lo que un paquete puede ser útil para mí solo si puede ejecutar funciones arbitrarias en paralelo. Mi objetivo es lograr el paralelismo suficiente para obtener el 100% de utilización de la CPU en 6 a 8 núcleos.

Answer 1

Ahora he creado una aplicación paralela usando luaproc . Aquí hay algunos conceptos erróneos que me impidieron adoptarlo antes, y cómo solucionarlos.

• Una vez que se lanzan los hilos paralelos, por lo que yo sé, no hay forma de que se comuniquen con el padre. Esta propiedad fue el gran bloque para mí. Eventualmente, me di cuenta del camino a seguir: cuando se terminan los hilos, el padre se detiene y espera. El trabajo que debería haber hecho el padre debería hacerse en lugar de un subproceso secundario, que debería estar dedicado a ese trabajo. No es un gran modelo, pero funciona.

• La comunicación entre padres e hijos es muy limitada . El padre puede comunicar solo valores escalares: cadenas, booleanos y números. Si el padre desea comunicar valores más complejos, como tablas y funciones, debe codificarlos como cadenas. Dicha codificación puede tener lugar en línea en el programa, o (especialmente) las funciones pueden ser estacionadas en el sistema de archivos y cargadas en el niño usando require .

• Los niños no heredan nada del entorno de los padres. En particular, no heredan package.path o package.cpath . Tuve que trabajar en esto por la forma en que escribí el código para los niños.

• La forma más conveniente de comunicarse de padres a hijos es definir al niño como una función y hacer que el niño capture la información de los padres en sus variables libres, conocidas en las listas de Lua como "valores ascendentes". Estas variables libres pueden no ser variables globales, y deben ser escalares. Aún así, es un modelo decente. Aquí hay un ejemplo:

  local function spawner(N, workers)
    return function()
      local luaproc = require ''luaproc''
      for i = 1, N do
        luaproc.send(''source'', i)
      end
      for i = 1, workers do
        luaproc.send(''source'', nil)
      end
    end
  end

  Este código se usa como, por ejemplo,

  assert(luaproc.newproc(spawner(randoms, workers)))

  Esta llamada es cómo los valores randoms y los workers se comunican de padres a hijos.

  La afirmación es esencial aquí, como si olvidara las reglas y accidentalmente capturara una tabla o una función local, luaproc.newproc fallará.

Una vez que entendí estas propiedades, luaproc efectivamente funcionó " de fábrica ", cuando se descargó de askyrme en github .

ETA: Existe una limitación molesta : en algunas circunstancias, al llamar a fread() en un subproceso puede evitar que se programen otros subprocesos. En particular, si ejecuto la secuencia

local file = io.popen(command, ''r'')
local result = file:read ''*a''
file:close()
return result

la operación de read bloquea todos los otros hilos . No sé por qué es esto, supongo que es una tontería pasando dentro de glibc. La solución alternativa que utilicé fue llamar directamente a read(2) , que requería un pequeño código de pegamento, pero esto funciona correctamente con io.popen y file:close() .

Hay otra limitación que vale la pena mencionar:

• A diferencia de la concepción original de Tony Hoare de comunicar el procesamiento secuencial, y a diferencia de la mayoría de las implementaciones maduras y serias del paso de mensajes sincrónicos, luaproc no permite que un receptor bloquee en múltiples canales simultáneamente. Esta limitación es grave y descarta muchos de los patrones de diseño con los que se maneja el paso de mensajes sincrónico, pero aún así es posible encontrar muchos modelos simples de paralelismo, especialmente el tipo de "parbegin" que necesitaba para resolver mi problema original.

Answer 2

Este es un ejemplo perfecto de MapReduce

Puede usar LuaRings para cumplir sus necesidades de paralelización.

Answer 3

La Lua simultánea puede parecer el camino a seguir, pero como señalo en mis actualizaciones a continuación, no funciona en paralelo. El enfoque que probé fue generar varios procesos que ejecutan cierres en escabeche recibidos a través de la cola de mensajes.

Actualizar

Concurrent Lua parece manejar funciones de primera clase y cierres sin problemas. Vea el siguiente programa de ejemplo.

require ''concurrent''

local NUM_WORKERS = 4       -- number of worker threads to use
local NUM_WORKITEMS = 100   -- number of work items for processing

-- calls the received function in the local thread context
function worker(pid)
    while true do
        -- request new work
        concurrent.send(pid, { pid = concurrent.self() })
        local msg = concurrent.receive()

        -- exit when instructed
        if msg.exit then return end

        -- otherwise, run the provided function
        msg.work()
    end
end

-- creates workers, produces all the work and performs shutdown
function tasker()
    local pid = concurrent.self()

    -- create the worker threads
    for i = 1, NUM_WORKERS do concurrent.spawn(worker, pid) end

    -- provide work to threads as requests are received
    for i = 1, NUM_WORKITEMS do
        local msg = concurrent.receive()

        -- send the work as a closure
        concurrent.send(msg.pid, { work = function() print(i) end, pid = pid })
    end

    -- shutdown the threads as they complete
    for i = 1, NUM_WORKERS do
        local msg = concurrent.receive()
        concurrent.send(msg.pid, { exit = true })
    end
end

-- create the task process
local pid = concurrent.spawn(tasker)

-- run the event loop until all threads terminate
concurrent.loop()

Actualización 2

Raspe todas esas cosas de arriba. Algo no se veía bien cuando estaba probando esto. Resulta que Concurrent Lua no es concurrente en absoluto. Los "procesos" se implementan con corrutinas y todos se ejecutan de forma cooperativa en el mismo contexto de subprocesos. ¡Eso es lo que obtenemos por no leer con cuidado!

Entonces, al menos eliminé una de las opciones, supongo. :(

Answer 4

Me doy cuenta de que esta no es una solución práctica, pero, ¿tal vez ir a la vieja escuela y jugar con tenedores? (Suponiendo que estás en un sistema POSIX)

Lo que hubiera hecho:

• Justo antes de su ciclo, coloque todas las pruebas en una cola, accesible entre procesos. (Un archivo, una LISTA de Redis o cualquier otra cosa que te guste más).

• También antes del ciclo, genera varias horquillas con lua-posix (igual que la cantidad de núcleos o incluso más según la naturaleza de las pruebas). En la bifurcación de los padres espere hasta que todos los niños dejen de fumar.

• En cada bifurcación en un bucle, obtenga una prueba de la cola, ejecútela, ponga resultados en alguna parte. (A un archivo, a una LISTA de Redis, en cualquier otro lugar que desee). Si no hay más pruebas en cola, salga.

• En la búsqueda principal, procese todos los resultados de prueba como lo hace ahora.

Esto supone que los parámetros de prueba y los resultados son serializables. Pero incluso si no lo son, creo que debería ser bastante fácil engañar sobre eso.

Answer 5

Norman escribió sobre luaproc:

"no es obvio para mí cómo usar el modelo de paso de mensajes escalar para obtener finalmente resultados en un hilo padre"

Tuve el mismo problema con un caso de uso con el que estaba tratando. Me gustó el proceso de Lua debido a su implementación simple y ligera, pero mi caso de uso tenía un código C que llamaba a lua, que activaba una co-rutina que necesitaba enviar / recibir mensajes para interactuar con otros hilos de luaproc.

Para lograr mi funcionalidad deseada, tuve que agregar funciones a luaproc para permitir el envío y la recepción de mensajes desde el hilo padre o cualquier otro hilo que no se ejecute desde el programador luaproc. Además, mis cambios permiten usar luaproc send / receive de corutinas creadas a partir de luaproc.newproc () estados lua creados.

Agregué una función luaproc.addproc () adicional a la API que se debe invocar desde cualquier estado lua que se ejecute desde un contexto no controlado por el programador luaproc para establecerse con luaproc para enviar / recibir mensajes.

Estoy considerando publicar la fuente como un nuevo proyecto github o contactando con los desarrolladores y ver si les gustaría sacar mis adiciones. Sugerencias sobre cómo debería ponerlo a disposición de los demás son bienvenidos.

Answer 6

Verifique la biblioteca de threads en la familia de antorchas. Implementa un modelo de grupo de subprocesos: primero se crean algunos subprocesos verdaderos (pthread en Linux y el subproceso de Windows en win32). Cada subproceso tiene un objeto lua_State y una cola de trabajos de bloqueo que admite trabajos agregados desde el hilo principal.

Los objetos Lua se copian desde el hilo principal al hilo de trabajo. Sin embargo, los objetos C, como los tensores de la antorcha o las estructuras de datos tds , se pueden pasar a los hilos de trabajo a través de punteros; así es como se logra la memoria compartida limitada.