<div dir="ltr"><div>Hi Jean-Marc,<br></div><div><br></div><div>Thanks a lot for reviewing this huge assembly function!</div><div><br></div><div>silk_warped_autocorrelation_FIX_c()'s kernel part is<br><div> for( n = 0; n < length; n++ ) {</div><div> tmp1_QS = silk_LSHIFT32( (opus_int32)input[ n ], QS );</div><div> /* Loop over allpass sections */</div><div> for( i = 0; i < order; i++ ) {</div><div> /* Output of allpass section */</div><div> tmp2_QS = silk_SMLAWB( state_QS[ i ], state_QS[ i + 1 ] - tmp1_QS, warping_Q16 );</div><div> state_QS[ i ] = tmp1_QS;</div><div> corr_QC[ i ] += silk_RSHIFT64( silk_SMULL( tmp1_QS, state_QS[ 0 ] ), 2 * QS - QC );</div><div> tmp1_QS = tmp2_QS;<br></div><div> }<br></div><div> state_QS[ order ] = tmp1_QS;</div><div> corr_QC[ order ] += silk_RSHIFT64( silk_SMULL( tmp1_QS, state_QS[ 0 ] ), 2 * QS - QC );</div><div> }</div></div><div>in which corr_QC[0, 1, ..., order] is the only output.</div><div><br></div><div>Suppose order = 10, and each stage of the inner loop is noted by s0, s1, ..., s9. And suppose we simultaneously process 8 input in SIMD, from in0 to in7. Let PROC(inx(sy)) denote processing input[x] at stage y.<br></div><div><br></div><div>If there is no dependency between inx(sy) and in(x+1)(sy), then we can do this</div><div><div><br></div><div>FOR in=0 TO N WITH in+=8</div><div> FOR y=0 TO order-1 WITH y++</div><div> PROC(in0(sy) in1(sy) in2(sy) in3(sy) in4(sy) in5(sy) in6(sy) in7(sy))</div><div> END FOR</div></div><div><div><div>END FOR</div><div></div></div></div><div><br></div><div>Definitely there is no any prolog and epilog needed.</div><div><br></div><div>However, the critical thing is that all the states in each stage when processing input[i] are reused by the next input[i+1]. That is input[i+1] must wait input[i] for 1 stage, and input[i+2] must wait input[i+1] for 1 stage, etc.</div><div>Then it becomes this</div><div><br></div><div><div><div><div>FOR in=0 to N WITH in+=8</div><div> PROC(in0(s0)) /* prolog 0 */</div><div> PROC(in0(s1) in1(s0)) /* prolog 1 */</div><div> PROC(in0(s2) in1(s1) in2(s0)) /* prolog 2 */</div><div> PROC(in0(s3) in1(s2) in2(s1) in3(s0)) /* prolog 3 */</div><div> PROC(in0(s4) in1(s3) in2(s2) in3(s1) in4(s0)) /* prolog 4 */</div><div> PROC(in0(s5) in1(s4) in2(s3) in3(s2) in4(s1) in5(s0)) /* prolog 5 */</div><div> PROC(in0(s6) in1(s5) in2(s4) in3(s3) in4(s2) in5(s1) in6(s0)) /* prolog 6 */</div><div> PROC(in0(s7) in1(s6) in2(s5) in3(s4) in4(s3) in5(s2) in6(s1) in7(s0)) /* fully process 8 inputs */</div><div> PROC(in0(s8) in1(s7) in2(s6) in3(s5) in4(s4) in5(s3) in6(s2) in7(s1)) /* continue */</div><div> PROC(in0(s9) in1(s8) in2(s7) in3(s6) in4(s5) in5(s4) in6(s3) in7(s2)) /* continue */</div><div> PROC(in0(s10) in1(s9) in2(s8) in3(s7) in4(s6) in5(s5) in6(s4) in7(s3)) /* continue */</div><div> PROC(in1(s10) in2(s9) in3(s8) in4(s7) in5(s6) in6(s5) in7(s4)) /* epilog 0 */</div><div> PROC(in2(s10) in3(s9) in4(s8) in5(s7) in6(s6) in7(s5)) /* epilog 1 */</div><div> PROC(in3(s10) in4(s9) in5(s8) in6(s7) in7(s6)) /* epilog 2 */</div><div> PROC(in4(s10) in5(s9) in6(s8) in7(s7)) /* epilog 3 */</div><div> PROC(in5(s10) in6(s9) in7(s8)) /* epilog 4 */</div><div> PROC(in6(s10) in7(s9)) /* epilog 5 */</div><div> PROC(in7(s10)) /* epilog 6 */</div><div>END FOR</div></div></div></div><div><br></div><div>And</div><div><div> PROC(in0(s7) in1(s6) in2(s5) in3(s4) in4(s3) in5(s2) in6(s1) in7(s0)) /* fully process 8 inputs */</div><div> PROC(in0(s8) in1(s7) in2(s6) in3(s5) in4(s4) in5(s3) in6(s2) in7(s1)) /* continue */</div><div> PROC(in0(s9) in1(s8) in2(s7) in3(s6) in4(s5) in5(s4) in6(s3) in7(s2)) /* continue */</div></div><div>is actually the expansion of the kernel loop</div><div>FOR i=0 TO order-6 WITH i++</div><div><div> PROC(in0(si+7) in1(si+6) in2(si+5) in3(si+4) in4(si+3) in5(si+2) in6(si+1) in7(si+0))</div></div><div>END FOR</div><div><br></div><div>The worst thing is that corr_QC[] is so sensitive that any extra processing will make them wrong and propagate to the next loop (next 8 inputs). state_QS[] is a little better but still very sensitive. For instance, if adding PROC(in0(s11') in1(s10) in2(s9) in3(s8) in4(s7) in5(s6) in6(s5) in7(s4)) to the kernel loop (by looping one more time) and remove epilog 0, then all final results will be wrong.</div><div><br></div><div>That's why the prolog and epilog cannot be saved to the best of my knowledge.</div><div><br></div><div>The assembly size of silk_warped_autocorrelation_FIX_neon() is about 2,744 bytes. Compared with the C code size (about 452 bytes), it's 2.3 KB larger. Considering silk_warped_autocorrelation_FIX_c() is the second place CPU heavy function in fixed-point, and our testing shows up to 7% CPU run time saving of the total encoder with this optimization (at Complexity 8), maybe we can take the I-cache burden even if finally we still cannot remove the big chunk of prolog and epilog.</div><div><br></div><div>Thanks,</div><div>Linfeng Zhang</div></div><div class="gmail_extra"><br><div class="gmail_quote">On Sat, Feb 4, 2017 at 4:17 PM, Jean-Marc Valin <span dir="ltr"><<a href="mailto:jmvalin@jmvalin.ca" target="_blank">jmvalin@jmvalin.ca</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi Felicia,<br>
<br>
I've had time to work through the math in the original function and I'm<br>
pretty sure it's possible to vectorize this without the huge<br>
prologue/epilogue.<br>
<br>
For the simple case where order = vector size = N (but it should easily<br>
generalize to larger order), what I came up with is:<br>
<br>
initialize X, Y, M, C to vector of zeros<br>
<br>
for i=0 to N+order<br>
T = [x(i), Y(0:N-2)]<br>
Y = M + coeff * (Y - T)<br>
M = T<br>
X = [x(i), X(0:N-1)]<br>
C = C + X*Y<br>
<br>
I think something similar to this (assuming I didn't mess up any<br>
details) should give you the correlations in vector C. Did I miss anything?<br>
<span class="im HOEnZb"><br>
Cheers,<br>
<br>
Jean-Marc<br>
<br>
<br>
On 31/01/17 12:30 PM, Felicia Lim wrote:<br>
</span><div class="HOEnZb"><div class="h5">> Hi,<br>
><br>
> Attached is a patch with arm neon optimizations for<br>
> silk_warped_autocorrelation_<wbr>FIX(). Please review.<br>
><br>
> Thanks,<br>
> Felicia<br>
><br>
><br>
</div></div><div class="HOEnZb"><div class="h5">> ______________________________<wbr>_________________<br>
> opus mailing list<br>
> <a href="mailto:opus@xiph.org">opus@xiph.org</a><br>
> <a href="http://lists.xiph.org/mailman/listinfo/opus" rel="noreferrer" target="_blank">http://lists.xiph.org/mailman/<wbr>listinfo/opus</a><br>
><br>
______________________________<wbr>_________________<br>
opus mailing list<br>
<a href="mailto:opus@xiph.org">opus@xiph.org</a><br>
<a href="http://lists.xiph.org/mailman/listinfo/opus" rel="noreferrer" target="_blank">http://lists.xiph.org/mailman/<wbr>listinfo/opus</a><br>
</div></div></blockquote></div><br></div>