How can I parallelize a while loop?


#1

I’m trying to use a while loop to search for a set of two points of the form (a,b) that gives me a successful result from a separate function.

For example (with only one point):

a = 101
while a > 100
    b = -5 + 10*rand()
    c = 0 + 20*rand()
    a = mainfunc([b,c])
end

I’m using an 8-core processor and would like to use every core for this computation. I first tried repeating the section inside the while loop 7 more times, using @spawn to put each computation on a separate core, but I ran into problems later with mainfunc not being defined on certain processes even though I used @everywhere include to include mainfunc’s definition file.

The @distributed macro seems to be only for “for” loops, and pmap seems to be intended for “for” loops as well since you have to pass in a collection of arguments.

What options do I have for speeding this up?


#2

Major disclaimer: I’m in no way an expert on Julia parallelism, and the below code may do something nasty. That said, it seems to speed up the kind of search you’re looking for.

The idea is to have a RemoteChannel that each process can write an eligible result into, and whenever the channel has a value, all processes can stop searching. Here, the function f just sleeps (to simulate long runtime) then adds its arguments. We’re searching for values a,b such that f(a,b) > 1.8.

using Distributed
using BenchmarkTools
addprocs()
@everywhere function f(a,b)
    sleep(.05)
    return a + b
end

function findcorner()
    while true
        a = rand()
        b = rand()
        fval = f(a, b)
        fval > 1.8 && return (a,b)
    end
end

function findcorner_parallel(n_parallel = nprocs())
    donechannel = RemoteChannel(() -> Channel{Any}(n_parallel))
    for _ in 1:n_parallel
        @spawn while !isready(donechannel)
            a = rand()
            b = rand()
            fval = f(a,b)
            fval > 1.8 && put!(donechannel, (a,b))
        end
    end
    return take!(donechannel)
end

@show nprocs()
@benchmark findcorner()
@benchmark findcorner_parallel()

I get output

julia> @show nprocs()
nprocs() = 9
9

julia> @benchmark findcorner()
BenchmarkTools.Trial:
  memory estimate:  9.25 KiB
  allocs estimate:  222
  --------------
  minimum time:     2.736 s (0.00% GC)
  median time:      3.922 s (0.00% GC)
  mean time:        3.922 s (0.00% GC)
  maximum time:     5.108 s (0.00% GC)
  --------------
  samples:          2
  evals/sample:     1

julia> @benchmark findcorner_parallel()
BenchmarkTools.Trial:
  memory estimate:  244.56 KiB
  allocs estimate:  3026
  --------------
  minimum time:     61.491 ms (0.00% GC)
  median time:      238.778 ms (0.00% GC)
  mean time:        264.791 ms (0.00% GC)
  maximum time:     872.580 ms (0.00% GC)
  --------------
  samples:          19
  evals/sample:     1

#3

Have you considered to spawn that while loop eight times and then with a while loop checking if any of the workers had finished their work?


#4

I’m learning as I go through this that there are a lot of undocumented rules about @spawn.
For example, in @evanfields’s answer, everything works fine. But if you try to use just the for loop in a .jl file, none of the workers can print to the console, and they don’t iterate more than once, even if the termination condition hasn’t been met; you have to specify the for loop inside a function.

Also, if you try to store a value to a variable declared outside the loop, each while loop spawned will finish after 1 iteration, with the termination condition still unmet. This causes the program to hang waiting for the RemoteChannel to be ready (if you’re trying to return the value from it with take!), while it’s not being updated. For example, if you want to have an iterator, both

i = 1
donechannel = RemoteChannel(() -> Channel{Any}(nprocs()))
function findcorner_parallel(n_parallel = nprocs())
    for _ in 1:n_parallel
        @spawn while !isready(donechannel)
            i += 1
            ...

and

i = 1
donechannel = RemoteChannel(() -> Channel{Any}(nprocs()))
function findcorner_parallel(n_parallel = nprocs())
    for _ in 1:n_parallel
        @spawn while !isready(donechannel)
            j = i
            j += 1
            ...

cause the spawned loops to quit without meeting the termination condition.

Only defining these variables right after the first line of the for loop (or within the spawned while loop, but that won’t do you much good for an iterator) will let the program continue. Maybe this is just the way Julia is supposed to work with variable scope, but it seems very strange to me that I can define new variables based on others originally declared outside the loop (e.g. with a and b already defined, newvar = a + b inside a spawned loop doesn’t cause any problems), but trying to do anything with a variable set equal to the value of another causes looping to fail silently.

@Janis_Erdmanis How would I check if an individual worker is finished?

Correction: the for loop will actually spawn the while loop correctly even when placed outside a function definition (all spawned workers repeating the calculation until a successful set of inputs is found), but the program will still hang until Enter is pressed if you try to set a variable using take!(donechannel), whether you put the assignment inside or outside the for loop.


#5

For processes there is a isready method (One can find methods with methodswith(typeof(myvariable))) which works like:

using Distributed
proc = @spawn sleep(10)
isready(proc) ### gives false

sleep(15)
isready(proc) ### gives true