<div dir="ltr"><div dir="ltr"><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Wed, May 27, 2020 at 7:37 PM Matthew Knepley <<a href="mailto:knepley@gmail.com">knepley@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr">On Wed, May 27, 2020 at 7:34 PM Jed Brown <<a href="mailto:jed@jedbrown.org" target="_blank">jed@jedbrown.org</a>> wrote:<br></div><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Mark Adams <<a href="mailto:mfadams@lbl.gov" target="_blank">mfadams@lbl.gov</a>> writes:<br>
<br>
> Nvidias's NSight with 2D Q3 and bs=10. (attached).<br>
<br>
Thanks; this is basically the same as a CPU -- the cost is searching the<br>
sorted rows for the next entry.  I've long thought we should optimize<br>
the implementations to fast-path when the next column index in the<br>
sparse matrix equals the next index in the provided block.  It'd just<br>
take a good CPU test to demonstrate that payoff.<br>
</blockquote></div><br clear="all"><div>So you first check whether the next index is the one in the set passed in, and otherwise</div><div>fall back on the search? Good idea.</div></div></blockquote><div><br></div><div><br></div><div>The existing code seems to have <b><font color="#ff0000">a line (low=i+1) </font></b>that seems to be trying to exploit consecutive indices but it is not quite right, I don't think, </div><div><br></div><div>This is the existing code fragment (this code has been cloned many times and there are several instances of this kernel).</div><div><br></div><div>I've <b><font color="#9900ff">added code</font></b> that I think might make this do the right thing.</div><div><br></div><div>     if (col <= lastcol) low = 0;<br>      else high = nrow;<br>      lastcol = col;<br>      while (high-low > 5) {<br>        t = (low+high)/2;</div><div><font color="#9900ff"><b>if (rp[low] == col) high = low+1;<br>else </b> </font>      if (rp[t] > col) high = t;<br>        else low = t;<br>      }<br>      for (i=low; i<high; i++) {<br>        if (rp[i] > col) break; <b>// delete this check if you don't add new columns</b><br>        if (rp[i] == col) {<br>   ap[i] += value;<br><b><font color="#ff0000">       low = i + 1;<br></font></b>          goto noinsert;<br>        }<br>      }<br></div><div><br></div><div>I'll  experiment with this. </div><div><br></div><div>Thanks,</div><div>Mark</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div><br></div><div>   Matt</div><div><br></div>-- <br><div dir="ltr"><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div>What most experimenters take for granted before they begin their experiments is infinitely more interesting than any results to which their experiments lead.<br>-- Norbert Wiener</div><div><br></div><div><a href="http://www.cse.buffalo.edu/~knepley/" target="_blank">https://www.cse.buffalo.edu/~knepley/</a><br></div></div></div></div></div></div></div></div>
</blockquote></div></div>