proof of correctness of your check for the busy loop about giotto-ph HOT 5 CLOSED

Hi,

I think you are talking about this loop. This condition comes directly from this paper. See algorithm 3, the small do{}while loop.

From the paper itself it states the following concerning the do{}while loop:

To accommodate the possibility that after we read the pivot piv :=pivots[ℓ] and before we read the pivot column R[piv], another thread updates R[piv], we must check that low(R[piv])= low(curr_column). If this condition fails, we re-read the pivot. That’s the point of the while-loop in line 6 of Algorithm 3.

I am not sure what other proof I could provide you with, but please let me know.

Best,
Julián

from giotto-ph.

Yes, it suffices to check that piv does not change in between the two assignments piv := pivots[l] and piv_column := R[piv] so that the index of piv_column is actually piv later in execution. The check low(piv_column)==l is more expensive. Notice that pivots[l] is monotonically moving toward the left over execution so that if you check pivots[l] again, either it stays the same or it has moved left (it never comes back). Thus you cannot have inconsistent piv_column and piv and have the second read on pivots[l] equal piv. This explains why you have the condition in the while loop and this line checking pivots[l] again after the second assignment.

from giotto-ph.

Hi,

First of all, I am really sorry to give you a so late reply, I though I gave you an answer, but I don't know what happened.

If I understand you right, you are saying that we could replace this loop from the original algorithm:

do
	piv := pivots[ℓ]
	piv_column := R[piv]
while ℓ != low(piv_column)

By:

do
	piv := pivots[ℓ]
	piv_column := R[piv]
while piv != pivots[ℓ]

Is this what you have as an idea ?
This would allow a less costly operation.
Hard to say, if it would have a significant impact on runtime, due to the multi-threaded execution.

I looked deeply into the current implementation of this section, and I think that we could simplify it even further.
I will try to modify and test some ideas and let you know if I get something interesting.

Best,
Julián

from giotto-ph.

@simonzhang00 wondering if you have any more comments on this topic? I think it would be interesting to see if your point can lead to a speedup (e.g. as @MonkeyBreaker is proposing).

from giotto-ph.

I have no further comments. Thanks and good luck.

from giotto-ph.