keeping track of local minima in threaded programs with PartialQueue

partialqueue.jl

#=
ZigZagBoomerang.jl has implemented something like a priority queue keeping track of 
local minima (or high priority task).

Think of graph where vertices are tasks that are assigned priorities (smaller = higher priority) 
and edges between two tasks indicate if the higher priority task has to be worked on before the
lower priority task (edge) or both can be worked on in parallel (no edge).

It’s thread-safe in the sense that priorities can be updated in different threads 
if one has a proper coloring of the vertices and updates the task of one color in @threads
=#

using ZigZagBoomerang, Graphs
using ZigZagBoomerang: PartialQueue, dequeue!, saturate, rkey, div1
using Graphs: Edge
using Random
using Base.Threads

Random.seed!(1)

ZigZagBoomerang.nv_(G::Graph) = nv(G) # patch, fixed on master

# number of regions
nregions = 4
# number of coordinates/keys
d = 12

# time surface
times = rand(d)

# undirected graph of neighbours
G = Graph(Edge.(([i=>i+1 for i in 1:d-1])))

# Make a Queue-structure keeping track of local minima
# (a coordinate is a local minima if it's time is smaller than all neighbours' (via the graph) times)
Q = PartialQueue(G, times, nregions)

# key 1:3 is in region 1, key 4:6 in region 2, etc. 
# it is also possible to provide a region map
rkey(Q,3) == 1 
rkey(Q,4) == 2 

# we can work on different regions in parallel... see below

# peek which local minima we have
@show peek(Q)

ncols = 2 # use a black and white coloring on the regions

# dequeue! some local minima to work with (a vector for each region)
minima = dequeue!(Q) 

peek(Q) # currently all local minima are removed from the queue to be worked on

# update/increment local time, (in parallel thanks to the threads makro)
for c in 1:ncols
    @threads for r in c:ncols:nregions # so never working on adjacent regions in parallel
        for (i,t) in minima[r]
            println("work with $i, $t on $(Threads.threadid())")
            Q[i] = Q[i] + rand()
        end
    end
end
# By now we have a new set of local minimas we can handle in threads 
peek(Q)

# rinse and repeat from line 49 

Illustration: Changing the priority of two local minimum indices in a line graph changes some neighbouring indices into local minima. The macro @threads strides first over blue regions and then over white regions making sure that separate threads work on non-adjacent regions.