<div>This paper was interesting to me when it came out, both for the different approach taken for work stealing and for the emphasis on not using atomic instructions like CAS to improve speed..</div><div><br></div><div>Has there been any discussion on this list about implementing these algorithms for the j.u.c.</div>

<div><br></div><div>(I&#39;m surprised to not find a Search function for the archives of this list)</div><div><br></div><div>best</div><div><br></div><div>kimo crossman</div><div><br></div><div><br></div><div><span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif; font-size: 16px; -webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px; "><strong>Idempotent work stealing (2009)</strong></span></div>

<div><font class="Apple-style-span" face="Arial, Helvetica, sans-serif" size="4"><span class="Apple-style-span" style="font-size: 16px; -webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px;"><b><a href="http://docs.google.com/viewer?url=http://domino.research.ibm.com/comm/research_people.nsf/pages/mtvechev.pubs.html/$FILE/idempotentWSQ09.pdf">http://domino.research.ibm.com/comm/research_people.nsf/pages/mtvechev.pubs.html/$FILE/idempotentWSQ09.pdf</a></b></span></font></div>

<div><br></div><div><span class="Apple-style-span" style="font-family: Verdana, Arial, Helvetica, sans-serif; font-size: 13px; -webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px; "><table cellpadding="0" cellspacing="0">

<tbody><tr><td class="small-text" style="font-family: Arial, Helvetica, sans-serif; font-size: 0.83em; color: rgb(0, 0, 0); "><a href="http://portal.acm.org/author_page.cfm?id=81332515587&amp;coll=GUIDE&amp;dl=GUIDE&amp;trk=0&amp;CFID=70118550&amp;CFTOKEN=52758888" target="_self" style="text-decoration: underline; color: rgb(0, 102, 153); background-color: transparent; ">Maged M. Michael</a></td>

<td class="small-text" style="font-family: Arial, Helvetica, sans-serif; font-size: 0.83em; color: rgb(0, 0, 0); "><small> IBM Thomas J. Watson Research Center, Yorktown Height, NY, USA</small></td></tr><tr><td class="small-text" style="font-family: Arial, Helvetica, sans-serif; font-size: 0.83em; color: rgb(0, 0, 0); ">

<a href="http://portal.acm.org/author_page.cfm?id=81100269652&amp;coll=GUIDE&amp;dl=GUIDE&amp;trk=0&amp;CFID=70118550&amp;CFTOKEN=52758888" target="_self" style="text-decoration: underline; color: rgb(0, 102, 153); background-color: transparent; ">Martin T. Vechev</a></td>

<td class="small-text" style="font-family: Arial, Helvetica, sans-serif; font-size: 0.83em; color: rgb(0, 0, 0); "><small> IBM Thomas J. Watson Research Center, Hawthorne, NY, USA</small></td></tr><tr><td class="small-text" style="font-family: Arial, Helvetica, sans-serif; font-size: 0.83em; color: rgb(0, 0, 0); ">

<a href="http://portal.acm.org/author_page.cfm?id=81100152268&amp;coll=GUIDE&amp;dl=GUIDE&amp;trk=0&amp;CFID=70118550&amp;CFTOKEN=52758888" target="_self" style="text-decoration: underline; color: rgb(0, 102, 153); background-color: transparent; ">Vijay A. Saraswat</a></td>

<td class="small-text" style="font-family: Arial, Helvetica, sans-serif; font-size: 0.83em; color: rgb(0, 0, 0); "><small> IBM Thomas J. Watson Research Center, Hawthorne, NY, USA</small></td></tr></tbody></table></span></div>

<div><br></div><div><span class="Apple-style-span" style="font-family: Verdana, Arial, Helvetica, sans-serif; font-size: 13px; "><p style="font-family: Verdana, Arial, Helvetica, sans-serif; font-size: 13px; ">Load balancing is a technique which allows efficient parallelization of irregular workloads, and a key component of many applications and parallelizing runtimes. Work-stealing is a popular technique for implementing load balancing, where each parallel thread maintains its own work set of items and occasionally steals items from the sets of other threads.</p>

<p style="font-family: Verdana, Arial, Helvetica, sans-serif; font-size: 13px; ">The conventional semantics of work stealing guarantee that each inserted task is eventually extracted exactly once. However, correctness of a wide class of applications allows for relaxed semantics, because either: i) the application already explicitly checks that no work is repeated or ii) the application can tolerate repeated work.</p>

<p style="font-family: Verdana, Arial, Helvetica, sans-serif; font-size: 13px; ">In this paper, we introduce <i>idempotent work tealing</i>, and present several new algorithms that exploit the relaxed semantics to deliver better performance. The semantics of the new algorithms guarantee that each inserted task is eventually extracted <i>at least</i> once-instead of <i>exactly</i> once.</p>

<p style="font-family: Verdana, Arial, Helvetica, sans-serif; font-size: 13px; "><u>For a wide range of applications dealing with irregular computation patterns. Sample domains include: parallel garbage collection, fixed point computations in program analysis, constraint solvers (e.g. SAT solvers), state space search exploration in model checking as well as integer and mixed programming solvers.</u></p>

<p style="font-family: Verdana, Arial, Helvetica, sans-serif; font-size: 13px; ">On mainstream processors, algorithms for conventional work stealing require special atomic instructions (CAS) or store-load memory ordering fence instructions in the owner&#39;s critical path operations. In general, these instructions are substantially slower than regular memory access instructions. By exploiting the relaxed semantics, our algorithms avoid these instructions in the owner&#39;s operations.</p>

<p style="font-family: Verdana, Arial, Helvetica, sans-serif; font-size: 13px; ">We evaluated our algorithms using common graph problems and micro-benchmarks and compared them to well-known conventional work stealing algorithms, the THE Cilk and Chase-Lev algorithms. We found that our best algorithm (with LIFO extraction) outperforms existing algorithms in nearly all cases, and often by significant margin</p>

</span></div>