<div dir="ltr"><div>Hello, Shintaro,</div>Thank you for your reply. That's exactly what I'm doing and how I fixed the problem on my side. I just wanted to see whether there is something else that I am missing.<div>Best,</div><div>Polykarpos</div></div><br><div class="gmail_quote"><div dir="ltr">On Thu, Nov 1, 2018 at 7:49 PM Iwasaki, Shintaro <<a href="mailto:siwasaki@anl.gov">siwasaki@anl.gov</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">




<div dir="ltr">
<div id="m_-7449790926838575747divtagdefaultwrapper" style="font-size:12pt;color:#000000;font-family:Calibri,Helvetica,sans-serif" dir="ltr">
<div id="m_-7449790926838575747divtagdefaultwrapper" dir="ltr" style="font-size:12pt;color:rgb(0,0,0);font-family:Calibri,Helvetica,sans-serif,EmojiFont,"Apple Color Emoji","Segoe UI Emoji",NotoColorEmoji,"Segoe UI Symbol","Android Emoji",EmojiSymbols">
<p style="margin-top:0;margin-bottom:0">Hello, <span style="font-family:Calibri,Helvetica,sans-serif,EmojiFont,"Apple Color Emoji","Segoe UI Emoji",NotoColorEmoji,"Segoe UI Symbol","Android Emoji",EmojiSymbols;font-size:16px">Polykarpos,</span></p>
<p style="margin-top:0;margin-bottom:0"><br>
</p>
<p style="margin-top:0;margin-bottom:0">I am Shitnaro Iwasaki, who is currently working on Argobots.</p>
<p style="margin-top:0;margin-bottom:0">Thank you for your reporting an issue!</p>
<p style="margin-top:0;margin-bottom:0"><br>
</p>
<p style="margin-top:0;margin-bottom:0">(0. Bug)</p>
<p style="margin-top:0;margin-bottom:0"><br>
</p>
<p style="margin-top:0;margin-bottom:0">ES1 pushes ULT1 in Pool1 <= (according to the SPMC rule, only ES1 can be a single producer of Pool1)</p>
<p style="margin-top:0;margin-bottom:0">ES1 pops ULT1 from Pool1</p>
<p style="margin-top:0;margin-bottom:0">ES1 suspends ULT1 to wait for something (e.g., ABT_self_suspend, ABT_thread_join, or ABT_mutex_lock)</p>
<p style="margin-top:0;margin-bottom:0">ES2 resumes ULT1 <= In this operation, ES2 pushes ULT1 to Pool1 (breaking the SPMC rule)</p>
<p style="margin-top:0;margin-bottom:0"><br>
</p>
<p style="margin-top:0;margin-bottom:0">1. Is this behavior by design?</p>
<p style="margin-top:0;margin-bottom:0"><br>
</p>
<p style="margin-top:0;margin-bottom:0">For now, this problem is known and it's user's responsibility to deal with it (i.e., using SPMC correctly is challenging).</p>
<p style="margin-top:0;margin-bottom:0">It can happen even without using a custom pool if the producer/consumer error check is enabled.</p>
<p style="margin-top:0;margin-bottom:0"><br>
</p>
<p style="margin-top:0;margin-bottom:0">2. Workarounds?</p>
<p style="margin-top:0;margin-bottom:0"><br>
</p>
<p style="margin-top:0;margin-bottom:0">2A. Use <span>ABT_unit_set_associated_pool somewhere</span></p>
<p style="margin-top:0;margin-bottom:0"><span style="font-size:12pt"><br>
</span></p>
<p style="margin-top:0;margin-bottom:0"><span style="font-size:12pt">There's no good place to put it, since everything happens in Argobots.</span><br>
</p>
<p style="margin-top:0;margin-bottom:0"><span>Even if you use <span style="font-family:Calibri,Helvetica,sans-serif,EmojiFont,"Apple Color Emoji","Segoe UI Emoji",NotoColorEmoji,"Segoe UI Symbol","Android Emoji",EmojiSymbols;font-size:16px">ABT_self_suspend,
 don't change the associated pool of the suspended ULT (though I haven't confirmed it).</span></span></p>
