Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.arch > #3482 > unrolled thread

Bit Interleaving, Instruction Set Support for

Back to article view | Back to comp.arch

Contents

  Bit Interleaving, Instruction Set Support for "Andy \"Krazy\" Glew" <andy@SPAM.comp-arch.net> - 2011-09-05 16:23 -0700
    Re: Bit Interleaving, Instruction Set Support for Mark Thorson <nospam@sonic.net> - 2011-09-05 20:07 -0800
      Re: Bit Interleaving, Instruction Set Support for "Andy \"Krazy\" Glew" <andy@SPAM.comp-arch.net> - 2011-09-05 21:25 -0700
        Re: Bit Interleaving, Instruction Set Support for Andrew Reilly <areilly---@bigpond.net.au> - 2011-09-06 05:09 +0000
          Re: Bit Interleaving, Instruction Set Support for torbenm@diku.dk (Torben Ægidius Mogensen) - 2011-09-06 10:20 +0200
            Re: Bit Interleaving, Instruction Set Support for Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-09-06 13:28 +0200
              Re: Bit Interleaving, Instruction Set Support for "Andy \"Krazy\" Glew" <andy@SPAM.comp-arch.net> - 2011-09-06 11:29 -0700
            Re: Bit Interleaving, Instruction Set Support for "Andy \"Krazy\" Glew" <andy@SPAM.comp-arch.net> - 2011-09-06 11:21 -0700
            Re: Bit Interleaving, Instruction Set Support for timcaffrey@aol.com (Tim McCaffrey) - 2011-09-09 19:10 +0000
              Re: Bit Interleaving, Instruction Set Support for "Andy \"Krazy\" Glew" <andy@SPAM.comp-arch.net> - 2011-09-10 12:50 -0700
              Re: Bit Interleaving, Instruction Set Support for torbenm@diku.dk (Torben Ægidius Mogensen) - 2011-09-13 10:34 +0200
        Re: Bit Interleaving, Instruction Set Support for Mark Thorson <nospam@sonic.net> - 2011-09-07 12:43 -0800
          Re: Bit Interleaving, Instruction Set Support for "Andy \"Krazy\" Glew" <andy@SPAM.comp-arch.net> - 2011-09-10 12:27 -0700
            Re: Bit Interleaving, Instruction Set Support for "Andy \"Krazy\" Glew" <andy@SPAM.comp-arch.net> - 2011-09-11 21:05 -0700
          Re: Bit Interleaving, Instruction Set Support for EricP <ThatWouldBeTelling@thevillage.com> - 2011-09-10 16:57 -0400
            Re: Bit Interleaving, Instruction Set Support for George Neuner <gneuner2@comcast.net> - 2011-09-10 23:14 -0400
              Re: Bit Interleaving, Instruction Set Support for nmm1@cam.ac.uk - 2011-09-11 10:16 +0100
                Re: Bit Interleaving, Instruction Set Support for EricP <ThatWouldBeTelling@thevillage.com> - 2011-09-11 12:30 -0400
      Re: Bit Interleaving, Instruction Set Support for Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-09-06 13:25 +0200
    Re: Bit Interleaving, Instruction Set Support for Quadibloc <jsavard@ecn.ab.ca> - 2011-09-05 21:02 -0700
    Re: Bit Interleaving, Instruction Set Support for Piotr Wyderski <peter.pan@neverland.mil> - 2011-09-06 14:12 +0200
      Re: Bit Interleaving, Instruction Set Support for Bakul Shah <usenet@bitblocks.com> - 2011-09-06 11:49 -0700
        Re: Bit Interleaving, Instruction Set Support for Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-09-07 11:18 +0200
          Re: Bit Interleaving, Instruction Set Support for Thomas Womack <twomack@chiark.greenend.org.uk> - 2011-09-07 10:54 +0100
            Re: Bit Interleaving, Instruction Set Support for Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-09-07 20:27 +0200
    Re: Bit Interleaving, Instruction Set Support for MitchAlsup <MitchAlsup@aol.com> - 2011-09-07 12:23 -0700

Page 2 of 2 — ← Prev page 1 [2]

