Package at.dms.kjc.sir.lowering.partition.dynamicprog

Adjusts the granularity of the stream graph, using a dynamic programming algorithm to optimize the load balancing.

See:
Description

Class Summary

DynamicProgPartitioner

Package at.dms.kjc.sir.lowering.partition.dynamicprog Description

Adjusts the granularity of the stream graph, using a dynamic programming algorithm to optimize the load balancing. The algorithm used is described in a yet-unpublished draft (contact thies@alum.mit.edu) and is similar to the dynamic programming partitioner described in this PLDI'03 paper (see Section 6.2).

The general strategy behind the algorithm is to calculate, for each hierarchical stream, the bottleneck work if that stream were spread across n processors. If this information is available for a set of sub-streams, then a parent stream can recursively calculate its bottleneck for a given n by assigning some of the n processors to some children and the rest of the processors to the other children. Generally speaking, the best partitioning is taken as the minimum bottleneck across all possible allocations of processors across all divisions of children.

The dynamic programming partitioner uses rectangles as a uniform representation of streams. An n-element pipeline is a rectangle that has a width of 1 and a height of n, while a splitjoin of n filters is a rectangle with a width of n and a height of 1. Splitjoins containing pipelines are represented as a single rectangle. Using this representation, the partitioning algorithm can assign any sub-rectangle to a single processor and implement the fusion using a hierarchical refactoring of the splitjoin.

To support the rectangle abstraction, all filters and streams are wrapped in configurations. The basic configuration is DPConfig, and there is a subclass for each stream type. The standard dynamic programming methods of get() (to calculate the partitioning costs for a sub-stream) and traceback() (to reconstruct the minimal-cost partitioning) are implemented by each type of configuration. The heart of the algorithm is in DPConfigContainer, which implements these two functions for arbitrary rectangles.

The high-level interface for the package is DynamicProgPartitioner, which contains constants and configuration-building code.

See Also:

at.dms.kjc.raw