Optimizing indirect memory read and write access on MIC

piyush_s_ — Fri, 02 May 2014 16:20:01 GMT

Extended addition (described below ) is one of the most performance critical kernel in our code (that implements important functions from sparse linear algebra).

AddEx(double* A, int LDA, double *B, int LDB, int*C, ...)
{
    for (jj = 0; jj < col; ++jj)
    {
        /*if jj segment is not empty */
        if (seg[jj]) 
        {

            for (i = 0; i < row; ++i)
            {

                A[C] -= B;

            }
            B += LDB;
        }
        A += LDA;
    } 

}

Compared, to something like SpMV ( which reads from indirect addresses), this both reads and write to indirect memory addresses

In general, we perform a number of extended additions operations on independent blocks A_{i} and B_{i} concurrently using openMP parallel for.

Assuming A[C] -= B takes 2 reads and 1 write ( C is assumed to be in cache ) , so in total 3*row*col memory ops, measuring time shows low bandwidth of around 52 GB/sec obtained. While there can be load imbalance among openMP threads, but still 52 GB/sec is quite low. I seek suggestions to improve it. My experience with SIMD instructions is limited, however, I tried as follows.

I took the inner loop

for (i = 0; i < row; ++i)
{

    A[C] -= B;

}

and replaced it with following SIMDized loop

            __m512i v_rel;
            __m512d v_A;
            __m512d v_B;
            __mmask8 mask;

            int row_8 = row/8*8;
            for (i = 0; i < row_8; i += 8)
            {
                v_rel = _mm512_extloadunpacklo_epi32 (v_rel, &C,
                                                      _MM_UPCONV_EPI32_NONE, _MM_HINT_NT);
                v_rel = _mm512_extloadunpackhi_epi32 (v_rel, &C[i + 16],
                                                      _MM_UPCONV_EPI32_NONE, _MM_HINT_NT);
                v_B = _mm512_extloadunpacklo_pd (v_B, &B,
                                                     _MM_UPCONV_PD_NONE, _MM_HINT_NT);
                v_B = _mm512_extloadunpackhi_pd (v_B, &B[i + 8],
                                                     _MM_UPCONV_PD_NONE, _MM_HINT_NT);
                v_A = _mm512_i32logather_pd (v_rel, A, _MM_SCALE_8);
                v_A = _mm512_sub_pd (v_A, v_B);
                _mm512_i32loscatter_pd (A, v_rel, v_A, _MM_SCALE_8);
            }
            
            /*handling remainders*/
            ....

The performance improves using SIMD and now it is around 60 GB/sec. There seems to be plently of room for improvement.

Upper bound on sizes of row and col is ~128 (defined by user ) (while LDA and LDB can be large, only a continues portion of length upto 128 of B maps to upto 128 contgeous portion of A). The source vector B has fewer rows than A. In general C is not monotonous (i.e. C>=C if i>j does not hold) .

If the prefetch instructions

TimP — Fri, 02 May 2014 16:50:00 GMT

If the prefetch instructions which presumably were generated in your C code loop weren't helping performance, does it mean that you aren't incurring cache misses, or that they weren't generated effectively? Your hint indicates that maybe the loop isn't big enough for prefetch within the loop to help (even if you follow the advice about indirect prefetch) https://www.google.com/url?q=https://software.intel.com/sites/default/files/article/326703/5.3-prefetching-on-mic-5.pdf&sa=U&ei=Rc1jU_-iE8-lyATAnIKoAQ&ved=0CCAQFjAB&sig2=ekDzB0nMI-kVyOncQjCy-w&usg=AFQjCNFTgB-iU0HO-1AS1RpGcB0UEUeS4Q , and some tinkering with initial prefetch may be needed. I don't know whether loop count directives should influence the C compiler. If it's worth the effort, you might try prefetching individually all the operands for a short loop before entering the loop. I assume the gather and scatter intrinsics involve looping over the individual cache lines. So the peak performance depends on how many separate cache lines are required for each iteration of the programmed loop. VTune KNC general analysis should help to show whether the performance limitation occurs at some level of cache and whether most of the time is spent in the gather and scatter.

topic Optimizing indirect memory read and write access on MIC in Software Archive

Optimizing indirect memory read and write access on MIC

If the prefetch instructions