Changes between Version 7 and Version 8 of ParallelDeletion
 Timestamp:
 Mar 16, 2016, 9:55:15 AM (4 years ago)
Legend:
 Unmodified
 Added
 Removed
 Modified

ParallelDeletion
v7 v8 78 78 79 79 This method uses only bitwise logic and shifting to perform deletion. 80 For deletion within 2^k bit fields, k steps are required. Each step i81 involves application of a mask to select of bits to move 2^i positions.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. 82 82 4 operations are required per step. 83 However, the calculation of masks requires k^2 preprocessing steps.83 However, the calculation of masks requires k^2^ preprocessing steps. 84 84 However, when applied to deletion of data from several parallel bit streams, the 85 85 preprocessing cost is shared across the streams. … … 88 88 89 89 In this method, deletion steps ensure that results are leftmost within 90 fields of size 2^i at step i. The process involves SIMD multiplication90 fields of size 2^i^ at step i. The process involves SIMD multiplication 91 91 operations at each step. 92 92 … … 94 94 95 95 In 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 process96 centre position of each 2^(i+1)^ bit field at step i. The process 97 97 involves SIMD rotate operations at each step. 98 98 … … 118 118 === Bit Stream Deletion === 119 119 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. 122 122 123 123