Planned SIMD support

[Cuda-Chen]

Hi developers,
usually SIMD is used for fast data storing/retrieval, and there is no exception for miniSEED.

As a result, is there any planned SIMD support for fast data storing/retrieval?

[chad-earthscope]

Hi @Cuda-Chen.

There are no plans for SIMD support at this time. Suggestions of how that paradigm might be employed by the library are welcome. PR (against develop) are, of course, also welcome.

[Cuda-Chen]

Hi @chad-earthscope ,
For my point-of-view, you may hear about a JSON parsing package called simdjson which can parse gigabytes of JSON in seconds.

As my experience, miniSEED data usually comes with hundreds of megabytes or even gigabytes for a one-day three-channel trace. Therefore, I come up with an idea that using SIMD can reduce the parse time further.

[chad-earthscope]

I think the approach has good potential, and also would take quite some work and add processor-specific functions. Certainly something to consider!

[chad-earthscope]

As a non-rigorous benchmark of libmseed 3 parsing miniSEED 2, I'm getting a record parse rate of about 2.6 GB/second on my laptop for minimal parsing (no decoding, consolidation into traces, printing, etc). This is close to the practical disk read speed of my laptop. Of course more time is needed to do something with those records, such as decompress the samples, combine them into contiguous traces, and/or print summaries.

Adding decompression of the data samples drastically drops the processing rate to 0.23 GB/second.

If I were to target an optimization it would be decompression of Steim 1 and 2 encodings. This may be a good, narrow case for a vectorized approach ala SIMD instructions.

[Cuda-Chen]

Hi @chad-earthscope ,

Got it. I can make a patch about decompressing of Steim 1 and 2 encoding with SIMD instructions and see whether it can boost the processing rate or not.

[Cuda-Chen]

Hi @chad-earthscope ,
Let me make some updates.

In order to find any possibilities for optimization, I use perf to find the hotspots.
However, it seems that we can optimize the read speed of trace (as msio_read uses fopen) using mmap before applying SIMD support on decompressing of Steim 1 and 2 encoding.

What's more, I would like to know how you measure the processing rate.

References

To find any possibilities for optimization, I use perf stat to find the hotspots.
The result of perf stat --repeat 5 ./lm_parse data/Steim1-AllDifferences-BE.mseed -D:

Performance counter stats for './lm_parse data/Steim1-AllDifferences-BE.mseed -D' (5 runs):

              3.11 msec task-clock                #    0.613 CPUs utilized            ( +-  8.72% )
                 1      context-switches          #  372.392 /sec                     ( +- 31.62% )
                 0      cpu-migrations            #    0.000 /sec                   
                70      page-faults               #   26.067 K/sec                    ( +-  0.73% )
         8,392,814      cycles                    #    3.125 GHz                      ( +- 10.28% )
         6,191,791      stalled-cycles-frontend   #   87.32% frontend cycles idle     ( +- 13.23% )
         4,384,861      instructions              #    0.62  insn per cycle         
                                                  #    1.14  stalled cycles per insn  ( +-  1.60% )
           878,394      branches                  #  327.107 M/sec                    ( +-  1.64% )
            27,931      branch-misses             #    3.30% of all branches          ( +-  3.67% )

           0.00507 +- 0.00138 seconds time elapsed  ( +- 27.13% )

In here, the stalled-cycles-frontend, instructions, and cycles may be the targets of optimization.
Therefore, I use perf record -e stalled-cycles-frontend:u,instructions:u,cycles:u ./lm_parse data/Steim1-AllDifferences-BE.mseed -D then use perf report.
The results of perf report:

# stalled-cycles-frontend
Samples: 10  of event 'stalled-cycles-frontend:u', Event count (approx.): 9747184                                                                                     
Overhead  Command   Shared Object     Symbol                                                                                                                          
  32.59%  lm_parse  [unknown]         [k] 0xffffffffaac00020                                                                                                          
  26.67%  lm_parse  [unknown]         [k] 0xffffffffaa446684                                                                                                          
  24.01%  lm_parse  [unknown]         [k] 0xffffffffaa156487                                                                                                          
  15.92%  lm_parse  [unknown]         [k] 0xffffffffaa0fa7a0                                                                                                          
   0.79%  perf-exe  [unknown]         [k] 0xffffffffaa099080                                                                                                          
   0.04%  perf-exe  [unknown]         [k] 0xffffffffa9e96106

# instructions
Samples: 10  of event 'instructions:u', Event count (approx.): 1392512                                                                                                
Overhead  Command   Shared Object         Symbol                                                                                                                      
  47.48%  lm_parse  ld-linux-x86-64.so.2  [.] do_lookup_x                                                                                                             
  42.80%  lm_parse  libc.so.6             [.] _IO_default_xsputn                                                                                                      
   9.27%  lm_parse  ld-linux-x86-64.so.2  [.] __GI___tunables_init                                                                                                    
   0.45%  lm_parse  ld-linux-x86-64.so.2  [.] _dl_start                                                                                                               
   0.00%  lm_parse  ld-linux-x86-64.so.2  [.] _start

