K-ballo changed the topic of #ste||ar to: STE||AR: Systems Technology, Emergent Parallelism, and Algorithm Research | stellar.cct.lsu.edu | HPX: A cure for performance impaired parallel applications | github.com/STEllAR-GROUP/hpx | Buildbot: http://rostam.cct.lsu.edu/ | Log: http://irclog.cct.lsu.edu/
K-ballo has quit [Quit: K-ballo]
diehlpk_work has quit [Remote host closed the connection]
hkaiser has quit [Quit: bye]
hkaiser has joined #ste||ar
K-ballo has joined #ste||ar
<srinivasyadav227>
hkaiser: hi, i have rebased the seperate_datapar branch against master few days back but, it also added few of the commits that i have not done, i again rebased today, but it still has the commits i did not do?, is there anything wrong i am doing here? i just did `git rebase upstream/master`
<K-ballo>
that's because your PR doesn't target master
<K-ballo>
and those commits from master aren't present in the branch you target
<K-ballo>
usually you'd rebase against the branch you are targeting, but also targeting non-master is rare
<hkaiser>
srinivasyadav227: you need to rebase onto the branch you're targetting, sorry for pointing you into the wrong direction
<hkaiser>
or let me rebase the target branch onto master first
<srinivasyadav227>
okay 🙂
<hkaiser>
I have rebased it now
<srinivasyadav227>
hkaiser: thanks, i will apply the changes soon ;)
<gonidelis[m]>
K-ballo: hkaiser where could i copy this range in order for the copy to parallelizable?
<gonidelis[m]>
but if i try with the `hpx::ranges::for_each` it does not
<gonidelis[m]>
sad
<gonidelis[m]>
it would be the perfect outro
<gonidelis[m]>
K-ballo: can you see pm please?
<K-ballo>
why wouldn't for_each work? it requires nothing extra
<gonidelis[m]>
hpx for_each won't
<gonidelis[m]>
i don't know why
<K-ballo>
are you triple sure? sounds like an hpx bug
<gonidelis[m]>
yes
<gonidelis[m]>
it is an hpx bug
<gonidelis[m]>
it should be running
<K-ballo>
make sure to report it
<gonidelis[m]>
i will
<gonidelis[m]>
i will probably fix it too
<gonidelis[m]>
K-ballo: pm...in case you have a spare minute.
<K-ballo>
gonidelis[m]: consider how a parallel for each would work
<K-ballo>
the simplest approach is to split the range into as many subranges as you have threads of execution
<gonidelis[m]>
yes
<K-ballo>
so if you have 2 threads, you'd split the range in the middle
<gonidelis[m]>
make the transformation on an elem by elem basis and decise on removal at the spot
<K-ballo>
so, how do you get to the middle?
<gonidelis[m]>
everything sounds great? ;p
<gonidelis[m]>
to the middle?
<gonidelis[m]>
say 2 threads... i split the range in half
<gonidelis[m]>
1 threads does the one half and the other does the other one
<K-ballo>
consider a good old iterator pair range: [first, last), how do you find the middle?
<gonidelis[m]>
ahh you need `remove_if` to provide with a sequnce of elements. so the non-removed ones would add overhead on finding where they should be put
<K-ballo>
no, forget remove_if
<gonidelis[m]>
first + last /2
<gonidelis[m]>
( ) *
<K-ballo>
first + last makes no sense, what does it mean to add iterators?
<gonidelis[m]>
last - first / 2
<K-ballo>
ok, better, bad precedence
<gonidelis[m]>
(last - first) / 2
<K-ballo>
there you go
<K-ballo>
and that requires random access iterators
<gonidelis[m]>
yy
<gonidelis[m]>
actually
<gonidelis[m]>
why
<gonidelis[m]>
?
<gonidelis[m]>
it requires random access for that to be o(1)
<gonidelis[m]>
it could be done in o(n) with bidir
<K-ballo>
iterators only provide functionality that is (amortized) o(1)
<gonidelis[m]>
ahhh ok
<gonidelis[m]>
yeah
<gonidelis[m]>
soudns right
<K-ballo>
and you are not allowed by the algorithm complexity guarantees to do that in o(n) anyhow
<gonidelis[m]>
we have algos for the o(n)'s
<gonidelis[m]>
ok great
<gonidelis[m]>
so that requires random access but i have bidir
<K-ballo>
so, in the traditional world, no random access -> no parallelizable
<gonidelis[m]>
actually why do you ask about the middle
<gonidelis[m]>
?
<gonidelis[m]>
yyyyes
<gonidelis[m]>
i wish that was the case
<K-ballo>
in the lazy ranges world it can be
<gonidelis[m]>
0.0
<K-ballo>
the middle comes from having 2 threads
<gonidelis[m]>
ahh yes
<gonidelis[m]>
you need to split it in hald
<K-ballo>
if I had 8 threads I'd ask for the 7 positions that split that into 8 subranges
<gonidelis[m]>
half
<gonidelis[m]>
ok
<gonidelis[m]>
how? what happened and all of a sudden a lazy view gives me the middle just that fast?
<K-ballo>
you can't get the middle in O(1)
<K-ballo>
but you don't necessarily need to
<gonidelis[m]>
ahhh why?
<K-ballo>
because your range has bidirectional iterators
<K-ballo>
but if you can get the middle of the underlying range in O(1) you are good to go, or the middle of the underlying range of that one, or ... and so on
<gonidelis[m]>
why is it that because i don't need to get the middle in o(1)?
<gonidelis[m]>
i don't understand your argument
<K-ballo>
you do still need to get to the middle in o(1), but it doesn't need to be the middle of the outmost range, you can pick any one of the lazy chain of operations
<K-ballo>
if you have remove_if(vector) you can't jump to the middle of it in O(1), but you can jump to the middle of the vector in O(1), and apply remove_if to different halves
<gonidelis[m]>
ahhhhhhhhhhhhhhh
<gonidelis[m]>
yes
<gonidelis[m]>
yeeeeeees
<gonidelis[m]>
ok
<gonidelis[m]>
see pm again then K-ballo ;p
<K-ballo>
no, keep algorithmic discussion public
<gonidelis[m]>
it's not algorithmic discussin
<gonidelis[m]>
K-ballo: what you propose is a fork-join parallelism
<gonidelis[m]>
and actually that's the go to solution in my talk if fused parallelism does not work
<gonidelis[m]>
and yes it runs faster
<gonidelis[m]>
(well of course it would)
<gonidelis[m]>
so it's a all a matter of what iterators would be exposed
<gonidelis[m]>
by your view
<gonidelis[m]>
great
<K-ballo>
I don't necessarily propose a fork-join parallelism, no
<gonidelis[m]>
no necessarily
<gonidelis[m]>
rather than a back-up solution
<K-ballo>
I don't know what "fused parallelism" is
<gonidelis[m]>
parallelize the two chained operations simultaneously
<hkaiser>
srinivasyadav227: why did you close #5298?
<srinivasyadav227>
hkaiser: sorry, that branch was completely messed up, so i deleted it (so it automatically got closed) , i have a backup branch, i have clean branch with changes rebased with fixing_datapar
<hkaiser>
srinivasyadav227: there is no need to close PRs, you can always force-push
<hkaiser>
to the branch, I mean
<srinivasyadav227>
nono..i deleted the branch, so it got closed automatically, i did not do manually
<hkaiser>
ok
<srinivasyadav227>
hkaiser: is there any way now i can push new branch to #5298 again?
<hkaiser>
if it's the same name, then you should be able to reopen it and push to it
<K-ballo>
gonidelis[m]: the operations are lazy, there's no choice but to parallelize them simultaneously.. what am I missing?
<srinivasyadav227>
yes, its same name ;)
<K-ballo>
I just remembered a conversation we had in issaquah when we first discussed adopting parallel algorithms, the complexity guarantee requirements do allow for advancing the bidirectional iterator, so it would actually be viable for a *sized* bidirectional range (just undesirable)
<K-ballo>
it wasn't an option pre ranges, because asking the size added an N
<hkaiser>
what is a 'sized' bidir iterator?
<K-ballo>
no, nevermind, that's still another N
<K-ballo>
sized range
<srinivasyadav227>
hkaiser: both branches have same name but its not allowing me to reopen, sorry, can i create another PR?
<K-ballo>
sized range knows its size in constant time, but it's not necessarily random access
<hkaiser>
srinivasyadav227: no other way, then
<gonidelis[m]>
<K-ballo "gonidelis: the operations are la"> hm yeah
<gonidelis[m]>
K-ballo: there is no straightforward way in parallelizing them fork-joinly
<hkaiser>
K-ballo: how would that work?
<srinivasyadav227>
hkaiser: ok, thanks, i will do it ;)
<K-ballo>
hkaiser: list | take_exactly(7)
<gonidelis[m]>
actually doing it in a fork-join way would destroy the concept of laziness