#3500

Andy "Krazy" Glew wrote:

Thanks for starting the thread, as bit operations are of vital 
importance in my low-level algorithms. Apart the operations
mentioned previously, I would like to have the following instruction:

bit_chunk_check(x, n):

where x is an unsigned integer and n is a positive integer.
The instruction checks whether x contains a chunk of n consecutive
set bits and returns an index of the first/last/some such a chunk.
It is a generalization of bsf/bsr.

It should be complemented with wide_chunk_check(x, y, n), with the
same semantics as above, but working on a double-length x:y intermediate 
value. An SSE/AVX-based implementation is preferred
because of the width of the registers.

Such a primitive is very important in bitmap-based index allocators
(for VM pages, disk sectors etc.) when you want to find *rapidly*
a consecutive range of free indexes.

And the most important thing: all the bit ops should have latency of 1 
cycle.

     Best regards
     Piotr Wyderski

[toc] | [prev] | [next] | [standalone]

#3506

On 9/6/11 5:12 AM, Piotr Wyderski wrote:
> Andy "Krazy" Glew wrote:
>
> Thanks for starting the thread, as bit operations are of vital importance in my low-level
> algorithms. Apart the operations
> mentioned previously, I would like to have the following instruction:
>
> bit_chunk_check(x, n):
>
> where x is an unsigned integer and n is a positive integer.
> The instruction checks whether x contains a chunk of n consecutive
> set bits and returns an index of the first/last/some such a chunk.
> It is a generalization of bsf/bsr.

Kind of a run-length-encoding. Would be neat if you could deal
with a bunch of bits. The result would be a count of alternating
zeroes and ones. So for example:

value	result (four 8-bit values in decimal)
0	32,0,0,0	; 32 zeroes, 0 ones
-1	0,32,0,0	; 0 zeroes, 32 ones
257	23,1,7,1	;
13	27,1,1,1	; actual encoding: 27,1,1,1,1,1 but only the first 4 can be returned

Also need a clz (clear leading zeroes) to pick up for example the
last two runs of 13 in the next round. Very useful in array
programming. A == B will yield a bitmap where A[i] == B[i]. To
then pick up those values from A or B (or another related array)
you need indices of places where A & B match.

Probably not doable in one cycle. But even knocking off one run
of zeroes and one of ones can be handy.

[toc] | [prev] | [next] | [standalone]

#3512

> On 9/6/11 5:12 AM, Piotr Wyderski wrote:
>> Thanks for starting the thread, as bit operations are of vital
>> importance in my low-level
>> algorithms. Apart the operations
>> mentioned previously, I would like to have the following instruction:
>>
>> bit_chunk_check(x, n):
>>
>> where x is an unsigned integer and n is a positive integer.
>> The instruction checks whether x contains a chunk of n consecutive
>> set bits and returns an index of the first/last/some such a chunk.
>> It is a generalization of bsf/bsr.

I agree that such an instruction would be nice, but probably not 
worthwhile to spend silicon on:

For short runs (< 10-12 bits) lookup tables work well, as soon as you 
want runs of 15 or more bits you can simply scan bytes:

In order to have a 15-bit run, there must be at least one zero byte, right?

With two zero bytes you know you've found a solution, now you just need 
to find out where it started, which you can use BS* to do.

Terje

-- 
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

[toc] | [prev] | [next] | [standalone]

#3513

In article <4gpjj8-unm.ln1@ntp6.tmsw.no>,
Terje Mathisen  <"terje.mathisen at tmsw.no"> wrote:
>> On 9/6/11 5:12 AM, Piotr Wyderski wrote:
>>> Thanks for starting the thread, as bit operations are of vital
>>> importance in my low-level
>>> algorithms. Apart the operations
>>> mentioned previously, I would like to have the following instruction:
>>>
>>> bit_chunk_check(x, n):
>>>
>>> where x is an unsigned integer and n is a positive integer.
>>> The instruction checks whether x contains a chunk of n consecutive
>>> set bits and returns an index of the first/last/some such a chunk.
>>> It is a generalization of bsf/bsr.
>
>I agree that such an instruction would be nice, but probably not 
>worthwhile to spend silicon on:
>
>For short runs (< 10-12 bits) lookup tables work well

