<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<style type="text/css" style="display:none;"><!-- P {margin-top:0;margin-bottom:0;} --></style>
</head>
<body dir="ltr">
<div id="divtagdefaultwrapper" style="font-size:12pt;color:#000000;font-family:Calibri,Helvetica,sans-serif;" dir="ltr">
<div id="divtagdefaultwrapper" 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 tabindex="-1" style="display:inline-block; width:98%">
<div id="divRplyFwdMsg" dir="ltr"><font face="Calibri, sans-serif" color="#000000" style="font-size:11pt"><b>From:</b> POLYKARPOS THOMADAKIS via discuss <discuss@lists.argobots.org><br>
<b>Sent:</b> Thursday, November 1, 2018 10:25:17 AM<br>
<b>To:</b> discuss@argobots.org<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>
</body>
</html>