<p style="margin-top:0;margin-bottom:0"><br>
</p>
<p style="margin-top:0;margin-bottom:0">2B. Disable the suspend-resume optimization in ABT_thread_join and ABT_mutex_lock</p>
<p style="margin-top:0;margin-bottom:0"><br>
</p>
<p style="margin-top:0;margin-bottom:0">For mutex: --enable-simple-mutex might help.</p>
<p style="margin-top:0;margin-bottom:0">For join: no way to avoid it.</p>
<p style="margin-top:0;margin-bottom:0"><span style="font-size:12pt">thread.c 426: add "</span><span style="font-size:12pt">goto yield_based;</span><span style="font-size:12pt">" can disable it (just FYI)</span></p>
<p style="margin-top:0;margin-bottom:0"><br>
</p>
<p style="margin-top:0;margin-bottom:0">2C. Use MPMC pool.</p>
<p style="margin-top:0;margin-bottom:0"><br>
</p>
<p style="margin-top:0;margin-bottom:0">3. Workaround in your case</p>
<p style="margin-top:0;margin-bottom:0"><br>
</p>
<p style="margin-top:0;margin-bottom:0">The following is based on my guess.</p>
<p style="margin-top:0;margin-bottom:0">If you are implementing a scalable (maybe Cilk-like) work stealing queue, <span style="font-size:12pt">you can create a single MPMC pool, </span><span style="font-size:12pt">which internally contains multiple SPMC
 queues (per execution stream).</span></p>
<p style="margin-top:0;margin-bottom:0"><span style="font-size:12pt">You can differentiate the caller by execution stream rank (<span>ABT_xstream_self_rank) </span></span><span style="font-size:12pt">so that you can </span>always <span style="font-size:12pt">push
</span><span style="font-size:12pt">into its local queue.</span></p>
<p style="margin-top:0;margin-bottom:0"><span style="font-size:12pt">I think it <span style="font-family:Calibri,Helvetica,sans-serif,EmojiFont,"Apple Color Emoji","Segoe UI Emoji",NotoColorEmoji,"Segoe UI Symbol","Android Emoji",EmojiSymbols;font-size:16px">is</span> the
 most beautiful workaround <span style="font-family:Calibri,Helvetica,sans-serif,EmojiFont,"Apple Color Emoji","Segoe UI Emoji",NotoColorEmoji,"Segoe UI Symbol","Android Emoji",EmojiSymbols;font-size:16px">at present</span>.</span><br>
