Browse Prior Art Database

Use of Translate and Test with Compare and Swap to Maintain Bit Maps

IP.com Disclosure Number: IPCOM000117054D
Original Publication Date: 1995-Dec-01
Included in the Prior Art Database: 2005-Mar-31
Document File: 2 page(s) / 56K

Publishing Venue

IBM

Related People

Cardall, DR: AUTHOR

Abstract

A method for maintaining a bit map which serializes multiple users.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 55% of the total text.

Use of Translate and Test with Compare and Swap to Maintain Bit Maps

      A method for maintaining a bit map which serializes multiple
users.

      The first non-zero bit is located using TRANSLATE AND TEST
(TRT) in a loop that tests 2048 bits with a single ASSEMBLER
instruction.  The output of the TRT instruction is the address of the
byte with a zero bit and the translated value which identifies the
zero bit.

      Once found, the bit can be set to 1 using COMPARE AND SWAP (CS)
- thus avoiding the stiff penalties of a serialization device.

The translated table:
  (256) Fixed(8) Init((128)1,(64)2,(32)3,(16)4,(8)5,(4)6,7,7,8,0)

For example, take a string of 292 bytes of binary 11111111 followed
by a byte containing binary 11011111.  Thus, the first zero bit is
number 2339 (292 times 8 plus 3).

      The first TRT would be for bytes 0 through 255 (2048 bits)
fails to return a non-zero translate value (binary 11111111 = decimal
255 which translates to the 256th table value - the "0" at the end of
the above table).

      The second TRT would be for bytes 256 through 511 and would
stop with the first non-zero translate value (binary 1101111 =
decimal 223 which translates to the 224th table value - a "3" above).
The TRT instruction returns both the translate value (which bit) and
the byte location.

      To clarify, binary values 00000000 through 01111111 would
translate to "1" (there are 128 values from 00000000 through 01111111
and 128 "1"s - i...