
<html><head><meta http-equiv="Content-Type" content="text/html charset=us-ascii"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><br class=""><div><blockquote type="cite" class=""><div class="">On Jun 9, 2016, at 9:21 AM, Vikram TV via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" class="">llvm-dev@lists.llvm.org</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div dir="ltr" style="font-family: Helvetica; font-size: 10px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><div class="gmail_extra"><br class="Apple-interchange-newline"><br class=""><div class="gmail_quote">On Wed, Jun 8, 2016 at 10:20 PM, Hal Finkel<span class="Apple-converted-space"> </span><span dir="ltr" class=""><<a href="mailto:hfinkel@anl.gov" target="_blank" class="">hfinkel@anl.gov</a>></span><span class="Apple-converted-space"> </span>wrote:<br class=""><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex;"><div class=""><div style="font-family: arial, helvetica, sans-serif; font-size: 10pt;" class=""><br class=""><hr class=""><blockquote style="border-left-width: 2px; border-left-style: solid; border-left-color: rgb(16, 16, 255); margin-left: 5px; padding-left: 5px; font-weight: normal; font-style: normal; text-decoration: none; font-family: Helvetica, Arial, sans-serif; font-size: 12pt;" class=""><b class="">From:<span class="Apple-converted-space"> </span></b>"Vikram TV via llvm-dev" <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank" class="">llvm-dev@lists.llvm.org</a>><br class=""><b class="">To:<span class="Apple-converted-space"> </span></b>"DEV" <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank" class="">llvm-dev@lists.llvm.org</a>><br class=""><b class="">Sent:<span class="Apple-converted-space"> </span></b>Wednesday, June 8, 2016 2:58:17 AM<br class=""><b class="">Subject:<span class="Apple-converted-space"> </span></b>[llvm-dev] [Proposal][RFC] Cache aware Loop Cost Analysis<span class=""><br class=""><br class=""><div dir="ltr" class="">Hi,<div class=""><br class=""></div><div class="">This is a proposal about implementing an analysis that calculates loop cost based on cache data. The primary motivation for implementing this is to write profitability measures for cache related optimizations like interchange, fusion, fission, pre-fetching and others.</div><div class=""><br class=""></div><div class="">I have implemented a prototypical version at <a href="http://reviews.llvm.org/D21124" target="_blank" class="">http://reviews.llvm.org/D21124</a>.</div></div></span></blockquote>I quick comment on your pass: You'll also want to add the ability to get the loop trip count from profiling information from BFI when available (by dividing the loop header frequency by the loop predecessor-block frequencies).</div></div></blockquote><div class="">Sure. I will add it. <br class=""></div><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex;"><div class=""><div style="font-family: arial, helvetica, sans-serif; font-size: 10pt;" class=""><span class=""><br class=""><blockquote style="border-left-width: 2px; border-left-style: solid; border-left-color: rgb(16, 16, 255); margin-left: 5px; padding-left: 5px; font-weight: normal; font-style: normal; text-decoration: none; font-family: Helvetica, Arial, sans-serif; font-size: 12pt;" class=""><div dir="ltr" class=""><div class=""></div><div class="">The patch basically creates groups of references that would lie in the same cache line. Each group is then analysed with respect to innermost loops considering cache lines. Penalty for the reference is:</div><div class="">a. 1, if the reference is invariant with the innermost loop,</div><div class="">b. TripCount for non-unit stride access,</div><div class="">c. TripCount / CacheLineSize for a unit-stride access.</div><div class="">Loop Cost is then calculated as the sum of the reference penalties times the product of the loop bounds of the outer loops. This loop cost can then be used as a profitability measure for cache reuse related optimizations. This is just a brief description; please refer to [1] for more details.</div></div></blockquote></span>This sounds like the right approach, and is certainly something we need. One question is how the various transformations you name above (loop fusion, interchange, etc.) will use this analysis to evaluate the effect of the transformation they are considering performing. Specifically, they likely need to do this without actually rewriting the IR (speculatively).</div></div></blockquote><div class="">For Interchange: Loop cost can be used to build a required ordering and interchange can try to match the nearest possible ordering. Few internal kernels, matmul are working fine with this approach.</div><div class="">For Fission/Fusion: Loop cost can provide the cost before and after fusion. Loop cost for a fused loop can be obtained by building reference groups by assuming a fused loop. Similar case with fission but with partitions.</div><div class="">These require no prior IR changes.</div></div></div></div></div></blockquote><div><br class=""></div><div>Hi Vikram,</div><div><br class=""></div><div>Is the analysis result specific to a loop nest or to a loop nest together with a set of reference groups?</div><div><br class=""></div><div>Adam</div><br class=""><blockquote type="cite" class=""><div class=""><div dir="ltr" style="font-family: Helvetica; font-size: 10px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><div class="gmail_extra"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex;"><div class=""><div style="font-family: arial, helvetica, sans-serif; font-size: 10pt;" class=""><span class=""><br class=""><blockquote style="border-left-width: 2px; border-left-style: solid; border-left-color: rgb(16, 16, 255); margin-left: 5px; padding-left: 5px; font-weight: normal; font-style: normal; text-decoration: none; font-family: Helvetica, Arial, sans-serif; font-size: 12pt;" class=""><div dir="ltr" class=""><div class=""></div><div class="">A primary drawback in the above patch is the static use of Cache Line Size. I wish to get this data from tblgen/TTI and I am happy to submit patches on it.</div></div></blockquote></span>Yes, this sounds like the right direction. The targets obviously need to provide this information.<span class=""><br class=""><blockquote style="border-left-width: 2px; border-left-style: solid; border-left-color: rgb(16, 16, 255); margin-left: 5px; padding-left: 5px; font-weight: normal; font-style: normal; text-decoration: none; font-family: Helvetica, Arial, sans-serif; font-size: 12pt;" class=""><div dir="ltr" class=""><div class=""></div><div class=""><br class=""></div><div class="">Finally, if the community is interested in the above work, I have the following work-plan:</div><div class="">a. Update loop cost patch to a consistent, commit-able state.</div><div class="">b. Add cache data information to tblgen/TTI.</div><div class="">c. Rewrite Loop Interchange profitability to start using Loop Cost.</div></div></blockquote></span>Great!<br class=""><br class="">This does not affect loop interchange directly, but one thing we need to also consider is the number of prefetching streams supported by the hardware prefetcher on various platforms. This is generally, per thread, some number around 5 to 10. Splitting loops requiring more streams than supported, and preventing fusion from requiring more streams than supported, is also an important cost metric. Of course, so is ILP and other factors.<br class=""></div></div></blockquote><div class="">Cache based cost computation is one of the metric and yes, more of other metrics need to be added.</div><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex;"><div class=""><div style="font-family: arial, helvetica, sans-serif; font-size: 10pt;" class=""><br class=""> -Hal<br class=""><blockquote style="border-left-width: 2px; border-left-style: solid; border-left-color: rgb(16, 16, 255); margin-left: 5px; padding-left: 5px; font-weight: normal; font-style: normal; text-decoration: none; font-family: Helvetica, Arial, sans-serif; font-size: 12pt;" class=""><span class=""><div dir="ltr" class=""><div class=""></div><div class=""><br class=""></div><div class="">Please share your valuable thoughts.</div><div class=""><br class=""></div><div class="">Thank you.</div><div class=""><br class=""></div><div class="">References:</div><div class="">[1] [Carr-McKinley-Tseng] <a href="http://www.cs.utexas.edu/users/mckinley/papers/asplos-1994.pdf" target="_blank" class="">http://www.cs.utexas.edu/users/mckinley/papers/asplos-1994.pdf</a></div><div class=""><br class=""></div><div class="">-- </div><div class=""><div class=""><div dir="ltr" class=""><div class=""><div dir="ltr" class=""><div class=""><br class=""></div><div class="">Good time...</div><div class="">Vikram TV</div><div class="">CompilerTree Technologies</div><div class="">Mysore, Karnataka, INDIA</div></div></div></div></div></div></div><br class=""></span>_______________________________________________<br class="">LLVM Developers mailing list<br class=""><a href="mailto:llvm-dev@lists.llvm.org" target="_blank" class="">llvm-dev@lists.llvm.org</a><br class=""><a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" target="_blank" class="">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><span class=""><font color="#888888" class=""><br class=""></font></span></blockquote><span class=""><font color="#888888" class=""><br class=""><br class=""><br class="">--<span class="Apple-converted-space"> </span><br class=""><div class=""><span name="x" class=""></span>Hal Finkel<br class="">Assistant Computational Scientist<br class="">Leadership Computing Facility<br class="">Argonne National Laboratory<span name="x" class=""></span><br class=""></div></font></span></div></div></blockquote></div><br class=""><br clear="all" class=""><div class=""><br class=""></div>--<span class="Apple-converted-space"> </span><br class=""><div data-smartmail="gmail_signature" class=""><div dir="ltr" class=""><div class=""><div dir="ltr" class=""><div class=""><br class=""></div><div class="">Good time...</div><div class="">Vikram TV</div><div class="">CompilerTree Technologies</div><div class="">Mysore, Karnataka, INDIA</div></div></div></div></div></div></div><span style="font-family: Helvetica; font-size: 10px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;" class="">_______________________________________________</span><br style="font-family: Helvetica; font-size: 10px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><span style="font-family: Helvetica; font-size: 10px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;" class="">LLVM Developers mailing list</span><br style="font-family: Helvetica; font-size: 10px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><a href="mailto:llvm-dev@lists.llvm.org" style="font-family: Helvetica; font-size: 10px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">llvm-dev@lists.llvm.org</a><br style="font-family: Helvetica; font-size: 10px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" style="font-family: Helvetica; font-size: 10px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a></div></blockquote></div><br class=""></body></html>