<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Sep 27, 2017 at 8:01 AM, Robert Granger <span dir="ltr"><<a href="mailto:robbieg.ranger@gmail.com" target="_blank">robbieg.ranger@gmail.com</a>></span> wrote:<br><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">Hi Kyle,<div><br></div><div>Thanks for cc'ing me into this conversation. I'm glad you have been looking at the potential for vectorisation, since this is an aspect that has not been studied in detail yet for these primes, as far as I know.</div></div></blockquote><div><br></div><div>I should explain what I did in a little detail then.</div><div>I flipped the order of summation for the odd terms. Instead of z_1 = (x_9 - x_11)(y_11 - y_9) ... (x_1 - x_0)(y_0 - y_1)</div><div>This gives you a 2x vectorization of scalar vs vector z_0, z_1 = (x_1 - (x_18,x_0))((y_18,y_0) - y_1) . . .</div><div>To get wider vectorization, you can work across the square diagonally.</div><div>16, 17 = (7,8)*9,</div><div>16,17,18 += (6,7,8)*10</div><div>16,17,18 += (5,6,7)*11</div><div>Because shuffling/permutation is relatively expensive, you can re-use the shuffled vectors with new broadcasts:</div><div>12,13 = (5,6)*7</div><div>16,17,18 += (4,5,6)*12<br></div><div>12,13,14,15 += (4,5,6,7)*8</div><div>I realize now that I write this, that I could have flipped the even terms instead, and then worked from the top down. It would probably be easier to follow.</div><div><br></div><div>To get the shuffled vectors, you can either do an overlapping load/insert and then shuffle. You can use those vectors 3 times before needing to reload.</div><div>Intel multiplies the even slots in a widening multiply, so you can put the values you'll need later in the odd slots</div><div><br></div><div>for instance to get the 3 vectors (6,7,8,9), (5,6,7,8), (4,5,6,7), you construct the 8x32 vector</div><div>6 4 7 5 | 8 6 9 7.</div><div>The overlap is because moving values across lanes has higher latency.</div><div><br></div><div>You can also do a simple load and permute:</div><div>6 2 7 3 | 8 4 9 5</div><div><br></div><div>It's a tradeoff. For squaring, the overlapping load technique is faster. For multiplication, because there are 2 permutes to hide some of the latency (3 cycles) and because</div><div>of the increased register pressure to perform the overlapped load vs a straight load, the permute is faster.</div><div> <br></div><div>To facilitate the overlapping loads, you allocate extra room for the coefficients and then copy the low coefficients into the high area before starting.</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>I just thought I should point out that the advantages you note for t near a power of 2, such as t = 2^26 - 2, were already detailed in the original paper of Chung and Hasan, "More Generalized Mersenne Numbers", Section 5.1 (reference [13] in my paper with Moss). It is only when t is not of such a nice form that one should use the Montgomery representation. However, the multiplication we introduced should be used in this case.</div></div></blockquote><div><br></div><div>Thanks for the pointer. I had read some of their papers, but had missed that point.</div><div>C doesn't have to be that small, a small safety margin (I'd have to do the math, but a few bits) less than sqrt(t) should suffice, because you have to reduce twice anyway, and the first reduction is overkill.</div><div>For multiprecision, you want c to be smaller so that the 2nd reduction is as few words as possible.</div><div>If you use signed coefficients, c can be positive as well, which isn't in the Chung Hasan paper.</div><div><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><br></div><div>All the best,</div><div> - Rob Granger</div></div><div class="gmail-HOEnZb"><div class="gmail-h5"><div class="gmail_extra"><br></div></div></div></blockquote><div><br></div><div>Thanks.</div><div><br></div><div>It means a lot to know I'm not wildly off the mark.</div><div>Kyle</div></div></div></div>