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.

Bitwise Logic

The operators | (or), & (and), ^ (xor), ~ (not) are supported as well as the corresponding operators for the first three: |=, &=, ^=.

Scanning Operations

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)

Spanning Operations

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

Error Streams

  • 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.

While Loops

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.

Last modified 4 years ago Last modified on Apr 6, 2013, 5:04:56 PM