Skip to content

Instantly share code, notes, and snippets.

@mschauer
Last active September 1, 2022 19:53
Show Gist options
  • Save mschauer/54c6baf5ced6160ef7acaa13463e0b9c to your computer and use it in GitHub Desktop.
Save mschauer/54c6baf5ced6160ef7acaa13463e0b9c to your computer and use it in GitHub Desktop.
keeping track of local minima in threaded programs with PartialQueue
#=
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
@mschauer
Copy link
Author

mschauer commented Sep 1, 2022

9E8E0411-BDB5-4424-B545-11EA8A33FD9C

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment