Re: parallelizing thousands of tests

[Benoit Germain <bnt.germain@...>]

2011/4/16 Norman Ramsey <nr@cs.tufts.edu>:

> Can anyone suggest which of the many parallel packages for Lua might
> be most suitable for parallelizing this loop?
>

Using Lanes [1], it would be pretty easy to setup 8 consumer threads
that take data from a single producer that would be your triple loop
here. Untested, but so that you can get the gist of it:


require "lanes"
local l = lanes.linda()

-- our thread body
local consumeTest = function()
  repeat
    local uid, key = l:receive( "in", "done") -- read a uid, test, bin
data sequence
    if key == "in" then
      local test = l:receive( key)
      local bin = l:receive( key)
      local outcome, witness = run_test( test, bin)
      l:send( "out", uid, outcome, witness) -- send a uid, outcome,
witness sequence as result
    end
  until key == "done"
end

-- send all test runs in the linda
local uid = 1
for tid, tests in pairs(tests) do  --- outer loop
  for i, test in pairs(tests) do   --- middle loop
    if test.valid then
      for sid, bin in pairs(binaries) do -- inner loop
        l:send( "in", uid, test, bin) -- send a uid, test, bin data
        uid = uid + 1
      end
    end
  end
end

-- launch some threads to consume data
local thread_gen = lanes.gen( "*", consumeTest)
for i = 1, 30 do
  thread_gen()
  -- when all tests are consumed, each thread will read this once then exit
  l:send( "done", true)
end

-- wait for completion (threads have consumed all the data sent in the linda)
local sleeperlinda = lanes.linda()
repeat
  -- sleep here so that you don't steal CPU from the workers
  -- i do this by waiting on some data I know doen't exit -> sleep until timeout
  local val, key = sleeperlinda( 0.1, "nonexistentkey")
until l:keys() == nil

-- collect all results in a single table
local collated = {}
repeat
  local uid, key = l:read( 0.01, "out") -- read uid, outcome, witness
  if key == "out" then
    local outcome = l:receive( "out")
    local witness = l:receive( "out")
    collated[uid] = {outcome, witness}
  end
end

-- collect results in final database
local uid = 1
for tid, tests in pairs(tests) do  --- outer loop
  local results = { }
  matrix[tid] = results
  for i, test in pairs(tests) do   --- middle loop
    if test.valid then
      results[i] = { }
      local results = results[i]
      for sid, bin in pairs(binaries) do -- inner loop
        results[sid] = collated[uid]
        uid = uid + 1
      end
    end
  end
end


Of course, this requires that all data exchanged through the linda is
supported. In essence, it means there is no full userdata. If this is
the case, you'll have the change the way it is implemented so that
Lanes can work with them.

-- 
Benoit.


[1] https://github.com/LuaLanes/lanes