Aug 20, 2011, 7:51:52 PM (8 years ago)

section 4

1 edited


  • docs/HPCA2012/03-research.tex

    r1302 r1331  
    113113processed in as a final post processing step. A further aspect of the parallel cursor method with bit stream addition is that the conditional branch statements used to identify syntax error at each each parsing position are eliminated. Hence, Parabix2 offers additional parallelism over Parabix1 in the form of multiple cursor parsing and further reduces branch misprediction penalties.
    115 \subsection{Parallel Bit Stream Compilation}
    117 While the description of parallel bit stream parsing in the previous section works conceptually on
    118 unbounded bit streams, in practice, a corresponding C implementation to process input streams into blocks
    119 of size equal to the SIMD register width of the target processor is required. In our work, we leverage the unbounded
    120 integer type of the Python programming language. Using a restricted subset of Python, we prototype and validate the
    121 functionality of applications, such as XML validation and UTF-8 to UTF-16 transcoding. We then compile this Python code
    122 into equivalent block-at-a-time C code. The key question becomes how to transfer information from one block to the next whenever
    123 token scans cross block boundaries.
    125 The answer lies in carry bit propagation. Since the parallel $scanto$ operation relies solely on bit-wise addition and logical operations,
    126 block-to-block information transfer is captured in entirety by the carry bit associated with each underlying addition operation. Logical operations
    127 do not require information flow across block boundaries. Properly determining, initializing and inserting carry bits into a block-by-block
    128 implementation is tedious and error prone. Thus we have developed compiler technology to automatically transform parallel bit stream
    129 Python code to block-at-a-time C implementations. Details are beyond the scope of this paper, but are described in the on-line
    130 source code repository at parabix.costar.sfu.ca.
Note: See TracChangeset for help on using the changeset viewer.