# 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: |=, &=, ^=.

## Shift Operations

• pablo.Advance(strm, shft) - shift the bit stream strm forward shft positions
• pablo.Lookahead(strm, shft) - shift the bit stream strm backward shft positions
• pablo.IndexedAdvance(strm, idx, shft) - shift bits in strm selected by the index stream idx forward by shft index positions
• Consider x = pablo.IndexedAdvance(strm, idx, shft)
• x[k] = 1, if and only if idx[k] = 1, k is the position of the nth 1 bit in idx, j is the position of the (n-shft)th 1 bit in idx, and strm[j] = 1.

## 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 on Mar 13, 2018, 8:49:53 PM