</p>
<p style="margin-top:0;margin-bottom:0"><span style="font-size:12pt"><br>
</span></p>
<p style="margin-top:0;margin-bottom:0">4. Misc</p>
<p style="margin-top:0;margin-bottom:0"><br>
</p>
<p style="margin-top:0;margin-bottom:0">To address this issue, the natural extension of Argobots calls different push/pop functions depending on contexts.</p>
<p style="margin-top:0;margin-bottom:0"><br>
</p>
<p style="margin-top:0;margin-bottom:0"></p>
<p style="font-family:Calibri,Helvetica,sans-serif,EmojiFont,"Apple Color Emoji","Segoe UI Emoji",NotoColorEmoji,"Segoe UI Symbol","Android Emoji",EmojiSymbols;font-size:16px">
Typically, work stealing queues need to differentiate them:</p>
<p style="font-family:Calibri,Helvetica,sans-serif,EmojiFont,"Apple Color Emoji","Segoe UI Emoji",NotoColorEmoji,"Segoe UI Symbol","Android Emoji",EmojiSymbols;font-size:16px">
- push (when creating a thread) and push (when suspending a thread (e.g., yield) (*)), push (when push back to the pool (e.g., set_ready))</p>
<p style="font-family:Calibri,Helvetica,sans-serif,EmojiFont,"Apple Color Emoji","Segoe UI Emoji",NotoColorEmoji,"Segoe UI Symbol","Android Emoji",EmojiSymbols;font-size:16px">
- pop (locally) and pop (remotely)</p>
<br>
<p></p>
<p style="margin-top:0;margin-bottom:0">(*) About push (suspend): In general, work stealing queues do not work if you limit local push and pop only to/from the bottom.</p>
<p style="margin-top:0;margin-bottom:0">For example, ES will reschedule the same ULT after ABT_thread_yield().</p>
<p style="margin-top:0;margin-bottom:0"><br>
</p>
<p style="margin-top:0;margin-bottom:0"><span style="font-size:12pt">Currently Argobots does not distinguish them. We are happy to have discussion about it.</span><br>
</p>
<p style="margin-top:0;margin-bottom:0"><br>
</p>
<p style="margin-top:0;margin-bottom:0">If I am misunderstanding and/or you have any questions, please feel free to send an e-mail (or post a github issue).</p>
<p style="margin-top:0;margin-bottom:0"><br>
</p>
<p style="margin-top:0;margin-bottom:0">Best Regards,</p>
<p style="margin-top:0;margin-bottom:0">Shintaro iwasaki</p>
<p style="margin-top:0;margin-bottom:0"><br>
</p>
</div>
<hr style="display:inline-block;width:98%">
<div id="m_-7449790926838575747divRplyFwdMsg" dir="ltr"><font face="Calibri, sans-serif" color="#000000" style="font-size:11pt"><b>From:</b> POLYKARPOS THOMADAKIS via discuss <<a href="mailto:discuss@lists.argobots.org" target="_blank">discuss@lists.argobots.org</a>><br>
<b>Sent:</b> Thursday, November 1, 2018 10:25:17 AM<br>
<b>To:</b> <a href="mailto:discuss@argobots.org" target="_blank">discuss@argobots.org</a><br>
<b>Cc:</b> POLYKARPOS THOMADAKIS<br>
<b>Subject:</b> [argobots-discuss] Possible issue</font>
<div> </div>
</div>
<div>
<div dir="ltr">
<div dir="ltr">
<div>Hello there,</div>
<div><br>
</div>
<div>I am experiencing the following issue using Argobots, I'm not sure if that's a bug or an assumption made by Argobots that is not explicit.</div>
<div>Here is the issue:</div>
<div><br>
</div>
<div>I have a set of custom pools, 1 per Execution Stream.</div>
<div><br>
</div>
<div>In each of the pools, only the associated execution stream can push while other streams can grab a unit from other streams' pool safely. </div>
<div>Those are the characteristics of an SPMC pool, so that's the type I specify on their creation.</div>
<div><br>
</div>
<div>The underlying data structure is a lock-free cyclic deque where the pushing is done at the bottom, the popping (where the owner stream of the pool grabs a unit) </div>
<div>also at the bottom, and the stealing (where a stream grabs a unit from the pools of another stream) from the top.</div>
<div><br>
</div>
<div>In this way when a ULT is created it's always pushed on the pool of the creating stream and can be stolen by other streams safely. The application works perfectly</div>
<div>with just creating and executing ULTs, however, when I need the join functionality is where the problem occurs. The workflow is as follows:</div>
<div><br>
</div>
<div>1) ULT 0 spawns its children ULTs in ES 0</div>
<div>2) ES 1 steals one (or more) of the ULT from ES 0</div>
<div>3) ULT 0 on ES 0 joins one of its children -> Argobots suspends its execution</div>
<div>4) ES 1 terminates with the execution of the stolen ULT. This will cause Argobots to try to awaken the blocked ULT 0 by pushing it back to the pool of its last stream,</div>
<div>   which is ES 0. </div>
<div><br>
</div>
<div>And here is the problem, ES 1 awakens ULT 0, pushes it to the pool of ES 0, thus, breaking the rule that only the associated stream of a pool is allowed to push to it.</div>
<div>Since the user has no API to defined to which pool a unit shall be pushed in such situations, I believed that by setting the pool type to SPMC Argobots would take care</div>
<div>of this. </div>
<div><br>
</div>
<div>The lines that produce this issue:</div>
<div><br>
</div>
<div>arch/abtd_thread.c:88 -> Terminating thread awakens blocked joiner</div>
<div>thread.c:2017 -> Joiner is pushed to the last pool it ran before blocking, causing one stream to push to the pools of another</div>
<div><br>
</div>
<div>My question is whether this behavior is the expected one or not. In other words, if the user is expected to take into consideration this behavior when designing his/her</div>
<div>custom pools.</div>
<div><br>
</div>
<div>Sorry for the long email and thank you for your time.<br>
</div>
<div><br>
</div>
<div>Best,</div>
<div>Polykarpos     </div>
</div>
</div>
</div>
</div>
</div>

</blockquote></div>