Pablo: A Language and Compiler for Parallel Bit Stream Programming
Pablo is a Python subset language that allows you to prototype parallel bit stream programs in Python based on the concept of unbounded (arbitrary-length) bit streams. Our Pablo compiler can then be used to translate Pablo programs to efficient block-at-a-time C++ code. The compiler supports the following features.
The operators | (or), & (and), ^ (xor), ~ (not) are supported as well as the corresponding operators for the first three: |=, &=, ^=.
These are the operations used for parallel scanning and parsing as documented in the EuroPar? 2011 paper: Parallel Scanning with Bitstream Addition.
- pablo.ScanThru(m, c)
- pablo.ScanTo(m, c)
- pablo.AdvanceThenScanThru(m, c)
- pablo.AdvanceThenScanTo(m, c)
Given bitstreams marking the starts and ends of constructs of interest, Pablo defines the following span operations.
- pablo.SpanUpTo(s, e) - all positions starting from and including positions in s, up to but not including e
- pablo.ExclusiveSpan(s, e) - all positions between s and e, not including either
- pablo.InclusiveSpan(s, e) - all positions between s and e, including both s and e as well
End of File Processing
- pablo.inFile(s) - stream s masked to exclude any bits past end-of-file
- pablo.atEOF(s) - stream s masked to include only the bit immediately past end-of-file
- pablo.assert_0(errstrm, errcode) asserts that any 1 bits in errstrm represent errors of type errcode
Pablo may use error assertions to optimize; that is, the compiler may optimize assuming that the all bits in the asserted error stream are indeed 0.
Parallel If Optimizations
The statement if E: S, where E is a bit stream expresion and S is a block of Pablo statements is a parallel if construct. It is semantically equivalent to S alone, but omits computation of S whenever the entire stream E is known to be zero.
The parallel if optimization is highly useful in block-at-a-time code, because the optimization is performed block-at-a-time: for any block in which E is known to be 0 at all bit positions in the block (and there are no incoming carries for operations within the block), the execution of S is omitted for the block.
Pablo supports the concept of iteration over bit streams using while loops of the form while E: S, where E is a bit stream expresion and S is a block of Pablo statements. The loop body S is repeatedly executed while any 1 bits remain in the stream E. In compilation to block-by-block processing, the iteration terminates for that block as soon as E becomes zero. At present, the semantics of while loops are restricted as follows: a one bit can only appear at any given position within a stream at most once. Programs that violate this constraint will produce undefined results.