Changes between Version 4 and Version 5 of ParallelDeletion


Ignore:
Timestamp:
Mar 15, 2016, 3:23:10 PM (3 years ago)
Author:
cameron
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • ParallelDeletion

    v4 v5  
    3030cost by sharing preprocessing overhead.   
    3131
    32 == Parallel Deletion Methods ==
     32== Overview of Parallel Deletion Methods ==
    3333
    3434=== Intra-Block Deletion vs. Block-by-Block Processing ===
     
    4747the new block to become the new pending block. 
    4848
    49 === Intra-Field Deletion ===
    50 
    51 When the ultimate goal is to produce streams of bytes, doublebytes, or other units,
    52 then it is often beneficial to limit the bit stream deletion work to smaller field sizes.
    53 For example, suppose that a stream of doublebytes (16-bit units) is to be produced after
    54 application of parallel deletion to a the corresponding 16 parallel bit streams.
    55 Working with 128-bit registers, each register will ultimately hold at most 8 doublebytes.
    56 Then we may proceed as follows:
    57  1.  Perform parallel deletion within 8-bit fields, so that nondeleted bits are leftmostin each such field.
    58  1.  Transpose to double byte form, producing a set of 16 register values in which the nondeleted double bytes are leftmost in each register.
    59  1.  Sequentially write the register values to the output stream, advancing the output stream pointer by the count of nondeleted elements each time.
    60 
    6149
    6250=== Intra-Block Parallel Deletion ===
     
    7361
    7462
     63=== Intra-Field Deletion ===
    7564
     65When the ultimate goal is to produce streams of bytes, doublebytes, or other units,
     66then it is often beneficial to limit the bit stream deletion work to smaller field sizes.
     67For example, suppose that a stream of bytes is to be produced after
     68application of parallel deletion to a the corresponding 8 parallel bit streams.
     69Working with 128-bit registers, each register will ultimately hold at most 16 bytes.
     70Then we may proceed as follows:
     71 1.  Perform parallel deletion within 16-bit fields, so that nondeleted bits are leftmost in each such field.
     72 1.  Perform the inverse Parabix transform to byte stream form, producing a squence of 8 register values in which the nondeleted bytes are leftmost in each register.
     73 1.  Sequentially write the register values to the output stream, advancing the output stream pointer by the count of nondeleted bytes for each register in turn.
     74
     75
     76
     77