David Kanter (dkanter@realworldtech.com) on 2/19/11 wrote:
---------------------------
>Michael S (already5chosen@yahoo.com) on 2/19/11 wrote:
>---------------------------
>>David Kanter (dkanter@realworldtech.com) on 2/18/11 wrote:
>>---------------------------
>>>
>>>Scatter/gather is necessary for large scale throughput processing (e.g. 16-wide
>>>vectors) and certainly beneficial for what I'd call a "GPU".
>>
>>If something is "necessary" for 16-wide vectors (and, >hopefully, AVX will gain
>>16-bit integer arithmetic support pretty soon and then >will become not only 4-wide
>>and 8-wide but 16-wide too) then it's likely very useful >for 8-wide vectors, don't you think?
>
>It will still be useful, but less so.
>
>>>However, it is largely
>>>anti-antithetical to the design principles of a CPU. If you look at how CPUs are
>>>designed, one of the most critical metrics is the absolute time of the three most common dependent operation pairs:
>>>
>>>1. int-int
>>>2. load-load
>>>3. load-int
>>>4. int-load (if your addressing is not sufficiently robust)
>>>
>>>Everyone who designs CPUs for AMD, IBM, Intel, etc. is very open about the premier
>>>importance of this loop in hardware, yet you are openly dismissive. What other conclusion can I arrive at?
>>>
>>
>>That's correct. Pay attention that load-FP path doesn't >make top 4. In fact, in
>>current-gen Intel and AMD processors load-FP latency is >faster than what's strictly
>>necessary for good performance. Pentium4 had much longer >load-FP latency and that
>>was te smallest of his problems. Supposedly, Bulldozer, >will have, much slower load-FP
>>latency than K10.
>
>BD's FP load latency is similar to the integer load latency.

I don't think so.

>
>>I am sure AMD had done enough of simulations to prove that >it has minimal effect on existing software.
>
>I don't think FP loads are that slow on bulldozer.
>
>>>The problem with scatter/gather is that the hardware is >>large, slow and power hungry.
>>
>>I don't see why it should be large, or slow or power >hungry. SG alignment muxes
>>should be much slower than full crossbar of hobold's >dreams. In fact, on the data
>>path side it should be pretty small incremental >complication on top of already existing
>>hardware for fast unaligned loads/stores.
>
>Unaligned is slow for 256b accesses on SNB and will probably stay that way until
>at least Haswell, maybe the next generation.

The HW required by scatter is much more similar to that of dual unaligned 128b loads, than to unaligned 256b. AFAIK, dual unaligned 128b on SNB is pretty fast.

>
>Moreover, handling unaligned (and store forwarding) is generally mapping 1-->1
>(forwarding) or 2-->1 (unaligned). That's substantially different than supporting 16-->1 realignment.
>

Don't forget - you need single-cycle throughput only for cases where all words hit just 2 cache lines. In other words, (for single precision case) only for strides= 8B, 12B and for just one (cache-line aligned) case of stride=16B. All other strides don't have to be fully pipelined. That's pretty significant simplification for alignment mux.

>Even in the 'fast' unaligned case, you still pay an extra cycle for each different
>cache line. And what happens if you have 16 different TLB misses? Now you've got
>an instruction that will take hundreds or thousands of cycles.

First, 8 misses. Second, that's not a problem at all, see below.
As a first approximation, any case that's not expected to be fast is not a problem.



>
>>On the address side multiplier that in parallel multiplies >an offset by 0 to 7 is certainly pretty small and fast.
>
>>>Putting it in your critical path for a CPU is a bad idea.
>>
>>But SIMD load is not a critical path. And SIMD store even >less so.
>
>It is on a critical path, since the load/store latency influences how many ROB
>entries you need. It doesn't need to be 4 cycles, but it has to be very low.

You are going to support just 1 SG per clock. And in important case of all parts hitting L1D cache (other cases are less important because you are going to wait regardless) you should be able to do scatter in 10-11 cycles - 3-4 times faster than LLC access.
As to impact to normal SIMD/FP load latency from L1D, it would be 1 clock at most, the difference that has no effect on sizing ROBs. But more likely normal case wouldn't be affected at all.

>
>>> So to recap:
>>>
>>>1. I am skeptical that mainstream graphics is likely to be <5% of cycles in the
>>>near future on a SW renderer. Your data is not even remotely convincing.
>>>
>>>2. I am skeptical that the power and area efficiency of throughput and latency
>>>processors will narrow to the point where it only makes sense to have one (over
>>>the next 5 years). It is much more logical to first tightly integrate them (which
>>>has only just started to happen with SNB, and that's not a great representative of throughput processors).
>>>
>>>2a. I also don't believe you understand the quantitative differences between throughput
>>>and latency processors (or the power and area implications thereof).
>>>
>>>2b. We haven't even begun to discuss the outer layers of the memory hierarchy yet on latency vs. throughput.
>>>
>>>3. I am skeptical that scatter/gather can be implemented in a CPU pipeline without causing significant problems.
>>
>>IMHO, SG with moderate throughput goals, i.e. similar to >that of LRB (at most 1
>>scatter or gather operation per clock, at most 1 cache >line per clock read by scatter
>>or written by gather) should not cause significant >problems to SNB-like microarchitecture.
>>Certainly much less than generic permute or 2 FMAs per >clock.
>
>I think FMAs are easier than scatter/gather.

I FMA per clock is easier. 2 FMAs per clock is much harder

>FMAs don't have to deal with all
>the memory ordering and exception handling issues that could arise from 16 independent accesses.

The problems you mentioned above are the easiest of all.
In fact there are no "issues" at all, exactly like there are no issues at all with string instructions.
Like with string instructions you just define scatter/gather instruction in a correct way. I.e. you make them restartable in parts, for example by specifying that arrival of each individual word clears bit in a mask register. Same as decrementing ECX register by partially-executed string instruction. Also you say in the manual that the order of access for individual words is undefined and implementation dependent. Once again - exactly like for string instructions.
BTW, it's 8 independent accesses for current version of AVX, not 16.

>
>Also, look at the latency on LRB in wallclock time versus Sandy Bridge.
>
>There is a cost.
>
>DK

Of course. But there are 1000 more important factors for the difference than the presence of scatter/gather.


Once again, the real challenge is not implementing "linear" scatter-gather, but proving its usefulness outside of 3D rendering.