What do you put in the lookup table, assuming x is a 64-bit quantity?

I would do

x01 = x & (x<<1)
x0123 = x01 & (x01<<2)
x012 = x01 & (x<<2)
x0123456 = x0123 & (x012<<4)
bitscan x0123456

[that's n-or-more but for file-allocation I thought that was what was
desired; if you want 011111110 then also and in ~(x>>1) and ~(x<<7)]

and curse slightly that there doesn't appear to be a
shift-whole-register-by-bits instruction defined on whole 128- or
256-bit registers in SSEn or AVX (iirc even the shift-by-bytes
requires the shiftcount to be known at compile time).

Obviously that requires a different loop for each value of n - though
I think it generalises reasonably to hardware using not that many
medium-sized multiplexers.

Tom

[toc] | [prev] | [next] | [standalone]

#3535

Thomas Womack wrote:
> In article<4gpjj8-unm.ln1@ntp6.tmsw.no>,
> Terje Mathisen<"terje.mathisen at tmsw.no">  wrote:
>>> On 9/6/11 5:12 AM, Piotr Wyderski wrote:
>>>> Thanks for starting the thread, as bit operations are of vital
>>>> importance in my low-level
>>>> algorithms. Apart the operations
>>>> mentioned previously, I would like to have the following instruction:
>>>>
>>>> bit_chunk_check(x, n):
>>>>
>>>> where x is an unsigned integer and n is a positive integer.
>>>> The instruction checks whether x contains a chunk of n consecutive
>>>> set bits and returns an index of the first/last/some such a chunk.
>>>> It is a generalization of bsf/bsr.
>>
>> I agree that such an instruction would be nice, but probably not
>> worthwhile to spend silicon on:
>>
>> For short runs (<  10-12 bits) lookup tables work well
>
> What do you put in the lookup table, assuming x is a 64-bit quantity?

Sorry, I sort of assumed that in a file system the bitmask will be 
_significantly_ larger than a single register!

I.e. it must be loaded from memory.

> I would do
>
> x01 = x&  (x<<1)
> x0123 = x01&  (x01<<2)
> x012 = x01&  (x<<2)
> x0123456 = x0123&  (x012<<4)
> bitscan x0123456
>
> [that's n-or-more but for file-allocation I thought that was what was
> desired; if you want 011111110 then also and in ~(x>>1) and ~(x<<7)]

Good idea.

Terje

-- 
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

[toc] | [prev] | [next] | [standalone]

#3540

On Monday, September 5, 2011 6:23:57 PM UTC-5, Andy Krazy Glew wrote:
> = Instruction Set Support for Bit Interleaving =
> 
> == What is Bit Interleaving? ==
> 
> [[Bit interleaving]] is a very common form of multi-operand bit permutation.
> It has been important enough to occasionally warrant special instruction 
> set support.
> 
> 2-way bit interleaving of A and B;
> 
>   for i = 0 to N do
>     result.bit[2*i] := A.bit[i]
>     result.bit[2*i+1] := B.bit[i]

What would be impractical about creating a table of 16-bit quantities and use thusly:

    for i = 0 to N/8 do
        result[i] = inter20[a[i]] | inter21[B[i]];

All one needs is 2 tables that takes a byt index and returns the expanded bit pattern of that byte.

> 3-way bit interleaving off A, B, C:
> 
>   for i = 0 to N do
>     result.bit[3*i] := A.bit[i]
>     result.bit[3*i+1] := B.bit[i]
>     result.bit[3*i+2] := C.bit[i]

    for i = 0 to N/8 do
      result[i] = inter30[A[i]] | inter31[B[i]] | inter32[C[i]];

This also deals with the bit reverse question that followed with a suitably set up table.

Seems to me that this is far faster if that is all you are trying to do--basically treating a byte as a short vector of bits.

I have not followed this thread closely so don't beat me up too badly.

Mitch

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | comp.arch

csiph-web