<html><body><p><font size="2" color="#2F2F2F">Dear all</font><font size="2" color="#2F2F2F">,</font><br><br><font size="2" color="#2F2F2F">Would you please review the following change?</font><br><font size="2" color="#2F2F2F">This is not a bug fix but refactoring.</font><br><br><font size="2" color="#2F2F2F">The taskqueue is implemented based on the ABP work-stealing algorithm as noted in comment. </font><font size="2" color="#2F2F2F">(</font><font size="2" color="#2F2F2F">It looks Chase-Lev work-stealing</font><font size="2" color="#2F2F2F">,</font><font size="2" color="#2F2F2F"> which addressed the overflow problem of ABP work-stealing</font><font size="2" color="#2F2F2F">,</font><font size="2" color="#2F2F2F"> but core algorithm is the same.</font><font size="2" color="#2F2F2F">)</font><br><font size="2" color="#2F2F2F"> 231 // Arora</font><font size="2" color="#2F2F2F">,</font><font size="2" color="#2F2F2F"> N. S.</font><font size="2" color="#2F2F2F">,</font><font size="2" color="#2F2F2F"> Blumofe</font><font size="2" color="#2F2F2F">,</font><font size="2" color="#2F2F2F"> R. D.</font><font size="2" color="#2F2F2F">,</font><font size="2" color="#2F2F2F"> and Plaxton</font><font size="2" color="#2F2F2F">,</font><font size="2" color="#2F2F2F"> C. G.</font><br><font size="2" color="#2F2F2F"> 232 // Thread scheduling for multiprogrammed multiprocessors.</font><br><font size="2" color="#2F2F2F"> 233 // Theory of Computing Systems 34</font><font size="2" color="#2F2F2F">,</font><font size="2" color="#2F2F2F"> 2 </font><font size="2" color="#2F2F2F">(</font><font size="2" color="#2F2F2F">2001</font><font size="2" color="#2F2F2F">),</font><font size="2" color="#2F2F2F"> 115-144.</font><br><br><font size="2" color="#2F2F2F">Correctness is presented with the following paper as also noted:</font><br><font size="2" color="#2F2F2F"> 241 // Le</font><font size="2" color="#2F2F2F">,</font><font size="2" color="#2F2F2F"> N. M.</font><font size="2" color="#2F2F2F">,</font><font size="2" color="#2F2F2F"> Pop</font><font size="2" color="#2F2F2F">,</font><font size="2" color="#2F2F2F"> A.</font><font size="2" color="#2F2F2F">,</font><font size="2" color="#2F2F2F"> Cohen A.</font><font size="2" color="#2F2F2F">,</font><font size="2" color="#2F2F2F"> and Nardell</font><font size="2" color="#2F2F2F">,</font><font size="2" color="#2F2F2F"> F. Z.</font><br><font size="2" color="#2F2F2F"> 242 // Correct and efficient work-stealing for weak memory models</font><br><font size="2" color="#2F2F2F"> 243 // Proceedings of the 18th ACM SIGPLAN symposium on Principles and</font><br><font size="2" color="#2F2F2F"> 244 // practice of parallel programming </font><font size="2" color="#2F2F2F">(</font><font size="2" color="#2F2F2F">PPoPP 2013</font><font size="2" color="#2F2F2F">),</font><font size="2" color="#2F2F2F"> 69-80</font><br><br><font size="2" color="#2F2F2F">There is a slight difference between the current taskqueue and </font><font size="2" color="#2F2F2F">Chase-Lev's deque. When an owner thread and thieves try to take the last task in the deque and a thief succeeds in stealing the task</font><font size="2" color="#2F2F2F">,</font><font size="2" color="#2F2F2F"> top is decreased by the owner thread in taskqueue</font><font size="2" color="#2F2F2F">,</font><font size="2" color="#2F2F2F"> while bottom is increased in </font><font size="2" color="#2F2F2F">Chase-Lev's deque.</font><br><br><font size="2" color="#2F2F2F">Le et al. use the characteristics that top monotonically increases for the proofs in their paper. I think there is no reason to decrease top in taskqueue. One tricky thing in current taskqueue is that loading a task before the CAS trial in pop_global() avoids the side effect that owner thread can push </font><font size="2" color="#2F2F2F">(</font><font size="2" color="#2F2F2F">thus</font><font size="2" color="#2F2F2F">,</font><font size="2" color="#2F2F2F"> overwrite with</font><font size="2" color="#2F2F2F">)</font><font size="2" color="#2F2F2F"> a new task in the same slot at which a thief stole the last task. I think it is more straightforward that top is changeable only via CAS and monotonically increased. Releasing incremented bottom is not necessary because succeeding push will release the bottom. Please note there is no concern in concurrency because size() in pop_global() returns 0 for dirty_size()=N-1 and so there is no thief trying a steal.</font><br><font size="2" color="#2F2F2F"> 180 return (sz == N - 1) ? 0 : sz;</font><br><br><font size="2" color="#2F2F2F">Bug: </font><font size="2" color="#2F2F2F"><a href="https://bugs.openjdk.java.net/browse/JDK-8208636">https://bugs.openjdk.java.net/browse/JDK-8208636</a></font><br><font size="2" color="#2F2F2F">Webrev: </font><font size="2" color="#2F2F2F"><a href="http://cr.openjdk.java.net/~mhorie/8208636/webrev.00/">http://cr.openjdk.java.net/~mhorie/8208636/webrev.00/</a></font><br><br><font size="2">I ran JTREG and SPECjbb2015 to confirm there is no change in the test results and performance. Again this is just a refactoring and it's true current taskqueue works even if it is not aligned with the formal proofs partly.</font><br><br><br><font size="2">Best regards,</font><br><font size="2">--</font><br><font size="2">Michihiro,</font><br><font size="2">IBM Research - Tokyo</font><BR>
</body></html>