Changes between Version 7 and Version 8 of ParallelDeletion


Ignore:
Timestamp:
Mar 16, 2016, 9:55:15 AM (4 years ago)
Author:
cameron
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • ParallelDeletion

    v7 v8  
    7878
    7979This method uses only bitwise logic and shifting to perform deletion. 
    80 For deletion within 2^k bit fields, k steps are required.   Each step i
    81 involves application of a mask to select of bits to move 2^i positions. 
     80For deletion within 2^k^ bit fields, k steps are required.   Each step i
     81involves application of a mask to select of bits to move 2^i^ positions. 
    82824 operations are required per step.
    83 However, the calculation of masks requires k^2 preprocessing steps.
     83However, the calculation of masks requires k^2^ preprocessing steps.
    8484However, when applied to deletion of data from several parallel bit streams, the
    8585preprocessing cost is shared across the streams.
     
    8888
    8989In this method, deletion steps ensure that results are leftmost within
    90 fields of size 2^i at step i.   The process involves SIMD multiplication
     90fields of size 2^i^ at step i.   The process involves SIMD multiplication
    9191operations at each step.
    9292
     
    9494
    9595In this method, deletion steps produce results that span or touch the
    96 centre position of each 2^(i+1) bit field at step i.   The process
     96centre position of each 2^(i+1)^ bit field at step i.   The process
    9797involves SIMD rotate operations at each step.
    9898
     
    118118=== Bit Stream Deletion ===
    119119
    120  1.  Generate Masks for Parallel Prefix Deletion(k): for deletion within 2^k-bit fields, produce k masks.
    121  2.  Apply Parallel Masks for Parallel Prefix Deletion(k, N): implement bit stream deletion within 2^k bit fields for N parallel streams.
     120 1.  Generate Masks for Parallel Prefix Deletion(k): for deletion within 2^k^-bit fields, produce k masks.
     121 2.  Apply Parallel Masks for Parallel Prefix Deletion(k, N): implement bit stream deletion within 2^k^ bit fields for N parallel streams.
    122122
    123123