Comment Feed for Regarding the simdization/vectorization of table look-up operations (TechOff on Channel 9)

Re: Re: Re: Regarding the simdization/vectorization of table look-up operations

evildictaitor — Fri, 10 Oct 2008 16:46:51 GMT

It's clearly not possible because of what I said in my previous post - while loading contiguous memory is possible due to the way intel processors agressively cache both page and bank requests, there is no way to stream memory from discontiguous parts of memory - so there is no way to stream two different 64bit addresses to registers under any intel processor, as a consequence of the way memory loads work in the processor.

Because these are nonprogrammable there's no way to tell the processor to preemptively load pages to the processor, or to ignore cache requests (believe me, I've tried), so no there is no way to stream 64bit addresses to registers.

As I said in my previous post, if you're performing a functional mapping over contiguous memory, then a GPU is your best bet, and CUDA is the best programming language to do it in. If you're performing a generalized lookup over non-contiguous data, then a programmable FPGA is the fastest method.

So basically the answer is no, unless you're willing to go rather outside of an what I would be expecting from an undergrad. The question then remains as to _why_ you would be wanting to do such a thing - given that any speed issues are usually due to

1. Bad Algorithm

2. Lots of overhead (perhaps due to an overuse of library or OS functions)

3. Bank or cache misses (as detailed earlier)

4. Limitation ultimately at the memory bus speed

So now I've repeated what I said before but in a wordier way. The answer is probably no, but it's qualified because there are cases where it isn't no. Happy now?

Dexter said:
What you want to be "vectorized" are 4 memory reads at different addresses

Are there any examples where you would want to vectorize 4 memory reads at the same address?

mov xmm1, [xmm0]

mov xmm2, xmm1

mov xmm3, xmm1

mov xmm4, xmm1

and the vectorized (using the fact that we get a cache and bank bonus) for contiguous addresses

mov xmm1, [xmm0]

mov xmm2, [xmm0 + 64]

mov xmm3, [xmm0 + 128]

mov xmm4, [xmm0 + 192]

has one bank miss if xmm0 is aligned on a 128 byte boundary

and for non continguous addresses

mov xmm1, [xmm0]

mov xmm2, [xmm0 + 64]

mov xmm3, [xmm0 + 128]

mov xmm4, [xmm0 + 192]

mov xmm1, [xmm1]

mov xmm2, [xmm2]

mov xmm3, [xmm3]

mov xmm4, [xmm4]

has 7-9 bank misses (4 from the direct accesses, one from the leas and 2-4 from the page table directories during the page table misses) and four cache fails, and is a whole lot slower (loading in four addresses stored as size_t* on xmm0)

Re: Re: Regarding the simdization/vectorization of table look-up operations

Dexter — Fri, 10 Oct 2008 11:42:07 GMT

What YOU are talking about? :)

Maybe his original post wasn't clear enough but in the second post he clearly mentioned different addresses. Basically he asks about an instruction like

mov xmm0, [xmm1]

which could load 2 values in xmm0 from 2 different addresses stored in xmm1. That means doing two 64 bit loads from 2 different addresses. As far as I know current Intel chips can do one 128 bit load from a single address.

Re: Regarding the simdization/vectorization of table look-up operations

evildictaitor — Thu, 09 Oct 2008 18:59:24 GMT

What are you talking about? Intel chipsets come with an onboard (nonprogrammable) hardware page and bank cache, which means so long as you're accessing contiguous memory you ARE vectorising memory reads, whether you like it or not.

Moreover, where were you going to vectorize these memory reads to? If you're applying a functional map over an array then to get high levels of parallelism you should look at using a GPU to take the body of work (see CUDA), or if you're looking at a generalized lookup table, there are programmable FPGAs, but if your program is really running slowly, it's probably due to (in order):

1. Bad algorithm.

2. Lots of overhead - overuse of standard libraries?

3. Bank or cache misses

4. Memory bus line speed.

Re: Re: Regarding the simdization/vectorization of table look-up operations

Shining Arcanine — Thu, 09 Oct 2008 14:06:58 GMT

Dexter, I am dealing with 64bit numbers, this will only involve 2 memory reads at different addresses until 2010 when Intel comes out with 256bit ymm registers.

Anyway, I was thinking about this yesterday after I made my post. If such an instruction existed, I assume it would fall back to a serial retrieval if the information is not stored in cache, while it could do a parallel retrieval if the information is in cache. In my case, the lookup table is small, as it has 64 entries that only require 6 bits of storage each, although I am storing them so they use 64bits each. It should be possible to store them in 64 bytes, which should easily fit on a cache line.

Also, another possibility would be to decrease the bus width by a factor of 4 and increase the clock speed by a factor of 4, which would allow the CPU to retrieve 32-bit blocks of data from up to 4 different memory locations (perfect for SIMD) in the same time it would have retrieved one 128-bit block of data, while it would still be able to retrieve one 128-bit block of data in the same time that it would have with the current 128-bit bus and clock rate. Of course, this is the Rambus approach to doing things, so it is unlikely it would ever be adopted in conventional computers.

Re: Regarding the simdization/vectorization of table look-up operations

Dexter — Thu, 09 Oct 2008 11:19:30 GMT

I'm not an expert in SIMD but I'll try to guess:

- What you call table look-up is basically indexed memory access
- What you want to be "vectorized" are 4 memory reads at different addresses

To vectorize some arithmetic or logical operation is easy, you put N ALUs in the CPU and you have them executing the same operation on different bit ranges of the input registers.

To vectorize memory reads what do you need? Well, I assume you need N memory access units, N buses and a N-ported memory. Tough job having all those and if you don't have them you'll end up serializing all memory reads. Maybe it could work if all reads would be on the same cacheline but that doesn't always happen.