Turn on suggestions

Auto-suggest helps you quickly narrow down your search results by suggesting possible matches as you type.

Showing results for

- Intel Community
- Software
- Software Development Technologies
- Intel® ISA Extensions
- Optimizing XOR and Popcount using AVX2

- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Mute
- Printer Friendly Page

sardar__kashif

Beginner

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

03-27-2019
03:34 AM

402 Views

Optimizing XOR and Popcount using AVX2

**We have to perform bit wise XOR operation on two arrays each containing 5 elements of uint64_t (unsigned long long) and then perform counting (pop count) of 1's.**

**What is the optimized way by using AVX2 256 bit wide YMM registers, AVX2 VPXOR and popcount to achieve this in minimum clock cycles. **

**Right now we are doing this by following code snippet**

for (j = 0; j < 5; j++){ xorResult = cylinderArrayVectorA^ cylinderArrayVectorB ; noOfOnes = _mm_popcnt_u64(xorResult); sumOfOnes += noOfOnes; }

Link Copied

3 Replies

McCalpinJohn

Black Belt

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

03-28-2019
10:06 AM

402 Views

Are you looking to minimize latency to compute this for a single pair of 5-element vectors, or to maximize throughput for performing this operation on independent pairs of 5-element vectors?

The minimum latency code may be the scalar code above. The two loads can be issued in one cycle, with one of the loads as a memory argument to the XOR (which is is effectively free, since 4 ports are available to execute XOR with single-cycle latency), the popcount instruction has 3 cycle latency and can only be executed on one functional unit, and the add is effectively free (4 ports are available to execute ADD with single-cycle latency). Minimum latency will be L1 data cache load latency (typically 4 cycles) plus about 16 cycles on the critical path. There are only about 20 instructions in the fully unrolled loop (load, xor, popcnt, add), so the out-of-order engine will have lots of room to issue & execute the surrounding code concurrently with this loop.

AVX2 *might* help if you need to perform this operation on lots of independent pairs of 5-element vectors, but it might not help. There is no vector population count instruction, so you would need to emulate this using bit tricks. Examples are https://graphics.stanford.edu/~seander/bithacks.html and https://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a-32-bit-integer. ...; It is important to note that instructions operating on 256-bit AVX2 registers that enable data to cross between the upper and lower 128-bit "lanes" have 3-cycle latency, while instructions that only allow "horizontal" data motion within 128-bit "lanes" have single-cycle latency. If I had to guess, I suspect that the best implementation would use two 128-bit registers for four of the elements and a GPR for the 5th element, but I have never analyzed a vectorized SW implementation of popcount....

McCalpinJohn

Black Belt

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

03-28-2019
10:36 AM

402 Views

jimdempseyatthecove

Black Belt

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

03-30-2019
05:17 AM

402 Views

It would help greatly to see a wider picture of what is going on.

You should be made aware that getting the inner most loop to run as efficiently as possible, can be counter productive to the performance of its use in the outer scopes.

The above comment is in reference to John's comment to

Single pair of 320-bit (5x64), or

multiple pairs of 320-bit vectors.

Add to this mix, a single 320-bit with multiple 320-bit vectors.

When the mix is large enough, it may be more effective to turn your horizontal 5-wide uint64_t bit vectors into 5 separate 1-wide 64-bit lanes of the 320-bit logical vector, then work on 4 separate 320-bit vector pairs, with each different partial 320-bit vector spread across the 4 uint64_t lanes. (even I cannot make sense of the above).

A problem with the above is you have scalar addition of the sums. If you have many such pairs of 320-bit vectors. IOW the loop you provided above (presumably operating on uint64_t type variables) could be re-used to operate on 4 such pairs concurrently across the width of the AVX/AVX2 SIMD registers.

Jim Dempsey

Topic Options

- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Printer Friendly Page

For more complete information about compiler optimizations, see our Optimization Notice.