Skip to content

Instantly share code, notes, and snippets.

@jwscook
Last active June 23, 2020 11:42
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jwscook/2a9f080a96a01d62a805a9f0f2b64244 to your computer and use it in GitHub Desktop.
Save jwscook/2a9f080a96a01d62a805a9f0f2b64244 to your computer and use it in GitHub Desktop.
Finding optimal threading of two consecutive double loops where some rows are skipped in the first double loop and the second double loop depends on the output of the first.
using Base.Threads, Random
function run(;waittime=1.0e-3)
function calcsubset(N)
Random.seed!(0)
return sort(shuffle(collect(1:N))[1:Int(ceil(round(N / 3)))])
end
# we know that only a sorted subset of rows need be iterated over for the first loop
function method1(m, subsetofrows)
Threads.@threads for i in subsetofrows
for j in 1:size(m, 2)
# do some things that are expensive that could alter any column for this row
Threads.sleep(waittime)
randj = j # could be any j, but for simplicity don't call rand here and just use current value of j
m[i, randj] += 1 # mutate m[i, randj]
end
end
# now go the other way round
Threads.@threads for j in 1:size(m, 2)
for i in 1:size(m, 1)
# something that alters this row and column and depends on it's current value
Threads.sleep(waittime)
m[i, j] += m[i, j] # calculation that depends on m[i, j]
end
end
return m
end
function method2(m, subsetofrows)
function firstloop(i)
for j in 1:size(m, 2)
# do some things that are expensive that could alter any column for this row
Threads.sleep(waittime)
randj = j # could be any j, but for simplicity don't call rand here and just use current value of j
m[i, randj] += 1 # mutate m[i, randj]
end
end
iloop = Dict()
for i in subsetofrows
iloop[i] = Threads.@spawn firstloop(i)
end
notsubset = [i for i in 1:size(m, 1) if !(i in subsetofrows)]
ordered_i_loop = vcat(notsubset, subsetofrows)
# now go the other way round
Threads.@threads for j in 1:size(m, 2)
for i in ordered_i_loop
(i in subsetofrows) && Threads.wait(iloop[i])
# something that alters this row and column and depends on it's current value
Threads.sleep(waittime)
m[i, j] += m[i, j] # calculation that depends on m[i, j]
end
end
return m
end
# practice
m_small = rand(3, 10)
subsetofrows = calcsubset(size(m_small, 1))
method1(deepcopy(m_small), subsetofrows)
method2(deepcopy(m_small), subsetofrows)
# real thing
m_working_size = rand(30, 1000)
subsetofrows = calcsubset(size(m_working_size, 1))
print("method1: ")
@time m1 = method1(deepcopy(m_working_size), subsetofrows)
print("method2: ")
@time m2 = method2(deepcopy(m_working_size), subsetofrows)
@assert all(m1 .== m2)
end
run()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment