Michael S (already5chosen@yahoo.com) on 1/5/11 wrote:
---------------------------
>Nicolas Capens (nicolas.capens@gmail.com) on 1/4/11 wrote:
>---------------------------
>>
>>Also note that the first implementation doesn't have to be entirely optimal. Currently
>>it's horrendously slow to serially extract offsets from one vector and load and
>>insert elements into another vector. So any small improvement would be very welcome
>>and can be gradually improved from one generation to the next when gather/scatter is used more frequently.
>>
>
>I suppose, due to VBROADCASTSS+BLENDPS software-based gather is now just slow rather than horrendously slow.
>But in many situations dedicated hardware will be of little help.
>Supposedly, for strides known at compiled time and with data not in L2 cache, LRB-style
>vector gather will provide no measurable performance benefit. Even for L2-resident
>data I'd expect only single-digit improvements over software-based gather.
>

The real issue is parallelizing arbitrary loops. Take for instance the use of a lookup table to compute transcendental functions. There are no fixed strides here; each element could have a different lookup index. But this data is expected to reside in L1 cache most of the time. So a gather operation would be way faster than serially accessing each element.

The situation will become even more critical with FMA support. A core can then perform 32 SP operations per cycle, but having to serially load elements means Amdahl's Law will cause the highly parallel FMA operation to be of no significance. This same law shows that even the smallest bit of improvement to the serial part of the task results in a significant speedup.

Note also that it's a chicken-and-egg problem. Currently developers often need to use many shuffle instrutions to get the data into an SIMD-friendly layout. This may give the impression that they don't really need gather/scatter support, while in fact their algorithms could be reorganized significantly to eliminate a lot of data shuffles. But developers first need these instructions before they can achieve any efficiency improvement. Heck, some developers haven't even bothered with SSE yet because the insert/extract bottleneck makes it not worth the effort of parallelizing. With gather/scatter support, in time a lot more applications can benefit from SIMD. That's why I'm pleading to initially implement them with minimal extra logic, which fixes the chicken-and-egg problem for both ends (i.e. it saves the CPU manufacturers from investing a lot of transistors in functionality that won't be used intensively for a couple of years).

AVX is also already prepared to be extended to 512-bit and 1024-bit. At these widths gather/scatter support is indispensible, so since these instructions will be needed anyhow, I believe it's best to add them as early as possible so developers can start taking benefit of them. The same software can then run faster on future architectures with better gather/scatter implementations, without waiting yet another few years for the new extensions to be picked up and the software to reach consumers.

>Of course, when the strides are known only in run-time or for very short strides
>or for L1-resident data the dedicated hardware could give more significant improvements.
>

This is the typical use case. But even when there are some L1 cache misses, a lot of data accesses can be in flight simultaneously. Every time some vector elements are located on the same cache line, it saves cycles and load/store slots. And in some cases these odds can be further improved by using 'tiling' techniques.