Intel® Software Network

The problem with this is encorporating this into the operating system for context switching. It would make more sense to increase the L1 cache size or increase number of and/or create a "sticky" TLB. These could be added without requirements of changes in O/S.

Example a periodic PREFETCHn of given type could reassert stickyness to a TLB. (Or LOCK PREFETCHn could (re)assert stickyness). Interrupt/ PUSHAF/ LGDT /...?? could remove stickyness (something already used in typical context switch by O/S).

For more "register" space, consider making better use of the SSE registers, currently 128 bits, soon to be 256 bits, later perhaps 512 bits.

Jim Dempsey

Now, I'm by no means an expert on the intracacies of Intel microcode, but I think there are enough clever people around to overcome current design limitations.

Again, thanks for the reply,

James

Hi James,

The L1 cache is already pretty much what you're asking for. It's incredibly fast, so don't be afraid of reading/writing memory if necessary. There's little chance that a dedicated array register would outperform it.

What's the actual algorithm you're implementing where you see this as being a bottleneck? Chances are that there are far better opportunities to speed it up than actually waiting for a hardware change...

Cheers,

Nicolas

How big is your block of data?

Since writes are relatively expensive and reads from L1 cache are cheap

count the occurances of same byte x 16 across width of xmm register for up to 255 iterations (4080 bytes) then use PSADBW (against 0's) to perform a horizontal add. Add the result 16 bits to a larger register, then continue for the next 4080 bytes. At end of block perform test for residual bytes, then store into 16/32/64 bit tally. loop back for remaining 255 bit values.

This reduces task to all reads and 256 writes.

Note, you could loop the 256 byte value iterations on something just less than L1 cache size on the input buffer. Change store into tally to add to tally (start with 0). Now you have 256 writes + (256 RMW)*(buffer size/L1 size) + something for odd bytes at end of buffer.

Also, this should work well on multi-threaded system, even HT system.

And, when byte set has known missing values you can omit those tests (e.g. contains only ASCII printable characters)

Jim Dempsey

From your description of the problem I would suggest

A specialized decompression function that runs as a parallel pipeline using SSE when possible. Note, this may be a nested series of parallel pipelines.

The container format would likely not change (still be describable in abstract terms in single thread model).

First stage would convert dictionary to format suitable for subsequent SSE manipulation.
  Second stage would convert packed tokens into SSE compatible tokens (copy and insert SSE bit masks)
     Third stage performs 1st level expansion fetch indirect and store using SSE bit masks
         Forth stage performs 2nd level expansion
             ...

The pipeline stages should be affinity arranged to take advantage of HT capable processors. HT siblings (L1 cache sharing messaging), L2 siblings (L2 cache sharing messaging), L3 siblings, Socket siblings, ...

First stage could likely be done once (held in seperate file or attribute of original file).

This would be relatively easy to construct using QuickThread (at least the cache level task scheduling).