# cycles
Samples: 15  of event 'cycles:u', Event count (approx.): 2351555                                                                                                      
Overhead  Command   Shared Object         Symbol                                                                                                                      
  33.74%  lm_parse  libc.so.6             [.] __vfprintf_internal                                                                                                     
  13.68%  lm_parse  lm_parse              [.] rlog_int                                                                                                                
  13.02%  lm_parse  libc.so.6             [.] strcmp                                                                                                                  
  10.17%  lm_parse  libc.so.6             [.] __strchrnul_sse2                                                                                                        
   9.72%  lm_parse  libc.so.6             [.] _IO_file_write@@GLIBC_2.2.5                                                                                             
   9.47%  lm_parse  lm_parse              [.] print_message_int                                                                                                       
   7.44%  lm_parse  ld-linux-x86-64.so.2  [.] get_common_cache_info.constprop.0                                                                                       
   2.57%  lm_parse  ld-linux-x86-64.so.2  [.] _dl_start                                                                                                               
   0.19%  lm_parse  [unknown]             [k] 0xffffffffaac00b40                                                                                                      
   0.01%  lm_parse  ld-linux-x86-64.so.2  [.] _start

[chad-earthscope]

Hi @Cuda-Chen ,

As a single record, a test of reading Steim1-AllDifferences-BE.mseed is way too small to be useful for any profiling. Note that strcmp is accounting for 13% of the cycles, and that is for a single call per run! Also, note that most of the cycles are spent in routines generating logging output/printing, which is not really useful for inspecting high performance data use cases.

As for using memory mapping to read files, keep in mind that a) libmseed already performs buffered reads, reading up to MAXRECLEN (131172 bytes currently) per system call, b) the "msio" routines are a file reading abstraction that allows reading from files and URLs (via libcurl), memory mapping can only be applied to files.

Here is a largish data set, 1x 40sps channel for a single year:
http://ds.iris.edu/files/staff/chad/TA_MSTX__B_H_Z.2010.mseed

This is good for testing the fundamentals of throughput, parsing, decoding, etc., as opposed to the "many channels" use cases.

For this kind of testing, I suggest using the -tg option of lm_parse, which will avoid generating a lot of printed logs and the cycles needed to generate console output, while also organizing the data into contiguous traces, a very common use case. You can add the -d or -D options to trigger decoding of the data (even though it will not be printed).

Below are your testing results, adding branches, with indicated data and my suggested options to avoid printing work:

perf record -e stalled-cycles-frontend:u,instructions:u,cycles:u,branches:u ./lm_parse TA_MSTX__B_H_Z.2010.mseed -tg -d

then

perf report

results:

#stalled-cycles-frontend:u
  16.93%  lm_parse  lm_parse              [.] msr_decode_steim2
   7.70%  lm_parse  [unknown]             [k] 0xffffffff93a00b40
   7.13%  lm_parse  libc.so.6             [.] __memmove_sse2_unaligned_erms
   5.73%  lm_parse  [unknown]             [k] 0xffffffff932a5407
   4.33%  lm_parse  [unknown]             [k] 0xffffffff939a7f92
   3.21%  lm_parse  [unknown]             [k] 0xffffffff932a5a7e
   2.10%  lm_parse  [unknown]             [k] 0xffffffff93a014b9
   2.10%  lm_parse  [unknown]             [k] 0xffffffff93a01149
   1.14%  lm_parse  [unknown]             [k] 0xffffffff939a7f00
   0.96%  lm_parse  libc.so.6             [.] __vfprintf_internal
   0.91%  lm_parse  lm_parse              [.] msr3_unpack_mseed2
   0.87%  lm_parse  libc.so.6             [.] _int_malloc
   0.87%  lm_parse  [unknown]             [k] 0xffffffff92f0b56a
   0.80%  lm_parse  lm_parse              [.] ms_gswap4
   0.61%  lm_parse  libc.so.6             [.] __GI___printf_fp_l
   0.56%  lm_parse  lm_parse              [.] json_serialize_to_buffer_r
   0.56%  lm_parse  [unknown]             [k] 0xffffffff93a00020
   0.52%  lm_parse  [unknown]             [k] 0xffffffff939a79e0
   0.51%  lm_parse  [unknown]             [k] 0xffffffff93a0018b
...

# instructions:u
  87.34%  lm_parse  lm_parse              [.] msr_decode_steim2
   1.97%  lm_parse  lm_parse              [.] ms_gswap4
   1.35%  lm_parse  libc.so.6             [.] __GI___printf_fp_l
   0.96%  lm_parse  libc.so.6             [.] __vfprintf_internal
   0.61%  lm_parse  libc.so.6             [.] hack_digit
   0.56%  lm_parse  lm_parse              [.] json_serialize_to_buffer_r
   0.50%  lm_parse  lm_parse              [.] json_serialize_string
   0.49%  lm_parse  libc.so.6             [.] _int_free
   0.48%  lm_parse  libc.so.6             [.] malloc
