<html>
<head>
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<p><br>
</p>
<div class="moz-cite-prefix">On 03/16/2017 01:31 PM, Mehdi Amini
wrote:<br>
</div>
<blockquote
cite="mid:A0DCA00F-3CFE-47B3-8D89-E1BAF9D0D8B3@apple.com"
type="cite">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
Hey,
<div class=""><br class="">
</div>
<div class="">I think it is a great idea!</div>
<div class=""><br class="">
</div>
<div class="">On Mar 16, 2017, at 9:06 AM, Kareem Ergawy via
llvm-dev <<a moz-do-not-send="true"
href="mailto:llvm-dev@lists.llvm.org" class="">llvm-dev@lists.llvm.org</a>>
wrote:<br class="">
<div>
<blockquote type="cite" class=""><br
class="Apple-interchange-newline">
<div class="">
<div dir="ltr" class=""><span
id="gmail-docs-internal-guid-8135b1eb-d7dc-5684-1e6b-204dee4d8904"
class="">
<div style="line-height: 1.38; margin-top: 0pt;
margin-bottom: 0pt;" class=""><span style="background-color: transparent; font-family: arial; font-size: 11pt; white-space: pre-wrap;" class="">Hello,</span><br
class="">
</div>
<br class="">
<div style="line-height: 1.38; margin-top: 0pt;
margin-bottom: 0pt;" class=""><span style="font-size: 11pt; font-family: arial; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;" class="">Below is a proposal for a GSoC project that I would like to work on this year. Your input and feedback is much appreciated.</span></div>
<br class="">
<div style="line-height: 1.38; margin-top: 0pt;
margin-bottom: 0pt;" class=""><span style="font-size: 11pt; font-family: arial; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;" class="">Background:</span></div>
<div style="line-height: 1.38; margin-top: 0pt;
margin-bottom: 0pt;" class=""><span style="font-size: 11pt; font-family: arial; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;" class="">=========</span></div>
<br class="">
<div style="line-height: 1.38; margin-top: 0pt;
margin-bottom: 0pt;" class=""><span style="font-size: 11pt; font-family: arial; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;" class="">My name is Kareem Ergawy and I currently work as part of the PIR project. PIR is an extension of the IR to support fork-join parallelism that is currently under review [1, 2, 3, 4].</span></div>
<br class="">
<div style="line-height: 1.38; margin-top: 0pt;
margin-bottom: 0pt;" class=""><span style="font-size: 11pt; font-family: arial; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;" class="">Goals:</span></div>
<div style="line-height: 1.38; margin-top: 0pt;
margin-bottom: 0pt;" class=""><span style="font-size: 11pt; font-family: arial; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;" class="">=====</span></div>
<br class="">
<div style="line-height: 1.38; margin-top: 0pt;
margin-bottom: 0pt;" class=""><span style="font-size: 11pt; font-family: arial; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;" class="">As a GSoC project, here I propose an extension for llvm analyses and transformations to support parallel IR. Such extension should serve as a foundation for an optimization framework for parallel regions. I would like to emphasize that, in this proposal, I am trying propose ideas that satisfy the following conditions:</span></div>
<br class="">
<div style="line-height: 1.38; margin-top: 0pt;
margin-bottom: 0pt;" class=""><span style="font-size: 11pt; font-family: arial; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;" class="">(1) Not specific to PIR but rather can be adapted to other explicit parallel representations in the IR. For example, see [5] for Hal Finkel's and Xinmin Tian's proposal for region annotations.</span></div>
</span></div>
</div>
</blockquote>
<div><br class="">
</div>
<div>Having both Hal and Johannes as mentor would be very nice
for this project indeed.</div>
<div>I’ll be happy to help as well if needed, but I feel Hal
and Johannes would do a great job here if they’re willing to
work on this.</div>
</div>
</div>
</blockquote>
<br>
I'm certainly happy to mentor this (and I know that Johannes is as
well).<br>
<br>
-Hal<br>
<br>
<blockquote
cite="mid:A0DCA00F-3CFE-47B3-8D89-E1BAF9D0D8B3@apple.com"
type="cite">
<div class="">
<div>
<div><br class="">
</div>
<div>— </div>
<div>Mehdi</div>
<div><br class="">
</div>
<div><br class="">
</div>
<div><br class="">
</div>
<div><br class="">
</div>
<br class="">
<blockquote type="cite" class="">
<div class="">
<div dir="ltr" class=""><span
id="gmail-docs-internal-guid-8135b1eb-d7dc-5684-1e6b-204dee4d8904"
class=""><br class="">
<div style="line-height: 1.38; margin-top: 0pt;
margin-bottom: 0pt;" class=""><span style="font-size: 11pt; font-family: arial; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;" class="">(2) Can be extended upon in the future. Hopefully, this will be the start of a parallel optimization pipeline that integrates nicely with llvm's sequential pipeline.</span></div>
<div class=""><br class="">
</div>
<div style="line-height: 1.38; margin-top: 0pt;
margin-bottom: 0pt;" class=""><span style="font-size: 11pt; font-family: arial; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;" class="">Proposed passes:</span></div>
<div style="line-height: 1.38; margin-top: 0pt;
margin-bottom: 0pt;" class=""><span style="font-size: 11pt; font-family: arial; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;" class="">=============</span></div>
<br class="">
<div style="line-height: 1.38; margin-top: 0pt;
margin-bottom: 0pt;" class=""><span style="font-size: 11pt; font-family: arial; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;" class="">Here I list a few passes that I think will help kicking off such a parallel-centric optimization pipeline.</span></div>
<br class="">
<div style="line-height: 1.38; margin-top: 0pt;
margin-bottom: 0pt;" class=""><span style="font-size: 11pt; font-family: arial; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;" class="">1 - Execution partial order analysis:</span></div>
<div style="line-height: 1.38; margin-top: 0pt;
margin-bottom: 0pt;" class=""><span style="font-size: 11pt; font-family: arial; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;" class="">----------------------------------------------</span></div>
<br class="">
<div style="line-height: 1.38; margin-top: 0pt;
margin-bottom: 0pt;" class=""><span style="font-size: 11pt; font-family: arial; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;" class="">Yuki et al. [6] characterize 2 parallel relations, namely: "Happens Before" and "May Happen in Parallel". As the names imply, these 2 relations can be used to calculate a partial ordering over statements. I believe such analysis can be used as a useful building block for later analyses and optimizations. For example, it can reduce the constraints induced by the sequential order of statements in the IR of a parallel program. Lifting such constraints can provide better optimization chances even for already existing sequential passes. For an example of using such pass, see point 3 below.</span></div>
<br class="">
<div style="line-height: 1.38; margin-top: 0pt;
margin-bottom: 0pt;" class=""><span style="font-size: 11pt; font-family: arial; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;" class="">2 - Redundant barrier removal:</span></div>
<div style="line-height: 1.38; margin-top: 0pt;
margin-bottom: 0pt;" class=""><span style="font-size: 11pt; font-family: arial; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;" class="">----------------------------------------</span></div>
<br class="">
<div style="line-height: 1.38; margin-top: 0pt;
margin-bottom: 0pt;" class=""><span style="font-size: 11pt; font-family: arial; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;" class="">Satoh et al. [7] developed a memory synchronization analysis algorithm. At each synchronization point n, the algorithm calculates 2 sets:</span></div>
<br class="">
<div style="line-height: 1.38; margin-top: 0pt;
margin-bottom: 0pt;" class=""><span style="font-size: 11pt; font-family: arial; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;" class="">(1) WSync(n): is the set of definitions/writes that may need to be synchronized at n.</span></div>
<div style="line-height: 1.38; margin-top: 0pt;
margin-bottom: 0pt;" class=""><span style="font-size: 11pt; font-family: arial; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;" class="">(2) RSync(n): is the set of uses/reads that may need to be synchronized at n.</span></div>
<br class="">
<div style="line-height: 1.38; margin-top: 0pt;
margin-bottom: 0pt;" class=""><span style="font-size: 11pt; font-family: arial; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;" class="">If intersect(WSync(n), RSync(n)) = {}, then no inter-thread flow dependencies require barrier synchronization. Removing such barriers will mitigate the associated runtime overhead.</span></div>
<br class="">
<div style="line-height: 1.38; margin-top: 0pt;
margin-bottom: 0pt;" class=""><span style="font-size: 11pt; font-family: arial; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;" class="">3 - Adapt polyhedral transformations for parallel contexts:</span></div>
<div style="line-height: 1.38; margin-top: 0pt;
margin-bottom: 0pt;" class=""><span style="font-size: 11pt; font-family: arial; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;" class="">--------------------------------------------------------------------------</span></div>
<br class="">
<div style="line-height: 1.38; margin-top: 0pt;
margin-bottom: 0pt;" class=""><span style="font-size: 11pt; font-family: arial; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;" class="">Chatarasi et al. [8] build on the "Happens Before" relation introduced in the the first point above to enable larger sets of polyhedral transformations. In particular, the complement of the "Happens Before" relation is used to mitigate conservative dependences. The reduced set of dependences can then be passed to a polyhedral transformation tool. I guess such idea can be a good addition to Polly since it enables faster and more meaningful transformations of parallel programs.</span></div>
<br class="">
<div style="line-height: 1.38; margin-top: 0pt;
margin-bottom: 0pt;" class=""><span style="font-size: 11pt; font-family: arial; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;" class="">Other passes:</span></div>
<div style="line-height: 1.38; margin-top: 0pt;
margin-bottom: 0pt;" class=""><span style="font-size: 11pt; font-family: arial; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;" class="">-------------------</span></div>
<br class="">
<div style="line-height: 1.38; margin-top: 0pt;
margin-bottom: 0pt;" class=""><span style="font-size: 11pt; font-family: arial; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;" class="">The 3 suggestions above provide a taste for what can be an analysis framework for parallel programs in IR. There are other examples in the literature that can be added as well. Also, new ones can be designed. I will try to implement as much as I can for the time period of GSoC. But the good thing about this project is its incremental nature. We have a set of self-contained measurable steps.</span></div>
<br class="">
<div style="line-height: 1.38; margin-top: 0pt;
margin-bottom: 0pt;" class=""><span style="font-size: 11pt; font-family: arial; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;" class="">Implementation:</span></div>
<div style="line-height: 1.38; margin-top: 0pt;
margin-bottom: 0pt;" class=""><span style="font-size: 11pt; font-family: arial; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;" class="">============</span></div>
<br class="">
<div style="line-height: 1.38; margin-top: 0pt;
margin-bottom: 0pt;" class=""><span style="font-size: 11pt; font-family: arial; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;" class="">I propose to implement such passes on top of PIR. Being currently active in development, I guess it can be a good vehicle to experiment with the idea of having parallel centric optimization pipeline.</span></div>
<br class="">
<div style="line-height: 1.38; margin-top: 0pt;
margin-bottom: 0pt;" class=""><span style="font-size: 11pt; font-family: arial; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;" class="">More about my background and commitments this Summer:</span></div>
<div style="line-height: 1.38; margin-top: 0pt;
margin-bottom: 0pt;" class=""><span style="font-size: 11pt; font-family: arial; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;" class="">===========================================</span></div>
<br class="">
<div style="line-height: 1.38; margin-top: 0pt;
margin-bottom: 0pt;" class=""><span style="font-size: 11pt; font-family: arial; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;" class="">Currently I am a CS master’s students at Saarland University where I work on the practical aspects of the PIR project. Also, over the past year I have been working on the design and implementation of a parallel primitives library called libpp (not public yet) as part of the AnyDSL compiler framework project [8]. The library is implemented in the research language Impala.</span></div>
<br class="">
<div style="line-height: 1.38; margin-top: 0pt;
margin-bottom: 0pt;" class=""><span style="font-size: 11pt; font-family: arial; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;" class="">During the coming Summer, I shouldn’t have any commitments other than mostly PIR and libpp for but only a few hours every week. This proposal integrates well with PIR and hopefully you will find it of general interest for the LLVM project. I would like to emphasize the idea that I am aiming at a parallel-centric optimization pipeline through this proposal and PIR is a nice vehicle to experiment with that.</span></div>
<br class="">
<div style="line-height: 1.38; margin-top: 0pt;
margin-bottom: 0pt;" class=""><span style="font-size: 11pt; font-family: arial; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;" class="">Final notes:</span></div>
<div style="line-height: 1.38; margin-top: 0pt;
margin-bottom: 0pt;" class=""><span style="font-size: 11pt; font-family: arial; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;" class="">=========</span></div>
<br class="">
<div style="line-height: 1.38; margin-top: 0pt;
margin-bottom: 0pt;" class=""><span style="font-size: 11pt; font-family: arial; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;" class="">Johannes Doerfert suggested me the general idea of that project and also provided very useful guidelines for writing the proposal.</span></div>
<br class="">
<div style="line-height: 1.38; margin-top: 0pt;
margin-bottom: 0pt;" class=""><span style="font-size: 11pt; font-family: arial; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;" class="">Thank you for reading this proposal and hopefully you will find it useful.</span></div>
<br class="">
<div style="line-height: 1.38; margin-top: 0pt;
margin-bottom: 0pt;" class=""><span style="font-size: 11pt; font-family: arial; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;" class="">[1] "[llvm-dev] [RFC][PIR] Parallel LLVM IR -- Stage 0 -- IR extension", <a moz-do-not-send="true" href="http://lists.llvm.org/pipermail/llvm-dev/2017-January/109615.html" class="">http://lists.llvm.org/pipermail/llvm-dev/2017-January/109615.html</a></span></div>
<div style="line-height: 1.38; margin-top: 0pt;
margin-bottom: 0pt;" class=""><span style="font-size: 11pt; font-family: arial; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;" class="">[2] <a moz-do-not-send="true" href="https://reviews.llvm.org/D29250" class="">https://reviews.llvm.org/D29250</a></span></div>
<div style="line-height: 1.38; margin-top: 0pt;
margin-bottom: 0pt;" class=""><span style="font-size: 11pt; font-family: arial; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;" class="">[3] <a moz-do-not-send="true" href="https://reviews.llvm.org/D30353" class="">https://reviews.llvm.org/D30353</a></span></div>
<div style="line-height: 1.38; margin-top: 0pt;
margin-bottom: 0pt;" class=""><span style="font-size: 11pt; font-family: arial; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;" class="">[4] <a moz-do-not-send="true" href="https://reviews.llvm.org/D30354" class="">https://reviews.llvm.org/D30354</a></span></div>
<div style="line-height: 1.38; margin-top: 0pt;
margin-bottom: 0pt;" class=""><span style="font-size: 11pt; font-family: arial; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;" class="">[5] "[llvm-dev] [RFC] IR-level Region Annotations", <a moz-do-not-send="true" href="http://lists.llvm.org/pipermail/llvm-dev/2017-January/108906.html" class="">http://lists.llvm.org/pipermail/llvm-dev/2017-January/108906.html</a></span></div>
<div style="line-height: 1.38; margin-top: 0pt;
margin-bottom: 0pt;" class=""><span style="font-size: 11pt; font-family: arial; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;" class="">[6] Chatarasi, Prasanth, Jun Shirako, and Vivek Sarkar. "Polyhedral transformations of explicitly parallel programs." 5th International Workshop on Polyhedral Compilation Techniques (IMPACT), Amsterdam, Netherlands. 2015.</span></div>
<div style="line-height: 1.38; margin-top: 0pt;
margin-bottom: 0pt;" class=""><span style="font-size: 11pt; font-family: arial; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;" class="">[7] Satoh, Shigehisa, Kazuhiro Kusano, and Mitsuhisa Sato. "Compiler optimization techniques for OpenMP programs." Scientific Programming 9.2, 3 (2001): 131-142.</span></div>
<div style="line-height: 1.38; margin-top: 0pt;
margin-bottom: 0pt;" class=""><span style="font-size: 11pt; font-family: arial; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;" class="">[8] <a moz-do-not-send="true" href="https://anydsl.github.io/" class="">https://anydsl.github.io/</a></span></div>
<div class=""><span style="font-size: 11pt; font-family: arial; background-color: transparent; vertical-align: baseline; white-space: pre-wrap;" class="">
</span></div>
</span></div>
_______________________________________________<br
class="">
LLVM Developers mailing list<br class="">
<a moz-do-not-send="true"
href="mailto:llvm-dev@lists.llvm.org" class="">llvm-dev@lists.llvm.org</a><br
class="">
<a class="moz-txt-link-freetext" href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br
class="">
</div>
</blockquote>
</div>
<br class="">
</div>
</blockquote>
<br>
<pre class="moz-signature" cols="72">--
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory</pre>
</body>
</html>