Last active
June 23, 2020 11:42
-
-
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.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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