...

# cycles:u
  71.81%  lm_parse  lm_parse              [.] msr_decode_steim2
   5.23%  lm_parse  [unknown]             [k] 0xffffffff93a00b40
   5.06%  lm_parse  libc.so.6             [.] __memmove_sse2_unaligned_erms
   1.67%  lm_parse  lm_parse              [.] ms_gswap4
   1.38%  lm_parse  libc.so.6             [.] __GI___printf_fp_l
   1.21%  lm_parse  libc.so.6             [.] __vfprintf_internal
   0.95%  lm_parse  lm_parse              [.] json_serialize_to_buffer_r
   0.87%  lm_parse  lm_parse              [.] msr3_unpack_mseed2
   0.81%  lm_parse  libc.so.6             [.] _int_malloc
   0.68%  lm_parse  libc.so.6             [.] _int_free
   0.67%  lm_parse  libc.so.6             [.] hack_digit
   0.65%  lm_parse  libc.so.6             [.] malloc
   0.57%  lm_parse  lm_parse              [.] json_serialize_string

# branches:u
  85.36%  lm_parse  lm_parse              [.] msr_decode_steim2
   1.50%  lm_parse  libc.so.6             [.] __GI___printf_fp_l
   1.39%  lm_parse  lm_parse              [.] ms_gswap4
   1.04%  lm_parse  libc.so.6             [.] __vfprintf_internal
   0.93%  lm_parse  libc.so.6             [.] hack_digit
   0.90%  lm_parse  lm_parse              [.] json_serialize_to_buffer_r
   0.70%  lm_parse  lm_parse              [.] json_serialize_string
   0.57%  lm_parse  libc.so.6             [.] _int_free
   0.56%  lm_parse  lm_parse              [.] msr3_unpack_mseed2
   0.53%  lm_parse  libc.so.6             [.] malloc
   0.52%  lm_parse  libc.so.6             [.] cfree@GLIBC_2.2.5

We have a clear target in msr_decode_steim2()! That routine can very likely be optimized even without using SIMD instructions.

Note: If you are going to generate a PR, please do so against the develop branch. There are number of additions on that branch that will soon be rolled into another pre-release.

[Cuda-Chen]

Hi @chad-earthscope ,
Thanks for providing the measurements and some tips about generating a PR!
I will take some look in msr_decode_steim2().

[chad-earthscope]

After the work in #90 and #102 here are some thoughts on application of SIMD vectorization to the steim decoders.

The work that could potentially be vectorized is the unpacking of difference values from encoded words, and possibly the sign-extension of these differences.

Note, as these are delta-based encodings, the differences cannot be applied in parallel/vector as each one requires the output of the prior calculation.

While I would prefer to the leave the vectorization to the compiler for portability and simplicity, I did find SIMD Everywhere as an option should the need for coded-SIMD be worth it.

[Cuda-Chen]

Hi @chad-earthscope ,

For the delta-based encodings, I think maybe we can prepare several masks for extracting the differences (thus vectorization can come into use). Taking the following code block as example:

// Steim-2 decoding
// the masks are shown in binary format
uint32_t mask_7x4 = 1110LLLLMMMMNNNNOOOOPPPPQQQQRRRR; // nibble=11, dnib=10: Seven 4-bit differences
uint32_t mask_5x6 = 1100GGGGGGHHHHHHIIIIIIJJJJJJKKKKKK; // nibble=11, dnib=00: Five 6-bit differences
uint32_t mask_3x10 = 1011XXXXXXXXXXYYYYYYYYYYZZZZZZZZZZ; // nibble=10, dnib=11: Three 10-bit differences

For coded-SIMD part, though I am a collaborator of sse2neon, I will vote on simde as the seismology community uses PowerPC.

[chad-earthscope]

In d4da78c I simplified the bit extraction loops and was disappointed that my development compiler (clang v14) did not automatically vectorize the loops. Instead the compiler choose to unroll them. After investigating, I forced vectorization of the loops with the pragmas:

#pragma clang loop vectorize(enable)
#pragma clang loop unroll(disable)

and confirmed that they had been vectorized and the result was slower. I was very hopeful to take the approach of arranging the code to let the compiler vectorize for the target system when possible, as this keeps the code most portable.

It's possible that masks for the packed bit ranges, combined with bit shuffling SIMD instructions like PSHUFB (and friends), would do better. But the experience so far does not leave me optimistic. Also, incorporation of such instructions quickly becomes specialized for architectures, but perhaps simde can help.

P.S. @Cuda-Chen, not sure what you meant by:

... as the seismology community uses PowerPC.

The seismology does not use the PowerPC architecture in any significant way that I'm aware of. If I had to guess, the vast majority of usage is commodity x86-64 hardware.

[Cuda-Chen]

Hi @chad-earthscope ,

... as the seismology community uses PowerPC.

not sure what you meant by:

When I was working in seismology-related company, there was a workstation with PowerPC architecture, and this is the reason that I thought we may need to support PowerPC if we had a chance to add SIMD support.