Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

parallel_scan, number of calls to combine_body not deterministic for N=800 #8

Open
jnorwood opened this issue Sep 7, 2020 · 0 comments

Comments

@jnorwood
Copy link

jnorwood commented Sep 7, 2020

I was hoping the parallel_scan operation would be deterministic, or at least have a deterministic version option similar to parallel_deterministic_reduce.

I initially saw that the number of calls to combine_body in the fig_2_14 example varies between 1 and 16 times when N=800 on my 4 core, 8 thread x86, but this was my misinterpretation. Apparently vscode debugger resumes all threads with a single resume.

I can add scoped_lock at scope start of scan body and combine body to see that all blocks are called. An example of the calls with N=8 is a bit more interesting vs the fragment shown in the book.

`
For N=8
combine (x=0,y=0)
sum[1..2), fs=True, 1
sum[3..4), fs=False, 3
sum[6..7), fs=False, 6
sum[5..6), fs=False, 5
sum[2..3), fs=False, 2
sum[4..5), fs=False, 4
combine(x=2,y=3)
combine(x=1,y=5)
combine(x=4,y=5)
combine(x=1,y=2)
combine(x=6,y=9)
sum[2..3), fs=True, 3
combine(x=6,y=4)
sum[5..6), fs=True, 15
combine(x=15,y=6)
sum[3..4), fs=True, 6
sum[7..8), fs=True, 28
sum[6..7), fs=True, 21
sum[4..5), fs=True, 10

parallel_sum = 0,1,3,6,10,15,21,28
`
However, the above sequence is incorrect, since the interval [1..2) is called with final_sum=True on first execution. This creates an error result if v[0]!=0. The interval[0..1) is the one that needs to be called first with final_sum=True. I'm adding a separate issue to make that explicit.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant